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

DOI10.1016/J.SIGPRO.2005.05.028zbMATH Open1163.94398OpenAlexW1996830635MaRDI QIDQ1027252FDOQ1027252

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

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

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)

Cited In (18)

• 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
• Title not available (Why is that?)
• A coordinate gradient descent method for \(\ell_{1}\)-regularized convex minimization
• 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 \(\ell_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
• For most large underdetermined systems of linear equations the minimal 𝓁₁‐norm solution is also the sparsest solution
• Phase transitions in error correcting and compressed sensing by \(\ell _{1}\) linear programming
• Lyapunov exponents for some isotropic random matrix ensembles

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)