Deterministic Fourier-Based Dictionary Design for Sparse Reconstruction

Abstract

This paper focuses on the design of a Fourier dictionary matrix formed by selecting specific rows of the inverse discrete Fourier transform matrix based on coherence-related metrics. While maximum coherence is a popular metric in compressive sampling, we also consider rms LN-coherence, which focuses on the largest LN (instead of one) inner products between different columns of the dictionary matrix. Finding a dictionary matrix optimizing either the maximum or the rms LN-coherence lead to a complicated optimization problem. Hence, we introduce a new metric called coherence deviation (CD), which gives a measure on the variation of all the inner products between different columns of the dictionary matrix, and motivate its use as an amenable alternative for both the maximum and rms LN-coherence. While finding a dictionary matrix optimizing the CD leads to a simplified optimization problem, the resulting cost function is a quartic function of a binary vector variable. Hence, we propose Greedy-β algorithm to provide sub-optimal solutions.