The linearized Bregman algorithms return the solution to

by solving the model

with an appropriate .

Exact regularization problem: for any and , there exists so that any “equalizes” the two problems, namely, as if does not exist. Proofs can be found in this paper and this paper.

depends on the data, but a typical value is 1 to 10 times the estimate of . This choice is justified in this paper.

If does not hold (as is noisy or is approximately sparse, or both), one can stop the algorithms when and obtain as a sparse solution. Like most other dual algorithms, the intermediate iterates are sparse.

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

The linearized Bregman algorithms return the solution to

by solving the model

where does the matrix nuclear-norm.

A typical value is 1 to 10 times the estimate of , the spectral norm of . This choice is justified in this paper.

Algorithms: fixed stepsize version, line search version, Nesterov acceleration with reset

Examples: easy, difficult 1, difficult 2