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

M. Lai and W. Yin

Published in SIAM Journal on Imaging Sciences

Overview

The augmented ell_1 Lagrange dual problem and nuclear-norm models

min_x~ |x|_1+frac{1}{2alpha}|x|_2^2quadmbox{s.t.}~Ax=b,
min_X~ |X|_*+frac{1}{2alpha}|X|_F^2quadmbox{s.t.}~mathcal{A}X=b

have very interesting theoretical and numerical properties.

  1. there exists a (data-dependent) alpha_0 such that as long as alpha>alpha_0, the solutions to the above problems are also solutions to their original problems without frac{1}{2alpha}|x|_2^2 and frac{1}{2alpha}|X|_F^2, respectively;

  2. to recover sparse x_0 and low-rank X_0, given a certain RIP condition (or NSP, SSP, RIPless condtions), one can choose alpha_0ge 10|x_0|_infty and alpha_0ge 10|X_0| and enjoy the stable recover x_0 and X_0, respectively;

  3. their Lagrange dual problems are unconstrained and continuously differentiable;

  4. the Lagrange dual of the augmented ell_1 problem has a property that we call restricted strongly convex, which together with the gradient Lipschitz property enables gradient descent (and its accelerations) to converge at a linear rate O(1/c^k), for some c>1, in the global sense.

The paper also study their relaxed versions with |Ax-b|_2lesigma and |mathcal{A}X-b|_Flesigma, respectively.

Code

Matlab demos of different versions of linearized Bregman

Citation

M. Lai and W. Yin, Augmented l1 and nuclear-norm models with a globally linearly convergent algorithm, SIAM Journal on Imaging Sciences, 6(2), 1059-1091, 2013. Doi:10.1137/120863290.


« Back