Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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. 
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. 

+ The paper presents analysis of spectral initialization with generative prior-based constraints. This is an interesting contribution. 

 - The paper also presents analysis for sparse phase retrieval and includes experiments and comparison with existing methods. 

- 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. 

- Overall, the paper is well written. 
limitations_and_societal_impact: - Very little discussion on limitations.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.

Additionally 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.

The 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. 

Spectral 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$).

They also show similar guarantees for the case of deep generative priors.
main_review: The main claims and contributions of this paper are as follows:

1. existence of a solution to the CPR problem using O($k \log L$) samples within small error margin. [Theorem 1]
2. spectral initialization for CPR with deep generative priors (only theoretical, no experiments)
3. 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]
4. improved sample complexity for spectral initialization in sparse phase retrieval. [Theorem 3]

[Theorem 1]
Authors 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.

[Theorem 3]
Spectral 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). 

[Theorem 2]
The 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.

[SPCA for initialization]
Authors use off the shelf SPCA solvers such as GRQI and TPower methods to solve the spectral initialization problem.

The paper is very well written, contributions are clearly highlighted and literature review is excellent. The results and derivations for sparse phase retrieval are convincing. 

The 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. 

It 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. 
limitations_and_societal_impact: Limitations: No experiments on CPR using spectral initialization for signals with deep generative prior.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Summary:

This 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.
main_review: __Strengths__:
1. All results and assumptions are stated clearly.

1. 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.

1. 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).

1. 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.

__Weaknesses__:

1. 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.

1. The novelty in the spectral initialization is unclear. Is it exactly the same as [66]?

1. [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?

1. 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.

__Novelty__:

The spectral initialization used in this paper is derived from [66]. 

From 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.

__Score Justification__:

I 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.

__General comments__:
1. 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).

1. 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.
Also, what does this assumption imply for the Lipschitz constant $L$? Does it need to be $1/r$?

1. 
limitations_and_societal_impact: I do not have concerns about the social impact of this work as it is primarily theoretical.
review_title: null

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)