A quadratically convergent algorithm for convex-set constrained signal recovery
A quadratically convergent algorithm for convex-set constrained signal recovery
复制标题
凸集约束信号恢复的二次收敛算法
DOI：
--
复制
发表时间：
1996
影响因子：
5.4
通讯作者：
K. Arun
中科院分区：
文献类型：
--
作者：
S. Dharanipragada;K. Arun
本文讨论了从线性测量中恢复被约束在凸集内的信号的问题。目前的标准是交替投影范例(POCS)，通常只有一阶收敛。提出了一种从线性测量和凸集约束条件下恢复信号的二次收敛迭代算法(牛顿算法)。利用牛顿算法得到了投影算子在凸集上的导数的存在性和构造性的一个新结果。新算法的一个有趣的特点是，每次迭代都需要解一个更简单的子空间约束重建问题。通过在每次牛顿迭代中使用共轭梯度算法，避免了矩阵求逆和存储，也得到了计算和存储效率高的算法版本。从计算的角度来看，该算法的每次迭代计算量与标准交替投影算法的每次迭代计算量相似。更快的收敛速度(与交替投影相比)使我们能够用更少的计算获得高分辨率重建。因此，该算法非常适合于图像恢复应用中通常出现的大规模问题。该算法在几个应用中得到了验证。
This paper addresses the problem of recovering a signal that is constrained to lie in a convex set, from linear measurements. The current standard is the alternating projections paradigm (POCS), which has only first-order convergence in general. We present a quadratically convergent iterative algorithm (Newton algorithm) for signal recovery from linear measurements and convex-set constraints. A new result on the existence and construction of the derivative of the projection operator onto a convex set is obtained, which is used in the Newton algorithm. An interesting feature of the new algorithm is that each iteration requires the solution of a simpler subspace-constrained reconstruction problem. A computation- and memory-efficient version of the algorithm is also obtained by using the conjugate-gradient algorithm within each Newton iteration to avoid matrix inversion and storage. From a computational point of view, the computation per iteration of this algorithm is similar to the computation per iteration of the standard alternating projections algorithm. The faster rate of convergence (compared to alternating projections) enables us to obtain a high-resolution reconstruction with fewer computations. The algorithm is thus well suited for large-scale problems that typically arise in image recovery applications. The algorithm is demonstrated in several applications.