A quadratically convergent algorithm for convex-set constrained signal recovery

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.