Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies the asymptotics of the AMP algorithms with PCA initialization.
main_review: I am very sorry that I do not have enough time to spend on this paper especially to go through the long appendix. But I do have concerns about the significance of the contribution.
1) It is unclear to me why the paper only studies the rank-1 PCA rather than rank-k PCA. It is great to see that the symmetric condition can be relaxed and the results hold for the asymmetric matrix but the rank-1 condition is a very strong condition.
2) The $u_t$ function in (3.2) is assumed to be continuously differentiable and Lipschitz. This is a standard assumption in AMP literature. However, for some applications of this work like phase retrieval, the $u_t$ function may not be differentiable everywhere depending on the loss function. It would be great to extend the assumption on $u_t$ to tolerate some non-differentiable points.
3) It would be great to have a section to discuss which application requires a PCA initialization with an AMP algorithm. The only application I know of is phase retrieval. In general, only the non-convex problems require special initialization and hence PCA initialization might be required. Also, we need the AMP algorithm to perform well on the non-convex problem with PCA initialization. These conditions quite limit the potential applications.

In summary, it seems to be a borderline paper or slightly below average to me.
limitations_and_societal_impact: This is a theoretical paper. I think the main limitation is what are the possible applications to the theorems.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the problem of estimating a signal from its noisy rank-1 measurement. PCA is a traditional method that can be used for this task. AMP is an alternative that can additionally leverage statistical priors on the unknown signal. AMP algorithms are traditionally analyzed using a scalar iteration known as state evolution (SE).

The focus of this paper is to theoretically establish SE for AMP under a more general noise matrix starting from an initialization using PCA. Having SE enables the analysis of the error behaviour of AMP in different settings. Empirical results focus on comparing AMP+PCA against PCA on simulated data.

Theoretical contributions: The paper develops a new AMP algorithm initialized using PCA. Theorem 1 and 2 are the main theoretical results in the paper that establish SE for the proposed algorithm for square-symmetric and rectangular matrices.

Empirical contribution: Validation of the superiority of AMP on simulated data over PCA. 
main_review: General comment: While I am familiar with AMP and SE, I am not an AMP researcher and thus have only loose familiarity with corresponding literature. My review thus should be weighted against others who have deeper expertise in AMP/SE. On the other hand, my review provides valid feedback from someone with expertise in optimization and ML.

Strengths: Generalizing the AMP and its analysis to rotationally invariant matrices can lead to new insights into AMP and its usage for statistical estimation from rank-1 measurements. The theorems show that one can establish SE for new AMP algorithms, which is also promising. Simulations highlight the benefit of AMP over PCA when leveraging structure on the signal. 

Issues: (1) A persistent issue in the AMP literature is the lack of applications on real data analysis. This paper follows this trend and limits itself to validating the theory on synthetic experiments. In fact, this is a major issue that is often overlooked in theoretical papers, but which limits the significance of the results to data analysis. (2) Empirical validation limits comparisons to PCA. Why not compare to prior AMP methods for estimating from noisy rank-1 matrices (even when there is a mismatch in the noise distribution)? (3) How tolerant is the theoretical analysis to deviations from the assumptions? Which assumptions are more important than others? The assumptions in the manuscript are often presented in a scattered form within other assumptions or paragraphs of text, which reduces clarity.

Summary: For someone not deeply familiar with the theoretical work on AMP, this paper seems to be proposing a novel algorithmic extension and proving that SE is applicable to that extension. As with most prior work on AMP, the method is never used for actual data analysis, but validated on a contrived set of simulations. In short, I think this paper could be of value to AMP researchers, but its potential to broader ML and data science has not been demonstrated. 
limitations_and_societal_impact: No issues with this.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The submitted paper addresses estimation of rank-1 matrices from observations (1.1) or (1.2) subject to rotationally invariant noise matrix W. The paper proposes approximate message passing (AMP) with long memory Onsager correction (3.2) in the square case or (3.10) in the rectangular case, inspired by an arXiv preprint [20]. AMP uses the conventional principal component analysis (PCA) estimate as the initial message (3.1) or (3.9). To eliminate dependencies between the initial message and the noise matrix W, non-trivial Onsager correction b_{t,1} in (3.3) or a_{t,1}, b_{t+1,1} given in (3.11) and (3.13) is proposed via state evolution while the other correction b_{t,t-j} in (3.3) or (3.12) and (3.14) is the same as in [20]. Theorems 1 and 2 claim state evolution recursion for the square and rectangular cases, respectively. The theoretical predictions are also verified via numerical simulations in artificial setting. 
main_review: Originality

 The main originality is in the proof strategy to handle dependencies between the initial PCA estimate and the noise matrix W. The strategy is different from in [43], where followed Bolthausen’s conditioning technique to analyze the conditional distribution of the data matrix X for given initial messages. 

