Matlab codes for linearized Bregman algorithms

Wotao Yin

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 alpha

Exact regularization problem: for any A 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 Amathbf{x}not=mathbf{b}?

If Amathbf{x}=mathbf{b} does not hold (as mathbf{b} is noisy or mathbf{x} 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

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 alpha

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


« Back