A QUADRATICALLY CONVERGENT ALGORITHM FOR CONVEX-SET CONSTRAINED SIGNAL RECOVERY

This paper addresses the problem of recovering a signal that is constr ained to lie in a convex set, from linear measurements. The current st andard is the alternating projections paradigm (POCS), which has only first-order convergence in general. We present a quadratically converg ent iterative algorithm (Newton algorithm) for signal recovery from li near measurements and convex-set constraints. A new result on the exis tence and construction of the derivative of the projection operator on to a convex set is obtained, which is used in the Newton algorithm. An interesting feature of the new algorithm is that each iteration requi res the solution of a simpler subspace-constrained reconstruction prob lem. A computation- and memory-efficient version of the algorithm is a lso obtained by using the conjugate-gradient algorithm within each New ton iteration to avoid matrix inversion and storage. From a computatio nal point of view, the computation per iteration of this algorithm is similar to the computation per iteration of the standard alternating p rojections algorithm. The faster rate of convergence (compared to alte rnating projections) enables us to obtain a high-resolution reconstruc tion with fewer computations. The algorithm is thus well suited for la rge-scale problems that typically arise in image recovery applications . The algorithm is demonstrated in several applications.