The proposed strategy is a two-phase approach: In the first phase, AMP uses a linear denoiser in (5.1) to obtain the conventional PCA estimate after a sufficiently large number of iterations. In the second phase, AMP switches the denoiser to a time-shifted nonlinear denoiser in (5.3). The proof is fully based on state evolution recursion derived in [20] under review (while I believe the correctness of the proof in [20]). 

The first part in the proof is the convergence of AMP in the first phase toward the PCA estimate. The proof utilizes a standard strategy in convergence analysis, such as the existence of a fixed point (Lemma B.4) and a construction of a contractive mapping (Lemma B.5). I guess that the linear denoiser enables such a proof. 

The second part is a proof of the consistency (Lemma B.8) between the actual AMP and the two-phase AMP in the second phase. This is an interesting step to justify the definition of the Onsager correction in the actual AMP. 

--Why do Theorems 1 and 2 need the continuous differentiability of the denoiser? The assumption excludes practical functions, such as soft thresholding and ReLU. Conventional state evolution only postulates the Lipschitz continuity, which implies continuous differentiability “almost everywhere.” 

--Why do not the authors need the non-negativity of the exponent T+1-(t-j) for 1/\alpha in (5.4)? In my understanding, this factor originates from the derivatives of the linear denoisers in the first phase for i\in\{t-j+1, …, T+1} in the case t-j+1\leq T+1. Thus, T+1-(t-j) must be non-negative. In the current definition, let j=1 to obtain T+1-(t-j)=T+2-t<0 for t>T+2. 

--AMP in the first phase uses the true signal plus noise as the initial message. Why cannot AMP start with only noise, i.e. random initialization?

Quality

 As pointed out above, the proof strategy is novel, general, and may be applicable to the other message passing. The mathematical quality in the proof is high while I did not fully read the whole proof in the supplementary material. For a further improvement in terms of references, I would like to introduce a reference [R1]. The reference is a first paper (posted on arXiv 27 March 2020 and published on IEEE TIT 04 May 2021) that presented rigorous state evolution for message passing algorithms with long memory Onsager correction, as cited in both [20] and [34].

[R1] K. Takeuchi, "Bayes-Optimal Convolutional AMP," in IEEE Transactions on Information Theory, vol. 67, no. 7, pp. 4405-4428, July 2021, doi: 10.1109/TIT.2021.3077471.

Optional comment 

--It would be better if the authors presented numerical simulations for not artificial but real problems.

Clarity

The paper is well written. Theorems 1 and 2 are presented concisely after defining AMP and state evolution recursion. The main idea in the proof strategy is clear. Nonetheless, a further improvement is possible. 

--Clarify the significance of b_{t,1}, (3.11), and (3.13) for readers to understand the main difference between AMP in [20] and the proposed AMP. I reached my understanding mentioned in Originality after I considered several possibilities, such as differences between measurement models or the definitions of free cumulants in [20] and the submitted paper. 

Significance 

 The submitted paper is a first attempt (i.e. rank-1 case) for estimation of low-rank matrices from rotationally orthogonal measurements. In my understanding, the paper has solved the main challenge in that problem. A generalization to the low rank case is possible. 

limitations_and_societal_impact:  The limitation is that the paper only addressed the rank-1 case. From a practical point of view, the low rank case may be desired. Since real data was not treated, the paper provides no negative social impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors consider the problem of estimating a structured rank-1 signal in the presence of rotationally invariant noise, which is a class of perturbations that is more general than Gaussian noise. For this problem, they propose an AMP algorithm that is initialized by PCA, and they derivate a state-evolution characterization that holds in the infinite-dimensional limit. The rationale is that PCA is a near-optimal estimator in the absence of structure, whereas AMP facilitates the exploitation of structure yet allows a rigorous asymptotic analysis. Their work builds upon previous work, such as PCA-initialized AMP with Gaussian noise, but is different in that, to handle rotationally invariant noise, their algorithm uses a PCA correction at every iteration, not just the first one. Their state-evolution analysis uses a two-phase artificial AMP formulation that has previously been used in the context of generalized linear models.  Although their analysis assumes a noise distribution with non-negative free cumulants, they provide empirical simulation results that suggest that derived state evolution is correct with any noise distribution with compact support.
main_review: The contribution is a significant extension of existing results in that it extends PCA-initialized rank-1 AMP from the case of Gaussian noise to more generic noise distributions.  The results are intuitive yet rigorous and mathematically sophisticated. Furthermore, the analysis agrees with simulations conducted outside the stated assumptions (on non-negative free cumulants). The writing is very clear and well organized. 

