Two are better than one: Fundamental parameters of frame coherence

Abstract

This paper investigates two parameters that measure the coherence of a frame: worst-case and average coherence. We first use worst-case and average coherence to derive near-optimal probabilistic guarantees on both sparse signal detection and reconstruction in the presence of noise. Next, we provide a catalog of nearly tight frames with small worst-case and average coherence. Later, we find a new lower bound on worst-case coherence; we compare it to the Welch bound and use it to interpret recently reported signal reconstruction results. Finally, we give an algorithm that transforms frames in a way that decreases average coherence without changing the spectral norm or worst-case coherence.

References in corpus (6)

• Near-ideal model selection by ${\ell }_1$ minimization
• SIC-POVMs: A new computer study
• Multi-Label Prediction via Compressed Sensing
• Identification of Matrices having a Sparse Representation
• Why Gabor Frames? Two Fundamental Measures of Coherence and Their Role in Model Selection
• Steiner equiangular tight frames

Cited by in corpus (23)

• Projection-Based and Look Ahead Strategies for Atom Selection
• Restricted isometry property of random subdictionaries
• Conditioning of Random Block Subdictionaries with Applications to Block-Sparse Recovery and Regression
• Equiangular tight frames and unistochastic matrices
• Toward the Classification of Biangular Harmonic Frames
• ExSIS: Extended Sure Independence Screening for Ultrahigh-dimensional Linear Models
• Frame Coherence and Sparse Signal Processing
• Finding Zeros: Greedy Detection of Holes
• Optimized Compressed Sensing via Incoherent Frames Designed by Convex Optimization
• Sparse Signal Processing with Frame Theory
• Compressive Demodulation of Mutually Interfering Signals
• Level set estimation from projection measurements: Performance guarantees and fast computation
• Certifying the novelty of equichordal tight fusion frames
• Explicit RIP Matrices in Compressed Sensing from Algebraic Geometry
• Constructions and properties of optimally spread subspace packings via symmetric and affine block designs and mutually unbiased bases
• On the geometry of nearly orthogonal lattices
• A Multiple Hypothesis Testing Approach to Low-Complexity Subspace Unmixing
• Coherence-Based Performance Guarantees of Orthogonal Matching Pursuit
• p-adic Welch Bounds and p-adic Zauner Conjecture
• Random Subdictionaries and Coherence Conditions for Sparse Signal Recovery
• Bounds on and Constructions of Unit Time-Phase Signal Sets
• On block coherence of frames
• On average coherence of cyclotomic lattices