A first-order augmented Lagrangian method for compressed sensing
From MaRDI portal
Abstract: We propose a first-order augmented Lagrangian algorithm (FAL) for solving the basis pursuit problem. FAL computes a solution to this problem by inexactly solving a sequence of L1-regularized least squares sub-problems. These sub-problems are solved using an infinite memory proximal gradient algorithm wherein each update reduces to "shrinkage" or constrained "shrinkage". We show that FAL converges to an optimal solution of the basis pursuit problem whenever the solution is unique, which is the case with very high probability for compressed sensing problems. We construct a parameter sequence such that the corresponding FAL iterates are eps-feasible and eps-optimal for all eps>0 within O(log(1/eps)) FAL iterations. Moreover, FAL requires at most O(1/eps) matrix-vector multiplications of the form Ax or A^Ty to compute an eps-feasible, eps-optimal solution. We show that FAL can be easily extended to solve the basis pursuit denoising problem when there is a non-trivial level of noise on the measurements. We report the results of numerical experiments comparing FAL with the state-of-the-art algorithms for both noisy and noiseless compressed sensing problems. A striking property of FAL that we observed in the numerical experiments with randomly generated instances when there is no measurement noise was that FAL always correctly identifies the support of the target signal without any thresholding or post-processing, for moderately small error tolerance values.
Recommendations
- Alternating direction algorithms for \(\ell_1\)-problems in compressive sensing
- Bregman Iterative Algorithms for \ell₁-Minimization with Applications to Compressed Sensing
- An accelerated proximal augmented Lagrangian method and its application in compressive sensing
- A time continuation based fast approximate algorithm for compressed sensing related optimization
- NESTA: A fast and accurate first-order method for sparse recovery
Cited in
(21)- Sparse solutions to an underdetermined system of linear equations via penalized Huber loss
- An efficient adaptive accelerated inexact proximal point method for solving linearly constrained nonconvex composite problems
- An accelerated proximal augmented Lagrangian method and its application in compressive sensing
- Efficient algorithms for robust and stable principal component pursuit problems
- An augmented Lagrangian trust region method for equality constrained optimization
- Conic optimization via operator splitting and homogeneous self-dual embedding
- OSGA: a fast subgradient algorithm with optimal complexity
- Gradient-based method with active set strategy for \(\ell _1\) optimization
- Decomposition into low-rank plus additive matrices for background/foreground separation: a review for a comparative evaluation with a large-scale dataset
- Adaptive inexact fast augmented Lagrangian methods for constrained convex optimization
- A distributed ADMM-like method for resource sharing over time-varying networks
- A Computational Framework for Multivariate Convex Regression and Its Variants
- A time continuation based fast approximate algorithm for compressed sensing related optimization
- Semidefinite programming for chance constrained optimization over semialgebraic sets
- Iteration Complexity of an Inner Accelerated Inexact Proximal Augmented Lagrangian Method Based on the Classical Lagrangian Function
- An adaptive superfast inexact proximal augmented Lagrangian method for smooth nonconvex composite optimization problems
- An accelerated inexact dampened augmented Lagrangian method for linearly-constrained nonconvex composite optimization problems
- A proximal augmented Lagrangian method for linearly constrained nonconvex composite optimization problems
- Accelerated gradient methods with biased gradient estimates: risk sensitivity, high-probability guarantees, and large deviation bounds
- A -inertial ADMM for efficient and stable nonconvex optimization
- The augmented Lagrangian methods: overview and recent advances
This page was built for publication: A first-order augmented Lagrangian method for compressed sensing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2910879)
