Gradient-based methods for sparse recovery

DOI10.1137/090775063MaRDI QIDQ3077129zbMATH OpenOpenAlexFDO

Authors William Hager, Dzung T. Phan, Hongchao Zhang

Publication date 22 February 2011

Published in SIAM Journal on Imaging Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0912.1660

zbMATH Keywords

BB methodcompressed sensingdenoisingimage reconstructioniterative shrinkage thresholding algorithmlinear convergencenonmonotone convergencenonsmooth optimizationsparse reconstruction by separable approximationsparse recoverysublinear convergence

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Large-scale problems in mathematical programming (90C06) Convex programming (90C25) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08)

Abstract: The convergence rate is analyzed for the SpaSRA algorithm (Sparse Reconstruction by Separable Approximation) for minimizing a sum $f(mx)+psi(mx)$ where $f$ is smooth and $psi$ is convex, but possibly nonsmooth. It is shown that if $f$ is convex, then the error in the objective function at iteration $k$, for $k$ sufficiently large, is bounded by $a/(b+k)$ for suitable choices of $a$ and $b$. Moreover, if the objective function is strongly convex, then the convergence is $R$-linear. An improved version of the algorithm based on a cycle version of the BB iteration and an adaptive line search is given. The performance of the algorithm is investigated using applications in the areas of signal processing and image reconstruction.

Recommendations

• Gradient-based algorithms with applications to signal-recovery problems
• Accelerated sparse recovery via gradient descent with nonlinear conjugate gradient momentum
• Nomonotone spectral gradient method for sparse recovery
• An iteratively approximated gradient projection algorithm for sparse signal reconstruction
• A gradient projection method for the sparse signal reconstruction in compressive sensing

Cited in

(43)

• On globally Q-linear convergence of a splitting method for group Lasso
• Bregman operator splitting with variable stepsize for total variation image reconstruction
• An extended projected residual algorithm for solving smooth convex optimization problems
• A truncated Newton algorithm for nonconvex sparse recovery
• A note on the spectral gradient projection method for nonlinear monotone equations with applications
• Convergence of slice-based block coordinate descent algorithm for convolutional sparse coding
• A new spectral method for \(l_1\)-regularized minimization
• A modified Newton projection method for \(\ell _1\)-regularized least squares image deblurring
• A preconditioned conjugate gradient method with active set strategy for \(\ell_1\)-regularized least squares
• A relaxed-PPA contraction method for sparse signal recovery
• Nomonotone spectral gradient method for sparse recovery
• The Moreau envelope based efficient first-order methods for sparse recovery
• An efficient augmented Lagrangian method with applications to total variation minimization
• An active set Newton-CG method for \(\ell_1\) optimization
• An \(\mathcal O(1/{k})\) convergence rate for the variable stepsize Bregman operator splitting algorithm
• Projection onto a polyhedron that exploits sparsity
• Recovering gradients from sparsely observed functional data
• A Barzilai-Borwein-like iterative half thresholding algorithm for the \(L_{1/2}\) regularized problem
• A model of regularization parameter determination in low-dose X-ray CT reconstruction based on dictionary learning
• scientific article; zbMATH DE number 5853153 (Why is no real title available?)
• Gradient-based algorithms with applications to signal-recovery problems
• Two-point step-size iterative soft-thresholding method for sparse reconstruction
• An active set algorithm for nonlinear optimization with polyhedral constraints
• On the rate of convergence of projected Barzilai-Borwein methods
• Gradient-based method with active set strategy for \(\ell _1\) optimization
• Projected Nesterov's Proximal-Gradient Algorithm for Sparse Signal Recovery
• Sparse signal recovery based on forward backward operator splitting
• A Barzilai-Borwein type method for minimizing composite functions
• Delayed gradient methods for symmetric and positive definite linear systems
• Efficient Least Residual Greedy Algorithms for Sparse Recovery
• Active set complexity of the away-step Frank-Wolfe algorithm
• A fast homotopy algorithm for gridless sparse recovery
• A Gradient-Enhanced L1 Approach for the Recovery of Sparse Trigonometric Polynomials
• A fast conjugate gradient algorithm with active set prediction for ℓ₁ optimization
• A hybrid finite-dimensional RHC for stabilization of time-varying parabolic equations
• Accelerated sparse recovery via gradient descent with nonlinear conjugate gradient momentum
• Convergence of a Class of Nonmonotone Descent Methods for Kurdyka–Łojasiewicz Optimization Problems
• Splitting augmented Lagrangian-type algorithms with partial quadratic approximation to solve sparse signal recovery problems
• A scalar Hessian estimation with a sparse nonmonotone line search technique for the sparse recovery problem
• Sparse recovery based on the generalized error function
• A new generalized shrinkage conjugate gradient method for sparse recovery
• On the forward-backward method with nonmonotone linesearch for infinite-dimensional nonsmooth nonconvex problems
• Finite-dimensional receding horizon control of linear time-varying parabolic PDEs: stability analysis and model-order reduction

This page was built for publication: Gradient-based methods for sparse recovery

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3077129)