Matlab codes for linearized Bregman algorithms

Zhimin Peng, Ming Yan, Wotao Yin, and Hui Zhang

Sparse signal recovery

The linearized Bregman algorithms return the solution to

$mathrm{minimize} |mathbf{x}|_1 ~mbox{subject to}~Amathbf{x}=mathbf{b}$

by solving the model

$mathop{mathrm{minimize}}_{mathbf{x}} |mathbf{x}|_1+frac{1}{2alpha}|mathbf{x}|_2^2quadmbox{subject to}~Amathbf{x}=mathbf{b}.$

with an appropriate alpha .

Choice of

Exact regularization problem: for any and mathbf{b} , there exists alpha_0>0 so that any alpha ge alpha_0 “equalizes” the two problems, namely, as if $frac{1}{2alpha}|mathbf{x}|_2^2$ does not exist. Proofs can be found in this paper and this paper.

alpha depends on the data, but a typical value is 1 to 10 times the estimate of $|mathbf{x}_{mbox{true}}|_infty$ . This choice is justified in this paper.

What if ?

If Amathbf{x}=mathbf{b} does not hold (as is noisy or is approximately sparse, or both), one can stop the algorithms when $|Amathbf{x}^k-mathbf{b}|_2approx|Amathbf{x}_{mbox{true}}-mathbf{b}|_2$ and obtain $mathbf{x}^k$ as a sparse solution. Like most other dual algorithms, the intermediate iterates $mathbf{x}^k$ are sparse.

Matlab codes and demos

fixed stepsize version (demo 1, demo 2);
line search version (demo 1, demo 2).
Nesterov acceleration version (demo 1, demo 2).
Nesterov acceleration with reset (demo 1, demo 2).
Comparisons: binary sparse test 1 test 2; Gaussian sparse test 1 test 2; Bernoulli matrix test 1 test 2; partial DCT matrix test 1 test 2

Low-rank matrix recovery / matrix completion

The linearized Bregman algorithms return the solution to

$mathrm{minimize} |mathbf{X}|_* ~mbox{subject to}~A(mathbf{X})=mathbf{b}$

by solving the model

$mathop{mathrm{minimize}}_{mathbf{X}} |mathbf{X}|_*+frac{1}{2alpha}|mathbf{X}|_F^2quadmbox{subject to}~A(mathbf{X})=mathbf{b},$

where |cdot|_* does the matrix nuclear-norm.

Choice of

A typical value is 1 to 10 times the estimate of $|mathbf{X}_{mbox{true}}|$ , the spectral norm of $mathbf{X}_{mbox{true}}$ . This choice is justified in this paper.

Matrix completion Matlab demos

Algorithms: fixed stepsize version, line search version, Nesterov acceleration with reset
Examples: easy, difficult 1, difficult 2