Nonmonotone Barzilai-Borwein gradient algorithm for _1-regularized nonsmooth minimization in compressive sensing

DOI10.1007/S10915-013-9815-8zbMATH Open1306.65216arXiv1207.4538OpenAlexW2067425611MaRDI QIDQ474971FDOQ474971

Liqun Qi, Yunhai Xiao, Soon-Yi Wu

Publication date: 25 November 2014

Published in: Journal of Scientific Computing (Search for Journal in Brave)

Abstract: This paper is devoted to minimizing the sum of a smooth function and a nonsmooth $el{l}_1$-regularized term. This problem as a special cases includes the $el{l}_1$-regularized convex minimization problem in signal processing, compressive sensing, machine learning, data mining, etc. However, the non-differentiability of the $el{l}_1$-norm causes more challenging especially in large problems encountered in many practical applications. This paper proposes, analyzes, and tests a Barzilai-Borwein gradient algorithm. At each iteration, the generated search direction enjoys descent property and can be easily derived by minimizing a local approximal quadratic model and simultaneously taking the favorable structure of the $el{l}_1$-norm. Moreover, a nonmonotone line search technique is incorporated to find a suitable stepsize along this direction. The algorithm is easily performed, where the values of the objective function and the gradient of the smooth term are required at per-iteration. Under some conditions, the proposed algorithm is shown to be globally convergent. The limited experiments by using some nonconvex unconstrained problems from CUTEr library with additive $el{l}_1$-regularization illustrate that the proposed algorithm performs quite well. Extensive experiments for $el{l}_1$-regularized least squares problems in compressive sensing verify that our algorithm compares favorably with several state-of-the-art algorithms which are specifically designed in recent years.

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

Recommendations

• Nonmonotone adaptive Barzilai-Borwein gradient algorithm for compressed sensing
• Nomonotone spectral gradient method for sparse recovery
• Non-smooth equations based method for \(\ell_1\)-norm problems with applications to compressed sensing
• A Barzilai-Borwein gradient projection method for sparse signal and blurred image restoration
• The Barzilai and Borwein gradient method with nonmonotone line search for nonsmooth convex optimization problems

zbMATH Keywords

nonconvex optimizationnumerical experimentsnonsmooth optimizationgradient algorithmiterationcompressive sensingquasi-Newton methodnonmonotone line searchHessian approximation\(\ell_1\) regularizationBarzilai-Borwein gradient algorithmglobally convergentpositive componentssmooth term

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30)

Cites Work

• NESTA: A Fast and Accurate First-Order Method for Sparse Recovery
• Newton's Method for Large Bound-Constrained Optimization Problems
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• A Fast Algorithm for Sparse Reconstruction Based on Shrinkage, Subspace Optimization, and Continuation
• Probing the Pareto frontier for basis pursuit solutions
• CUTE
• Nonlinear total variation based noise removal algorithms
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Smooth minimization of non-smooth functions
• A quasi-Newton approach to nonsmooth convex optimization problems in machine learning
• A Singular Value Thresholding Algorithm for Matrix Completion
• Updating Quasi-Newton Matrices with Limited Storage
• Nonmonotone Spectral Projected Gradient Methods on Convex Sets
• The Barzilai and Borwein Gradient Method for the Large Scale Unconstrained Minimization Problem
• Two-Point Step Size Gradient Methods
• A Nonmonotone Line Search Technique and Its Application to Unconstrained Optimization
• An augmented Lagrangian approach for sparse principal component analysis
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Stable signal recovery from incomplete and inaccurate measurements
• A coordinate gradient descent method for nonsmooth separable minimization
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Compressed sensing
• Alternating direction method for covariance selection models
• On the convergence of an active-set method for ℓ₁minimization
• Alternating Direction Algorithms for $\ell_1$-Problems in Compressive Sensing
• Fixed-Point Continuation for $\ell_1$-Minimization: Methodology and Convergence
• A Nonmonotone Line Search Technique for Newton’s Method
• The cyclic Barzilai-–Borwein method for unconstrained optimization
• Title not available (Why is that?)
• Title not available (Why is that?)
• Efficient online and batch learning using forward backward splitting
• \(R\)-linear convergence of the Barzilai and Borwein gradient method
• A comparison of optimization methods and software for large-scale L1-regularized linear classifi\-cation
• Title not available (Why is that?)
• A coordinate gradient descent method for \(\ell_{1}\)-regularized convex minimization
• On the Barzilai and Borwein choice of steplength for the gradient method
• Quantitative robust uncertainty principles and optimally sparse decompositions
• A fast hybrid algorithm for large-scale \(l_{1}\)-regularized logistic regression
• On the asymptotic behaviour of some new gradient methods
• A derivative-free nonmonotone line search and its application to the spectral residual method
• A nonmonotone filter Barzilai-Borwein method for optimization

Cited In (11)

• Alternating direction and Taylor expansion minimization algorithms for unconstrained nuclear norm optimization
• Nonmonotone adaptive Barzilai-Borwein gradient algorithm for compressed sensing
• A diagonally scaled Newton-type proximal method for minimization of the models with nonsmooth composite cost functions
• A new generalized shrinkage conjugate gradient method for sparse recovery
• A scalar Hessian estimation with a sparse nonmonotone line search technique for the sparse recovery problem
• A class of line search-type methods for nonsmooth convex regularized minimization
• Low-rank and sparse matrices fitting algorithm for low-rank representation
• An approximate Newton-type proximal method using symmetric rank-one updating formula for minimizing the nonsmooth composite functions
• Exact Penalty Function for $\ell_{2,1}$ Norm Minimization over the Stiefel Manifold
• Accelerating optimization by tracing valley
• Combining line search and trust-region methods forℓ1-minimization

Uses Software

• L-BFGS
• CUTEr
• NESTA
• SPGL1
• FPC_AS
• TwIST

This page was built for publication: Nonmonotone Barzilai-Borwein gradient algorithm for \(\ell_1\)-regularized nonsmooth minimization in compressive sensing

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