Spark-level sparsity and the _1 tail minimization

DOI10.1016/J.ACHA.2017.07.001MaRDI QIDQ1748258zbMATH OpenOpenAlexFDO

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)

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

Mathematics Subject Classification ID

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

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.

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

Cites work

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

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

Describes a project that uses

Uses Software

• CoSaMP
• PDCO

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)