Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors
Authors: Zhaoqiang Liu
Subhroshekhar Ghosh
Jonathan Scarlett
Venue: NeurIPS 2021 Poster (2021)
Keywords: Phase retrieval
generative models
sparsity
optimal sample complexity
spectral initialization

Abstract: Compressive phase retrieval is a popular variant of the standard compressive sensing problem in which the measurements only contain magnitude information. In this paper, motivated by recent advances in deep generative models, we provide recovery guarantees with near-optimal sample complexity for phase retrieval with generative priors. We first show that when using i.i.d. Gaussian measurements and an $L$-Lipschitz continuous generative model with bounded $k$-dimensional inputs, roughly $O(k \log L)$ samples suffice to guarantee that any signal minimizing an amplitude-based empirical loss function is close to the true signal. Attaining this sample complexity with a practical algorithm remains a difficult challenge, and finding a good initialization for gradient-based methods has been observed to pose a major bottleneck. To partially address this, we further show that roughly $O(k \log L)$ samples ensure sufficient closeness between the underlying signal and any {\em globally optimal} solution to an optimization problem designed for spectral initialization (though finding such a solution may still be challenging). We also adapt this result to sparse phase retrieval, and show that $O(s \log n)$ samples are sufficient for a similar guarantee when the underlying signal is $s$-sparse and $n$-dimensional, matching an information-theoretic lower bound. While these guarantees do not directly correspond to a practical algorithm, we propose a practical spectral initialization method motivated by our findings, and experimentally observe performance gains over various existing spectral initialization methods for sparse phase retrieval.

Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors
Zhaoqiang Liu National University of Singapore dcslizha@nus. edu.
Subhroshekhar Ghosh National University of Singapore subbrooorkk@gail.com
Jonathan Scarlett
National University of Singapore scarlett@comp. nus
nus aus.. sg
Abstract
Compressive phase retrieval is popular variant of the standard compressive sensing problem in which the measurements only contain magnitude information. In this paper, motivated by recent advances in deep generative models, we provide recovery guarantees with near-optimal sample complexity for phase retrieval with generative priors. We first show that when using i.i.d. Gaussian measurements and I.-Lipschitz continuous generative model with bounded k-dimensional inputs, roughly Okk log L) samples suffice to guarantee that any signal minimizing an amplitude-based empirical loss function is close to the true signal. Attaining this sample complexity with practical algorithm remains a difficult challenge, and finding good initialization for gradient-baser methods has been observed to pose a major bottleneck. To partially address this, we further show that roughly O(k log L) samples ensure sufficient closeness between the underlying signal and any globally optimal solution to optimization problem designed for spectral initialization (though finding such a solution may still be challenging). We also adapt this result to sparse phase retrieval, and show that (s log n) samples sufficient for similar guarantee when the underlying signal is s-sparse and n--iimnnsionl,, matching wwfformatinnthhorrree
lower bound. While these guarantees do not directly correspond to practical algorithm, we propose a practical spectral initialization method motivated by our findings. and experimentally observe performance gains over various existing spectral initialization methods for sparse phase retrieval.
Introduction
In this paper, we consider the (real-valued) phase retrieval problem, which aims to recover a signal R from noisy magnitude-only measurements:
y/4 (a., x)] + 7b: 1,2,,...
where a, E R" is the i-th sensing vector, and represents additive noise. This problem arises naturally in areas such diffraction imaging. X-ray crystallography, microscopy, optics and astron- omy [8], where it is often difficult or even impossible to observe the linear measurements directly, and one can only record the magnitudes or intensities (squared magnitudes).
In many real applications, to reduce the required number of measurements, it is of interest to exploit structure in the signal being estimated. In partieular, for applications related to signal processing and imaging, it is well-known that the underlying signal typically admits a sparse or approximately sparse
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

