Augmented L1 and Nuclear-Norm Models with a Globally Linearly Convergent Algorithm

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/(2\alpha )||x|{|}_2^2$, where $x$ is a vector, as well as the minimization of $||X|{|}_{\ast }+1/(2\alpha )||X|{|}_F^2$, where $X$ is a matrix and $||X|{|}_{\ast }$ 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|{|}_{\ast }$ 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/(2\alpha )||x|{|}_2^2$ returns (nearly) the same solution as minimizing $||x|{|}_1$ almost whenever $\alpha \ge 10||x^0|{|}_{\infty }$. The same relation also holds between minimizing $||X|{|}_{\ast }+1/(2\alpha )||X|{|}_F^2$ and minimizing $||X|{|}_{\ast }$ for recovering a (nearly) low-rank matrix $X^0$, if $\alpha \ge 10||X^0|{|}_2$. Furthermore, we show that the linearized Bregman algorithm for minimizing $||x|{|}_1+1/(2\alpha )||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.

arXiv admin note: text overlap with arXiv:1207.5326 by other authors

References in corpus (3)

• Guaranteed Rank Minimization via Singular Value Projection
• Strongly Convex Programming for Exact Matrix Completion and Robust Principal Component Analysis
• Accelerated Linearized Bregman Method

Cited by in corpus (27)

• Sparse Recovery via Differential Inclusions
• On the Convergence of Decentralized Gradient Descent
• Gradient methods for convex minimization: better rates under weaker conditions
• Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm
• Linearized Bregman Iterations for Automatic Optical Fiber Fault Analysis
• EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization
• New Analysis of Linear Convergence of Gradient-type Methods via Unifying Error Bound Conditions
• On the Convergence of Asynchronous Parallel Iteration with Unbounded Delays
• On Convergence of the Alternating Projection Method for Matrix Completion and Sparse Recovery Problems
• SMART: The Stochastic Monotone Aggregated Root-Finding Algorithm
• Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties
• Sparse Sampling Kaczmarz-Motzkin Method with Linear Convergence
• Non-ergodic Convergence Analysis of Heavy-Ball Algorithms
• An Efficient Two-Stage Sparse Representation Method
• The restricted strong convexity revisited: Analysis of equivalence to error bound and quadratic growth
• Linear convergence of the Randomized Sparse Kaczmarz Method
• Guarantees of Augmented Trace Norm Models in Tensor Recovery
• The Minimizer of the Sum of Two Strongly Convex Functions
• Dual Smoothing and Level Set Techniques for Variational Matrix Decomposition
• A dual algorithm for a class of augmented convex models
• Proximal-Like Incremental Aggregated Gradient Method with Linear Convergence under Bregman Distance Growth Conditions
• Projected shrinkage algorithm for box-constrained L1-minimization
• Regularized Kaczmarz Algorithms for Tensor Recovery
• Mirror frameworks for relatively Lipschitz and monotone-like variational inequalities
• Robust Compressed Sensing Under Matrix Uncertainties
• Linear convergence of random dual coordinate incremental aggregated gradient methods
• A Nonconvex Nonsmooth Regularization Method for Compressed Sensing and Low-Rank Matrix Completion