Frame Coherence and Sparse Signal Processing
The sparse signal processing literature often uses random sensing matrices to obtain performance guarantees. Unfortunately, in the real world, sensing matrices do not always come from random processes. It is therefore desirable to evaluate whether an arbitrary matrix, or frame, is suitable for sensing sparse signals. To this end, the present paper investigates two parameters that measure the coherence of a frame: worst-case and average coherence. The authors first provide several examples of frames that have small spectral norm, worst-case coherence, and average coherence. Next, they present a new lower bound on worst-case coherence and compare it to the Welch bound. Later, they propose an algorithm that decreases the average coherence of a frame without changing its spectral norm or worst-case coherence.