Constructing Test Instances for Basis Pursuit Denoising

The number of available algorithms for the so-called Basis Pursuit Denoising problem (or the related LASSO-problem) is large and keeps growing. Similarly, the number of experiments to evaluate and compare these algorithms on different instances is growing. In this correspondence, we present a method to produce instances with exact solutions that is based on a simple observation, related to the so-called source condition from sparse regularization.

• Publication year

  2011

• Venue

  IEEE Transactions on Signal Processing

• Publication date

  2011-03-15

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/TSP.2012.2236322arXiv 1103.2897
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Practical Compressed Sensing: Modern data acquisition and signal processing

  2011cited by this paper
• Necessary and sufficient conditions for linear convergence of ℓ1‐regularization

  2011cited by this paper
• Beyond convergence rates: exact recovery with the Tikhonov regularization with sparsity constraints

  2010cited by this paper
• Steepest descent

  2010cited by this paper
• Templates for convex cone problems with applications to sparse signal recovery

  2010cited by this paper
• Theoretical and Empirical Results for Recovery From Multiple Measurements

  2009cited by this paper
• From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images

  2009cited by this paper
• Alternating Direction Algorithms for 1-Problems in Compressive Sensing

  2009cited by this paper
• Inline hologram reconstruction with sparsity constraints.

  2009cited by this paper
• NESTA: A Fast and Accurate First-Order Method for Sparse Recovery

  2009cited by this paper
• Fixed-Point Continuation for l1-Minimization: Methodology and Convergence

  2008cited by this paper
• Bregman Iterative Algorithms for (cid:2) 1 -Minimization with Applications to Compressed Sensing ∗

  2008cited by this paper
• Probing the Pareto Frontier for Basis Pursuit Solutions

  2008cited by this paper
• Convergence rates and source conditions for Tikhonov regularization with sparsity constraints

  2008cited by this paper
• Iterated Hard Shrinkage for Minimization Problems with Sparsity Constraints

  2008cited by this paper
• Reduce and Boost: Recovering Arbitrary Sets of Jointly Sparse Vectors

  2008cited by this paper
• REGULARIZATION PROPERTIES OF TIKHONOV REGULARIZATION WITH SPARSITY CONSTRAINTS

  2008cited by this paper
• Sparse regularization with lq penalty term

  2008cited by this paper
• Sparse Reconstruction by Separable Approximation

  2008cited by this paper
• L1Packv2: A Mathematica package for minimizing an l1-penalized functional

  2007cited by this paper
• Gradient Projection for Sparse Reconstruction: Application to Compressed Sensing and Other Inverse Problems

  2007cited by this paper
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization

  2007cited by this paper
• On the performance of algorithms for the minimization of ℓ1-penalized functionals

  2007cited by this paper
• A semismooth Newton method for Tikhonov functionals with sparsity constraints

  2007cited by this paper
• Efficient sparse coding algorithms

  2006cited by this paper
• Recovery Algorithms for Vector-Valued Data with Joint Sparsity Constraints

  2006cited by this paper
• Just relax: convex programming methods for identifying sparse signals in noise

  2006cited by this paper
• Decoding by linear programming

  2005cited by this paper
• Convex Optimization

  2004cited by this paper
• A conditional gradient method with linear rate of convergence for solving convex linear systems

  2004cited by this paper
• An iterative thresholding algorithm for linear inverse problems with a sparsity constraint

  2003cited by this paper
• Atomic Decomposition by Basis Pursuit

  1998cited by this paper
• On Projection Algorithms for Solving Convex Feasibility Problems

  1996cited by this paper
• Regression Shrinkage and Selection via the Lasso

  1996cited by this paper
• Proximity maps for convex sets

  1959cited by this paper
• An algorithm for quadratic programming

  1956cited by this paper

• Inertial terms enhanced iteration schemes for fixed points of pseudocontractions and zeros of monotone operators

  2026cites this paper
• Dual-sensor blade tip timing with multi-source information and adaptive dictionary update

  2025cites this paper
• Basis pursuit by inconsistent alternating projections

  2025cites this paper
• Sparse Recovery: The Square of ℓ1/ℓ2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell _1/\ell _2$$\end{document} No

  2024cites this paper
• A cut-and-project perspective for linearized Bregman iterations

  2024cites this paper
• A time-frequency sparse strategy based on optimal flux atom and scale lp approximation operator

  2022cites this paper
• Accelerated Sparse Recovery via Gradient Descent with Nonlinear Conjugate Gradient Momentum

  2022cites this paper
• Inertial Iteration Scheme for Approximating Fixed Points of Lipschitz Pseudocontractive Maps in Arbitrary Real Banach Spaces

  2022cites this paper
• ECG Signal Denoising and Reconstruction Based on Basis Pursuit

  2021cites this paper
• MINIMIZATION OF L1 OVER L2 FOR SPARSE SIGNAL

  2021cites this paper
• A new Halpern-type averaging algorithm with inertial and error terms for fixed points of asymptotically nonexpansive maps

  2020cites this paper
• Feature Extraction of Echo Signal of Weld Defect Guided Waves Based on Sparse Representation

  2020cites this paper
• MINIMIZATION OF L1 OVER L2 FOR SPARSE SIGNAL RECOVERY WITH CONVERGENCE GUARANTEE∗

  2020cites this paper
• New strong convergence method for the sum of two maximal monotone operators

  2020influential citation
• Sparse representations for fault signatures via hybrid regularization in adaptive undecimated fractional spline wavelet transform domain

  2020cites this paper
• New strong convergence method for the sum of two maximal monotone operators

  2020cites this paper
• Iterative method with inertial terms for nonexpansive mappings: applications to compressed sensing

  2019cites this paper
• Multi-Resolution Parallel Magnetic Resonance Image Reconstruction in Mobile Computing-Based IoT

  2019cites this paper
• Accelerated Schemes for the $L_1/L_2$ Minimization

  2019cites this paper
• Proximal envelopes: Smooth optimization algorithms for nonsmooth problems

  2017cites this paper
• Iterative Soft/Hard Thresholding With Homotopy Continuation for Sparse Recovery

  2017cites this paper
• Numerical methods and second order theory for nonsmooth problems

  2016cites this paper
• Fast L1–L2 Minimization via a Proximal Operator

  2016cites this paper
• Architecture for one-shot compressive imaging using computer-generated holograms.

  2016cites this paper
• Iterative Soft / Hard Thresholding Homotopy Algorithm for Sparse Recovery

  2016cites this paper
• Efficient evaluation of scaled proximal operators

  2016cites this paper
• Coercive functions from a topological viewpoint and properties of minimizing sets of convex functions appearing in image restoration

  2015influential citation
• Solving Basis Pursuit

  2015influential citation
• Performance of first- and second-order methods for ℓ1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell _1$$\end{doc

  2015cites this paper
• Improved smoothed L0 reconstruction algorithm for ISI sparse channel estimation

  2014cites this paper
• On the Relationship between Conjugate Gradient and Optimal First-Order Methods for Convex Optimization

  2014cites this paper
• Computational aspects of compressed sensing

  2014influential citation
• Forward-backward truncated Newton methods for convex composite optimization

  2014cites this paper
• A Semismooth Newton Method with Multidimensional Filter Globalization for l1-Optimization

  2014cites this paper
• Sparsity-aware channel estimation with contaminated pilot sequence

  2014cites this paper
• Douglas-rachford splitting: Complexity estimates and accelerated variants

  2014cites this paper
• Computing and analyzing recoverable supports for sparse reconstruction

  2013cites this paper
• The Linearized Bregman Method via Split Feasibility Problems: Analysis and Generalizations

  2013cites this paper
• A cyclic projected gradient method

  2012cites this paper
• Necessary and Sufficient Conditions of Solution Uniqueness in 1-Norm Minimization

  2012cites this paper
• SparOptLib - A Testing Library of Sparse Solution Recovery Problems

  2012cites this paper
• Homogeneous Penalizers and Constraints in Convex Image Restoration

  2012cites this paper
• SparOptLib - A Testing Library of Sparse Solution Recovery Problems

  2012cites this paper
• Practical Compressed Sensing: Modern data acquisition and signal processing

  2011cites this paper
• On Cyclic Gradient Descent Reprojection

  2011cites this paper
• Templates for convex cone problems with applications to sparse signal recovery

  2010cites this paper
• Edinburgh Research Explorer Performance of first-and second-order methods for ℓ1-regularized least squares problems

  year unknowncites this paper