Fast, Sample-Efficient Algorithms for Structured Phase Retrieval
We consider the problem of recovering a signal x * ∈ R n , from magnitude-only measurements, y i = | a i , x * | for i = {1, 2, . . . , m}. Also known as the phase retrieval problem, it is a fundamental challenge in nano-, bio-and astronomical imaging systems, and speech processing. The problem is ill-posed, and therefore additional assumptions on the signal and/or the measurements are necessary. In this paper, we first study the case where the underlying signal x * is s-sparse. We develop a novel recovery algorithm that we call Compressive Phase Retrieval with Alternating Minimization, or CoPRAM. Our algorithm is simple and can be obtained via a natural combination of the classical alternating minimization approach for phase retrieval, with the CoSaMP algorithm for sparse recovery. Despite its simplicity, we prove that our algorithm achieves a sample complexity of O s 2 log n with Gaussian samples, which matches the best known existing results. It also demonstrates linear convergence in theory and practice and requires no extra tuning parameters other than the signal sparsity level s. We then consider the case where the underlying signal x * arises from structured sparsity models. We specifically examine the case of block-sparse signals with uniform block size of b and block sparsity k = s/b. For this problem, we design a recovery algorithm that we call Block CoPRAM that further reduces the sample complexity to O (ks log n). For sufficiently large block lengths of b = Θ(s), this bound equates to O (s log n). To our knowledge, this constitutes the first end-toend linearly convergent family of algorithms for phase retrieval where the Gaussian sample complexity has a sub-quadratic dependence on the sparsity level of the signal.
The authors' rebuttal contains some points which should be explicitly included in a revised version if the paper is accepted.
-----------
The authors study the problem of compressive (or sparse) phase retrieval, in
which a sparse signal x\in\R^n is to be recovered from measurements abs(Ax),
where A is a design (measurement) matrix, and abs() takes the entry-wise
absolute value. The authors propose an iterative algorithm that applies CoSaMP
in each iteration, and prove convergence to the correct, unknown sparse vector x
with high probability, assuming that the number of measurements is at least
C*s*log(n/s), where s is the sparsity of x and n is the ambient dimension. 
The paper is well written and clear, and the result is novel as far as I can
tell. However, the problem under study is not adequately motivated. The authors
only consider real-valued signals throughout the paper, yet bring motivation
from real phase retrieval problems in science in which the signals are, without
exception, complex. The authors aim to continue the work in refs. [21,22] which
also considered only real-valued signals. Looking at those papers, I could find
no satisfying motivation to study the problem as formulated. 
The algorithm proposed is compared with those proposed in refs. [21,22]. 
According to Table 1, it enjoys the same sample complexity requirement and the
same running time (up to constants) as SPARTA [22] and TWF [21]. (While the
sample complexity requirement is proved in the paper - Theorem 4.2 - I could not
find a proof of the running time claimed in Table 1). As far as I could see, the only
improvements of the proposed algorithm over prior art is the empirical
performance (Section 6). 
In addition, the authors study a closely related problem, where the signal is
assumed to be block sparse, and develop a version of the algorithm adapted to
this problem.
As for the sparse (non-block) version, in my opinion the limited simulation
study offered by the authors is not sufficient to establish that the proposed
algorithm improves in any way over those of [21,22]. Without a careful empirical
study, or alternatively a formal results showing that the proposed algorithm
improves over state of the art, the merit of the proposed algorithm is not
sufficiently established. 
As for the block version, it seems that here the algorithm, which is
specifically tailored to the block version, improves over state of the art.
However, in my opinion the problem of recovery of *real* block-sparse signals
from absolute value of linear measurements is not sufficiently motivated. 
Other comments: 
The authors assume a Gaussian measurement matrix. The main results (Theorem 4.1,
Theorem 4.2, Theorem 5.2) must explicitly specify this assumption. As written
now, the reader may incorrectly infer that the Theorem makes no assumptions on
the measurement matrix.