Linearized Bregman (LB) algorithm is known for its efficiency in solving the following problem

min s.t. , (1)

especially when the problem considered is of very large-scale. Recently, Yin has shown in [1] that the LB method is equivalent to a gradient descent algorithm applied to the Lagrangian dual of

min s.t. (2)

When is large, problem (2) can be regarded as equivalent to problem (1), and we can solve (2) in order to obtain the minimizer for (1). The Lagrangian dual of (2) assumes the form

min (3)

where

argmin

To be clear, we call the gradient descent algorithm applied to the Lagrangian dual (3) as the **Dual-Based LB Algorithm**, which is equivalent to the LB method as mentioned earlier.

In our paper published in IASTED-VIIP [2], we show that the Dual-Based LB Algorithm possesses a convergence rate of . Further, inspired by Beck and Teboulle [3], we propose a fast iteration scheme by carrying out FISTA type of iterations in the dual space (3), denoted as **Fast** **Dual-Based LB Algorithm**. We proved that the convergence rate of the fast method is . For readers interested to know more, please refer to [2] for algorithmic details and convergence proof.

Let’s apply the fast algorithm for compressive sensing of a synthetic image of size 512 by 512, which was produced by retaining its largest wavelet coefficients of an original image known as “man”. Thus is sparse in the wavelet domain as 97.33% of its wavelet coefficients are zeros. Next we adopted a sampling matrix which was a partial 2-D DCT matrix with randomly chosen rows of size with and .The CS reconstructed image with 20% of DCT sampled coefficients using Fast Dual-Based LB is illustrated as follows

The difference between the reconstructed image and the original image is hardly noticeable. It took the proposed fast algorithm 217 iterations (41.1 seconds) to converge to a relative contraint error . The relative reconstruction error measured by was found to be 0.0116.

By comparison, a total of 3168 iterations (601.6 seconds) were needed for the conventional LB algorithm to produced a reconstructed image of relative reconstruction error 0.0118.

As was demonstrated by this example, the fast algorithm is almost 15 times faster than the conventional method.

[1] W. Yin, “Analysis and generalizations of the linearized Bregman method,” *SIAM Journal on Imaging *Sciences, vol. 3, no. 4, pp. 856–877, 2010.

[2] J. Yan and W.-S. Lu, “Fast dual-based linearized Bregman algorithm for compressive sensing of digital images,” *Proceedings of the IASTED International Conference on Visualization, Imaging and Image Processing (VIIP *2012), pp. 43-49, Banff, Canada, July 2012.

[3] A. Beck and M. Teboulle, “A fast iterative shrinkage thresholding algorithm for linear inverse problems,” *SIAM Journal on Imaging Sciences, *vol. 2, no. 1, pp. 183–202, 2009.