Two are better than one: fundamental parameters of frame coherence (Q427070)

This paper only considers finite-dimentional frames and investigates two parameters that measure the coherence of a frame: worst-case and average coherence. The authors use them to derive near-optimal probabilistic guarantees on both sparse signal detection and reconstruction in the presence of noise, and provide a catalog of nearly tight frames with small worst-case and average coherence. They also find a new lower bound on worst-case coherence, compare it to the Welch bound and use it to interpret recently reported signal reconstruction results. Finally, they present an algorithm that transforms frames in a way that decreases average coherence without changing the spectral norm or worst-case coherence.