A Primal Dual Active Set with Continuation Algorithm for the \ell^0-Regularized Optimization Problem
A Primal Dual Active Set with Continuation Algorithm for the \ell^0-Regularized Optimization Problem
复制标题
DOI：
--
复制
发表时间：
2014-03
期刊：
影响因子：
--
通讯作者：
Yuling Jiao;Bangti Jin;Xiliang Lu
中科院分区：
文献类型：
--
作者：
Yuling Jiao;Bangti Jin;Xiliang Lu
为了解决压缩感知中经常出现的正则化最小二乘问题，我们提出了一种带连续算法的原始对偶有效集。该算法将原始对偶有效集方法与正则化参数上的连续策略相结合。在每次内部迭代中，它首先从原始变量和对偶变量中识别活动集，然后通过求解定义在活动集上的(通常是小的)最小二乘问题来更新原始变量，从该最小二乘问题可以显式地更新对偶变量。在一定的感知矩阵条件下，即互不相干性或受限等距性质，以及噪声水平下，证明了算法的有限步全局收敛。给出了大量的数值算例，说明了算法的有效性和准确性，并进行了收敛分析。
We develop a primal dual active set with continuation algorithm for solving the \ell^0-regularized least-squares problem that frequently arises in compressed sensing. The algorithm couples the the primal dual active set method with a continuation strategy on the regularization parameter. At each inner iteration, it first identifies the active set from both primal and dual variables, and then updates the primal variable by solving a (typically small) least-squares problem defined on the active set, from which the dual variable can be updated explicitly. Under certain conditions on the sensing matrix, i.e., mutual incoherence property or restricted isometry property, and the noise level, the finite step global convergence of the algorithm is established. Extensive numerical examples are presented to illustrate the efficiency and accuracy of the algorithm and the convergence analysis.