2015/07/10 by Christoph Studer, Studer, Christoph · 1 citation
Computer Science · Engineering · Mathematics · Physics and Astronomy · #Algorithm #Artificial intelligence #Compressed sensing #Computer science #Data mining #Discrete mathematics #Kernel (algebra) #Kernel density estimation #Matching (statistics) #Matching pursuit #Mathematics #Measure (data warehouse) #Microwave Imaging and Scattering Analysis #Pattern recognition (psychology) #Random lasers and scattering media #SIGNAL (programming language) #Signal processing #Signal recovery #Sparse and Compressive Sensing Techniques #Sparse approximation #Statistics #Telecommunications #Zero (linguistics) #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1507.02821
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2015/07/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.