Spark-level sparsity and the _1 tail minimization

DOI10.1016/J.ACHA.2017.07.001zbMATH Open1397.94018arXiv1610.06853OpenAlexW2963846424MaRDI QIDQ1748258FDOQ1748258

Authors: Chun-Kit Lai, Shidong Li, Daniel Mondo 

Publication date: 9 May 2018

Published in: Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Abstract: Solving compressed sensing problems relies on the properties of sparse signals. It is commonly assumed that the sparsity s needs to be less than one half of the spark of the sensing matrix A, and then the unique sparsest solution exists, and recoverable by $el{l}_1$-minimization or related procedures. We discover, however, a measure theoretical uniqueness exists for nearly spark-level sparsity from compressed measurements Ax = b. Specifically, suppose A is of full spark with m rows, and suppose $fracm2$ < s < m. Then the solution to Ax = b is unique for x with $|x{|}_{0}leqs$ up to a set of measure 0 in every s-sparse plane. This phenomenon is observed and confirmed by an $el{l}_1$-tail minimization procedure, which recovers sparse signals uniquely with s > $fracm2$ in thousands and thousands of random tests. We further show instead that the mere $el{l}_1$-minimization would actually fail if s > $fracm2$ even from the same measure theoretical point of view.

Full work available at URL: https://arxiv.org/abs/1610.06853

Recommendations

• Recovery of sparsest signals via \(\ell^q \)-minimization
• The restricted isometry property and its implications for compressed sensing
• For most large underdetermined systems of linear equations the minimal 𝓁₁‐norm solution is also the sparsest solution
• A necessary and sufficient condition for exact sparse recovery by \(\ell_1\) minimization
• A note on guaranteed sparse recovery via \(\ell_1\)-minimization

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cites Work

• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ ¹ minimization
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• A mathematical introduction to compressive sensing
• A note on the complexity of \(L _{p }\) minimization
• Iterative thresholding for sparse approximations
• High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension
• On sparse reconstruction from Fourier and Gaussian measurements
• Sparse signal reconstruction via iterative support detection
• A null space analysis of the \(\ell_1\)-synthesis method in dictionary-based compressed sensing
• Atomic decomposition by basis pursuit
• Compressed Sensing and Redundant Dictionaries
• Analysis versus synthesis in signal priors
• Full spark frames
• Compressive sensing and structured random matrices
• Subspace Pursuit for Compressive Sensing Signal Reconstruction
• Sparse Solution of Underdetermined Systems of Linear Equations by Stagewise Orthogonal Matching Pursuit
• Compressed sensing with coherent and redundant dictionaries
• Stability Results for Random Sampling of Sparse Trigonometric Polynomials
• Random sampling of sparse trigonometric polynomials
• On compressive sensing applied to radar
• Compressed remote sensing of sparse objects
• Compressed Sensing With General Frames via Optimal-Dual-Based $\ell _{1}$-Analysis
• Sparse frame DOA estimations via a rank-one correlation model for low SNR and limited snapshots

Cited In (2)

• Effectiveness of the tail-atomic norm in gridless spectrum estimation
• The finite steps of convergence of the fast thresholding algorithms with \(f\)-feedbacks in compressed sensing

Uses Software

• PDCO
• CoSaMP

This page was built for publication: Spark-level sparsity and the \(\ell_1\) tail minimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1748258)