Efficient Compressive Phase Retrieval with Constrained Sensing Vectors
We propose a robust and efficient 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 programs that are solved sequentially. In recent years, various methods are proposed for compressive phase retrieval, but they have suboptimal sample complexity or lack robustness 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 jointly sparse and low-rank matrix has remained elusive. Deviating from the models with generic measurements, 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 O(k log 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.
In this paper the authors propose a two stage approach to the compressive phase retrieval problem. The idea is that if the measurement matrix factorizes into the product of a Gaussian matrix and and RIP matrix one can use a convex program to recover the RIP matrix times the sparse signal and then use standard techniques to recover the sparse signal from such RIP measurements. The paper text is readable and the results are correct. However, my main concern is that this approach heavily relies on modeling assumptions of the measurement ensemble that do not correspond to a realistic model of interest.I only have one main comment. (The proofs seem correct to me):First sentence of the abstract: "We propose a new approach to the problem of compressive phase...", last sentence of the second paragraph, and first sentence of 1.2 "the main challenge in the CPR problem in its general formulation is to design an accurate estimator that has optimal sample complexity and computationally tractable"I disagree with this claim. If the paper is to be accepted I would recommend some caution about such statements and claims. Indeed the main challenge is to get to optimal sample and computational complexity. However, in this process you are not allowed to pick your algorithm based on your sensing mechanism! This is certainly not elusive. In particular if one can choose the measurement models there are already papers that do get to optimal sample complexity and this one would not be the first. e.g. see"Fast and Robust Compressive Phase Retrieval with Sparse-Graph Codes" Dong Yin, Kangwook Lee, Ramtin Pedarsani, and Kannan RamchandranLet me clarify what I mean. Imagine you get just generic Gaussian measurement vectors this approach simply can not work because the matrix does not factorize. For example, In a realistic setup you have a signal which is sparse in an over-complete basis and you wish to recover that signal from quadratic measurements of the order of sparsity (say from a few Gaussian or Fourier measurements). That is the overall measurement matrix w.r.t the sparse signal is a fat matrix times a fat matrix. Not a tall matrix multiplied by a fat matrix. So even if the RIP assumption holds on the over-complete dictionary it is still not a useful model. Simply put model (2) is unrealistic.The challenge is sparse phase retrieval is really can we come up with an algorithm that can handle sparsity o(k) e.g. an algorithm that works generically like for Gaussian measurements.