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

This paper studies the long-existing idea of adding a nice smooth function to “smooth” a nondifferentiable objective function in the context of sparse optimization, in particular, the minimization of \|x\|₁+1/2α\|x\|₂², where x is a vector, as well as the minimization of \|X\|_*+1/2α\|X\|F², where X is a matrix and \|X\|_* and \|X\|F are the nuclear and Frobenius norms of X, respectively. We show that they let sparse vectors and low-rank matrices be efficiently recovered. In particular, they enjoy exact and stable recovery guarantees similar to those known for the minimization of \|x\|₁ and \|X\|_* under the conditions on the sensing operator such as its null-space property, restricted isometry property (RIP), spherical section property, or “RIPless” property. To recover a (nearly) sparse vector x⁰, minimizing \|x\|₁+1/2α\|x\|²₂ returns (nearly) the same solution as minimizing \|x\|₁ whenever α≥ 10\|x⁰\|_∞. The same relation also holds between minimizing \|X\|_*+1/2α\|X\|F² and minimizing \|X\|_* for recovering a (nearly) low-rank matrix X⁰ if α≥ 10\|X⁰\|₂. Furthermore, we show that the linearized Bregman algorithm, as well as its two fast variants, for minimizing \|x\|₁+1/2α\|x\|₂² 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 sparse solution or any properties on A. To the best of our knowledge, this is the best known global convergence result for first-order sparse optimization algorithms.