Analysis and Generalizations of the Linearized Bregman Method
Analysis and Generalizations of the Linearized Bregman Method
复制标题
DOI：
10.1137/090760350
复制
发表时间：
2010-12
期刊：
影响因子：
--
通讯作者：
W. Yin
中科院分区：
文献类型：
--
作者：
W. Yin
分析并改进了求解基追踪及相关稀疏优化问题的线性化Bregman方法。分析表明，线性化Bregman方法具有精确正则化性质，即当其光滑参数$\alpha$大于一定值时，它收敛于基追踪问题的精确解.分析的基础上表明，线性化Bregman算法是等效的梯度下降适用于一定的对偶配方。这一结果促使推广的算法，使使用基于梯度的优化技术，如线搜索，Barzilai-Borwein，有限内存BFGS（L-BFGS），非线性共轭梯度，Nesterov的方法。在数值模拟中，两个建议的实现，一个使用Barzilai-Borwein步骤与非单调线搜索，另一个使用L-BFGS，给出了更准确的解决方案，在更短的时间比基本实现的线性化Bregman方法与所谓的踢技术。
This paper analyzes and improves the linearized Bregman method for solving the basis pursuit and related sparse optimization problems. The analysis shows that the linearized Bregman method has the exact regularization property; namely, it converges to an exact solution of the basis pursuit problem whenever its smooth parameter $\alpha$ is greater than a certain value. The analysis is based on showing that the linearized Bregman algorithm is equivalent to gradient descent applied to a certain dual formulation. This result motivates generalizations of the algorithm enabling the use of gradient-based optimization techniques such as line search, Barzilai-Borwein, limited memory BFGS (L-BFGS), nonlinear conjugate gradient, and Nesterov's methods. In the numerical simulations, the two proposed implementations, one using Barzilai-Borwein steps with nonmonotone line search and the other using L-BFGS, gave more accurate solutions in much shorter times than the basic implementation of the linearized Bregman method with a so-called kicking technique.