representation in some known basis 44]. Motivated by this, and considering the popularity of the standard compressive sensing (CS) problem [6]. the sparse phase retrieval problem has attracted significant research interest.
Moreover, inspired by the successful applications of deep generative models in many fields [5]. recently a new perspective of CS has emerged, for which the sparsity assumption is replaced by generative model assumption. That instead of assuming sparsity, the signal is assumed be close to the range of a generative model [5]. In addition to the theoretical developments in [5], the authors also provide impressive numerical results showing that for some imaging applications, using generative priors can significantly reduce the required number of measurements (e.g., by a factor of 5 to 10) for
recovering the signal up to a given accuracy. uollow-up works of [5] include [58] 22 45 just to name few.
67 12 29
In this paper, we focus on providing recovery guarantees with near-optimal sample complexity bounds (e.g., optimal up to constant factors) for the compressive phase retrieval problem, considering both sparse and generative priors.
1.1 Related Work
In this subsection, we provide a summary of some relevant works, which can roughly be divided into (i) the general phase retrieval problem with no structural assumptions the signal, (ii) sparse phase retrieval, and (iii) phase retrieval with generative models.
General phase retrieval: A wide range of approaches have been designed to solve the phase retrieval problem. Error-reduction approaches [18] [4] work well in practice, but they lack provable guarantees. Convex methods such PhaseLift [9] and PhaseCut [62] lift the phase retrieval problem to higher dimension, and typically suffer from high computation cost. Convex relaxations that operate in the natural domain of the signal are proposed in []. However, these convex relaxation based methods are not empirically competitive against widely-used non-convex methods.
Following the seminal work of Netrapalli et al. [42), several works have studied theoretically- guaranteed non-convex optimization algorithms for phase retrieval [8
10
63 72). These algorithms
start from spectral initialization method, and then use an iterative algorithm (e.g., alternating minimization or gradient descent) to further decrease the approximation error. For the general phase retrieval problem, the optimal sample complexity of O(n) can be achieved by certain non-convex methods [10 63 722. Interestingly, optimal (up to a logarithmic factor) sample complexity guarantees It is worth mentioning that 8 10 and trust-region methods (55]
have also been provided in the case of random initialization [55] I1.
some variants of the classic Wirtinger Flow (WF) algorithm consider squared measurements:
y x) Ei, i 1,2...., m,
(2)
and minimize the intensity based empirical loss function:
fr(w) = 2 y |2
(3)
where A E R is the sensing matrix with its i-th row being af and |. is applied element-wise. Nonetheless, numerical results suggest that algorithms minimizing the amplitude based empirical risk (with the measurement model (
f(w) = ly
Aw
usually more efficient in computation 663
72 54 Based this, we focus on the measurement
model I and the associated loss function
Sparse phase retrieval: A variety of algorithms have been devised for sparse phase retrieval 44
533 50). In particular, there exist various non-convex optimization based algorithms, including thresholded//roojectee WF 77 [54], sparse truncated amplitude flow [64], compressive phase retrieval with alternating minimization (28). and sparse phase retrieval by hard iterative pursuit (6). All of these approaches are analyzed under the assumption of using sensing matrix with i.i.d. Gaussian entries. addition, similar non-convex methods for the general phase retrieval problem, all of these approaches start with spectral initialization step, and then an iterative algorithm to refine

---

the initial vector. More specifically, in the initialization step, these approaches try to accurately estimate the support of the underlying signal.
Unlike the general phase retrieval setting in which optimal sample complexity guarantees are provided for some practical algorithms, for non-convex methods of sparse phase retrieval, the typical sample complexity requirement is O(s² logn2. where s is the spansity level. This does not match the
information theoretic lower bound 49 57| the bottleneck comes from the accurate estimation of
the support set [64] 54 288 Improved guarantees are also available in the noiseless setting under
more restrictive assumptions on the magnitudes of the non-zero entries [68]. In addition, for sparse phase retrieval, recovery guarantees with respect to globally optimal solutions of both the intensity and amplitude based loss functions have been provided in [13] 26 [4 [3 69], achieving the optimal sample complexity (ss log v.). However, designing a computationally efficient algorithm achieving the optimal sample complexity for s-sparse vectors remains an important open problem.
Phase retrieval with generative models: Phase retrieval using generative models has been studied in [20 [25] (2 [52 666 [1. Extensive numerical experiments for phase retrieval with generative models, as well as both Gaussian and coded diffraction pattern measurements, have been presented in [52]. Algorithms proposed in both works [20 (52) minimize the objective function directly over the latent variable z E IK* using gradient descent, where A is the latent dimension. The corresponding objective function is highly non-convex, and performing gradient descent directly over limits the explorable solution space, which may lead to getting stuck in local minima.
We highlight two particularly relevant works in more detail. To guarantee favorable global geometry for gradient methods, the authors of (20) assume a ReLU neural network generative model with i.i.d. zero-mean Gaussian weights and offsets. In addition, the neural network needs to be sufficiently expansive such that n; 2 Q(; log ni;-)). ), where n, represents the number of neurons in the i-th layer. Under such conditions, sample complexity Okdd log n) is obtained, where is the number of layers. In another related work studying an approximate message passing algorithm, the authors of I maintain i.i.d. Gaussian weights but slightly relax to general activation functions (not only ReLU) and n, 2 (m) Under these conditions, the nigh-dimensional regime is studied (n, m. k + co with m/n kept fixed), and an asymptotic analysis is given (not yet established as fully rigorous). We also note that (I] focuses on the case that z ~ P2 for some separable Pz. Both [ and (20) focus on the noiseless case, though states that the extension to noisy phase retrieval is possible.
Recovery guarantees for non-convex optimization algorithms for phase retrieval with pre-trained ReLU neural network priors and untrained neural network priors have been provided in [2 27).
with assumptions of noiseless measurements and the existence of a good initial vector. Recovery guarantees for phase retrieval with generative models can also be found in (66]. within more general setting of using differentiable but unknown link functions. The weaker assumption of an unknown link function comes a price; namely, it is an open problem to handle signals with representation error [47]. Moreover, the assumption of diffcrentiability makes it is not directly applicable to the measurement model ( and the loss function considered in [66] different from both (3) and 4 which are widely adopted for phase retrieval.
1.2 Contributions
We show that for compressive phase retrieval with i.i.d. Gaussian measurements, when the signal is close to the range of an L-Lipschitz continuous generative model with bounded k- dimensional inputs, roughly O(k log L) samples suffice for ensuring the closeness between the signal and any vector minimizing the amplitude-basce empirical loss function (4)
To address the sample complexity barrier posed by spectral initialization, we propose a relevant optimization problem, and show that roughly O(k log L.) samples sufficient guarantee that any globally optimal solution of the optimization problem is close to the true signal. This suggests the plausibility of practical spectral initialization algorithms that are able to find such a global optimum, though we do not attempt to provide one that can provably do so.
We adapt our analysis to the case of sparse phase retrieval, and show that roughly O(s log m) samples suffice for a similar recovery guarantee where 8 the sparsity level and n is the ambient dimension. This matches the information-theerctie lower bound up to constant factors
3

---

for broad signal-to- to-noose ratios, and up to logarithmic factor in general: see for example 7 Theorem 3.2] and [34 Section 6.1]).
Motivated by our theoretical findings for sparse phase retrieval, propose spectral initializa- tion method based on sparse principal component analysis. We verify on synthetic experiments that our initialization method significantly outperforms several popular spectral initialization methods of sparse phase retrieval (in the sense of relative error). This further corroborates the optimal sample complexity guarantee in our theory.
1.3 Notation
We use upper and lower case boldface letters to denote matrices and vectors respectively. We write
[N] = 21, ..... N for a positive integer N. We define the bn-ball (r) == (z E R |2z|2 S r).
and the unit sphere Sn-1 {x E R || 11. We use G to denote an L-Lipschitz continuous generative model from B to IR.. For a set B C (r), we write G(B) = [G(z)
B}. The
i.dd sensing matrix A E m assumed to have i.i.d. standard normal entries, i.e., Oij ~ (O 1). For any IR"" we use T
___ denote the corresponding normalized vector. The support (set)
of a vector is the index set of its non-zero entries. For any X E R=xx and any index set I S [m]. X, denotes the [ n sub-matrix of X that only keeps the rows indexed by We use ||X| 2- to denote the spectral norm of a matrix X. For any positive integer N, we use IN to denote the identity matrix in N We use the generic notations C and C" to denote large positive constants, and we use and e' to denote small positive constants; their values may differ from line to line.
2 Amplitude-Based Loss Minimization for Generative Priors
In this section, provide recovery guarantees with respect to optimal solutions of the amplitude based loss function (4) for phase retrieval with generative models. We let the generative model G (x (r) T be any T--Lipschitz continuous function, and we suppose that the underlying signal x is close to (but does not need to lie in) the range of G. We are interested in the case & n (i.e., relatively small latent dimension). The sensing matrix A is assumed to have i.i.d. standard normal entries. Let q E Range(G) G) minimize (4) to within additive T > 0 of the optimum, i.c.,
lyy
Aqqll 1 min wERange(G)
Ily AAw
(5)
and define p E Range(G G) be the point that is closest to the signal x, i.e.,
p = arg
min (GR
||x w/
(6)
With the above settings in place, we present the following theorem, proved in Appendix B
Theorem 1. Consider the observation model ( with i.i.d. Gaussian measurements, and p,
satisfying 5 66 with parameter т. Then, for any 8 > we have that if m 12(k log Lr with
probability e (mmm, it holds that
min x x112. llq +x4+x122+ s O (
000011111100 11p-x12
mlla VF + +6).
(7)
vm
Since we assume that x is close to the range of G. the representation error ||p x||2 is small (compared ||x||2)) The optimization error also ideally small. In addition, is common to assume that ||لح| v/m < c||x||2 (e.g., see 72)). where e > is also small. A typical d-layer neural network generative model has poly(n)-bounded weights in each layer, and thus its Lipschitz constant is T== O(d) (5) Then, the values of and ō can be as extreme
((d) and 8 ςotay without affecting the final scaling. In this case, Theorem reveals that roughly ( log L) samples suffice to guarantee that any optimal solution of the amplitude-bet based loss function 4 close to the true signal (up to unavoidable possible global sign flip). By the analysis of Information-theoree lower bounds in 31 37 this scaling cannot be improved without further assumptions.
'erre and subsequently, all 2(()) statements assumed have large enough implied constant.

---

3 Spectral Initializations with Generative Priors
In Theorem we provided recovery guarantees with respect to optimal solutions of the amplitude based loss function. However, it is not clear whether such guarantee is achievable by practical algorithms.
A notable recent work is [25], showing that for depth-d, width-w ReLU neural network, roughly Okd log w) samples suffice for their alternating phase projected gradient descent (APPGD) ap- proach to obtain accurate estimate of the signal, as long as there exists proper initial vector x()), in the sense that min [||x x ||: x + x [[a] S c| c||x||2 for some small positive constant c. However, as we know from sparse phase retrieval, designing a practical algorithm to find a proper initial vector with near-optimal sample complexity can be more difficult than designing the subsequent iterative algorithm that refines the initial guess, and this still remains as an open problem. is also important to note that [25] assumes accurate projections onto the range of the generative model, but this is not guaranteed in practice, due to the use of approximations [5] 48).
Existing initialization methods for sparse phase retrieval typically first estimate the support of the sparse signal, and then perform a power method on sub-matric corresponding the estimated support set to calculate an initial vector. Without extra assumptions beyond sparsity, these methods have a suboptimal sample complexity of O(s² log n). For phase retrieval with generative models, the situation is even worse there is no theoretically-guaanttee address this gap, we provide recovery guarantees for a spectral initialization method of phase retrieval with generative models. We emphasize that our guarantees only concern the global optima of suitably-defined optimization problem; see (14) below. Similarly to [25], the caveat remains that practical solutions may fail to find such optima (e.g., due to inexact projections).
initialization method at all. To
We assume that x in the range of G (r) + R" (again assumed be L-Liscchitz continuous), and we assume that the noise terms 122 ................................ 7m are bounded as follows:
| < coll col|x||22
(8)
where co > 0 is sufficiently small constant. This assumption states that the signal to noise ratio (SNR) is sufficiently large, and has also been made in relevant existing works (see, e.g.. 722 Theorem 3)). Moreover, we assume that
|/ S c|||1|2,
(9)
where e₁ > is also sufficiently small constant. This assumption is satisfied, for example, when (assuming (8).
|| o 1
(10)
vm
ie., when none of the noise entries are unusually large. Again, similar assumptions have been made in existing works such [TO Theorem 2], and [1] Theorem 2
Let be defined as
X
π 2
Σ
91-
(11)
m
Using sub-Gaussin concentration [60] Proposition 5.10], A close to ||x||2 with high probability
given enough samples. In the following, we focus on estimating the normalized signal vector
X = x | For this purpose, similar to the idea in 335 we consider normalized generative model
G D - 5n-1, where D = {z E Bh (r) [|G(z)]l2 > Rmin J for some Rmin > S denotes
G(2) the unit sphere in RR,, and G(z) |G>>) Then, & is Í--Lipschitz continuous with L R
"This matches the O(k log L) scaling upon substituting L (w=)) for ReLU networks S
*When 17 is Gaussian with 1 ~ (0 o o'm.... (10) is not guaranteed, but any "truncated Gaussian" does satisfy (10) In addition. to circumvent this issue under Gaussian noise. we may instead assume that a /log m < ||x|22 in (and remove the assumption in (9). We also note that [10 71. the authors consider intensity based measurement model, and accordingly, the corresponding assumption is for Izlles instead of for Inlls.
TXx la * As discussed in 35]. the dependence on Rmin the sample complexity is very mild. Under the typical
Tx]];
scaling n ((d) for d-layer neural network, the scaling laws remain unchanged even with Rmin ,,oaay
5

---

In the following, we adopt an idea from [72 of considering an empirical matrix with truncation operation. We note that [72] only considered doing so for general phase retrieval; we are not aware of any work doing so for constrained settings (e.g.. with sparse or generative priors), and we found that handling such settings required substantial additional effort. more detail, we consider the following matrix defined with truncation operation (see Remark Femark2bbloov below for discussion comparing to the non-truncated counterpart):
Σ
T a, pissuesuAh
(12)
where 1, are positive constants satisfying 1 < < < u, and À is given in 11 Note that for the noiseless case with y/ = Ka,,, x)1, in accordance with the above-mentioned closeness between À and ||x||2, 2, it is useful to consider the following expectation:
1
:=
E
ya 1 ((ll = |xx12((70 + Boxxx")
(13)
where for g (0, 1), we define To := E ((<lo and 30 := 1 [<<<ls)<< 7o (cf.
Lemma 8 in Appendix
Based on the observation that X is leading eigenvector of J and the
assumption x E Range G), we consider using the following optimization problem to find an that
approximates X:
& == arg max WEG(D)
W Vw.
(14)
In addition, in order to take the norm of x into account, we set the the initial vector x (()) as
(0) Ax.
(15)
We show that roughly Ol log L) samples suffice for ensuring the closeness between x and (up to global signal flip). Formally, we have the following.
Theorem 2. Consider the model with i..dd Gaussian measurements and noise satisfying (8
and let & be as defined in (14). Suppose that & E G(D) and u > 1 > 1 + C1, where C1 2
?
x
appears in 9 Given a sufficiently small positive constant cf when m = S2(k logglo(((nn Lnr)), we have with probability 1 e -Q(m)) that
min 1 - &1|2, || + x||2] < 0.9c.
(16)
In addition, we have with probability 1 e- (((m)) that x (0) Xλ satisfies
min (0) x||2,11x(0) x||2} } < c||x||2-
(17)
The proof is given in Appendix C Using well-established chaining arguments as those in 5 35 36 the sample complexity 2(k log(Tar)) can be reduced to 22(k log(Lr)) However, since for a typical
d-layer neural network, we have the Lipschitz constant L = ((d) (and thus L and r can also be of order n ((d)) [5]. such a reduction is typically of minor importance.
4 Sparse Phase Retrieval
The proof of Theorem relies on the fact that x lies in Range(G) C S"-1, with the d-covering number being upper bounded by (4r)* Letting Σς be the of all s-sparse unit vectors in R", we
know that the 5-covering number of ΣΦ is upper bounded by (c) < (sm) 3 Based on this observation, we can readily adapt the proof of Theorem 2 to obtain the following theorem.
*This weaker than the assumption that ||x||2 > Rmin made (35]. Moreover, even ||x||| S Rmin. the condition G(D) may be satisfied (e.g., when G is ReLU neural network generative model with offsets, then the range of G becomes cone, and 0 < [xx|a < Amin. we can choose a sufficiently large C' such that C||x||22 > Renin, with Cx Range(G)).
"Note that the smaller is taken to be here, the smaller the constant needs to be the assumption 8

---

Theorem 3. Consider the model ① with ii.d. Gaussian measurements and noise satisfying 8 and suppose that x E IR" s-sparse. Let X be defined as (TI). Suppose that u
C₁
||]]| where 01 2 |xx|a
appears in and V is defined in 12). b. Let x be defined as
& = arg DIXX W Vw. WEER
(18)
Then, when m (tss log n)), we have with probability 1 -2(m) that
min 8||2, || + x||2] 0.9c,
(19)
where C > is a sufficiently small constant. In addition, we have with probability 1 1- -(m) that (())= = X& satisfies
minf 1/12211x<00 + xx|l2} < c||x||2--
(20)
Implications regarding SPCA and support recovery: We note that 18 essentially a problem of sparse principal component analysis (SPCA) [73 3 sparse phase retrieval typically start from estimating the support of x. with an accurate estimate of the support requiring suboptimal O(s² log n) sample complexity 17 64 [28]. This serves as the major bottleneck of the sample complexity upper bound of the whole procedure (i.e., the initialization step and the subsequent iterative step). and it is unknown whether there is a practical and sample-optimal approach for estimating the support. fact, to our knowledge, even the following question has not been answered previously:
Existing spectral initialization methods for
Key question: Does there exist any spectral-based method (computationally efficient or otherwise) attaining accurate initial vector with near-optimal sample complexity?
We provide positive answer this question, showing that O(s log samples suffice ensure that any optimal solution of the SPCA problem (18) is close to the underlying (normalized) signal.
Motivated by the strong sample complexity guarantee provided in Theorem 3 we propose a spectral initialization method for sparse phase retrieval as described Algorithm
particular, after
calculating V from A and y. we algorithmss for SPCA solve (18). We observe via numer- ical experiments in Section 5 that our initialization method outperforms several popular spectral initialization methods used for sparse phase retrieval.
Remark 1. In various works on SPCA, it has been shown that there exists statistical-compaatiine gap for achieving consistency and optimal convergence rates uniformly over a parameter space e.g., see 14 65 Z1). However, the models therein are all different from ours (e.g., the spiked covariance model (77), so it is unclear to what extent we should expect similar computational difficulties.
Remark 2. The truncation function 1 (IX) in (12 plays an important role our analysis. Specifically, it allows us to apply sub-exponential concentration bounds to certain quantities of interest, where the non- truncatedd version would involve heavier-tailed random variables (e.g., sub- Weibull of order a < 1 [21] Theorem 3.1]) We believe that this distinction could be even more important when seeking uniform recovery guarantees, though we do not do so this work. In Section we present numerical results for applying SPCA to the non con-truncated weighted empirical matrix
1 m
m Σ ya
(21)
We will see our experiments that the method corresponding to the truncated empirical matrix V outperforms the method corresponding to the non-truncated empirical matrix V. although the expectations of these two matrices have a very similar structure. Thus, we believe that truncation may potentially help in overcoming the computational challenges discussed above.
We note that 43 56 consider solving sparse phase retrieval via practical SPCA methods, in more general setting considering an unknown link function. They consider weighted empirical covariance matrix with no truncation, and the derived sample complexity has quadratic dependence on s.
7

---

Algorithm 1 A spectral initialization method for sparse phase retrieval based on SPCA (PRI-SPCA)
Input: A, V,L.u
Output: An initial vector (0)
1) Calculate À from (II) and then calculate V from
2) Use an SPCA algorithm to compute & according to 18
3) Letx = AX.
5 Numerical Experiments
In this section, we perform synthetic experiments to complement our theoretical results. We focus only on the sparse setting, in part because numerous existing algorithms are known for sparse priors but not for generative priors. Having said this, generative priors come with their own unique practical challenges (c.g., approximate projection methods), and we believe that their empirical study and associated practical variations would also be of significant interest for future work.
We compare our method (PRI-SPCA; see Algorithm [ with spectral initialization methods used in several popular algorithms for sparse phase retrieval: Thresholded Wirtinger flow (ThWF) [7]. sparse truncated amplitude flow (SPARTA) (64), and compressive phase retrieval with alternating minimization (CoPRAM) (28 We also compare with the approach of solving SPCA problem with
respect to V (ef. (2I)). which is non-truncated version of V. The corresponding method is termed
PRI-SPCA-PE NT, with 'NT' standing for no truncation. For PRI SPCA, we set = and u = 5, as
previously suggested in [72).
In our experiments, we present the numerical results using the generalized Rayleigh quotient iteration (GRQI) method (33. but we observed that other popular SPCA methods such as the truncated power method (TPower) [70] give similar averaged relative errors [
Various algorithms have been developed tackle the SPCA problem, see, e.g..
For GRQI, we set the deflation parameter to be 0.2, and the total number of iterations to be 100. Since the sparsity level & typically assumed to be known priori for SPARTA and CoPRAM (ThWF assumes the knowledge of parameter that plays the similar role as s), for GRQI, we set the parameter about the maximum number of non-zero indices Note that the time complexity of each iteration of GRQI is O(ns + s²). which scales mildly compared to the subsequent Os log n) time complexity of the iterative methods used in the three approaches (for ThWF, the corresponding time complexity is O l)g.). See [28 Table IJ). The number power method steps used in all the methods is fixed to be 100.
The authors of (33 suggest using the column of maximal norm as starting point of GRQI. Because this policy has time complexity of O( we instead choose the column corresponding to the largest diagonal entry as the starting point. Due to the structure of V (ef. (13), this modified strategy very similar to the suggested policy, but with a smaller time complexity requirement. For fair comparison, all power methods used in ThWF, SPARTA, and CoPRAM are similarly initialized. For the initialization method used in ThWF, we set the tuning parameter as a = 0.1, as suggested in [7]. Similarly, we set [Z] [ for the initialization method of SPARTA.
The support of the signal vector uniformly random, and the non-zero entries are generated from i.i.d. standard normal distributions. The noise vector is generated from the distribution (O, a ( where 0 represents the noise level. The initial relative error is defined as
min [|x x0)) ||x + x()) 12)
(22)
||x||2
where (0) is an initial vector produced by each of the above mentioned initialization methods. The reported relative error is averaged over 50 random trials, and error bars indicate a single standard deviation over these trials. All numerical experiments are conducted using MATLAB R2014b on machine with an Intel Core i5 CPU at 1.8 GHz and 8GB RAM.
We the MATLAB package shared by the authors of (28 at luttps::/githiii model- model-copram The package not only contains the codes for CoPRAM, but also for ThwP SPARTA. "Using TPower also results in small relative error for our PRI SPCA method, but in general, we found it to be less stable than GRQI in the absence of a careful design of its starting point.
coom/GauriJane Gaggtaat
8

---

1. Sample size effect: In our first experiment, similarly to [4], we consider noiseless measure- ments, and we fix the signal dimension as 1000. We consider equaling both 10 and 20. The number of measurements m takes values in {100, 200,, 3000). From Figure | we observe that our PRI-SPCA method almost always achieves the smallest initial relative error, thus outperforming all other methods, including the PRI-SPCA-NT method, which uses the non-truncated empirical matrix V.
2. Sparsity effect: We consider noiseless measurements and fix 1000, and set m = 1000 or 2000, and vary s in {5, 10..... 50}. We observe from Figure 2 our PRI-SPCA method also gives the best empirical performance.
that for this experiment,
3. Noise effect: To demonstrate that PRI-SPCA also performs well in the noisy case, we vary in {0.1, ......... 1}. . In addition, similarly to [44,, we fix n 1000, m 3000, and consider equaling both 10 and 20. For this experiment, similarly to that in (28), we do not compare with ThWF, it uses quadratic measurements. From Figure 3 we observe that PRI-SPCA outperforms SPARTA and CoPRAM, and it is better than PRI-SPCA-NT at low noise levels.
In Appendix E we additionally compare with other initialization methods in terms of the effectiveness when combining with the subsequent iterative algorithm of CoPRAM. In particular, relative error and empirical success rate the noiseless case, whereas for the noisy case, we compare the relative error when using approximately the same running time. We observe that for most cases, our PRI-SPCA method is superior to all other methods we compare with. This again suggests that PRI-SPCA can serve as good initialization method in practice.
compare the
Conclusion and Future Work
We have provided near-optimal recovery guarantee for amplitude-based loss minimization for phase retrieval with generative priors. In addition, motivated by the bottleneck of the spectral initialization for compressive phase retrieval, we have provided near-optimal recovery guarantees with respect to the optimal solutions of optimization problems designed for spectral initialization. An immediate future research direction is to design provably sample-optimal and computationally efficient spectral initialization methods that build on our theoretical results. In addition, extensions to complex-valued 332 46 would be of significant interest.
phase retrieval
Acknowledgment.. This work supported by the Singapore National Research Foundation (NRF) under grant R-252-000-A74-288 and the Singapore Ministry of Education (MoE) under grants R- R-146-000-250-133 and R- R-146-000-312-111 14.

---

1.4
COPRAM PRI-SPCA PRI-SPCA-NT THWE SPARTA
PRI-SPCA PRCA-CTN
1.2
1.2
THWF SPARTA
Initial relative error
0.8
0.8
0.6
0.4
0.4
0.2
500
1000
1500
2000
2500
3000
500
1000
1500
2000
2500
3000
No. of measurements m;;
No. messurements mi)
Figure 1: Average relative error number of measurements with 10 (Left), 20 (Right).
1.4
1.2
Initial relative erro
0.8
0.6
CaPRAM
0.4
PRI-SPCA PRI PPCA-CA-NTT THWF SPARTA
COPRAM
PRI-SPCA PRI-SPCA-NT TRWE SPARTA
0.20
20
30
50
10
20
30
50
Sparisty level
1000
Sparisty level
2000
Figure Average relative error vs. sparsity level s with m = 1000 (Left), m 2000 (Right).
1.1
CaPRAM
CaPRAM
0.9
PRI-SPCA PRI-SPCANNT
PRI-SPCA
PRI-SPCA-NT SPARTA
0.8
SPARTA
Initial relative error
0.7
0.6
0.7
0.5
0.6
0.4
0.5
0.3
0.2
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
Noise level a
10
Noise level d; = 20
Figure Average relative enror vs. noise level with (Left), 20 (Right).
10

---

References
[1] B. Aubin, B. Loureiro, A. Baker et al., "Exact asymptotics for phase retrieval and compressed sensing with random generative priors." in Math. Sci. Mach. Learn. (MSML). PMLR, 2020, pp. 55-73.
[2] S. Bahmani and J. Romberg, "Phase retrieval meets statistical learning theory: A flexible convex relaxation," in Int. Conf. Artif. Intell. Stat. (AISTATS). PMLR, 2017, pp. 252-260.
[3] R. Baraniuk, M. Davenport, R. Vore, and M. Wakin, "A simple proof of the restricted isometry property for random matrices," Constr: Approx., vol. 28, no. 3, pp. 253-263, 2008.
[4] Q. Berthet and P. Rigollet, "Complexity theoretic lower bounds for sparse principal component detection," in Conf. Learn. Theory (COLT). PMLR, 2013, pp. 1046-1066.
[5] A. Bora, A. Jalal, E. Price, and A. G. Dimakis, "Compressed sensing using generative models," in Int. Conf. Mach. Learn. (ICML), 2017, pp. 537-546.
[6] J.-F. Cai, J. Li, X. Lu, and J. You, "Sparse signal recovery from phaseless measurements via hard thresholding pursuit," hutps://arriv.org/////0000... 08777, 2020.
[7] T. 'T. Cai, X. Li, Z. Ma et al., "Optimal rates of convergence for noisy sparse phase retrieval via thresholded Wirtinger flow," Ann. Stat., vol. 44, no. 5. pp. 2221-2251, 2016.
[8] E. J. Candès, X. Li, and M. Soltanolkotabi, "Phase retrieval via Wirtinger flow: Theory and algorithms," IEEE Trans. Inf. Theory, vol. 61, no. 4, pp. 1985-2007, 2015.
[9] E. J. Candès, T. Strohmer, and V. Voroninski, "Phasel.ift Exact and stable signal recovery from magnitude measurements via convex programming." Comm. Pure Appl. Math., vol. 66, no. 8, pp. 1241-1274, 2013.
[10] Y. Chen and F. J. Candès, "Solving random quadratic systems of equations is nearly as easy as solving linear systems," Comm. Pure Appl. Math., vol. 70, no. 5, pp. 822-883, 2017.
[11] Y. Chen, Y. Chi, J. Fan, and C. Ma, "Gradient descent with random initialization: Fast global convergence for nonconvex phase retrieval," Math. Program., vol. 176, no. 1, pp 5-37, 2019.
[12] J. Cocola, P. Hand, and V. Voroninski, "Nonasymptotic guarantees for spiked matrix recovery with generative priors," in Conf. Neur. Inf. Proc. Sys. (NeurlPS), vol. 33, 2020.
[13] Y. C. Eldar and S. Mendelson, "Phase retrieval: Stability and recovery guarantees," Appl. Comput. Harmon. Anal., vol. 36, no. 3. pp. 473-494, 2014.
[14] J. R. Fienup. "Phase retrieval algorithms: A comparison," Appl. Opt., vol. 21, no. 15, pp. 2758-2769, 1982.
[15] D. Foster, Generative Deep Learning: Teaching Machines to Paint, Write, Compose and Play. O'Reilly Media, Inc, USA, 2019.
[16] S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing. Springer New York, 2013.
[17] C. Gao, Z. Ma, H. H. Zhou et al., "Sparse CCA: Adaptive estimation and computational barriers." Ann. Stat., vol. 45, no. 5, pp. 2074-2101, 2017.
[18] R. W. Gerchberg, "A practical algorithm for the determination of phase from image and diffraction plane pictures," Optik, vol. 35, pp. 237-246, 1972.
[19] T. Goldstein and C. Studer, "Phasemax: Convex phase retrieval via basis pursuit," IEEE Trans. Inf. Theory, vol. 64, no. 4, pp. 2675-2669, 2018.
[20] Hand, O. Leong, and V. Voroninski, "Phase retrieval under a generative prior," in Conf. Neur Inf. Proc. Sys. (NeurIPS), 2018, pp. 9154-9164.
[21] B. Hao, Y. Yadkori, Z. Wen, and G. Cheng, "Bootstrapping upper confidence bound," Conf. Neur. Inf. Proc. Sys. (NeurIPS), 2019.
[22] R. Heckel and P. Hand, "Deep decoder: Concise image representations from untrained non- convolutional networks," " Int. Conf. Learn. Repr. (ICLR), 2019.
[23] M. Huang and 7. Xu, "The estimation performance of nonlinear least squares for phase retrieval," IEEE Trans. Inf. Theory, vol. 66, no. 12, pp. 7967-7977, 2020.
[24] M. Huang and 7. Xu, "Performance bound of the intensity- model for noisy phase retrieval,"
https//aazzivorg/aas220004440 2020.
11

---

[25] R. Hyder, V. Shah, C. Hegde, and M. S. Asif, "Alternating phase projected gradient descent with generative priors for solving compressive phase retrieval," in Int. Conf. Acoust. Sp. Sig. Proc. (ICASSP). IEEE, 2019, pp. 7705-7709.
[26] M. Iwen, A. Viswanathan, and Y. Wang, "Robust sparse phase retrieval made easy," Appl. Comput. Harmon. Anal., vol. I, no. 42, pp. 135-142, 2017.
[27] G. Jagatap and C. Hegde, "Algorithmic guarantees for inverse imaging with untrained network priors," " in Conf. Neur. Inf. Proc. Sys. (NeurIPS), vol. 32, 2019.
[28] G. Jagatap and C. Hegde, "Sample-efficient algorithms for recovering structured signals from magnitude-only measurements," IEFE Trans. Inf. Theory, vol. 65, no. 7, pp. 4434-4456, 2019.
[29] A. Jalal, L. Liu, A. G. Dimakis, and C. Caramanis, "Robust compressed sensing using generative models," " Conf. Neur. Inf. Proc. Sys. (NeurIPS), 2020.
[30] M. Journée, Y. Nesterov, P. Richtárik, and R. Sepulchre, "Generalized power method for sparse principal component analysis." J. Mach. Learn. Res., vol. 11, no. 2, 2010.
[31] A. Kamath, S. Karmalkar, and E. Price, "On the power of compressed sensing with generative models," in Int. Conf. Mach. Learn. (ICML), 2020.
[32] F. Krahmer and D. Stöger, "Complex phase retrieval from subgaussian measurements," J. Fourier Anal. Appl., vol. 26, no. 6, pp. 1-27, 2020.
[33] V. Kuleshov, "Fast algorithms for sparse principal component analysis based on Rayleigh quotient iteration," in Int. Conf. Mach. Learn. (ICML). PMLR, 2013, pp. 1418-1425.
[34] G. Lecué and S. Mendelson, "Minimax rate of convergence and the performance of empirical risk minimization in phase recovery," Electron. J. Probab., vol. 20, pp. 1-29, 2015.
[35] Z. Liu, S. Gomes, A. Tiwari, and J. Scarlett, "Sample complexity bounds for 1-bit compressive sensing and binary stable embeddings with generative priors," " Int. Conf. Mach. Learn. (ICMI.), 2020.
[36] Z.. Liu and J. Scarlett, "The generalized Lasso with nonlinear observations and generative priors," in Conf. Neur. Inf. Proc. Sys. (NeurIPS), vol. 33, 2020.
[37] Z. Liu and J. Scarlett, "Information-theowe
lower bounds for compressive sensing with generative models," IEEE J. Sel. Areas Inf. Theory, vol. 1, no. 1, pp. 292-303, 2020.
[38] Ma and A. Wigderson, "Sum-of-squares lower bounds for sparse PCA," Conf. Neur. Inf. Proc. Sys. (NeurIPS), vol. 28, pp. 1612-1620, 2015.
[39] Z. Ma, "Sparse principal component analysis and iterative thresholding," Ann Stat., vol. 41,
no. 2. pp. 772-801, 2013.
[40] S. Mallat, A wavelet tour of signal processing. Elsevier, 1999.
[41] B. Moghaddam, Y. Weiss, and S. Avidan, "Spectral bounds for sparse PCA: Exact and greedy algorithms," Conf. Neur. Inf. Proc. Sys. (NeurIPS), vol. 18, p. 915, 2006.
[42] Netrapalli, P. Jain, and S. Sanghavi, "Phase retrieval using alternating minimization," JEEE Trans. Sig. Proc.. vol. 63, no. 18, pp.
2015.
[43] M. Neykov, Z. Wang, and H. Liu, "Agnostic estimation for misspecified phase retrieval models," " Conf. Neur: Inf. Proc. Sys. (NeurIPS), 2016.
[44] H. Ohlsson, A. Yang, R. Dong, and S. Sastry, "CPRL-An extension of compressive sensing to the phase retrieval problem," " Conf. Neur. Inf. Proc. Sys. (NeurIPS), vol. 25. pp. 1367-1375, 2012.
[45] G. Ongie, A. Jalal, C. A. Metzler, R. G. Baraniuk, A. G. Dimakis, and R. Willett, "Deep learning techniques for inverse problems in imaging." IEFE J. Sel. Areas Inf. Theory, vol. 1, no. 1, pp. 39-56, 2020.
[46] T. Pang, Q. Li, Z. Wen, and Z. Shen, "Phase retrieval: A data-driven wavelet frame based approach," Appl. Comput. Harmon. Anal., vol. 49, no. 3, pp. 971-1000, 2020.
[47] Y. Plan and R. Vershynin, "The generalized Lasso with non-linear observations," IEEE Trans. Inf. Theory, vol. 62, no. 3, pp. 1528-1537, 2016.
[48] A. Raj, Y. Li, and Y. Bresler, "GAN-based projector for faster recovery with convergence guarantees in linear inverse problems," in IEEE/CVF Int. Conf. Comp. Vision (ICCV), 2019.
12

---

[49] J. Scarlett and V. Cevher, "An introductory guide to Fano's inequality with applications in statistical estimation," " htpp://annxiv.rr//110000005
2019.
[50] P. Schniter and S. Rangan, "Compressive phase retrieval via generalized approximate message passing," " IEEE Trans. Sig. Pruc., vol. 63, no. 4, pp. 1043-1055, 2014.
[51] V. Shah and C. Hegde, "Solving linear inverse problems using GAN priors: An algorithm with provable guarantees," in Int. Conf. Acoust. Sp. Sig. Proc. (ICASSP). IEEE, 2018, pp. 1609-4613
[52] F. Shamshad and A. Ahmed, "Compressed sensing-based robust phase retrieval via deep generative priors," IEEE Sens. J., vol. 21, no. 2. pp. 2286-2298, 2020.
[53] Y. Shechtman, A. Beck, and Y. C. Eldar, "GESPAR: Efficient phase retrieval of sparse signals," IEEE Trans. Sig. Proc., vol. 62, no. 4, pp. 928 928-9998-999 03-,938,222 2014.
[54) M. Soltanolkotabi, "Structured signal recovery from quadratic measurements: Breaking sample complexity barriers via nonconvex optimization," IEEE Trans. Inf. Theory, vol. 65, no. 4, pp. 2374-2400, 2019.
[55] J. Sun. Q Qu, and J. Wright, "A geometric analysis of phase retrieval," Found. Comput. Math., vol. 18, no. 5, pp. 1131-1198, 2018.
[56] Y. S. Tan, "Sparse phase retrieval via sparse PCA despite model misspecification: A simplified and extended analysis," hupps//aazzvvorr//122..66 1204 2017.
[57] L. V. Truong and J. Scarlett, "Support recovery in the phase retrieval model: Information- theoretic fundamental limits."" IEEE Trans. Inf. Theory. vol. 66, no. 12, pp. 7887-7910, 2020.
[58] D. Van Veen, A. Jalal, M. Soltanolkotabi. E. Price, S. Vishwanath. and A. G. Dimakis. "Com- pressed sensing with deep image prior and learned regularization." http://aarzivorr///86666664/ 2018.
[59] S. S. Vempala, The random projection method. American Mathematical Soc., 2005, vol. 65.
[60] R. Vershynin, "Introduction the non-asymptotic analysis of random matrices," https///axit.or//aax//11113313 2010.
[61] V. Voroninski and Z.. Xu, "A strong restricted isometry property, with application phaseless compressed sensing," " Appl. Comput. Harmon. Anal., vol. 40, no. 2, pp. 386-395, 2016. [62] Waldspurger, A. d' Aspremont, and S. Mallat, "Phase recovery, maxcut and complex semidefi- nite programming," Math. Program., vol. 149, no. pp. 47-81, 2015,
[63] G. Wang. G. B. Giannakis, and Y. C. Eldar, "Solving systems of random quadratic equations via truncated amplitude flow," IEEE Trans. Inf. Theory, vol. 64, no. 2, pp. 773-794, 2017.
[64] G. Wang, L. Zhang, G. B. Giannakis, M. Akçakaya, and J. Chen, "Sparse phase retrieval via truncated amplitude flow," IEEE Trans. Sig. Pruc., vol. 66, no. 2, pp. 479-491, 2017.
[65] T. Wang, Q. Berthet, R. J. Samworth et al., "Statistical and computational trade-offs in estimation of sparse principal components," Ann. Stat., vol. 44, no. 5, pp. 1896-1930. 2016.
[66] X. Wei, Z. Yang, and Z. Wang, "On the statistical rate of nonlinear recovery in generative models with heavy-tailed data," in Int. Conf. Mach. Learn. (ICML), 2019, pp. 6697-6706.
[67] J. Whang, Q. Lei, and A. G. Dimakis, "Compressed sensing with invertible generative models and dependent noise." " https://arxiv.orr/2033 00000, 2020.
[68] F. Wu and P. Rebeschini, "Hadamard Wirtinger flow for sparse phase retrieval," in Int. Conf. Artif. Intell. Stat. (AISTATS). PMLR, 2021, pp. 982-990.
[69] Y. Xia and Z. Xu, "The recovery of complex sparse signals from few phaseless measurements." Appl. Comput. Harmon. Anal., vol. 50, pp. 1-15, 2021.
[70] X.-T. Yuan and T. Zhang, "Truncated power method for sparse eigenvalue problems," J. Mach. Learn. Res., vol. 14, no. 4, 2013.
[71] H. Zhang, Y. Chi, and Y. Liang. "Provable non-convex phase retrieval with outliers: Median truncated Wirtinger flow," in Int. Conf. Mach. Learn. (ICML). PMLR, 2016, pp. 1022-1031.
[72] H. Zhang, Y. Zhou, Y. Liang, and Y. Chi, "A nonconvex approach for phase retrieval: Reshaped Wirtinger flow and incremental algorithms," J. Mach. Learn. Res., vol. 18, 2017.
[73] H. Zou, T. Hastie, and R. Tibshirani, "Sparse principal component analysis," " Comput. Graph. Stat., vol. 15, no. 2, pp. 265-286, 2006.
13


Reviews:
[{"review_id": "iThdM_iz6Yl", "reviewer": "Reviewer_Uh34", "summary": "Summary:\n\nThis paper proposes a spectral initialization algorithm for compressive phase retrieval and show that it is provably close to the ground truth. They also generalize previous results in compressive phase retrieval using generative models. Finally, the authors show that sparse PCA can be used to find a good initialization for sparse phase retrieval.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "__Strengths__:\n1. All results and assumptions are stated clearly.\n\n1. Prior work has analyzed the sample complexity of phase retrieval using $d$-layered ReLU networks. Theorem 1 shows that similar sample complexity is true for $L$-Lipschitz generative models. The result seems correct.\n\n1. The authors propose a new spectral initialization algorithm, and their theoretical result shows that it is close to the true vector. This result can be combined with existing results in literature that depend on a good initialization to guarantee a polynomial time algorithm (under certain assumptions).\n\n1. Algorithm 1 is interesting. Specifically, the use of sparse PCA to find an approximate initialization is interesting and novel to the best of my knowledge.\n\n__Weaknesses__:\n\n1. I think the claim that the authors have found an efficient algorithm for generative networks is overstated. The authors state that their spectral normalization result can be combined with the Theorem in [24] to get a polynomial time algorithm. However, the results in [24] assume that there exists a polynomial time algorithm to project onto the range of a generative model, and this is a strong assumption which is simply not true for many generative models. I think the authors should clarify this in their claims.\n\n1. The novelty in the spectral initialization is unclear. Is it exactly the same as [66]?\n\n1. [66] provides a sample complexity bound of $n \\log n$ for phase retrieval of _general vectors_, and Theorem 3 in this paper provides a sample complexity bound of $s \\log n$ for phase retrieval of _sparse vectors_. The authors should elaborate the novelty in Theorem 3. Can Theorem 3 be derived from [66] by replacing the metric entropy of general vectors with the metric entropy of sparse vectors?\n\n1. The experiments are unconvincing. They are all synthetic experiments without a trained generative model, and it is unclear whether the proposed method using a generative model actually outperforms sparsity-based algorithms. Furthermore, most error bars overlap.\n\n__Novelty__:\n\nThe spectral initialization used in this paper is derived from [66]. \n\nFrom my understanding of the paper, Theorem 1 follows from traditional analysis techniques in compressed sensing and phase retrieval. The case of $d$-layered ReLU generative networks have been explored in prior work, and this work generalizes it to $L$-Lipschitz generative models.\n\n__Score Justification__:\n\nI do have some concerns about the novelty of the results in this paper, as the spectral initialization technique and the other analysis techniques are largely borrowed from prior work. However, the authors do present a fairly complete analysis of the considered problem, and hence I think the merits outweigh the flaws.\n\n__General comments__:\n1. Below Eqn 9, the authors say that $\\|\\|\\eta\\|\\|_\\infty = O( \\|\\| \\eta \\|\\|_2 / \\sqrt{m})$ is a reasonable assumption. However, even in the simple case where $\\eta$ is Gaussian, the correct bound would be $\\|\\|\\eta\\|\\|_\\infty = O(\\|\\| \\eta \\|\\|_2  \\sqrt{\\log m }/ \\sqrt{m})$.  I do not think it is a big problem since it is only an extra log-factor, but I think it should be stated correctly (and the Theorem statements should also account for this extra log factor, if necessary).\n\n1. I understand that the assumption that range($G$) lies in the unit ball is necessary. However, if it lies within a $R$ radius ball, how do the bounds change? I think the dependence may be polynomial in $R$, but it would be nice to have an explicit formula.\nAlso, what does this assumption imply for the Lipschitz constant $L$? Does it need to be $1/r$?\n\n1. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not have concerns about the social impact of this work as it is primarily theoretical.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not have concerns about the ethics of this paper as it is primarily theoretical.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 "}, "extra_text": {}}, {"review_id": "Ibt34ToOWQW", "reviewer": "Reviewer_yozY", "summary": "This paper presents interesting theoretical analysis for compressive phase retrieval under sparse and generative priors for the signals. The results are sample optimal and suggest that O(k log L) iid Gaussian measurements are sufficient to guarantee near-perfect signal recovery, where L is the network Lipschitz constant.The paper also discusses a spectral initialization approach with generative priors. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "+ The paper presents some new theoretical result for the recovery of a signal from amplitude measurements under generative prior assumption. The sample complexity seems similar to the earlier results in [24], but this paper uses different assumption/process for initialization. \n\n+ The paper presents analysis of spectral initialization with generative prior-based constraints. This is an interesting contribution. \n\n - The paper also presents analysis for sparse phase retrieval and includes experiments and comparison with existing methods. \n\n- The authors do not provide any algorithm to recover such initialization, nor do they provide any simulations for generative prior-based phase retrieval. It will be great if the authors can provide some additional insights and experiments for spectral initialization and recovery under generative priors. \n\n- Overall, the paper is well written. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "- Very little discussion on limitations. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "6GFNTuf4Mh", "reviewer": "Reviewer_b8Ro", "summary": "This paper considers the problem of noisy compressive phase retrieval (CPR) of $n$ dimensional signal under two different priors: (i) $L$-Lipschitz continuous generative model with latent dimension $k$ and (ii) underlying sparsity $s$. The main claims of this paper are theoretical in nature, where the authors derive the sample requirements for existence of a solution for CPR under both types of priors (assuming there exists an algorithm that can  solve the CPR minimization). The sample requirements obtained are of the order required for a linear compressive sensing problem, and therefore roughly sample optimal.\n\nAdditionally the authors use a _truncated_ spectral initialization algorithm for CPR, which they show has solution that lies close enough to the ground truth signal using only O($k\\log L$) (and O($s\\log n$)) samples.\n\nThe authors design a related spectral initialization technique which can be combined with any other off-the-shelf CPR algorithms, while requiring fewer sample requirements then prior state of art. \n\nSpectral initialization has been previously used for the general phase retrieval problem as well as under sparsity and structured sparsity priors, however incurring increased sample requirements. In this paper the authors prove closeness of a truncated spectral initialization to ground truth in sparse phase retrieval which brings down the sample requirement from O($s^2 \\log n$) to O($s\\log n$).\n\nThey also show similar guarantees for the case of deep generative priors.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main claims and contributions of this paper are as follows:\n\n1. existence of a solution to the CPR problem using O($k \\log L$) samples within small error margin. [Theorem 1]\n2. spectral initialization for CPR with deep generative priors (only theoretical, no experiments)\n3. sample optimality has been shown for local convergence of CPR with deep generative priors, however this paper introduces an alternate procedure for spectral initialization, which brings down the sample requirement for initialization and therefore overall global convergence of CPR. [Theorem 2]\n4. improved sample complexity for spectral initialization in sparse phase retrieval. [Theorem 3]\n\n[Theorem 1]\nAuthors provide guarantee for existence of a solution for CPR. If ground truth $x \\approx p = G(z)$ and $q = G(\\hat{z})$ that minimizes the phase retrieval objective up to additive term $\\tau$ (assuming there exists some algorithm that can achieve this), then the authors provide theoretical guarantees to show that $distance(q,x)$ is upper bounded by $distance(p,x)$ up to an additive error factor.  Such guarantees have been shown for the problem of compressed sensing before [4], but is novel in the case of compressed phase retrieval.\n\n[Theorem 3]\nSpectral initialization for the case of sparse phase retrieval has been previously solved [27,58] by first indentifying the sparse support based on the diagonal entries of matrix $V$ from this paper and then performing PCA (or power method) on this reduced support to identify the top singular vector of V. The previous approach is approximate, and therefore if solved exactly can yield better sample complexity. This is the key contribution in this paper where they derive the sample requirement for the spectral initialization problem, by assuming that the one can tractably solve for the top singular vector of $V$ that lies in the signal prior set (s-sparse signals or k,L generative signals). \n\n[Theorem 2]\nThe authors also provide theoretical conditions under which such spectral initialization produces a good initialization when deep generative priors are considered. Both Theorems 2 and 3 use covering arguments and lemmas from previous derivations which have been properly presented.\n\n[SPCA for initialization]\nAuthors use off the shelf SPCA solvers such as GRQI and TPower methods to solve the spectral initialization problem.\n\nThe paper is very well written, contributions are clearly highlighted and literature review is excellent. The results and derivations for sparse phase retrieval are convincing. \n\nThe only set-back of this paper is that there are no experiments for CPR using deep generative priors (with spectral initialization). How would one go about designing a deep generative prior (DGP) constrained version of PCA? This paper will benefit from such discussion. \n\nIt has also been observed in several papers that random initialization of latent space vector ($z if x=G(z)$) (or network weights) suffices for solving CPR with deep generative (or untrained) networks for local and possibly global convergence. It would be interesting to see how spectral initialization with DGP version of PCA would fare against random initialization. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations: No experiments on CPR using spectral initialization for signals with deep generative prior.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of phase retrieval with generative priors. First they show under Gaussian measurements and a generative model that is $L$-Lipschitz and has $k$ inputs, $O(k \log L)$ measurements suffice for recovery. Furthermore they give an algorithm, predicated on solving a particular spectral initialization problem, that actually attains this number of measurements. There is a catch here: The optimization problem itself is likely hard. This is not surprising. After all, even in sparse phase retrieval there is conjectured to be a computational vs. statistical gap (and evidence is known based on the planted clique problem). Compared to the closely related work of Hand-Leong-Voroninski the main differences are (1) Hand et al. work with $d$-layer networks and get suboptimal dependence on $d$, whereas the bounds here are optimal up to constant factors (2) Hand et al. require an expansion condition on the network, which is not needed here. However (3) Hand et al. show that expansion gives a favorable optimization landscape, and thus have no hidden assumptions about being able to solve computationally hard problems. 
Decision: Accept (Poster)