Breakdown of equivalence between the minimal \(\ell^1\)-norm solution and the sparsest solution

DOI10.1016/j.sigpro.2005.05.028zbMath1163.94398OpenAlexW1996830635MaRDI QIDQ1027252

David L. Donoho, Yaakov Tsaig

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)

Related Items

Computing and analyzing recoverable supports for sparse reconstruction, Stable high-order cubature formulas for experimental data, Two Algorithms for Compressed Sensing of Sparse Tensors, Theory of compressive sensing via \(\ell_1\)-minimization: a non-RIP analysis and extensions, Analog random coding, Lyapunov exponents for some isotropic random matrix ensembles, Noisy 1-bit compressive sensing: models and algorithms, Second order self-adaptive dynamical system for sparse signal reconstruction and applications to image recovery, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, A coordinate gradient descent method for \(\ell_{1}\)-regularized convex minimization, Parameter selection for nonnegative $l_1$ matrix/tensor sparse decomposition, Sparse Representation of Signals in Hardy Space, PHASE TRANSITIONS IN ERROR CORRECTING AND COMPRESSED SENSING BY ℓ₁ LINEAR PROGRAMMING, New analysis of manifold embeddings and signal recovery from compressive measurements