Misspecified Phase Retrieval with Generative Priors
Authors: Zhaoqiang Liu
Xinshao Wang
Jiulong Liu
Venue: NeurIPS 2022 Accept (2022)
Keywords: Phase retrieval
generative priors
model misspecification
single index model
near-optimal statistical rate

Abstract: In this paper, we study phase retrieval under model misspecification and generative priors. In particular, we aim to estimate an $n$-dimensional signal $\mathbf{x}$ from $m$ i.i.d.~realizations of the single index model $y = f(\mathbf{a}^T\mathbf{x})$, where $f$ is an unknown and possibly random nonlinear link function and $\mathbf{a} \in \mathbb{R}^n$ is a standard Gaussian vector. We make the assumption $\mathrm{Cov}[y,(\mathbf{a}^T\mathbf{x})^2] \ne 0$, which corresponds to the misspecified phase retrieval problem. In addition, the underlying signal $\mathbf{x}$ is assumed to lie in the range of an $L$-Lipschitz continuous generative model with bounded $k$-dimensional inputs. We propose a two-step approach, for which the first step plays the role of spectral initialization and the second step refines the estimated vector produced by the first step iteratively. We show that both steps enjoy a statistical rate of order $\sqrt{(k\log L)\cdot (\log m)/m}$ under suitable conditions. Experiments on image datasets are performed to demonstrate that our approach performs on par with or even significantly outperforms several competing methods. 

