Probing the Pareto Frontier for Basis Pursuit Solutions

DOI10.1137/080714488zbMath1193.49033OpenAlexW2083042020MaRDI QIDQ3558672

Michael P. Friedlander, Ewout van den Berg

Publication date: 6 May 2010

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/67410b26b2d54f78b9fd06ee6100572ef288a810

zbMATH Keywords

Newton's method duality convex program sparse solutions root-finding projected gradient basis pursuit one-norm regularization

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Numerical methods involving duality (49M29)

Related Items

Algorithms that satisfy a stopping criterion, probably, Efficient projection algorithms onto the weighted $\ell_1$ ball, Parallel multipopulation optimization for belief rule base learning, An efficient DY-type spectral conjugate gradient method for system of nonlinear monotone equations with application in signal recovery, A smoothing SQP framework for a class of composite $L_q$ minimization over polyhedron, Fast projection onto the simplex and the $l_1$ ball, Projection algorithms for nonconvex minimization with application to sparse principal component analysis, A dual method for minimizing a nonsmooth objective over one smooth inequality constraint, An efficient projection method for nonlinear inverse problems with sparsity constraints, Sparse high-dimensional FFT based on rank-1 lattice sampling, Quantifying initial and wind forcing uncertainties in the gulf of Mexico, Inertial accelerated primal-dual methods for linear equality constrained convex optimization problems, Infinite-dimensional compressed sensing and function interpolation, Reweighted $\ell_1$ minimization method for stochastic elliptic differential equations, A weighted $\ell_1$-minimization approach for sparse polynomial chaos expansions, Compressive sampling of polynomial chaos expansions: convergence analysis and sampling strategies, Gradient projection Newton pursuit for sparsity constrained optimization, Sparse microwave imaging: principles and applications, A regularized semi-smooth Newton method with projection steps for composite convex programs, Accelerated Bregman method for linearly constrained $\ell _1-\ell _2$ minimization, ParNes: A rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals, Isotropic sparse regularization for spherical harmonic representations of random fields on the sphere, A hybrid quasi-Newton projected-gradient method with application to lasso and basis-pursuit denoising, A note on the spectral gradient projection method for nonlinear monotone equations with applications, Generalized Kalman smoothing: modeling and algorithms, An inexact alternating directions algorithm for constrained total variation regularized compressive sensing problems, The matrix splitting based proximal fixed-point algorithms for quadratically constrained $\ell_{1}$ minimization and Dantzig selector, A polynomial chaos framework for probabilistic predictions of storm surge events, Dualization of signal recovery problems, Optimal dual certificates for noise robustness bounds in compressive sensing, A filtered bucket-clustering method for projection onto the simplex and the $\ell_1$ ball, Sampling in the analysis transform domain, On the representation of functions with Gaussian wave packets, Phase transitions for greedy sparse approximation algorithms, Accelerated linearized Bregman method, A cyclic projected gradient method, Primal and dual alternating direction algorithms for $\ell _{1}$-$\ell _{1}$-norm minimization problems in compressive sensing, $L^1$ regularization method in electrical impedance tomography by using the $L^1$-curve (Pareto frontier curve), Global convergence via descent modified three-term conjugate gradient projection algorithm with applications to signal recovery, Alternating direction method of multipliers for sparse principal component analysis, Iterative reweighted minimization methods for $l_p$ regularized unconstrained nonlinear programming, Guaranteed clustering and biclustering via semidefinite programming, The smoothing FR conjugate gradient method for solving a kind of nonsmooth optimization problem with $l_1$-norm, An active-set proximal-Newton algorithm for $\ell_1$ regularized optimization problems with box constraints, Nonmonotone adaptive Barzilai-Borwein gradient algorithm for compressed sensing, Level set methods for stochastic discontinuity detection in nonlinear problems, First-order optimality condition of basis pursuit denoise problem, Generation of nested quadrature rules for generic weight functions via numerical optimization: application to sparse grids, Nonmonotone Barzilai-Borwein gradient algorithm for $\ell_1$-regularized nonsmooth minimization in compressive sensing, A perturbation view of level-set methods for convex optimization, Greedy subspace pursuit for joint sparse recovery, Level-set methods for convex optimization, A pseudo-heuristic parameter selection rule for $l^1$-regularized minimization problems, An efficient adaptive forward-backward selection method for sparse polynomial chaos expansion, Decomposition into low-rank plus additive matrices for background/foreground separation: a review for a comparative evaluation with a large-scale dataset, A compressed-sensing approach for closed-loop optimal control of nonlinear systems, A parallel proximal splitting method for disparity estimation from multicomponent images under illumination variation, Homogeneous penalizers and constraints in convex image restoration, Numerical methods for $A$-optimal designs with a sparsity constraint for ill-posed inverse problems, Convergence of fixed-point continuation algorithms for matrix rank minimization, A performance guarantee for orthogonal matching pursuit using mutual coherence, Two-dimensional random projection, Templates for convex cone problems with applications to sparse signal recovery, Non-smooth equations based method for $\ell_1$-norm problems with applications to compressed sensing, Compressed solving: a numerical approximation technique for elliptic PDEs based on compressed sensing, A projection method for convex constrained monotone nonlinear equations with applications, Fixed point and Bregman iterative methods for matrix rank minimization, A non-adapted sparse approximation of PDEs with stochastic inputs, Sparse approximate solution of partial differential equations, A numerical exploration of compressed sampling recovery, Projected Landweber iteration for matrix completion, Sparse identification of nonlinear dynamical systems via reweighted $\ell_1$-regularized least squares, The distance between convex sets with Minkowski sum structure: application to collision detection, Signal reconstruction by conjugate gradient algorithm based on smoothing $l_1$-norm, Recovery of seismic wavefields by an $l_{q}$-norm constrained regularization method, A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem, New augmented Lagrangian-based proximal point algorithm for convex optimization with equality constraints, Enhancing $\ell_1$-minimization estimates of polynomial chaos expansions using basis selection, Enhancing sparsity of Hermite polynomial expansions by iterative rotations, Underdetermined separation of speech mixture based on sparse Bayesian learning, Robust PCA via regularized \textsc{Reaper} with a matrix-free proximal algorithm, A gradient descent based algorithm for $\ell_p$ minimization, Analysis of compressed distributed adaptive filters, Numerical analysis for conservation laws using $l_1$ minimization, GPU accelerated greedy algorithms for compressed sensing, Matrix-free interior point method for compressed sensing problems, SSN: learning sparse switchable normalization via SparsestMax, SPGL1, Divide and conquer: an incremental sparsity promoting compressive sampling approach for polynomial chaos expansions, $h$-$p$ adaptive model based approximation of moment free sensitivity indices, Reconstruction of jointly sparse vectors via manifold optimization, Compressive Hermite interpolation: sparse, high-dimensional approximation from gradient-augmented measurements, A fast algorithm for solving linear inverse problems with uniform noise removal, Enabling numerically exact local solver for waveform inversion -- a low-rank approach, Learning ``best kernels from data in Gaussian process regression. With application to aerodynamics, Sparse representation based two-dimensional direction of arrival estimation using co-prime array, Constructing $L_1$-graphs for subspace learning via recurrent neural networks, Generalization bounds for sparse random feature expansions, Iterative choice of the optimal regularization parameter in TV image restoration, Easy implementation of advanced tomography algorithms using the ASTRA toolbox with spot operators, Doubly iteratively reweighted algorithm for constrained compressed sensing models, Derivative-based SINDy (DSINDy): addressing the challenge of discovering governing equations from noisy data, A dual active set method for $\ell1$-regularized problem, A Variable Density Sampling Scheme for Compressive Fourier Transform Interferometry, Sparse subsampling of flow measurements for finite-time Lyapunov exponent in domains with obstacles, A proximal trust-region method for nonsmooth optimization with inexact function and gradient evaluations, Global convergence via modified self-adaptive approach for solving constrained monotone nonlinear equations with application to signal recovery problems, Sparsity optimization in design of multidimensional filter networks, A fast $\ell_1$-solver and its applications to robust face recognition, Fusion of sparse reconstruction algorithms for multiple measurement vectors, Projections onto the canonical simplex with additional linear inequalities, Global sensitivity analysis based on high-dimensional sparse surrogate construction, A General Non-Lipschitz Infimal Convolution Regularized Model: Lower Bound Theory and Algorithm, Large sparse signal recovery by conjugate gradient algorithm based on smoothing technique, Numerical Integration in Multiple Dimensions with Designed Quadrature, Compressive Sensing with Cross-Validation and Stop-Sampling for Sparse Polynomial Chaos Expansions, Constructing Surrogate Models of Complex Systems with Enhanced Sparsity: Quantifying the Influence of Conformational Uncertainty in Biomolecular Solvation, An augmented Lagrangian based parallel splitting method for separable convex minimization with applications to image processing, A Proximal Strictly Contractive Peaceman--Rachford Splitting Method for Convex Programming with Applications to Imaging, A General Theory of Singular Values with Applications to Signal Denoising, Extracting Sparse High-Dimensional Dynamics from Limited Data, A Level-Set Method for Convex Optimization with a Feasible Solution Path, Synchrotron radiation-based $l_1$-norm regularization on micro-CT imaging in shale structure analysis, Nonlinear regularization techniques for seismic tomography, A Proximal Quasi-Newton Trust-Region Method for Nonsmooth Regularized Optimization, On Efficiently Solving the Subproblems of a Level-Set Method for Fused Lasso Problems, Group SLOPE – Adaptive Selection of Groups of Predictors, The modified accelerated Bregman method for regularized basis pursuit problem, An Iterative Reduction FISTA Algorithm for Large-Scale LASSO, Generalized conditional gradient method for elastic-net regularization, Difference-of-Convex Algorithms for a Class of Sparse Group $\ell_0$ Regularized Optimization Problems, Polyak's gradient method for split feasibility problem constrained by level sets, Performance comparisons of greedy algorithms in compressed sensing, Noisy Euclidean Distance Realization: Robust Facial Reduction and the Pareto Frontier, Solving constrained nonsmooth group sparse optimization via group Capped-$\ell_1$ relaxation and group smoothing proximal gradient algorithm, Solution sets of three sparse optimization problems for multivariate regression, Analysis of sparse recovery for Legendre expansions using envelope bound, A Restricted Dual Peaceman-Rachford Splitting Method for a Strengthened DNN Relaxation for QAP, Randomized Block Proximal Damped Newton Method for Composite Self-Concordant Minimization, Matrix-Free Convex Optimization Modeling, A Randomized Nonmonotone Block Proximal Gradient Method for a Class of Structured Nonlinear Programming, A gradient enhanced $\ell_{1}$-minimization for sparse approximation of polynomial chaos expansions, A simple homotopy proximal mapping algorithm for compressive sensing, Basis adaptive sample efficient polynomial chaos (BASE-PC), CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion, Super-resolution radar, Retraction-based first-order feasible methods for difference-of-convex programs with smooth inequality and simple geometric constraints, Polynomial approximation via compressed sensing of high-dimensional functions on lower sets, Stochastic Collocation Methods via $\ell_1$ Minimization Using Randomized Quadratures, A Highly Efficient Semismooth Newton Augmented Lagrangian Method for Solving Lasso Problems, Compressive Sensing, Do log factors matter? On optimal wavelet approximation and the foundations of compressed sensing, A greedy Newton-type method for multiple sparse constraint problem, AAA interpolation of equispaced data, Stochastic Collocation vial₁-Minimisation on Low Discrepancy Point Sets with Application to Uncertainty Quantification, Compressed Sensing with Sparse Corruptions: Fault-Tolerant Sparse Collocation Approximations, Sliced-Inverse-Regression--Aided Rotated Compressive Sensing Method for Uncertainty Quantification, Calibration of reduced-order model for a coupled Burgers equations based on PC-EnKF, Optimized Sampling for Multiscale Dynamics, A projected gradient method for αℓ ₁ − βℓ ₂ sparsity regularization ^**, An Introduction to Compressed Sensing, Accelerating Sparse Recovery by Reducing Chatter, A fast homotopy algorithm for gridless sparse recovery, Discrete chirp-Fourier transform and its application to chirp rate estimation, Inexact primal–dual gradient projection methods for nonlinear optimization on convex set, Error Localization of Best $L_{1}$ Polynomial Approximants, Relaxed Regularization for Linear Inverse Problems, Simultaneous-shot inversion for PDE-constrained optimization problems with missing data, Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices, IMRO: A Proximal Quasi-Newton Method for Solving $\ell_1$-Regularized Least Squares Problems, Penalty Methods for a Class of Non-Lipschitz Optimization Problems, Gradient descent and fast artificial time integration, Least Sparsity of $p$-Norm Based Optimization Problems with $p>1$, Lattice-Based Patterned Fabric Inspection by Using Total Variation with Sparsity and Low-Rank Representations, Spherical Designs and Nonconvex Minimization for Recovery of Sparse Signals on the Sphere, Linearized alternating directions method for $\ell_1$-norm inequality constrained $\ell_1$-norm minimization, Faster gradient descent and the efficient recovery of images, A Practical Guide to the Recovery of Wavelet Coefficients from Fourier Measurements, An Efficient Proximal Block Coordinate Homotopy Method for Large-Scale Sparse Least Squares Problems, CURVELET-WAVELET REGULARIZED SPLIT BREGMAN ITERATION FOR COMPRESSED SENSING, Tensor Least Angle Regression for Sparse Representations of Multidimensional Signals, Unnamed Item, On the Probabilistic Cauchy Theory for Nonlinear Dispersive PDEs, Exact Clustering of Weighted Graphs via Semidefinite Programming, Sparse Solutions by a Quadratically Constrained ℓq (0 <q< 1) Minimization Model, Sparse Polynomial Chaos Expansions: Literature Survey and Benchmark, Analysis and Algorithms for Some Compressed Sensing Models Based on L1/L2 Minimization, Relaxed Regularization for Linear Inverse Problems, The Gap between Theory and Practice in Function Approximation with Deep Neural Networks, Accelerated Iterative Regularization via Dual Diagonal Descent, Stochastic Collocation Algorithms Using $l_1$-Minimization for Bayesian Solution of Inverse Problems, Convergence Rate Analysis of a Sequential Convex Programming Method with Line Search for a Class of Constrained Difference-of-Convex Optimization Problems, Group Sparse Optimization for Images Recovery Using Capped Folded Concave Functions, Alternating direction method of multipliers for solving dictionary learning models, Recovering Wavelet Coefficients from Binary Samples Using Fast Transforms, Primal–dual first-order methods for a class of cone programming, An Algorithm Solving Compressive Sensing Problem Based on Maximal Monotone Operators, Sparse Solutions of a Class of Constrained Optimization Problems, On the Absence of Uniform Recovery in Many Real-World Applications of Compressed Sensing and the Restricted Isometry Property and Nullspace Property in Levels, An active-set proximal quasi-Newton algorithm for ℓ₁-regularized minimization over a sphere constraint, Nonuniform recovery of fusion frame structured sparse signals, Optimality properties of an augmented Lagrangian method on infeasible problems, A modified Newton projection method for $\ell _1$-regularized least squares image deblurring, Solving Basis Pursuit, Combining line search and trust-region methods forℓ1-minimization

Uses Software