2015/07/10 by Christoph Studer, Studer, Christoph
Engineering · Physics and Astronomy · #Microwave Imaging and Scattering Analysis #Random lasers and scattering media #Sparse and Compressive Sensing Techniques #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1507.02821
openalex publication_date 2015/07/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
Sparse signals (i.e., vectors with a small number of non-zero entries) build the foundation of most kernel (or nullspace) results, uncertainty relations, and recovery guarantees in the sparse signal-processing and compressive-sensing literature. In this report, we study a signal-density measure, the ratio between the ℓ1-norm and the ℓ_∞-norm of a vector, which extends the common notion of sparsity to non-sparse signals whose entries' magnitudes decay rapidly. By taking into account such magnitude information, we derive a kernel result and an uncertainty relation that are more general and less restrictive than those based on the ℓ0-pseudonorm. Furthermore, we use this density measure to analyze orthogonal matching pursuit (OMP). We show that OMP provably (i) recovers sparse signals with decaying magnitudes using up to 2\boldsymbol× more non-zero coefficients than guaranteed by standard, sparsity-based results and (ii) identifies the largest entries of arbitrary signals under a suitable magnitude-decay condition.