Augmented _1 and nuclear-norm models with a globally linearly convergent algorithm

DOI10.1137/120863290zbMATH Open1279.68329arXiv1201.4615OpenAlexW2075826622MaRDI QIDQ2873229FDOQ2873229

Authors: Ming-Jun Lai, Wotao Yin 

Publication date: 23 January 2014

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

Abstract: This paper studies the long-existing idea of adding a nice smooth function to "smooth" a non-differentiable objective function in the context of sparse optimization, in particular, the minimization of $||x|{|}_1+1/(2alpha)||x|{|}_2^2$, where $x$ is a vector, as well as the minimization of $||X|{|}_{\ast }+1/(2alpha)||X|{|}_F^2$, where $X$ is a matrix and $||X|{|}_{*}$ and $||X|{|}_F$ are the nuclear and Frobenius norms of $X$, respectively. We show that they can efficiently recover sparse vectors and low-rank matrices. In particular, they enjoy exact and stable recovery guarantees similar to those known for minimizing $||x|{|}_1$ and $||X|{|}_{*}$ under the conditions on the sensing operator such as its null-space property, restricted isometry property, spherical section property, or RIPless property. To recover a (nearly) sparse vector $x^0$, minimizing $||x|{|}_1+1/(2alpha)||x|{|}_2^2$ returns (nearly) the same solution as minimizing $||x|{|}_1$ almost whenever $alphage10||x^0|{|}_{i}nfty$. The same relation also holds between minimizing $||X|{|}_{\ast }+1/(2alpha)||X|{|}_F^2$ and minimizing $||X|{|}_{*}$ for recovering a (nearly) low-rank matrix $X^0$, if $alphage10||X^0|{|}_2$. Furthermore, we show that the linearized Bregman algorithm for minimizing $||x|{|}_1+1/(2alpha)||x|{|}_2^2$ subject to $Ax=b$ enjoys global linear convergence as long as a nonzero solution exists, and we give an explicit rate of convergence. The convergence property does not require a solution solution or any properties on $A$. To our knowledge, this is the best known global convergence result for first-order sparse optimization algorithms.

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

Recommendations

• Truncated $l_{1-2}$ Models for Sparse Recovery and Rank Minimization
• On first-order algorithms for \(\ell_{1}/\)nuclear norm minimization
• An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems
• Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization
• Fixed-Point Continuation for $\ell_1$-Minimization: Methodology and Convergence

zbMATH Keywords

matrix completioncompressed sensingsparse optimizationlow-rank matrixexact regularizationglobal linear convergence

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Convex programming (90C25) Interior-point methods (90C51) Computing methodologies for image processing (68U10)

Cited In (36)

• Eventual linear convergence of the Douglas-Rachford iteration for basis pursuit
• A new piecewise quadratic approximation approach for \(L_0\) norm minimization problem
• Cardinality minimization, constraints, and regularization: a survey
• Revisiting linearized Bregman iterations under Lipschitz-like convexity condition
• Linear convergence of descent methods for the unconstrained minimization of restricted strongly convex functions
• Proximal linearization methods for Schatten \(p\)-quasi-norm minimization
• Extragradient and extrapolation methods with generalized Bregman distances for saddle point problems
• Asynchronous stochastic coordinate descent: parallelism and convergence properties
• Iterative methods based on soft thresholding of hierarchical tensors
• Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
• Optimality conditions and numerical algorithms for a class of linearly constrained minimax optimization problems
• Sparse + low-energy decomposition for viscous conservation laws
• On first-order algorithms for \(\ell_{1}/\)nuclear norm minimization
• Low-rank matrix recovery problem minimizing a new ratio of two norms approximating the rank function then using an ADMM-type solver with applications
• EXTRA: an exact first-order algorithm for decentralized consensus optimization
• Restricted strong convexity and its applications to convergence analysis of gradient-type methods in convex optimization
• Sparse recovery via differential inclusions
• Acceleration and restart for the randomized Bregman-Kaczmarz method
• Regularized Kaczmarz Algorithms for Tensor Recovery
• On the convergence of asynchronous parallel iteration with unbounded delays
• Low-rank matrix recovery via regularized nuclear norm minimization
• A time continuation based fast approximate algorithm for compressed sensing related optimization
• New analysis of linear convergence of gradient-type methods via unifying error bound conditions
• Proximal-like incremental aggregated gradient method with linear convergence under Bregman distance growth conditions
• Stability of the elastic net estimator
• Redundancy techniques for straggler mitigation in distributed optimization and learning
• Projected shrinkage algorithm for box-constrained \(\ell _1\)-minimization
• Extended randomized Kaczmarz method for sparse least squares and impulsive noise problems
• On the convergence of decentralized gradient descent
• An improved algorithm for basis pursuit problem and its applications
• Local linear convergence of a primal-dual algorithm for the augmented convex models
• Variance reduction for root-finding problems
• Sparse sampling Kaczmarz–Motzkin method with linear convergence
• A flexible ADMM algorithm for big data applications
• Linear convergence of the randomized sparse Kaczmarz method
• The restricted strong convexity revisited: analysis of equivalence to error bound and quadratic growth

This page was built for publication: Augmented \(\ell_1\) and nuclear-norm models with a globally linearly convergent algorithm

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