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

M. Lai and W. Yin

Published in SIAM Journal on Imaging Sciences

Technical report

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.

there exists a (data-dependent) such that as long as , 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;
to recover sparse and low-rank , given a certain RIP condition (or NSP, SSP, RIPless condtions), one can choose and and enjoy the stable recover and , respectively;
their Lagrange dual problems are unconstrained and continuously differentiable;
the Lagrange dual of the augmented 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 , for some , 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