求解稀疏最小二乘问题的新型Bregman迭代正则化算法

A New Bregman Iterative Regularization Algorithm for Sparse Least Squares Problems

由于允许从少量数据中恢复原始图像或信号的压缩感知原理的引入,基于l1范数正则化的最优化方法近来越来越受到重视。利用最小二乘问题的一种等价形式和Bregman迭代方法的一些技巧,本文给出了已有A+线性Bregman迭代方法的一种推导过程。进一步结合不动点连续迭代方法和非满值最小二乘问题的等价形式,获得了一种求解带有约束的l1范数最小优化问题的新型算法,并给出了新型算法与A+线性Bregman迭代算法之间的联系,同时证明了新算法所获得的解是所求问题的一个最优解。新算法与已有A+算法类似,仅仅需要矩阵向量乘法和压缩算子的计算,从而使得新算法很容易实现,且运算速度明显快于已有算法。最后,通过数值实验表明,新方法对于稀疏信号的恢复问题与原方法相比具有速度快、可有效减少停滞现象等优点。

The class of t1 norm regularization problems has received much attention recently because of the introduction of ＂compressed sensing＂ which allows images and signals to be reconstructed from small amounts of data. With an equivalent form of least squares problem and some techniques of Bregman iterative methods, we give out a derivation of A＋ linear Breg- man iteration method that has already existed. Furthermore, combining with the continuous fixed-point iteration method and the new form of the non-surjective least square problem, a new method for solving the constrained l1 norm optimization prob- lem is obtained. Simultaneously, the relationship between the A＋ linear Bregman iteration and the new iterative method is given. The solution obtained by the new method is proved to be the optimal solution of the constrained l1 norm optimization problem that we considered. Similar to A＋ linear Bregman iteration method that has exists, the new method needs only matrix-vector operation and shrinkage operator that is easy to implement in our considered problems. Finally, numerical results show that, for sparse signal recovery problem, the new method is faster, efficient and simple than A＋ Bregman iterative methods that have been existed. At the same time, the new method reduced the stagnation of iterative procedure.