Linearized Bregman iterations for compressed sensing

By Jian-Feng Cai, Stanley J. Osher, Zuowei Shen. Mathematics of Computation, 2009

349 citations recorded by the source corpus.

Finding a solution of a linear equation Au = f with various minimization properties arises from many applications. One such application is compressed sensing, where an efficient and robust-to-noise algorithm to find a minimal l 1 norm solution is needed. This means that the algorithm should be tailored for large scale and completely dense matrices A, while Au and A T u can be computed by fast transforms and the solution we seek is sparse. Recently, a simple and fast algorithm based on linearized Bregman iteration was proposed in [28, 32] for this purpose. This paper is to analyze the convergence of linearized Bregman iterations and the minimization properties of their limit. Based on our analysis here, we derive also a new algorithm that is proven to be convergent with a rate. Furthermore, the new algorithm is simple and fast in approximating a minimal l 1 norm solution of Au = f as shown by numerical simulations. Hence, it can be used as another choice of an efficient tool in compressed sensing.

Subfields: Biomedical Engineering, Computational Mechanics, Signal Processing

View Paper: https://www.semanticscholar.org/paper/b32ff53f37ee442bfac2924351b61e832d3ba243

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Biomedical Engineering

In Computational Mechanics

In Signal Processing

Citations in the corpus

Real time robust L1 tracker using accelerated proximal gradient approach (2012, methodology): “In recent years, there have been great progresses on fast numerical methods for solving large-scale 1-norm related minimization problems arising in image science, such as Linearized Bregman iteration [4], Split Bregman method [8] etc.”
The Convex Geometry of Linear Inverse Problems (2010, methodology): “Such an approach corresponds to the classic method of multipliers [6] and has proven effective for solving problems regularized by the 1 norm and for total variation denoising [13, 75].”
A collaborative framework for 3D alignment and classification of heterogeneous subvolumes in cryo-electron tomography (2010, background): “ther Lipschitz continuous: k∇f(X1)− ∇f(X2)k ≤ LfkX1 −X2k, one may approximate f(X) locally as a quadratic function and solve Xk+1 = arg min X∈H Q(X,Yk) . = f(Yk)+h∇f(Yk),X −Yki+ Lf 2 kX −Ykk 2 +g(X), (8) which is assumed to be easy, to update the solution X. The convergence behavior of this iteratio”
The Split Bregman Method for L1-Regularized Problems (2009, methodology): “Bregman iteration has also been applied to solve the basis pursuit problem in [30, 5, 20], and was subsequently applied to medical imaging problems in [14].”
Blind motion deblurring from a single image using sparse approximation (2009, methodology): “Usually it takes only a few iterations for (16) to get a fair approximation to the solution of (14) ([6]), and the accuracy of the approximation is adequate during the iterations of Algorithm 1 until the last a few steps.”
NESTA: A Fast and Accurate First-Order Method for Sparse Recovery (2009, methodology): “e large systems of linear equations to compute the Newton steps. On the other hand, inspired by iterative thresholding ideas [24,30,20], we have now available a great number of rst-order methods, see [31,9,34,35] and the many earlier references therein, which may be faster but not necessarily accura”
Fixed point and Bregman iterative methods for matrix rank minimization (2009, methodology): “We present further directions for extending the approach proposed in [7; 21] for compressed sensing to the rank minimization problem and give conclusions in Section 8.”
A Singular Value Thresholding Algorithm for Matrix Completion (2008, methodology): “Uzawa’s algorithm is, in fact, a subgradient method applied to the dual problem, where each step moves the current iterate in the direction of the gradient or of a subgradient.”
Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization (2012, background): “We refer to [5, 6] for analogous discussions on the basis pursuit problem.”
Fast Convex Optimization Algorithms for Exact Recovery of a Corrupted Low-Rank Matrix (2009, background): “One striking example of this is the current popularity of iterative thresholding algorithms for 1 norm minimization problems arising in compressed sensing [22] [1] [23] [4].”
A Systematic Review of Compressive Sensing: Concepts, Implementations and Applications (2018, methodology): “Other improved versions of this algorithm are linearized Bregman algorithm [35], Split Bregman algorithm [36], etc.”
Split Bregman Methods and Frame Based Image Restoration (2009, methodology): “With algorithms (1.4) and (1.6), the synthesis based approach can be considered well developed.”
Signal and noise separation in prestack seismic data using velocity-dependent seislet transform (2015, background): “Iterations in equations 12 and 13 start with f0 1⁄4 0 and f̂0 1⁄4 Fd and are related to the linearized Bregman iteration (Cai et al., 2009), which converges to the solution of the constrained minimization problem: min f kfk1 s:t: Bf 1⁄4 d: (18)”
Coordinate descent optimization for l 1 minimization with application to compressed sensing; a greedy algorithm (2009, background): “When δ is large enough, its solution is the solution of (23), see [2, 33].”