As pointed out by other reviewers, the lack of experimental results on real data constitutes a major weakness of this paper. Thus, I believe that it would be difficult for this paper to attract a wide audience.  

Overall, this seems like a good contribution to NeurIPS, but not a great one.
limitations_and_societal_impact: The reviewer does not see any possibility of negative societal impact.
review_title: null

final_score: rating: 10: Top 5% of accepted NeurIPS papers, seminal paper
review_content: summary: This paper considers the rank-1 signal recovery for rotationally invariant noise matrices. It uses PCA to generate an initialization of AMP that is correlated with the signal but independent of the noise. Different from the IID Gaussian noise matrix case, rotationally invariant noise matrix makes the construction and the state evolution of AMP be more difficult. For example, the Onsager term in AMP not only involves the memory in last iteration, but also contains all the memories in preceding iterations. Therefore, the PCA initialization will change the expression of AMP (and its SE) in all the iterations. In a word, this work focuses on a hard rank-1 signal recovery problem with general rotationally invariant noise matrices. The authors propose a modified AMP to solve this problem. Furthermore, the state evolution of the proposed AMP is also rigorously proved. 
main_review: The following are the concerns of the reviewer.

1.	The symmetric square matrix case can be treated as an instance of the rectangular matrix (let m=n). Right? If so, it is unnecessary to discuss the symmetric case. The authors can directly focus on the rectangular case and then briefly introduce symmetric case as a special instance. 

2.	The authors claim that the existing AMP requires an initialization that is correlated with the signal but independent of the noise, which is not practical. Thus, they consider the PCA initialization to solve this issue. However, the reader may be curious that how the existing works solve this issue without PCA. Do you mean that the existing AMP does not work? If yes, how they do the simulation?

3.	The reviewer guesses that the AMP structure in (3.1) and (3.2) is not firstly proposed by this paper. The related references should be cited when they introduce them.

4.	The main concerns are the two assumptions of Theorem 1. When the assumption “alpha > alpha_S” holds? Is it hard to satisfy this assumption? Are there any examples to show that this assumption holds? 

5.	Some numerical results are provided to support the second (non-negative) assumption of Theorem 2. This assumption rigorously holds for IID Gaussian matrix A. But it is still unclear if this assumption holds for the general rotationally invariant matrix, which is the scenario that this paper focuses. This may limit the contribution of this work.

6.	In the simulation results, the proposed AMP always outperforms the existing PCA for IID Gaussian matrix A (see Fig. 1(a) and Fig. 2(a)). However, for other general matrices focused on this paper, the proposed AMP may be worse than the existing PCA in some cases (see Fig. 1(b), Fig. 1(c), Fig. 2(b) and Fig. 2(c)). Sometimes, the proposed AMP is always worse than the existing PCA (see Fig. 1(d) and Fig. 2(d)). This also limits the contribution of this work.

7.	The reviewer is looking forward to seeing that the authors can construct a new VAMP/OAMP or memory AMP that always outperforms the existing PCA. 

8.  Symbol u_t is confusing. It is used for estimate function and also for function output.
limitations_and_societal_impact: yes
review_title: null

Meta-review: This paper received 5 reviews. The scores/confidences were 6/3, 6/2, 8/5, 6/3, and 10/4, implying that all the reviewers evaluated this paper positively. We can notice that there is a relatively large spread among these review scores, but I think that the review contents are more or less coherent across all the reviews: The major strength of this paper is certainly its high technical quality, as commented by most reviewers. On the other hand, the major weakness is that it does not succeed in demonstrating significance of the theoretical contribution in real applications, so that it would be difficult for this paper to attract a wide audience beyond those who have specific interest in AMP and related iterative inference methods. The five reviews weighed these points differently on the basis of their own expertise, resulting in the spread of the scores. I am thus happy to recommend acceptance of this paper for presentation at the NeurIPS conference. At the same time, I would like to encourage the authors to consider demonstrating the significance of their contribution in real-world settings.

Very minor points:
- Lines 107-109: One would have to assume that $O$ is independent of $\Lambda$.
- Lines 127-129: Similarly, one would have to assume that $O$ and $Q$ are independent and independent of $\Lambda$.
Decision: Accept (Poster)