Misspecified Phase Retrieval with Generative Priors
Zhaoqiang Liu National University of Singapore wwwlliihanuseedu.co. edu.sg
Xinshao Wang University of Oxford xinshao wangdeng ox ac.uk
Jiulong Liu Chinese Academy Sciences jiulongliu@lsec. cc. cn
Abstract
In this paper, study phase retrieval under model misspecification and generative priors. In particular, we aim to estimate an n-dimennsinal signal x from m i.i.d. re- alizations of the single index model y f(a" x),",,, where is unknown and possibly random nonlinear link function and a E R is standard Gaussian vector. We make the assumption Cov(y: [y, (a (a"x)² x) o which corresponds to the misspec- ified phase retrieval problem. In addition, the underlying signal x is assumed to lie in the range of an L-Lipschitz continuous generative model with bounded k- dimensional inputs. We propose a two-step approach, for which the first step plays the role of spectral initialization and the second step refines the estimated vector produced by the first step iteratively. We show that both steps enjoy a statistical rate of order / /(k log L.) (log m)/m under suitable conditions. Experiments on image datasets are performed to demonstrate that our approach performs on par with or even significantly outperforms several competing methods.
Introduction
Compressed sensing (CS) is perhaps the most popular instance of high dimeensiiiii inverse problems, for which one has the linear measurement model
y y= a= + 7)
where a E IR the sensing vector, x E IR is the sparse signal to estimate, and 1) represents additive noise. It has been well-known for CS that roughly m O(s log(n/s)) i.i.d. Gaussian measurements are sufficient to ensure the accurate recovery of a signal with 8 non-zero entries [8 I 23 77
Phase retrieval (PR) arises in numerous scientific areas including X-ray crystallography. acoustics, astronomy, microscopy, optics, wireless communications, and quantum information [13, where one cannot measure a" directly, and can only record its magnitude. For example, the following noisy magnitude-only measurement model has been adopted in various prior works on sparse (real-valued)
PR 92 39
36 9 71:
y = y= +
where the signal x is assumed to be sparse, and the sensing vector a is assumed to be standard Gaussian vector.
However, both the linear and magnitude-only measure models and 2 are idealized views of the data generating process. To make the setup more general, one can utilize the following semi-parametric single index model (SIM) for general nonlinear models:
f(afxxxx x),
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

where f R + I is an unknown (possibly random) nonlinear link function, and a is typically assumed be Gaussian. In addition, since the norm of x E IR" is absorbed into the SIM, for brevity, it is common to assume that x is unit vector, i.e., ||*|| 1. SIMs have long been studied in the conventional setting where the number of measurements m. > n 30
45 In recent years, they have also been analyzed in the high-dimensional setting where m < mainly under the assumption
that the underlying signal is sparse, Relevant works include but are not limited to [72 63 26 73 68
For all these works, it is crucial to impose the following assumption on the SIM:
Covly, a' x] # O.
(4)
The pivotal condition in 4 is fairly generic and encompasses notable special examples such noisy 1-bit measurements and general (non-binary) quantization schemes. However, it is not satisfied by PR models including (2) and the related models
y = T x - 7/, y - (a x)² +1,
(5)
where 1) refers to zero-mean random noise that is independent of a. In order to formalize a class of SIMs that encompass the above-mentioned PR models (and more general models, see the discussion in Section (.2) as special cases, misspecified phase retrieval (MPR) has been studied in 64 98 with
the condition 44) being replaced by the assumption
Covly, (a" (a"x)²]= + O.
It is worth mentioning that another motivation behind studying MPR is that the theoretical analysis for PR typically relies on the correct model specification that the data points are indeed generated by the correct model, and the MPR model enables theoretical analysis under statistical model misspecification.
In both works 64, 988, the signal is assumed to be sparse. Recently, motivated by tremendous successful applications of deep generative models and following the seminal work [6] on generative model based linear CS, it has been popular to study high-dimensional inverse problems under
60 40 651. In particular, instead of being sparse, the underlying signal is assumed to be contained in (or lie near) the range of generative model. It has been empirically demonstrated in [6] and its various follow-up works (c.g.. see [99 [5] [88 and a literature review in (78) that compared to sparsity based methods, corresponding generative model based al algorithms require significantly fewer samples to recover the signal up to a given accuracy.
generative priors 76, 31 32 34 96
67 95|
In this paper, we study the MPR problem under generative modeling assumptions.
1.1 Related Work
In this subsection, we summarize some relevant works on PR and SIM, for both cases with or without generative priors.
PR and SIM without generative priors: There is large amount of literature providing practical
algorithms for PR, including convex methods [66] 14 12 90 29 and empirically more competitive
non-convex methods (27
21
70
In particular, in the seminal work [62] and a variety of its
82 8) whether it is for general PR (with no priors on the signal) or sparse PR. two-step approaches have been proposed with provable guarantees. The first step consists of spectral initialization method, and the second step is typically an iterative (such as alternating minimization and gradient descent) algorithm that further refines the initial guess of the first step. For general PR, the spectral initialization step turns out to be unnecessary, and optimal sample complexity guarantees can be established even when using random initialization [83] [6]. However, to the best of our knowledge, it is not the case for sparse PR. More specifically, all theoretically-guaraatt guaranteed non-convex algorithms for sparse PR require spectral initialization, and this typically results in sub-optimal sample complexity of (s² log n) (instead of O(s log n1)), where refers to the number of non-zero entries of the signal to estimate.
follow-up works 113
10
15
9
99
39
MPR is also closely related to SIMs, which have been extensively studied in the conventional setting where m > n1, see, e.g.,
30
35 59
High-dimensional SIMs have received lot of attention in
recent years, with theoretical guarantees for signal estimation and support recovery 22 24 74 84
55 72
28 93
669
20
In particular, motivated by the idea that under the assumption
SIM can be converted into scaled linear measurement model with unconventional noise, the authors

---

of [72] consider minimizing the linear least-squares objective function over a convex set. They show that a reliable estimation of the signal can be obtained by such a simple method despite the unknown nonlinear link function.
As mentioned earlier, MPR with sparse priors has been studied in 66 98 The work (64] implements a two-step procedure based on convex optimization, with the first step being a spectral initialization method. More specifically, a semidefinite program is solved to produce an initial vector, and then an l regularized least square is solved to obtain a refined estimator. Such procedure suffers from high computational costs. more efficient two-step approach, which is simple variant of the thresholded Wirtinger flow method [10), is proposed in [98]. In the first step, identical to that in [[O], the initial vector calculated by thresholded spectral method that first estimates the support of the sparse signal by thresholding and then performs the classic power method over the submatrix corresponding to the estimated support. In the second step, a thresholded gradient descent algorithm employed.
Both approaches in 664 98 can attain the optimal statistical rate of order v(s log n2). m. provided that the sensing vector is standard Gaussian and the number of samples m = S2( log n). In addition, the second step of the approach proposed in [98] is shown to achieve linear convergence rate.
PR and SIM with generative priors: PR with generative priors has been studied in [31 37 38 80 3,47] More specifically, an approximate message passing algorithm is proposed in B1. The authors minimize the objective over the latent space in RR* using gradient descent, where is the latent dimension of the generative prior. Corresponding algorithms may easily get stuck in local minima since the explorable solution space is limited. Recovery guarantees for projected gradient descent algorithms over the ambient space in R" for noiseless PR with pre-trained or untrained neural network priors have been proposed [37 38 No initialization methods have been proposed in these works, making the assumption on the initial vector therein a bit stringent. On the other hand, the authors of [47) propose a spectral initialization method for PR with generative priors and provide recovery guarantees with respect to globally optimal solutions of a corresponding optimization problem. The optimization problem is non-convex, and a projected power method is proposed in [50) to approximately find optimal solution.
of 80
Generative model based SIMs have been studied in S1 provide optimal sample complexity upper bounds under the assumption of Gaussian sensing vectors. But their results rely on the assumption 4 which is not satisfied by widely adopted PR models. The SIM studied in [94] encompasses certain PR models as special cases, and the sensing vector can be non-Gaussian. However, the nonlinear link function / is assumed to be differentiable, making it not directly applicable to the PR model in (2). Moreover, it is worth mentioning that in both works [94] [1),, the recovery guarantees are with respect to globally optimal solutions of typically highly non-convex optimization problems. Attaining these optimal solutions is practically difficult.
The authors of 51
1.2 Contributions
Throughout this paper, we assume that the signal lies in the range of an L-Lipsehitz continuous generative model with bounded k-dimensional inputs. Our main contributions are as follows:
We propose a two-step approach for MPR with generative priors. In particular, in the first step, we make use of the projected power method proposed in [50] to obtain a good initial vector for the iterative algorithm used in the second step.
We show that under appropriate initialization, both steps attain a statistical rate of order /(k L) - (log m)/m. and the second step achieves a linear convergence rate. The initialization condition for the first step mild in the sense that allows the inner product between the starting point and the signal x to be a sufficiently small positive constant. In contrary, the initialization condition for the second step more restrictive, making the first step necessary. Notably, unlike for the works on MPR with sparse priors [64] 988] that require the sub-optimal O log n) sample complexity, the sample complexity requirement for our recovery guarantees ((k L)- (log m)). which is naturally conjectured to be
near-optimal [52 [22) 42).
We perform numerical experiments on image datasets to corroborate our theoretical results. In particular, for the noisy magnitude-only measurement model (2). we observe that our approach gives reconstructions that are competitive with those of the alternating phase
projected gradient descent (APPGD) algorithm proposed in (37), which is the corresponding
3

---

fifte-of-theasse art method, though we do not utilize the knowledge of the link function and allow for model misspecification. Moreover, for several closely related measurement models that satisfy the condition (6). our approach leads to superior reconstruction performance compared to all other competing methods, including APPGD.
2
Problem Formulation
In this section, we overview some important assumptions that we adopt. Before proceeding, we present the notation used in this paper.
2.1 Notation
We use upper and lower case boldface letters denote matrices and vectors respectively, For any positive integer N, we use the shorthand notation [N] = {1, 2, ,N and In represents the identity matrix in I N The support (set) of vector is the index set of its non-zero entries. We use |||22-2 to represent the spectral norm of X. We use (r) to denote the radius-r in RR i.e., (r) == {z E IR* | < r]. and S represents the unit sphere in R", i.e., Sn-1 == (s E R ||s||2 = 1}. We use G denote pre-trained T--Lipschitz continuous generative model from (r) to R We focus the setting where k < n. For any set S C B (r), we write S). Our goal is to estimate the signal E Range( (G) G())(r) from
G(S) = (G(z) (C(2) realizations of the sensing vector and the observation y (generated according to the SIM in (3). For any two sequences of real values {a,) and {b, ). we write a = O(by) if there exist an absolute constant C1 and positive integer j1 such that for any j > j1, layl I C1by. aj = 22bb)) if there exist an absolute constant C2 and positive integer J2 such that for any J > f2, layl > C2bj. We use the generic notations C and C" to denote large positive constants, and we use c to denote a small positive constant; their values may differ from line to line.
2.2 Setup
First, the following are the standard definitions of sub-exponential random variable and the associ- ated sub-exponential norm.
Definition 1. A random variable X is said to be sub-exponential if there exists positive constant C' such that (E [[X /p < for all p 2 L, or equivalently, if there exists positive constant C' such that X > u) & exp(1 u/C') all u 2 0. The sub-exponential norm of X is defined as
||, = sup P
(E |
We will focus on the following settings except where stated otherwise:
The observations are independently generated according to the SIM where f is the link function that is unknown and possibly random.
We have an T.-Lipschitz continuous generative model G (*(r) - TR. For conve- nience, similarly to [48 50), we assume that the generative model normalized such that Range(G) G) S 5 For a general (unnormalized) generative model, we may essentially consider its normalized version. See, e.g., (50) Remark 1].
The signal x is contained in the range of i. x E Range (G) C S
The sensing vector a E I is standard Gaussian, i.e., a ~ (O I,)..
The random variable [aa x) is sub-exponential with the sub-exponential norm being denoted by Ky, i.e., Ky : || addition, we use M, to denote the expectation of y, i.e., M, := --Ely.
Remark 1. y will be sub-exponential when f(x) comprises of x plus lower order terms with < 2 (since the product of two sub- Gaussian random variables is sub-exponential) and therefore we will see that the y corresponding to all the measurement models presented in our paper is sub- aab-exponential. We remark that the assumption of sub-exponential is not essential and it can easily relaxed. For example, when y = =² with e being an even integer that is larger than 2, there will be only minor change in the order of the log m
term in the sample complexity and statistical rate. However, for brevity, we follow [64 98 and make the assumption of sub- sabb-exponential y to avoid non-essential complications.

---

We consider MPR and assume that"
= Cov [v. (a" x)]
> 0,
equivalenty,
V v:= Cov [f(g) 9² > 0,
where ~ (0, 1) is standard normal random variable. Note that the assumption (8) is
only with respect to the nonlinear link function f. The condition in 7 is satisfied by PR
models described 2 and (5). It is also satisfied by relevant models such as [98]
2 x taan (Ia" xl) + 7, y = 2(a T x)² + sin( aa xl) + 17.
See 64
Proposition 3 and Remark 4] for more general examples.
3
Algorithm
In this section, we describe our two-step algorithm devised for MPR with generative priors. Suppose that we have i.dd realizations of and y, namely a1,...,am am and yı..... Vmn To estimate the signal> x, we consider the following two-step approach:
1. We perform Ti iterations in the first step. In particular, let
m
m Σ ys (a.a? In)
(10)
We perform the projected power method proposed in 50 For / 0,1,..., 1, let
((+11) = Pa (Vw(t))
(11)
where P-(-) denotes the projection function onto Range(G) and obtain x0) w (T)) Similarly to 43 477, we the starting point (0) as the column of L - y,a,a (i.e.. a shifted version of V) that corresponds to the largest diagonal entry. Note that it is easy to calculate that [E[]]= = 1xxx (see, e.g., 47 Lemma 8)), for which each column is scalar
product of x. This motivates the use of a shifted version of V to get the initialization vector.
2. We perform TV iterations in the second step. In particular, let
V1
(12)
2
be the empirical mean of the observations. We perform the following iterative procedure:
For t 0, T2 1, let
m m
[/4 7) (af x()) 2
0(0)
(13)
(0) (y) 7) a x(() , 1,2....,m.
(14)
((+1) =x (1) 5 ((0)) (af x(1)
-1(") ai:
(15)
m
x( (++1) Pg (x(()1))
(16)
where Ç >> 0 is a tuning parameter, and ()() can be thought of as an approximation of defined in (7) The idea behind calculating (1) is that by comparing 4 and (6) we observe
that to transform the MPR model into conventional SIM, we may use (y - E (a) x) to
'The that 0 be similarly handled by considering -y TTha is, for any s E R" (s(s) := G( arg minge (+))) GG(z) - s||2). Similarly to 79 37 38 50
we implicitly assume the exact projection in our analysis. In practice, approximate methods such as gradient- and based projections 779 75 have been shown to work well.
5

---

Algorithm A two-step approach for misspecified phase retrieval with generative priors
Input: {(ai J step size Ç > number of iterations Zi for the first step, number of iterations Ty for the second step, pre-traines generative model G, initial vector w(O)
First step:
1: for t 0, 0.1,...,
do
2: w(++1) = Pa (Po((wl!) (w
3: end for
Second step:
Let x (0) = w (()
1: for 0, 0, 1, ..... T2 do
2: Calculate 21t), Di (1)
x(++1) and (1+1) according
13
15 and (16) respectively
3: end for
Output: & == x
replace y. see also 664. Moreover, 15) can be considered as gradient descent step with
respect to linear measurement model with the scale factor g(() and observations 7/ Then,
in (16), we project the calculated vector x(++1) onto Range(G). Finally, we use == (Ta)) to represent the estimated vector obtained after T2 iterations.
For convenience, we summarize the details in Algorithm I
Theoretical Results
The following theorem establishes recovery guarantees for the first step of Algorithm D The proof is given the supplementary material. Note that Ky : ||y|| (cf. Section 2.2) is considered fixed constant and is omitted in the O-)) notation.
Theorem 1. Assume that there exists a positive integer such that x3 w(to) 2 co, where co is sufficiently small positive constant. Suppose that m = Ω2(( log(nIr)), m)) with a large enough implied constant. Then, we have that with probability 1 (1/m)), it holds for all t to that
x CKy V (klog((Trr) (log m) 0 (A: log(nTT)) (log m) )
(V
10
(17)
co
m
m
Since d-layer feedforward neural network generative model from (r) to R" is typically L-
Lipschitz continuous with L n ((d) [6] and we may set (dd) the upper bound in (77 is of order /lk log L) (logm)/me Such statistical rate is naturally conjectured to be near-optimal according to information- -ttoorrttctc lower bounds established for MPR with sparse priors [64] and generative model based principal component analysis (50]. Therefore, Theorem
[ reveals that the
first step of Algorithm] attaans the near-optimal statistical rate under appropriate initialization and exact projections. The accurate projection assumption is perhaps the major caveat Theorem [ However, it is a standard assumption in relevant works including [79] 37 38 71 [50] In practice,
both gradient- and GAN-basce projection methods (79 75 have been shown be highly effective in approximating the projection step.
Remark 2. Spectral initialization steps in relevant works on sparsity based PR 92
25
36
or MPR 164 198) require the sub-optimal sample complexity O(s² logn), where refers to the number of non-zero entries. In contrary, according to Theorem ! our spectral initialization step only requires the opar-optimal O( log L). (log m)) sample complexity (with linear rather than a quadratic dependence on ke). However, we note that such an advantage of our spectral initialization step comes price. In particular, we require the initialization condition x" x"w "w(t) 2 Co. which is not required by spectral initialization steps in the above-mentioned works on sparse PR/MPR.
For some upplications, we may assume that the dataset contains only vectors whose elements are all non non-negative. For example, this is natural ussumption for image datasets. During pre-training, we can easily set the activation fanction of the last layer of the neural network generative model to be certain non-negative function such as ReLU sigmoid, and the range of such
Remark 3.

---

generative model is contained in the non-negative orthant. Therefore, the assumption that x' w(ta) 2 co for sufficiently small positive constant co is also mild. Similar assumptions have been made in relevant works including 1 50) where it is not appropriate to assume that -x is also contained in the structured set (such as a closed convex cone or the range of a deep generative model). As result,
we provide an upper bound on ||w()) x||2. instead of min min(|( [ x||2, || + x112], which is commonly adopted distance measure in relevant literature on real-valued PR.
Moreover, although the projected power iterations in the first step of Algorithm can attain the near-optimal statistical rate under appropriate conditions, it is evident in a large body of literature on
PR (see, e-g., 662 10
99
98 64) that such spectral method better serves as the initialization
step of a subsequent iterative approach. This motivates us to propose the second step of Algorithm [ and in our numerical experiments, we clearly observe the benefit of the second step. More specifically, y.
compared to simply performing the projected power method, performing both steps of Algorithm | leads to significantly better reconstructed images when the total number of iterations is fixed to be the same, namely Ti + T2.
Next, we present the following theorem, which is proved in the supplementary material. This theorem shows that under appropriate initialization and the assumption of exact projections, the iterative algorithm in the second step of Algorithm converges linearly to point achieving the near-optimal statistical rate of order v log L)- (log m) m//m.
Theorem 2. Assume that the step size Ç and 0)), which is the initial vector for the second step of Algorithm 1 satisfy
2. + 5CV -|x110 - x x1|2 + 31 = 132,
(18)
where both B1 and 32 are positive constants 3 Suppose that m = (K log( (nIr)) (log (logm)) with
large enough implied constant. Then, we have with probability - (11 /m). the following event
m occurs: There exists a positive integer To O (log (k (oogg )), such that the sequence (1|x(() -x(12) (T) is monotonically decreasing, with the following inequality holds for all t S To:
|x(0) - >12 <1 (1-B2)) B2) -|xx(0) -x122 + CKy
(klog(n (log
B2 V
(19)
m
In addition, we have for all t To that
(v (klog(nLr) (log m)
|0000 -xx x11 CK₁y
(k (log((Lr)) (logm) 0
(20)
B2
m
m
Remark 4. In our analysis, we need impose the assumption 18 the step size C and initial
vector (0)_ This makes the first step of Algorithm I necessary since when [|x(0) - x||2 2 is not small, say [)x(0) - x = 1, the condition (18) cannot be satisfied. In comparison, to attain the near- netr-oltimal statistical rate O( /(k L)- (log m m /m), the initialization condition of the first step of Algorithm 1 is milder, and x" w (see Theorem 1 only needs to be lower bounded by sufficiently small positive constant (thus [[w(t))) - -xl12 can be close to v2). However, although the second step of Algorithm 1 requires a more restrictive initialization condition, we observe from our experimental results that clearly refines the estimate of the first step. Such phenomenon is also observed in various works
related to PR, including [62
13 10 99
64).
Remark 5. In Remark 4 we have briefly discussed the comparison of the initialization condition
x" (to) 2 co in Theorem 1 and the typical initialization condition |x w < x|| In the
following, we provide more detailed discussion: When both x and (to) are unit vectors (this is the setting of our Theorem 1.. the typical initialization requirement ||x 1x-wii -w(to))l2 < 61|x||| can be
reduced to 2(1 (1-x""w w(to)) < 82, or equivalently, x" <T'((oo] - Z Note that ö is typically small positive constant (e.g., 8 == in [IO] and 8 = in (31), and thus the typical initialization condition requires xT (to) to be larger than some positive constant that is close to 1. This is stronger than the assumption (to) 2 co. where co is a sufficiently small positive constant.
3,8 is sufficiently small, and it is used to absorb certain o(1) term.
'It basically assumes the weak recovery of the signal, see, e.g.. 61.
7

---

Remark 6. The condition in (18) requires [1 - Sy| 2. This reveals that we should choose Ç such that 22 2n) and good choice of Ç is Ç (for this case, the condition (88) reduces to |bx(0)) -x112 < (t). Since the knowledge of the link funetion (and thus the knowledge of v. which is dependent on f: See (8) cannot be assumed, in our experiments, we use e( to approximate v.
That is, Ç is set to be pin) in the t-th iteration of the second step of Algorithm 1 (though it is slightly varying instead of being fixed).
Numerical Results
In this section, we demonstrate the empirical performance of our Algorithm I (denoted by MPRG). We remark that these numerical experiments are proof-of-concep. rather than seeking to be com- prehensive since our contributions are primarily theoretical. We present some numerical results for the MNIST 44 dataset in the main document. Additional results for the MNIST dataset and some experimental results for the CelebA [53] dataset are presented in the supplementary material.
The MNIST dataset contains 60, 000 images of handwritten digits. The size of each image is 28 x 28, and thus the dimension of the image vector is 784. For the MNIST dataset. the generative model G is set to be (the normalized version of) a pre-trained variational autoencoder (VAE) model with the latent dimension being k 20. We make use of the VAE model pre-trained by the authors of [6] directly. For this VAE model, both the encoder and decoder are set to be fully connected neural networks with two hidden layers, and the architecture is 20 500 500 784. The VAE model is trained by the Adam optimizer with a mini-batch size 100 and a learning rate of 0.001, and is trained from the images in the training set. The projection step (-) (cf. (TT) is approximated by the Adam optimizer with a learning rate of 0.1 and 120 steps.
We report the results on 10 testing images that are selected from the test set. Note that these images are unseen by the pre-trained generative model. We perform 10 random restarts. For reconstructed images, we choose the best among these 10 random restarts to reduce the impact of local minima. We also provide quantitative comparisons with respect to the reconstruction error || x||2. where x is the underlying signal and X refers to the estimated (normalized) vector produced by each of the methods described below. The reconstruction error is averaged over both the 10 testing images and 10 random restarts. All experiments are run using Python 3.6 and TensorFlow 1.5.0, with NVIDIA GeForce GTX 1080 Ti 11GB GPU.
For Algorithm 1 we set 7i = 20 and To = 30. As mentioned in Section 3 the starting point w is set to the column of 1 E y. (i.e., a shifted version of V defined in (T0) that corresponds mn to the largest diagonal entry. In addition, as mentioned in Remark we set the step size Ç as ( = D
(cf. (I3) in the t-th iteration of the second step of Algorithm [ We compare our Algorithm T (denoted by MPRG) with the following methods: 1) The method proposed in (98), which is for misspecified phase retrieval with sparse priors and is denoted by MPRS. All the involved parameters are set to be the same as those in 198]. 2) Simply performing the first step of Algorithm [ Ti + T2 = 50 iterations. The corresponding method is denoted by PPower. The purpose of comparing PPower is to verify the benefit of the second step of Algorithm [ 3) Simply performing the second step of [ for Ti + T2 50 iterations. The corresponding method is denoted by Step2. The purpose of comparing to Step2 is to check whether the first step of Algorithm T is practically useful. 4) The Alternating Phase Projected Gradient Descent (denoted by APPGD) algorithm proposed in B7 This algorithm is specifically designed for phase retrieval with magnitude-on measurements (cf. and generative priors, and the corresponding iterative procedure
m
x (++1) = Pa (4)
Σ m
T
a (
Vi sign (a
xffx(() aj
(21)
where T >> O is the step size. We follow 37 to set 5 = 0.9. For a fair comparison, we use the vector produced after Ti- 20 iterations of the first step of Algorithm T as the initialization vector of APPGD, and then we run APPGD for T2 = 30 iterations.
We first consider the noisy magnitude-only measurement models for i [m].
|af x
+ +
(22)
=
a x + 7)1
(23)
8

---

where are i..d. realizations of an N00 o²) random variable. For such measurement model, the corresponding random nonlinear link function is f(z) | + or f(x) (0, )²). The numerical results for (22 and (3 are demonstrated in Figures a From these figures, we observe that the sparsity based method MPRS attains poor reconstructions, and the results of PPower are not desirable. The three methods Step2, APPCD, MPRG lead to similar reconstruction error, but the reconstructed images APPGD and MPRG are better than those Step2. In particular, our method MPRG leads to mostly accurate reconstructions that are competitive compared to those of APPGD, even if we do not make use of the knowledge of the link function and MPRG not specifically designed for the magnitude-on
71. where
measurement models.
7
2
O
4
4
S
9
7
2
4
4
9
9
&
0
6
3
$
5
7
2
0
4
9
9
7
4
2
G
4
4
0
2
4
4
9 9
5
2
0
4
3
6
9
2
0
4
4
9
S
4
2
O
4
1
7
2
0
4
4
7
(a)
22
with m 200 and a
(b)
23
with m
400 and
0.01
Figure 1: Examples of reconstructed MNIST images for the measurement models 22 and
MPRS
1.4
Reconstruction Error
1.4
PPower
Reconstruction Error
MPRS PPower
Step2
1.2
APPGD
Step2
APPGD
MPRG
1.0
1.0
MPRG
0.8
0.8
0.6
0.4
0.0
0.2
0.4
0.8
1.0
200
300
400
500
600
700
800
(a)
22
fixed m
400
(b)
23 with fixed
Figure 2: Quantitative comparisons of the performance for the measurement model
22 and 23
Next, we consider the following two measurement models:
y: = | x + tanh (| ||al x() + 7ss
(24)
2(a x)² + sin( a x|) + 77s-
(25)
where again γл are i.i.d. realizations of A (0, o²) random variable. For both models (24) and 25
the corresponding link functions satisfy the condition (8) for MPR [98]. The numerical results are presented in Tngures[aandy
We observe from these figures that for the measurement models (24)
and (25). our method MPRG achieves the best reconstructions. In particular, it outperforms APPGD in terms of recovery quality and/or reconstruction error.
Conclusion and Future Work
We have proposed two-step approach for phase retrieval under model misspecification and generative priors. We show that under suitable conditions, both steps of our approach obtain estimated vectors that achieve the near-optimal statistical rate of order /(k log L.) (log m)/m. where & is the latent dimension and the Lipschitz constant of the generative model respectively, and m refers the number of samples.

---

7
2
O
4
4
9
5
9
7
2
O
4
4
9
9
6
8
8
9
4
2
6
3
3
3
9
5
3
6
9
6
7
2
6
4
8
6
5
8
6
6
9
9
6
9
4
2
/
6
1
1
2
6
9 9
2
2
6
3
6
7
2
6
4
(a)
with 200 and a
0.01
with
300 and a
Figure 3: Examples of reconstructed MNIST images for the models in 24 and 25
MPRS
MPRS
Reconstruction Error
1.3
PPower
Reconstruction Error
PPower
Step2
1.2
1.2
APPGD
Step2
APPGD
1.1
MPRG
1.0
MPRG
1.0
0.9
0.8
0.7
0.4
0.0
0.2
0.4
0.6
0.8
1.0
200
300
400
500
600
700
800
0
(a)
(2 with fixed m = 200
(b)
25
with fixed o = 0.5
Figure 4: Quantitative comparisons of the performance for the measurement models in (24) and 25
We assume accurate projections in analysis and use gradient-basee based method approximate the projection step Pa(() our experiments. Although the exact projection assumption commonly 71 50,, it is very interesting future research direction to design proaabe-ggarranteed efficient methods for the projection step.
made in relevant works 779 37 38
In addition, we focus on real Gaussian measurements. While we believe that based the technical results in [62, [3] (which study complex Gaussian measurements). is straightforward extend work to the complex case, the extension to practical non-Gaus Ganssaansi measurement models such as sub-sampled Fourier measurements a very interesting future direction. Another direction is to use different preprocessing functions to enhance the performance of our spectral initialization method [56] 54 57 Moreover, one has the access to the nonlinear link function f. the Bayes- optimal performances
characterized using message- taatggeppssnngggg algorithms [5] 58, 3]. would be
interesting to connect or compare our results with the corresponding Bayes-optimal rate.
Acknowledgment. J. Liu was partially supported by NSFC Grant #1 #12288201 and the Fund of the Youth Innovation Promotion Association, CAS (2022002). We sincerely thank the five anonymous reviewers and area chair for their careful reading and helpful comments. We are extremely grateful to Dr. Jonathan Scarlett for proofreading the manuscript and giving valuable suggestions.
References
[1] E. Castro, E. J. Candes, and M. A. Davenport, "On the fundamental limits of adaptive sensing," IEEE Trans. Inf. Theory, vol. 59, no. 1, pp. 472-481, 2012
[2] M. Asim, M. Daniels, O. Leong, A. Ahmed, and P. Hand, "Invertible generative models for inverse problems: Mitigating representation error and dataset bias," in Int. Conf. Mach. Learn. (ICML... PMLR, 2020, pp. 399-409.
[3] B. Aubin, B. Loureiro, A. Baker, F. Krzakala, and L. Zdeborová, "Exact asymptotics for phase retrieval and compressed sensing with random generative priors," in Math. Sci. Mach. Learn. (MSML). PMLR, 2020, pp. 55-73.
10

---

[4] 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.
[5] Barbier, F. Krzakala, N. Macris, L. Miolane, and L.. Zdeborová, "Optimal errors and phase transitions in high-dimensional generalized linear models," PNAS, vol. 116, no. 12, pp. 5451- 5460, 2019.
[6] 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.
[7] J.-F. Cai, Y. Jiao, X. Lu, and You, "Sample-efficien sparse phase retrieval via stochastic alternating minimization," htpp::/auriv..rr/22112279999 2021.
[8] J. Cai, J. Li, X. Lu, and J. You. "Sparse signal recovery from phaseless measurements via hard thresholding pursuit," http:://arii..rg/ab/20000.333..
2020.
[9] J. Cai, M. Huang, D. Li, and Y. Wang. "Solving phase retrieval with random initial guess is nearly as good as by spectral initialization," https://urziv.or//bb/22 wtt.://rrrrab//1/1..330. 101.03540, 2021.
[10] T. Cai, Li, and Ma, "Optimal rates of convergence for noisy sparse phase retrieval via thresholded Wirtinger flow." Ann. Stat., vol. 44, no. 5. pp. 2221-2251, 2016.
[11] E. J. Candes and M. A. Davenport, "How well can we estimate sparse vector?" Appl. Comp. Harm. Analysis, vol. 34, no. pp. 317-323, 2013.
[12] E. J. Candes, C. Eldar, T. Strohmer, and V. Voroninski, "Phase retrieval via matrix completion," SIAM Rev, vol. 57, no. 2, pp. 225-251, 2015.
[13] E. J. Candès, X. Li, and M. Soltanolkotabi, "Phase retrieval via Wirtinger flow: Theory and algorithmss" " IEEE Trans. Inf. Theory, vol. 61, no. 4, pp. 1985-2007, 2015.
[14] E. J. Candès, T. Strohmer, and V. Voroninski, "PhaseLift: Exact and stable signal recovery from magnitude measurements via convex programming." Comm. Pure Appl. Math., vol. 66, no.
pp. 1241-1274, 2013.
[15] 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.
[16] 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.
[17] L. Cheng, P. Zeng, and Y. Zhu, "BS-SIM: An effective variable selection method for high- dimensional single index model," Electron. J. Stat., vol. 11, no. 2, pp. 3522-3548, 2017.
[18] Y. Deshpande, A. Montanari, and E. Richard, "Cone-constrained principal component analysis." Conf. Neur. Inf. Proc. Sys. (NeurIPS), 2014, pp. 2717-2725.
[19] M. Dhar, A. Grover, and S. Ermon, "Modeling sparse deviations for compressed sensing using generative models," " in Int. Conf. Mach. Learn. (ICML). PMLR, 2018, pp. 1214-1223.
[20] H. Eftekhari, M. Banerjee, and Y. Ritov, "Inference high-dimensional single-index models under symmetric designs," J. Mach. Learn. Res., vol. 22, pp. 27-1,
[21] J. R. Fienup. "Phase retrieval algorithms: A comparison," Appl. Opt., vol. 21. no. 15, pp. 2758-28 27692769,11 1982.
[22] J. C. Foster, J. M. Taylor, and B. Nan, "Variable selection in monotone single-index models via the adaptive Lasso," Stat. Med., vol. 32, no. 22, pp. 3944-3954, 2013.
[23] S. Foucart and H. Rauhut, Mathematical Introduction to Compressive Sensing. Springer New York. 2013.
[24] R. Ganti, N. Rao, R. M. Willett, and R. Nowak, "Learning single index models in high dimensions." htps://arziv.org//S5 (aarr///500.000 506.08910.. 2015.
[25] B. Gao, X. Sun, Y. Wang, and Z.. Xu, "Perturbed amplitude flow for phase retrieval," IEEE Trans. Sig. Proc., vol. 68, pp. 5427-5440, 2020.
[26] M. Genzel, "High- diigh-dimensional estimation of structured signals from non-lime non-linear observations with general convex loss functions," IEEE Trans. Inf. Theory. vol. 63, no. 3, pp. 1601-1619, 2016.
[27] R. Gerchberg, practical algorithm for the determination of phase from image and diffraction plane pictures," Optik, vol. 35, pp. 237-246, 1972.

---

[28] L. Goldstein, S. Minsker, and X. Wei, "Structured signal recovery from non-linear and heavy- tailed measurements," IEEE Trans. Inf. Theory, vol. 64, no. 8, pp. 5513-5530. 2018.
[29] T. Goldstein and C. Studer, "Phasemax: Convex phase retrieval via basis pursuit," IEEE Trans. Inf. Theory, vol. 64, no. 4, pp. 2675-2689, 2018.
[30] A. K. Han, "Non- parametric analysis of generalized regression model: the maximum rank correlation estimator," J. Econom., vol. 35, no. 2-3, pp. 303-316, 1987.
[31] Hand, O. Leong, and V. Voroninski, "Phase retrieval under a generative prior." in Conf. Neur Inf. Proc. Sys. (NeurIPS), 2018, pp. 9154-9164.
[32] P. Hand and V. Voroninski, "Global guarantees for enforcing deep generative priors by empirical risk," in Conf. Learn. Theory (COLT). PMLR, 2018, pp. 970-978.
[33] B. Hao, Y. Yadkori, Z. Wen, and G. Cheng, "Bootstrapping upper confidence bound," Conf. Neur. Inf. Proc. Sys. (NeurIPS), 2019.
[34] R. Heckel and P. Hand, "Deep decoder: Concise image representations from untrained non- convolutional networks," in Int. Conf. Learn. Repr. (ICLR), 2019.
[35] Horowitz, Semiparametric and nouparametric methods in econometrics. Springer, 2009,
vol. 12.
[36] M. Huang and Z. Xu, "The estimation performance of nonlinear least squares for phase retrieval," IEEE Trans. Inf. Theory, vol. 66, no. 12, pp. 7967-7977, 2020.
[37] R. Hyder, Shah, 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.
[38] G. Jagatap and C. Hegde, "Algorithmic guarantees for inverse imaging with untrained network priors," in Conf. Neur. Inf. Proc. Sys. (NeurIPS), vol. 32, 2019.
[39] G. Jagatap and C. Hegde, "Sample-efficient algorithms for recovering structured signals from magnitude-only measurements," IEEE Trans. Inf. Theory, vol. 65, no. 7, pp. 4434-4456, 2019.
[40] A. Jalal, Karmalkar, A. Dimakis, and F. Price, "Instance-optimal compressed sensing via posterior sampling," in Int. Conf. Mach. Learn. (ICMI.), 2021.
[41] A. Jalal, I.. Liu, A. G. Dimakis, and C. Caramanis, "Robust compressed sensing using generative models," " Conf. Neur. Inf. Proc. Sys. (NeurIPS), 2020.
[42] A. Kamath, Karmalkar, and Price, "On the power of compressed sensing with generative models," in Int. Conf. Mach. Learn. (ICML), 2020, pp. 5101-5109.
[43] 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.
[44] Y. LeCun, Bottou, Bengio, and P. Haffner, "Gradient-basee learning applied to document recognition," Proc. IEEE, vol. 86, no. 11, pp. 2278 2224, 1998.
[45] K.-C. Li and N. Duan, "Regression analysis under link violation," Ann. Stat., pp. 1059-1052, 1989.
[46] Liu and Z. Liu, "Non-iterative recovery from nonlinear observations using generative models."
in IEEE Comput. Soc. Conf. Comput. Vis. Pattern. Recognit. (CVPR), 2022, pp. 233-243,
[47] Z. Liu, S. Ghosh, and J. Scarlett, "Towards sample-optimal compressive phase retrieval with sparse and generative priors," in Conf. Neur. Inf. Proc. Sys. (NeurIPS), 2021.
[48] Z. Liu, S. Gomes, A. Tiwari, and J. Scarlett, "Sample complexity bounds for 1-bit compressive sensing and binary stable embeddings with generatiee priors," in Int. Conf. Mach. Leurn. (ICML), 2020.
[49] Z. Liu and J. Han, "Projected gradient descent algorithms for solving nonlinear inverse problems with generative priors," in Int. Jr. Conf. Artif. Intell. (IJCAI), 2022.
[50] Z. Liu, J. Liu, S. Ghosh, J. Han, and J. Scarlett, "Generative principal component analysis." in Int. Conf. Learn. Repr. (ICLR), 2022.
[51] Z. Liu and J. Scarlett, "The generalized Lasso with nonlinear observations and generative priors,"
in Conf. Neur. Inf. Proc. Sys. (NeurIPS), vol. 33, 2020.
12

---

[52] Z. Liu and J. Scarlett, "Information -eeerorttctt lower bounds for compressive sensing with generative models," IEEE J. Sel. Areas Inf. Theory, vol. 1, no. 1, pp. 292-303, 2020.
[53] Z. Liu, P. Luo, X. Wang. and X. Tang, "Deep learning face attributes in the wild," in Proc. IEEE Int. Conf. Comput. Vis. (ICCV), 2015, pp. 3730-3738.
[54] M. Lu and G. Li, "Phase transitions of spectral initialization for high-dimenniooal non-convex estimation," " Inf. Inference, vol. 9, no. 3. pp. 507-541, 2020.
[55] S. Luo and S. Ghosal, "Forward selection and estimation in high dimensional single index models," Stat. Methodol., vol. 33, pp. 172-179, 2016.
[56] W. Luo, W. Alghamdi, and Y. M. Lu, "Optimal spectral initialization for signal recovery with applications to phase retrieval," IEEE Trans. Sig. Proc., vol. 67, no. 9, pp. 2347-2356, 2019.
[57] A. Maillard, F. Krzakala, Y. M. Lu, and L. Zdeborová, "Construction of optimal spectral methods in phase retrieval," in Math. Sci. Mach. Learn. (MSML). PMLR, 2022, pp. 693-720.
[58] A. Maillard, B. Loureiro, F. Krzakala, and L. Zdeborová, "Phase retrieval in high dimensions: Statistical and computational phase transitions," Conf. Neur. Inf. Proc. Sys. (NeurlPS), vol. 33,
pp. 11 071-11 082, 2020.
[59] McCullagh and J. Nelder, Generalized linear models. Routledge, 2019.
[60] S. Menon, A. Damian, S. Hu, N. Ravi, and C. Rudin, "Pulse: Self-supervised photo upsampling via latent space exploration of generative models," in IEEE Comput. Soc. Conf. Comput. Vis. Puttern. Recognit. (CVPR), 2020, pp. 2437-2445.
[61] M. Mondelli and A. Montanari, "Fundamental limits of weak recovery with applications to phase retrieval," in Conf. Learn. Theory (COLT). PMLR, 2018, pp. 1445-1450.
[62] P. Netrapalli, P. Jain, and S. Sanghavi, "Phase retrieval using alternating minimization," IEEE Trans. Sig. Proc., vol. 63, no. 18, pp. 4826 2015.
[63] M. Neykov, J. S. Liu, and T. Cai, " "Lg-regularized least squares for support recovery of high dimensional single index models with Gaussian designs," J. Mach. Learn. Res., vol. 17, 1, pp. 2976-3012 2012,,0122222200 2016.
[64] M. Neykov, Z. Wang, and H. Liu, "Agnostic estimation for misspecified phase retrieval models," J. Mach. Learn. Res., vol. 21, pp. 1-39, 2020.
[65] T. V. Nguyen, Jagatap, and C. Hegde. "Provable compressed sensing with generative priors via Langevin dynamics," https///arii.org2200212666 2021.
[66] H. Ohlsson, A. Yang, R. Dong, and S. Sastry, "CPRL-An extension of compressive sensing to the phase retrieval problem," Conf. Neur. Inf. Pruc. Sys. (NeurIPS), vol. 25, pp. 1367-1375, 2012.
[67] 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 Sel. Areas Inf. Theory, vol. 1, no. 1, pp. 39-56. 2020.
[68] S. Oymak and M. Soltanolkotabi, "Fast and reliable parameter estimation from nonlinear observations," SIAM Optim., vol. 27, no. 4, pp. 2276-2300, 2017.
[69] A. Pananjady and D. P. Foster, "Single-index models in the high signal regime," IEEE Trans. Inf. Theory, vol. 67, no. 6, pp. 4124, 2021.
[70] E. J. R. Pauwels, A. Beck, C. Eldar, and S. Sabach, "On fienup methods for sparse phase retrieval," JEEE Trans. Sig. Proc., vol. 66, no. 4, pp. 982-991, 2017.
[71] P. Peng, S. Jalali, and X. Yuan, "Solving inverse problems via auto-encoders," IEEE J. Sel. Areas Inf. Theory, vol. 1, no. 1, pp. 312-323, 2020.
[72] Y. Plan and Vershynin. "The generalized Lasso with non- non-linear observations," IEEE Trans. Inf. Theory, vol. 62, no. 3, pp. 1528-1537, 2016.
[73] Y. Plan, R. Vershynin, and E. Yudovina, "High-dimensional estimation with geometric con- straints," Inf. Inference, vol. 6, no. 1, pp. 1-40, 2017.
[74] Radchenko, "High dimensional single index models," J. Multivar. Anal., vol. 139, pp. 266-282, 2015.
13

---

[75] A. Raj, Y. Li, and Y. Bresler, "GAN-based projector for faster recovery with convergence guarantees in linear inverse problems," in Proc. IEEE Int. Conf. Compur. Vis. (ICCV), 2019.
[76] Rick Chang, C.-L. Li, B. Poczos, B. Vijaya Kumar, and A. C. Sankaranarayanan, "One network to solve them all-solving linear inverse problems using deep projection models," in Proc. IEEE Int. Conf. Comput. Vis. (ICCV), 2017, pp. 5888-5897.
[77] J. Scarlett and V. Cevher, "Limits on support recovery with probabilistic models: An information- theoretic framework," " IEEE Trans. Inf. Theory, vol. 63, no. 1, pp- 593-620, 2016.
[78] Scarlett, R. Heckel, M. R. Rodrigues. P. Hand, and Y. C. Eldar, "Theoretical perspectives on deep learning methods in inverse problems," https://arxivorr/222000 /4373, 2022.
[79] 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. 4609-4613.
[80] 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.
[81] R. Sherman, "The limiting distribution of the maximum rank correlation estimator," Econo- metrica, pp. 123-137, 1993.
[82] M. Soltanolkouabi, "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.
[83] J. Sun, Q. Qu, and J. Wright, "A geometric analysis of phase retrieval," Found. Comput. Math., vol. 18, no. 5, pp. 1131-1198, 2018.
[84] C. Thrampoulidis, E. Abbasi, and B. Hassibi, "Lasso with non-linear measurements is equivalent to one with linear measurements," in Conf. Neur. Inf. Proc. Sys. (NeurIPS), 2015, pp.
[85] 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," https://arriioor///88..0444 2018.
[86] R. Vershynin, "Introduction to the non-asymptotic analysis of random matrices,"
https://urrivoor//b///011111 1.00100/ 2010.
[87] R. Vershynin, High-dimenssionll probability: An introduction with applications in data science. Cambridge university press, 2018, vol. 47.
[88] M. J. Wainwright, and noisy setting," IEEE Trans. Inf. Theory, vol. 55, no. 12, pp. 5728-5741, 2009.
iintormmatiintthooreeee limits on sparsity recovery in the high-dimensional
[89] M. J. Wainwright, High-dimensional statistics: A non-asymptotic viewpoint. Cambridge University Press, 2019, vol. 48.
[90] I. Waldspurger, A. d' Aspremont, and S. Mallat, "Phase recovery, maxcut and complex semidefi- nite programming," Math. Program., vol. 149, no. 1, pp. 47-81, 2015.
[91] 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.
[92] 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.
[93] X. Wei, "Structured recovery with -tavedt measurements: A thresholding procedure and 05959, 2018
optimal rates," httpss//arxivoor/abbbb/
[94] X. Wei, Z. Yang, and Z. Wang, "On the statistical rate of nonlinear recovery in generative models with heavy-tailed data," in Ini. Conf. Mach. Learn. (ICML), 2019, pp. 6697-6706.
[95] J. Whang, Q. Lei, and A. G. Dimakis, "Compressed sensing with invertible generative models and dependent noise," htpp://arsiv.or/2003...o
2020.
[96] Y. Wu, M. Rosca, and T. Lillicrap. "Deep compressed sensing," in Int Conf. Mach. Learn. (ICML). PMLR, 2019, pp. -860-
[97] Z. Yang. K. Balasubramanian, and H. Liu, "Highh-imenniooall non-Gaussian single index models via thresholded score function estimation," in Int. Conf. Mach. Learn. (ICML). PMLR, 2017, pp. 3851-3860.
14

---

[98] Z. Yang, L. F. Yang, E. X. Fang, T. Zhao, Z. Wang, and M. Neykov, "Misspecified nonconvex statistical optimization for sparse phase retrieval," Math. Program., vol. 176, no. pp. 545-571, 2019.
[99] 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.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] The limitations are relevant to our future work, described in Section
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (cither in the supplemental material or as a URL)? [Yes] The code is included in the supplementary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "wUN_QqPkOrt", "reviewer": "Reviewer_NiZz", "summary": "The paper considers the problem of recovering a signal $x \\in \\mathbb{R}^n$ from $m$ measurements corresponding to a single index model of the form $y_i = f(a_i^\\top x)$. Here, $a_i\\in \\mathbb{R}^n$ are sensing vectors and $f:\\mathbb{R} \\rightarrow \\mathbb{R}$ is an unknown (may be random) non-linear function. The single index model encompasses the classical phase retrieval problem $y_i = |a_i^\\top x| +\\eta$ (among others), where $\\eta$ is noise. Under the assumption on $f$ that $(a^\\top x)^2$ and $y$ have non-null covariance, $x$ is in the range of a $L$-Lipschitz generative model $G:\\mathbb{R}^k \\rightarrow \\mathbb{R}^n$ and suitable randomness on $a_i$ and $y_i$, the paper studies a two-stage algorithm for recovering $x$ given $(y_i )_{i=1}^m$ and $G$: the first step provides an initial estimate of $x$ using spectral methods and the second step iteratively refines this estimate by solving a related linear recovery problem using a descent-type method and projecting onto the range of the generator at each iteration.", "questions": "- Algorithm 1 part 1 uses the matrix V to get the initialization for part 2. Could you provide a intuition on what V is (or what the action of V on an arbitrary vector gives)?\n\n- Figure 1a shows denoising property of your algorithm. Does the decay in reconstruction error match the theorem of $C/\\sqrt{m}$ (for a fixed k)?\n\n- The paper focuses on the case where the exact form of $f$ is not known. This is true for the numerical experiments presented as well. How would recovery of the MNIST images change if $f(x) = |x|$ and this information was used? (for example using the algorithms in [71] or [30]). Comparison of to these methods would be interesting.\n\n\n", "limitations": "The paper adequately addresses its limitations. \n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper studies an interesting problem.\n- The paper builds on existing work on projected power method to obtain an estimate and introduces a new scheme to refine the estimate.\n- The paper provides a statistically optimal rate of recovery on the order of $\\sqrt{k/m}$ with near-optimal sample complexity of $O(k\\log(L)\\log(m))$.\n\nWeakness:\n\n- The paper is not clearly written. For example:\n\t- In the abstract, the notation Cov[.,.] should explained before using it.\n\t- In line 22, the \"For example\" line provides example of works that study methods of solving the phase retrieval problem while referencing (to the previous sentence) to applications of phase retrieval instead. \n\t- In line 31, the authors state that norm of $x$ is absorbed in SIM without an explanation (maybe stating that the problem is only well-defined up to that norm scaling would be beneficial to the readers).\n\t- The paper starts by associating Compressed Sensing unambiguously with the case where the underlying signal is sparse. However, this is misleading as the prior on signal can be arbitrary but low dimensional and the signal recovery problem can still be referred to as compressed sensing.\n\n- The paper considers the case where the measurement matrix is random gaussian. A discussion on viability (or lack-thereof) of the proposed algorithm on a more realistic measurement models like sub-sampled Fourier would be useful for the readers.\n\n- The paper provides limited discussion on the projection onto the range of the generative model under the conditions required for Theorem 2. That is, under the conditions like $L$-Lipschitz generative model, is there a guarantee that gradient based method as used in the experiment in the paper will converge to the global minimum/minima? \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "qYOA7I0tli8", "reviewer": "Reviewer_VWWv", "summary": "The goal is to recover signals under the misspecified phase retrieval model, where measurements are generated $y_i = f(a_i^T x)$, $i = 1 \\ldots m$, for i.i.d. Gaussian $a_i \\in \\mathbb{R}^n$, for $x$ generated by an $L$-lipschitz generative model, and for an unknown link function $f$. If $f$ satisfies the criteria $\\text{Cov}_{g = a^Tx}[f(g), g^2] \\not = 0$, then the proposed algorithm can be used to recover $x$ at order $O((k \\log L) \\cdot (\\log m))$ measurements, conjectured to be near-optimal. This assumption is natural for the MPR problem as it captures any nonzero correlation between the misspecified measurements and the phaseless measurements in the correctly-specified phase retrieval model. \n\nThe proposed algorithm has two steps. The first step estimates the principal component of\n\n $V = \\frac{1}{m} \\sum_{i=1}^m y_i (a_i a_i^T - I_n)$, for which $\\mathbb{E}_{a\\sim \\mathcal{N}}[V] = \\nu x x^T$. The second step views misspecified phase retrieval as a conventional SIM with measurements $\\tilde{y}_i = (y - \\mathbb{E}[y])(a^T x)$, applying a projected gradient based method to iteratively improve the estimate from the first step. Both of these steps can be applied independently to solve MPR separately, with the first having weaker initialization assumptions. The authors find empirically that the second step improves estimates provided by the first step. Additionally, they prove that the first and second steps enjoy near-optimal statistical rates, and that the second step converges exponentially fast to an estimate below the guaranteed statistical error threshold.", "questions": "- In experiments using approximate projections onto the range of pretrained GANs, how quickly does step 2 converge? Is it that Theorem 2 holds approximately in experiments using approximate projections?\n- What is the recovery performance when step 2 is run with initialization $\\mathbf{w}^{(0)}$, the column with the largest diagonal entry in $\\frac{1}{m} \\sum_{i=1}^m y_i a_i a_i^T$? In other words, what is the performance of the combination step 1+2 relative to the performance of step 2 only? Is step 1 required to satisfy the initialization requirements for step 2, in practice? This question is related to my concern about the strictness/weakness of Theorem 2 assumptions.", "limitations": "- The method requires exact projection onto the range of a generator function. However, this seems to be a standard assumption in the literature, for which approximate methods work well.\n- It is unclear whether the recovery condition in Theorem 2 is strict or mild. However, the benefit of step 2 is clearly beneficial empirically, whether or not Theorem 2 can be satisfied.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n- Theorems 1 and 2 are clearly stated and relevant to the empirical problem. I did not find any obvious errors while reviewing their proofs.\n- Theorem 1 seems to be a small, but original and valuable contribution relative to [45] and [47]. The authors establish in Lemma 6 a bound on the error $E = V - \\nu x x^T$, thereby controlling the misspecification error for the MPR problem. Following from the results of [47], Lemma 6 implies the estimation rate for step 1, giving theoretical justification to the practical method introduced in [45].\n- To the best of my knowledge, exponential converge attained by Theorem 2 is original and valuable. Some results in the S-REC framework [5, 48] show that global optimizers of a certain non-convex objective achieve low estimation error, _without_ proving that this non-convex objective can be efficiently optimized. Therefore it is interesting that the gradient-based approach of step 2 has exponential convergence above the statistical error level.\n- Empirical evaluations clearly demonstrate the significant benefit of the second step of the algorithm.\n- Empirical evaluations are favorable to MPRG (proposed), which performs better than or on-par with alternative methods.\n\nWeaknesses: \n\n- It’s difficult to know the practical significance of the initialization requirements for Theorems 1 and 2, particularly the latter. Regarding theorem 1, Remark 2 is a convincing argument that the Theorem 1 requirement is mild. However, it’s unclear whether (18) is strict or mild, and whether there is any reason to believe it holds approximately in practice.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "miOX_i6vhL", "reviewer": "Reviewer_YJ4f", "summary": "This work proposes a two-step algorithm for solving the misspecified phase retrieval problem. The algorithm is constructed based on two key assumptions:  a) the $m$ (possibly noisy) observations $y_{i}$ are generated by a single-index model $y_{i} = f(a_{i}^{\\top}x)$ (a.k.a. generalised linear model) with $a\\sim\\mathcal{N}(0,I_{n})$, but *crucially* the statistician does not has access to the link function $f$ -  she only knows that the observations $y$ correlate with $(a^{\\top}x)^2$; b) the signal $x$ is drawn from a *known* generative prior, i.e. $x=G(z)$ where $G:B(r)\\to\\mathcal{S}^{n-1}$ is $L$-Lipschitz and $z\\in B(r)\\subset\\mathbb{R}^{k}$ is a latent representation ($B(r)$ is the ball radius $r$ and $\\mathcal{S}^{n-1}$ the unit sphere). The algorithm consists of a spectral initialisation-type step, based on a projected power method, plus a descent-like step.\n\nThe main theoretical contributions are:\n\n1. A bound on the reconstruction performance of the first step, stating that for sufficiently enough data $m = \\Omega(k\\log(nLr))$, the first step achieves near-optimal reconstruction performance $O(\\sqrt{k\\log(nLr)/m})$ (up to a log factor in $m$) with probability $1-O(1/m)$ (Theorem 1).\n2. A bound on the reconstruction performance showing that for a suitable learning rate and warm initialisation (the reason why step 1 is required), the second step achieves near-optimal reconstruction with probability $1-O(1/m)$ for sufficient data $m = \\Omega(k\\log(nLr))$ (Theorem 2)\n\nNumerical simulations with real datasets, different link functions and with trained generative models are used to illustrate the performance of the proposed algorithm, and to compare it with other methods in the literature. ", "questions": "-**[Q1]**: The information about the generative model only appears in the bounds eqs. (17) and (18) through the Lipschitz constant $L$ and the radius $r$ (in particular their product $Lr$). Can the authors provide some intuition on how these quantities are connected with the expressiveness of the prior? For instance, for a fixed generative model architecture, how $L$ changes from random initialisation throughout the training? Can this result be used to help us choosing a specific prior for a given task?\n\n-**[Q2]**: The bounds in Step 1 eq. (17) and Step 2 eq. (20) scale in the same way with the quantities $(L, r, m, n, k)$ involved in the problem. Is it clear that performing Step 2 always improve over Step 1 (i.e. $\\beta_{2}>\\beta_{1}$)? If not, did the authors observe any example in which Step 2 after Step 1 hurts reconstruction?\n\n-**[Q3]**: In which sense is the rate $\\sqrt{(k\\log{L})(\\log{m})/m}$ near-optimal? For a given generative prior, say a fully connected random network, how does this compares with the Bayes-optimal rate derived in [3]?\n\n-**[Q4]**: How would the algorithm perform in the matched case, where the statistician would have access to the exact link function $f$ generating the observations $y$ (i.e. we could let $\\hat{\\nu}^{t}\\to \\nu$)? Can a tighter bound be derived for this case? Would it consistently beat APPGD?\n\n-**[Q5]**: It would be interesting to have also an experiment with the link $y=|a^{\\top}x + \\eta|$ in Sec. 5, which is relevant to some experimental settings where $y\\geq 0$.", "limitations": "Some limitations of this work are discussed, e.g. the fact that the theoretical guarantees assume exact knowledge of the projection $\\mathcal{P}_{G}$ which in practice needs to be approximated and the choice of step size $\\zeta$ for Step 2, which in practice also needs to be estimated by $1/\\hat{\\nu}^{t}$.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Phase retrieval is an important problem naturally arising in different signal processing tasks from science and engineering [SEC+]. Although it is not very different from linear reconstruction problems from the point of view of information theory (both require $m\\approx n$ samples for statistically reconstructing a Gaussian signal [MLK+]), it is a notably harder problem computationally. Therefore, designing algorithms that exploit structure in the signal for efficient reconstruction is a significant endeavour.\n\nWhile many works have approached this problem by deriving algorithms for sparse signals (c.f. [SEC+] for a review), a more recent line of work have investigated the setting where the signal is drawn from a generative model, typically parametrised by a deep neural network (e.g. VAEs, GANs, etc.) [30], with promising computational advantages. This paper builds on this line, with the main difference with respect to the literature being the \"misspecified\" setting, i.e. the algorithm proposed does not rely on the knowledge of a particular link function for the observation likelihood.\n\n**Strengths**:\nThe contribution is timely and well-placed within the literature. As discussed above, phase retrieval is a challenging computational problem relevant to different fields. Therefore the design of efficient algorithms that exploit structure with theoretical guarantees is a significant contribution to this line of work.\n\n**Weaknesses**:\nThis work heavily builds on previous contributions - the algorithm proposed is a combination of methods from the literature (projected power method [45, 47] and projected descent [70]). While I don't think this is a problem per se, this makes the presentation hard to parse for a reader who is not familiar with this literature. For instance, the authors could discuss better where the proposed algorithm comes from, and provide some intuition for Steps 1 & 2. The authors could also be more explicit about what information is assumed to be known to the statistician in the derivation of the algorithm (the term \"misspecified\" is not very precise, and can mean different things in statistics).\n\n**References** (numbered refs. are from the bibliography in the paper)\n\n[SEC+] Y Shechtman, YC Eldar, O Cohen, HN Chapman, J Miao, M Segev, *Phase Retrieval with Application to Optical Imaging: A contemporary overview*, in IEEE Signal Processing Magazine, vol. 32, no. 3, pp. 87-109, May 2015.\n\n[MLK+] A Maillard, B Loureiro, F Krzakala, L Zdeborová, *Phase retrieval in high dimensions: Statistical and computational phase transitions*, NeurIPS 2020.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "jgyU9ZueFcS", "reviewer": "Reviewer_nWLU", "summary": "The authors study a single index model (SIM) for observations of the form $y = f(ax)$, with $f$ being unknown nonlinear function, $a$ is Gaussian, and $Cov[y,(ax)^2] \\neq 0$. This is also referred as Misspecified phase retrieval (MPR). The inverse problem is solved under the assumption that $x$ has a generative prior. The overall algorithm is a two step approach which utilizes a spectral type initialization, followed by projected iterative descent rule using this initialization. The algorithm is validated via numerical simulations.", "questions": "Can the condition $x^T w^{t_0} > c_0$ be experimentally validated? What does $c_0$ typically look like under finite sampling.\n\nWhat are some classes of functions $f$ that would satisfy $y = f(ax)$ being subexponential? The paper would benefit from additional discussion on the link function $f$.\n\nWould the theoretical arguments fall through for non-Gaussian measurements? ", "limitations": "Authors have made useful references to papers with potential overlap, as well as provided discussions on the limitations of their assumptions which is good.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n-Use of generative priors in the context of misspecified phase retrieval (MPR) under new set of assumptions.\n\n-Theoretical assumptions and remarks are well presented.\n\nWeaknesses:\n\n-Not enough motivating discussion on why one needs to study Misspecified phase retrieval (largely left to reference papers). \n\n-Gaussian measurements are not practical. \n\n-Strong theoretical assumptions. Requires $x^T w^{t_0} > c_0$. \n\n-How is $x^T w^{t_0} > c_0$ a weaker requirement than closeness of initialization requirement $\\||x-w^{t_0}\\|| < \\delta \\||x\\||$ (for which spectral initialization is typically used)? \n\n-Sample complexity comparison is unfair if $x^T w^{t_0} > c_0$ is used. Given proper initialization, even prior methods incur O(k) samples for generative priors or O(s) for sparse priors. \n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7aHXDd-oStf", "reviewer": "Reviewer_c4oX", "summary": "This work considers the phase retrieval problem. In this model, the statistician is given \n$m$ i.i.d. observations of $y = f(\\mathbf{a}^T \\mathbf{x})$, in which $\\mathbf{a} \\sim \\mathcal{N}(0,\\mathrm{I}_n)$, and $\\mathbf{x} \\in \\mathbb{R}^n$ (the vector to recover) is assumed to be generated using a generative \nprior $G : \\mathbb{R}^k \\to \\mathbb{R}^n$ (typically with $k \\ll n$).\nCrucially, she does not know the function $f$, a setting which the authors call misspecified phase retrieval.\nUnder the following fairly general condition on the function $f$: $\\mathrm{Cov}[f(g), g^2] \\neq 0$,\nfor $g \\sim \\mathcal{N}(0,1)$, the authors develop in Section 3 an algorithm that is agnostic to the function $f$, and that is made of two steps: \n- First, a general spectral method on a well-chosen matrix, mixed with a projection on the range of the generative model.\n- Secondly, a simple iterative algorithm approximating procedures used in other single-index models, again completed with a projection step.\n\nIn Section 4, the authors provide two theorems giving guarantees on the performance of each step of the algorithm described above, \nand argue that under certain conditions they reach near-optimal performance.\n\nFinally, the authors provide numerical experiments in Section 5 to illustrate how their procedure performs with respect to some previous algorithms.\n\nPlease note that given the length and available time, I did not check in full detail the proofs given in the supplementary material, and only read them superficially.\nI also read the Section D of the supplementary on additional numerical experiments. However, I did not look at the provided code. ", "questions": "1. From my understanding, the condition $\\mathrm{Cov}[f(g), g^2] \\neq 0$ is crucial for the spectral method, since it ensures that for $m$ large enough, an isolated eigenvalue \n(with eigenvector in the direction of $\\mathbf{x}$) pops out in the spectrum of $\\mathbf{V}$. Is this the only point in which this condition is necessary? \nThis point should be discussed in relation with another question I have on the spectral method used, see below.\n\n2. The paper does not discuss a recent literature on spectral methods for phase retrieval,\ncf. e.g. [3-6] for studies in the case of Gaussian vectors $\\mathbf{a}_i$.\nIn particular, [4,6] shows that, in the case in which $f(g)$ is known and $\\mathbf{x}$ does not come from a generative prior, \nthe optimal spectral method is as in $(10)$, in which $y_i$ is replaced by a function $T^\\star(y_i)$, with e.g.\\ $T^\\star(y) = 1 - y^{-1}$ for noiseless magnitude observations. Moreover, \nin this case, recovery can be achieved for $m = \\Theta(n)$, rather than $m = \\Omega(n \\log^2 n)$ given by Theorem 1 here.\nWhile this setting has significant differences from the one considered here (in particular $T^\\star(y)$ is not accessible), maybe the authors should also consider the impact of the use of different functions $T(y) \\neq y$ in the spectral method.\nThis might allow interesting comparisons with the literature mentioned, potentially improve drastically the performance of the method, as well as maybe relaxing the main condition assumed on $f(g)$ (see my point 1)?\n\n[3] Mondelli, M., \\& Montanari, A. (2018, July). Fundamental limits of weak recovery with applications to phase retrieval. In Conference On Learning Theory (pp. 1445-1450). PMLR.\n\n[4] Luo, W., Alghamdi, W., \\& Lu, Y. M. (2019). Optimal spectral initialization for signal recovery with applications to phase retrieval. IEEE Transactions on Signal Processing, 67(9), 2347-2356.\n\n[5] Lu, Y. M., \\& Li, G. (2020). Phase transitions of spectral initialization for high-dimensional non-convex estimation. Information and Inference: A Journal of the IMA, 9(3), 507-541.\n\n[6] Maillard, A., Krzakala, F., Lu, Y. M., \\& Zdeborová, L. (2022, April). Construction of optimal spectral methods in phase retrieval. In Mathematical and Scientific Machine Learning (pp. 693-720). PMLR.\n\n3. If the statistician has access to $f$, the Bayes-optimal performances has been characterized using message-passing algorithms\nin detail in [7-9] (in particular [9] tackles the case of generative models, and is mentioned in the paper).\nDo the authors know how this Bayes-optimal error compares to the ones obtained in Figures 2 and 4? \nIt would be interesting to compute it, to gauge the influence of two effects: ($i$) the gain offered by the knowledge of $f$, and $(ii)$ the gain offered by the use of the generative model (e.g. by comparing the Bayes-optimal performance without a generative prior to the one reached by MPRG -- which is agnostic to $f$ and uses generative priors). In general, I believe the paper would benefit from discussing more the practical influence of the structure induced by the generative prior on the reconstruction error.\n\n[7] Barbier, J., Krzakala, F., Macris, N., Miolane, L., \\& Zdeborová, L. (2019). Optimal errors and phase transitions in high-dimensional generalized linear models. Proceedings of the National Academy of Sciences, 116(12), 5451-5460.\n\n[8] Maillard, A., Loureiro, B., Krzakala, F., \\& Zdeborová, L. (2020). Phase retrieval in high dimensions: Statistical and computational phase transitions. Advances in Neural Information Processing Systems, 33, 11071-11082.\n\n[9] Aubin, B., Loureiro, B., Baker, A., Krzakala, F., \\& Zdeborová, L. (2020, August). Exact asymptotics for phase retrieval and compressed sensing with random generative priors. In Mathematical and Scientific Machine Learning (pp. 55-73). PMLR.\n\n4. In Remark 2: while I see that one might assume all coordinates of $\\mathbf{x}$ to be positive, \ncould the authors clarify why they can assume that $\\mathbf{w}^t$ has only positive coordinates? \n\n5. This paper only considers real phase retrieval. Can the authors comment on the possibility of extension of their work to the (more relevant for many applications) complex case? It is likely that the results extends quite straightforwardly, which would be interesting to mention.\n\n6. Finally, I found the following typos: \n- Line 58: ``seminar work''\n- Line 73: ``an SIM''\n- Line 79: ``an $l_1$ regularized least square''\n- Line 219: ``all non-negative vectors''?\n- In Theorem 2, there is no mention of $\\beta_1$ in both eqs. (19) and (20), some $\\beta_2$ must surely be changed to a $\\beta_1$ (at the end of (19) and in (20) ?)\n- Line 698 (supplementary): ``there exists such a net with the cardinality satisfies''", "limitations": "Nothing to signal on societal impacts. On limitations of this work and how the authors address them, see the previous points.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- I found the paper overall very well organized, as well as well-written and pleasant to read, and I thank the authors for that.\nIn general, the results are quite clearly stated and discussed.\nMoreover, the limitations of the results are not hidden and well discussed, e.g. the projection step in the algorithm that needs to be approximated, \nthe Lipschitz condition on the generative model, the ``informative initialization'' assumption required in Theorem 1, or the additional $\\log m$ in the rates obtained with respect to the optimal ones.\n\n- The numerical results are well-presented and convincing. While the improvements over APPGD or the pure spectral method are small, \nthey seem to be significative.\n\n- On the other hand, the initialization condition of Theorem 1 seems quite limiting: it basically assumes weak recovery of the signal, while usually spectral methods are used to obtain such a weakly-correlated estimator. The theorem only covers how the method improves from weak to strong correlations. While this does not seem to be an issue in practice (if I understood correctly, the authors do not force such a weak correlation to exist in the numerical simulations), it limits the scope of Theorem 1. \n\n- Another criticism I have is that, from a non-specialist viewpoint, the results seem somehow incremental with respect to [1]: while I was not familiar with this paper before, a rapid read suggests that perhaps the main addition of the present paper is to consider generative models, which in the end only leads to minor changes in the algorithm with respect to Algorithm 1 of [1].  Moreover, the analysis of the spectral method relies on results of [2], and is quite classical in my eyes. Perhaps the authors should discuss more the novelties of this work with respect to such previous analyses (e.g. by an exploration of the gains offered in practice by generative priors, see also my question below).\n\n[1] Neykov, M., Wang, Z., \\& Liu, H. (2020). Agnostic estimation for misspecified phase retrieval models. The Journal of Machine Learning Research, 21(1), 4769-4807.\n\n[2] Liu, Z., Liu, J., Ghosh, S., Han, J., \\& Scarlett, J. (2022). Generative principal component analysis. arXiv preprint arXiv:2203.09693.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept