Breakdown of equivalence between the minimal ^1-norm solution and the sparsest solution

DOI10.1016/J.SIGPRO.2005.05.028MaRDI QIDQ1027252zbMATH OpenOpenAlexFDO

Authors Yaakov Tsaig, David Donoho

Publication date 1 July 2009

Published in Signal Processing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.sigpro.2005.05.028

zbMATH Keywords

linear programmingrandom matrix theorybasis pursuitsparse representationsunderdetermined systems of linear equationsovercomplete systemspartial Fourier matrix ensemblepartial Hadamard matrix ensemblerandom signs matrix ensemble

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Recommendations

• For most large underdetermined systems of linear equations the minimal 𝓁₁‐norm solution is also the sparsest solution
• For most large underdetermined systems of equations, the minimal 𝓁₁‐norm near‐solution approximates the sparsest near‐solution
• Fast Solution of $\ell _{1}$-Norm Minimization Problems When the Solution May Be Sparse
• Sparsest solutions of underdetermined linear systems via \( \ell _q\)-minimization for \(0<q\leqslant 1\)
• Exact and approximate sparse solutions of underdetermined linear equations

Cited in

(18)

• Lyapunov exponents for some isotropic random matrix ensembles
• Computing and analyzing recoverable supports for sparse reconstruction
• New analysis of manifold embeddings and signal recovery from compressive measurements
• Parameter selection for nonnegative $l_1$ matrix/tensor sparse decomposition
• Second order self-adaptive dynamical system for sparse signal reconstruction and applications to image recovery
• Stable high-order cubature formulas for experimental data
• A coordinate gradient descent method for \(\ell_{1}\)-regularized convex minimization
• scientific article; zbMATH DE number 6746123 (Why is no real title available?)
• Two algorithms for compressed sensing of sparse tensors
• Analog random coding
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Noisy 1-bit compressive sensing: models and algorithms
• Theory of compressive sensing via _1-minimization: a non-RIP analysis and extensions
• Mean breakdown points for compressed sensing by uniformly distributed matrices
• Analysis of the equivalence relationship between \(l_{0}\)-minimization and \(l_{p}\)-minimization
• Sparse representation of signals in Hardy space
• Phase transitions in error correcting and compressed sensing by \(\ell _{1}\) linear programming
• For most large underdetermined systems of linear equations the minimal 𝓁₁‐norm solution is also the sparsest solution

This page was built for publication: Breakdown of equivalence between the minimal \(\ell^1\)-norm solution and the sparsest solution

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