Nuit Blanche: Efficient Compressive Phase Retrieval with Constrained Sensing Vectors

Monday, August 03, 2015

Efficient Compressive Phase Retrieval with Constrained Sensing Vectors

Interesting that a random gaussian projection helps in the decoupling of two regularization terms in a nonlinear compressive sensing problem.

Efficient Compressive Phase Retrieval with Constrained Sensing Vectors by Sohail Bahmani, Justin Romberg

We propose a new approach to the problem of compressive phase retrieval in which the goal is to reconstruct a sparse vector from the magnitude of a number of its linear measurements. The proposed framework relies on constrained sensing vectors and a two-stage reconstruction method that consists of two standard convex optimization programs that are solved sequentially.
Various methods for compressive phase retrieval have been proposed in recent years, but none have come with strong efficiency and computational complexity guarantees. The main obstacle has been that there is no straightforward convex relaxations for the type of structure in the target. Given a set of underdetermined measurements, there is a standard framework for recovering a sparse matrix, and a standard framework for recovering a low-rank matrix. However, a general, efficient method for recovering a matrix which is jointly sparse and low-rank has remained elusive.
In this paper, we show that if the sensing vectors are chosen at random from an incoherent subspace, then the low-rank and sparse structures of the target signal can be effectively decoupled. We show that a recovery algorithm that consists of a low-rank recovery stage followed by a sparse recovery stage will produce an accurate estimate of the target when the number of measurements is $\mathsf O(k\,\log\frac{d}{k})$, where $k$ and $d$ denote the sparsity level and the dimension of the input signal. We also evaluate the algorithm through numerical simulation.