Mean breakdown points for compressed sensing by uniformly distributed matrices

DOI10.14495/JSIAML.2.111MaRDI QIDQ2843151zbMATH OpenOpenAlexFDO

Authors Ryuichi Ashino, Rémi Vaillancourt

Publication date 9 August 2013

Published in JSIAM Letters (Search for Journal in Brave)

Full work available at URL https://www.jstage.jst.go.jp/A_PRedirectJournalInit?sryCd=jsiaml&kijiCd=2_0_111&screenID=AF06S010&noVol=2&noIssue=0

zbMATH Keywords

numerical examplesphase transitioncompressed sensingrandom matrices\(\ell_1\) linear programmingmean breakdown pointssparse solution of underdetermined system

Mathematics Subject Classification ID

Linear programming (90C05) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Random matrices (algebraic aspects) (15B52)

Recommendations

• Breakdown of equivalence between the minimal \(\ell^1\)-norm solution and the sparsest solution
• For most large underdetermined systems of linear equations the minimal 𝓁₁‐norm solution is also the sparsest solution
• Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices
• For most large underdetermined systems of equations, the minimal 𝓁₁‐norm near‐solution approximates the sparsest near‐solution
• Nonuniform sparse recovery with subgaussian matrices

Cited in

(1)

• Phase transitions in error correcting and compressed sensing by \(\ell _{1}\) linear programming

Describes a project that uses

Uses Software

• L1-MAGIC

This page was built for publication: Mean breakdown points for compressed sensing by uniformly distributed matrices

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