Solving Basis Pursuit

DOI10.1145/2689662zbMath1371.65055OpenAlexW2110813874WikidataQ113310273 ScholiaQ113310273MaRDI QIDQ5270711

Andreas M. Tillmann, Marc E. Pfetsch, Dirk A. Lorenz

Publication date: 30 June 2017

Published in: ACM Transactions on Mathematical Software (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2689662

zbMATH Keywords

test problemscompressed sensingunderdetermined linear systemcompressive samplingtest setbasis pursuitsolver comparison\(\ell_{1}\)heuristic optimality checkminimum \(\ell_{1}\)-norm solutionprimal-dual optimal pair

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20) Numerical mathematical programming methods (65K05) Approximation methods and heuristics in mathematical programming (90C59) Complexity and performance of numerical algorithms (65Y20)

Related Items

Efficient iterative method for SOAV minimization problem with linear equality and box constraints and its linear convergence, A primal-dual homotopy algorithm for \(\ell _{1}\)-minimization with \(\ell _{\infty }\)-constraints, A simple homotopy proximal mapping algorithm for compressive sensing, An infeasible-point subgradient method using adaptive approximate projections, Complexity and applications of the homotopy principle for uniformly constrained sparse minimization, Fast Iterative Solution of the Optimal Transport Problem on Graphs

Uses Software

• SoPlex
• NESTA
• SPGL1
• FPC_AS
• L1TestPack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Smooth minimization of non-smooth functions
• An infeasible-point subgradient method using adaptive approximate projections
• Convergence and computational analyses for some variable target value and subgradient deflection methods
• Conditional subgradient optimization -- theory and applications
• Least angle regression. (With discussion)
• A Fast Algorithm for Sparse Reconstruction Based on Shrinkage, Subspace Optimization, and Continuation
• Analysis and Generalizations of the Linearized Bregman Method
• Linearized Bregman iterations for compressed sensing
• Necessary and sufficient conditions for linear convergence of ℓ1-regularization
• Alternating Direction Algorithms for $\ell_1$-Problems in Compressive Sensing
• Beyond convergence rates: exact recovery with the Tikhonov regularization with sparsity constraints
• On Sparse Representations in Arbitrary Redundant Bases
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Greed is Good: Algorithmic Results for Sparse Approximation
• Just relax: convex programming methods for identifying sparse signals in noise
• Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
• Probing the Pareto Frontier for Basis Pursuit Solutions
• Fast Solution of $\ell _{1}$-Norm Minimization Problems When the Solution May Be Sparse
• A new approach to variable selection in least squares problems
• Uncertainty principles and ideal atomic decomposition
• Constructing Test Instances for Basis Pursuit Denoising
• Validation of subgradient optimization
• Convergence Analysis of Deflected Conditional Approximate Subgradient Methods
• Bregman Iterative Algorithms for $\ell_1$-Minimization with Applications to Compressed Sensing
• Sparse Signal Reconstruction via Iterative Support Detection
• Compressed sensing