Optimal Algorithms for the Inhomogeneous Spiked Wigner Model

Summary

This paper considers approximate message passing algorithms for reconstructing a rank-1 signal when corrupted by a symmetric matrix of noise with a block-variance structure; it is assumed the signal _x^*_ has iid coordinates generated from a prior distribution. One then forms the matrix $Y = x^* (x^*)^T/\sqrt{N} + A \odot \sqrt{\Delta}$, where $\Delta$ is a blockwise constant, positive matrix. The matrix $A$ is a symmetric gaussian matrix with iid off-diagonal entries of size $N \times N$. The number of blocks $q$ appears to bounded independent of matrix size, and it is assumed one has access to the scale matrix Delta. The first algorithm is a proper generalization of an AMP recursion for the case of a rank-1 signal with Wigner noise. The state evolution is shown to converge (Theorem 1.2 -- using a modification of existing techniques) and correspond to the solution of the Bayes optimal estimator (Theorem 1.4). The spectral method designs a linear recurrence which is (locally? and conditionally?) optimal, in that it also recovers the same estimator by computing a principal eigenvector of an associated matrix.

Strengths

1) The mathematical content is sound. The main content (theorem 1.2) is proven in the supplemental material. This adds an algorithmic aspect to a model which has attracted recent information theoretic attention. 2) The paper presents an algorithm which is optimal for the problem posed. The algorithm is part of a larger well-studied class. 3) The performance of the algorithm is illustrated numerically in a simple case. 4) A linear method is presented, which may reproduce the more complicated general AMP performance for the hidden spike.

Weaknesses

0) The article does not provide any broader context for the technical results it develops; all but the first few pages are technicalities related to AMP theory. It is targeted at experts in approximate message passing, and it does not develop much of the information-theoretic aspects of the model (which I gather are proven in Guionnet et al). There is no conclusion. There is nothing in the way of practical considerations or relations to application (although I would say this alone is forgivable, if the paper were otherwise immaculate). Much of the main text is occupied by technicalities related to the formulation of the main theorem and in summoning relevant AMP theory from Javanmard and Montanari as well as Deshpande et al. 1) The main theorem (1.2) is an adaptation of an existing result. Moreover, approximate message passing algorithms are well studied and many theorems exist for them. The presence of non-iid noise makes it somewhat unique, but I think it is fair to say that this is not a big extension of existing theorems. (In particular, there is a change of variables to connect the homogeneous and inhomogeneous cases). 2) The spectral method, which is introduced, is largely left half-baked. There is a conjecture (1.6) related to it, and there is a 1 page description of how the method is developed. There is an equation (42) showing that the overlap evolution is unstable when a certain Perron-Frobenius eigenvalue is larger than 1. But finally, the main points here are left as conjectures.

Questions

Major: 0) Much of the valuable main paper space is used on technicalities of how one AMP is formally recast as another. What conclusions should be drawn from this? What is the context of the information-theoretic properties of the model? What is the surprise of the linear method (mentioned briefly in the third bullet at the start?). Lots of needed context is missing from this paper. 1) The spectral method proposed at the end would seem to suggest that there is, finally, no need for the AMP algorithm (spectral methods are wildly simpler). However the actual claims about what the spectral method does are left quite implicit (reading section 3). In simple language, what do you conjecture happens for the spectral method above/below what transition? A simple theorem in section 3 might be appropriate. 2) What is the recovery transition, and why should the spectral method be optimal? (or what more than optimism justifies Conjecture 1.6)? Good numerical results would be appropriate. 3) The version of the AMP algorithm that solves the inhomogeneous spiked Wigner problem is finally presented in (32). The assumptions that you formulate are not clearly directly relevant to this theorem (i.e. you could formulate your algorithm without all the heavy assumptions). This means that in some sense these assumptions are really technicalities suited for those who want AMP details and/or proof details. What are the minimal assumptions you need for actually solving the inhomogeneous spiked Wigner model? 4) A discussion of the extent to which it is possible to actually implement the AMP iteration for the posterior would add to the broader appeal. Minor: * What is t in Assumption 1.1 part 2. Does the family include all t? Also this sentence is malformed. What is the assumption? * What is M in (4)? * Eq (11) contains an $x_j$ as yet unused?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The assumptions are clear.

Summary

This paper studies the (symmetric) rank-1 matrix estimation problem with inhomogeneous noise. Here inhomogeneous noise refers to a symmetric noise matrix that is block-wise constant where the number of blocks is a constant relative to the dimension. This paper proposes an approximate message passing (AMP) algorithm and shows the corresponding state evolution result. Another piece of contribution is the design of a spectral algorithm that outputs the principal eigenvector of a rescaled and recentered matrix. Numerics suggest that this outperforms the naive estimator of the principal eigenvector of the data matrix per se.

Strengths

The most interesting (at least to me) part of the paper is Section 3 where a nonstandard spectral algorithm is introduced and analyzed to some extent. As the authors commented, this estimator outperforms (at least numerically) the naive one corresponding to the original matrix Y. Another satisfactory aspect of the result is the coincidence between the fixed point of AMP and that of the Bayes-optimal estimator (i.e., E[x^* | Y]), though this is not surprising.

Weaknesses

1. The majority of the paper is devoted to AMP and its state evolution whose proof is a rather standard reduction to the matrix-valued AMP by Javanmard--Montanari. I didn't check the details carefully since everything goes as expected. But it's still good to see things written down formally. 2. Section 3 is interesting at a heuristic level. However, I have a doubt regarding the authors' claim. In line 131, it is claimed that "we rigorously show that with SNR<1 our proposed spectral method fails to recover the signal". I don't think the analysis in Section 3 constitutes a proof of this claim. It was shown that the trivial fixed point of an AMP with linear denoiser is attractive when SNR<1. I agree with this, but this does not imply that the asymptotic overlap of the spectral estimator is 0 when SNR<1. The iterate of the linearized AMP converges (in constant number of steps) to the principal eigenvector (i.e., the spectral estimator) only when a spectral gap is present. When SNR<1, there is no spectral gap and it is unclear how the iterate of linearized AMP is related to the principal eigenvector. It may converge to some other vector, depending on the initialization. In fact, rigorously speaking, I think it's fundamentally unlikely to prove subcritical behaviour by exploiting linearized AMP. The analysis only proves the attraction of 0 when SNR<1, which is an *evidence* that the phase transition threshold is 1. However, this implies neither "spectral fails when SNR<1" nor "spectral works when SNR>1". 3. If I understand correctly, the Delta matrix is assumed to be *known*. A very important aspect that was not discussed at all (correct me if I'm wrong) is what happens when Delta is unknown which appears (to me) to be a slightly more realistic assumption. In that case the Bayes-AMP is no longer a practical algorithm (even with warm start) and the spectral algorithm is also not computable. In fact, is it fair to say that the proposed spectral algorithm outperforms the naive one *because* it uses Delta information? Can the price of lacking the knowledge of Delta be quantified? I know this may go beyond the scope of the present paper. But it seems to be an interesting nontrivial point that's worth mentioning/discussing.

Questions

1. Line 7, "info-theoretic optimal Bayes fixed-point equations" sounds like a confusing phrase. Consider expanding it as "the FP equations satisfied by the Bayes-optimal estimator". 1. Line 17, replace "etc..." with "etc." 2. Line 20 "block-constant Gaussian noise" is mildly confusing (sorry for being pedantic). The noise is never constant; consider saying "Gaussian noise with block-constant variance profile" or something like that. 3. Line 46, is the word "detect" properly used? Or do the authors mean "weak recovery"? My understanding is that they are not the same question. 3. I couldn't parse the grammar of 2. of Assumption 1.1. 5. L in the definition of PL functions seems to be a floating parameter. In standard theory, L is tied to the regularity of prior distributions and initializers. This needs to be quantified. 5. There are multiple mistakes in Remark 1.3. The correct statement should be "convergence under all L-PL functions is equivalent to convergence in Wasserstein-L". Also, bounds on k-th (k>2) moment is a *stronger* assumption than bounds on 2nd moment, consequently, convergence in W_k is *stronger* than W_2. 5. In Equation (6), has the notation E_{posterior} been defined? If not, then this notation is definitely too sloppy. 5. Line 137, there are redundant spaces in "N - vector". 5. Line 141, please explicitly write i in [N] when introducing the notation f_t^i. 5. Equation (33), I'm not familiar with the physics jargon "Nishimori identity" and didn't check Lelarge--Miolane, but isn't this just the law of total expectation (https://en.wikipedia.org/wiki/Law_of_total_expectation)? 5. In Section 3, an AMP with denoiser f_t(x) = x is considered. Why is identity denoiser a good thing to consider, besides its simplicity? I understand this comes from linearization. But for the sake of being self-contained, I suggest comment on this. 4. This paper handles heterogeneous noise. Is it true that with essentially no additional effort, heterogeneous prior can also be handled? At least when the partition for the prior is the same as that for the noise? I didn't check the details and may be wrong. 5. The number of blocks q is assumed to be a constant relative to N. What happens if it grows with N? Clearly if q=N nothing can be said. But this question makes sense for sufficiently slowly growing q. After the reduction to matrix-valued AMP, the SE result of Javanmard--Montanari is no longer applicable since they require the width of the matrix iterates to be a constant. Could the authors comment on what can potentially happen here?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

N/A

Summary

The paper provides an analysis of an AMP algorithm for the spiked Wigner model with inhomogeneous noise. The paper builds on the matrix AMP framework to derive the state evolution equations for the considered AMP recursion for the studied model. The paper further shows that if the denoising functions are the Bayes one, then the fixed point equation of the state evolution of the AMP algorithm is the same as the one satisfied by the Bayes optimal estimator. The paper also leverages the developed machinery to study the properties of a spectral algorithm which is motivated by considering the the identity denoising functions. It is conjectured that this spectral algorithm exhibits optimal phase transition.

Strengths

I find the paper to be generally well-written and it is not hard to follow. The problem that is considered is interesting and the presented results generalize previously known results for the spiked Wigner model with homogenous noise to the non-homogenous case.

Weaknesses

Minor comments: - Page 1: Please state whether $\tilde{\Delta}$ and/or $g$ are assumed to be known. From Eq.(3) it seems that we do assume that $\Delta$ is known. - Page 2, line 82: The notation for $f_t:\mathbb{R}^N\times \mathbb{N} \to\mathbb{R}^N$ is confusing/informal because from the displayed equation, it seems that $f_t$ takes input from $\mathbb{R}^N$. Is $t$ supposed to be the input integer in $\mathbb{N}$? - Page 2, line 83: If $f_t^a$ are general Lipschitz functions, it is not clear to me why $f_t$ is linear. - Page 3, line 112: It seems to me that if we replace the second moment assumption by finite $k$-th moment, we are strengthening the assumption, not weakening it.

Questions

- In the abstract it is claimed that the spectral method is shown to match the information-theoretic transition. If I understand the arguments of the paper correctly, it seems that this is only a conjecture that is based on a heuristic, and no rigorous proof was given. Did I miss anything?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

No concerns regarding potential societal impact of this work.

Summary

This paper considers the spiked Wigner problem with inhomogeneous noise, i.e. the inverse problem of estimating a rank-matrix through an inhomogeneous noise channel. This problem naturally arises in many applications and a universality result makes the problem considered quite general with regards to the noise distribution. The authors have made several contributions in this paper: 1. They have derived the AMP recursions to solve the spiked Wigner problem. 2. The most interesting property of AMP-like methods is that their behavior can be characterized exactly through a set of low-dimensional state evolution equations. This paper obtains the state evolution for the AMP recursion that solves the problem considered. 3. The authors analyze the AMP algorithm with identity denoisers and show that it corresponds to an spectral method for a specific matrix. More interestingly, the authors conjecture that this linear version of AMP detects a spike in the same region as the general AMP.

Strengths

- The paper considers an interesting problem with many applications. - The authors derive an AMP method to solve this problem. - The authors obtain the state evolution of this AMP recursion, thus fully characterizing the macroscopic behavior of the AMP recursion at **each** iteration of the algorithm and **not** just the fixed points. This result gives us a **theoretical** way of obtaining the estimation error of the AMP method using very general metrics - The authors show that when the Bayes optimal denoisers are used (i.e. the mean of the posterior) the fixed point equations exactly match the Bayes optimal fixed point equation of another recent work. - Finally, the authors analyze the linear version of the AMP algorithm and show it is equivalent to spectral method for a specific matrix. To summarize, the authors look at the spiked Wigner problem with inhomogeneous noise, derive an AMP method to solve it, and fully characterize the theoretical behavior of the AMP method in a certain high-dimensional asymptotics. This is in contrast to many other methods that are used in practice, but have no theoretical guarantees or guarantees of the form of high-probability upper bounds on the error in certain metrics. AMP methods, allow us to obtain the **exact** error in many **different error metrics** in a certain **high-dimensional limit**.

Weaknesses

The weaknesses that come to my mind are mostly the usual weaknesses of the AMP algorithms: - The AMP algorithms are often described as not very useful to solve problems in practice due to their instability often requiring a lot of tweaks such as damping to make them converge. I do not see much comments in this work regarding the stability of the AMP method described. This is in part due to generality of the algorithm (described using general denoisers) and in fact for the linear case the authors show a condition for convergence, however no mention of convergence or potential issues in the general case is mentioned. I should admit however that for example Bayes optimality of the AMP method with Bayes optimal denoisers makes this method interesting in practice for this problem. - That being said, AMP having theoretical guarantees would still be very valuable as a theoretical tool. However, obtaining the errors through the state evolution equations are often very nontrivial due to the need to calculate expectations in a recursive formula that often need MCMC methods and are sometimes computationally not much better than running AMP for several instances of the problem and estimating the final error. - As mentioned above, the AMP results only hold in a certain asymptotic regime. However in practice, very good match is observed even for moderately sized problems as the authors also mention. ## Minor comments I believe the work is hard to follow for someone who is even familiar with the problem considered but not familiar with the AMP literature. It assumes the readers are knowledgeable in this area and very familiar with previous works which makes it hard to follow.

Questions

- It would be nice if more explanations are added regarding the convergence of the AMP algorithm, any issues it might have in practice and the usefulness of the state evolution equations as they are recursive equations that do not seem trivial to simulate. For example, the convergence of AMP, or uniqueness of its fixed points (if it is in fact unique) should either be shown or it should be clearly mentioned that these are open questions that need to be addressed in order for this AMP method to be fully characterized. - In many AMP papers, the authors make a correspondence between the AMP algorithms and estimators that are more familiar to the community. For example, using certain (generalized) proximal operators as the denoisers, the AMP would then can be shown to have fixed points that are also critical points of a certain loss function, i.e. AMP would be doing a form of M-estimation. Similarly, one could make a correspondence between other Bayesian estimators such as MMSE estimator and denoisers that use the posterior distribution such as the Bayes optimal one also mentioned in the paper. Can such results be shown for the AMP algorithm considered here? For example showing that AMP with a certain denoiser is minimizing a certain loss function, etc.? Since people are much more familiar these optimization based estimators, it would make this paper a lot easier to understand and follow. Similarly for the Bayesian estimators which are trying to estimate the signal based on the posterior, such as MMSE estimator, it would be good to make the correspondence between AMP and such estimators more clear.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

- The practical limitations of the AMP algorithms and how easy/hard it is to use the state evolution in practice are not adequately discussed.

Thank you for the prompt and detailed reply

I thank the authors for their prompt and detailed reply (and revision of the manuscript which I didn't check). "Weakness" 2: I agree with the authors' reply and I'm fine with heuristics (as long as it's made clear which is rigorous which is heuristic). After all, these heuristics are likely to yield accurate predictions. If space permitted, please consider making more clear in the manuscript the gap between attraction of trivial fixed point and the ineffectiveness of spectral estimator (as discussed in the reply). Weakness 3: I agree that in some settings, Delta is naturally known. Regarding the proposed strategy of first estimating \tilde{Delta} & partition then plugging them into AMP (or whatever subsequent procedure), is it obvious that in the proportional regime these can be estimated consistently? If not, then there is an asymptotic price to pay. Another point is that we observe Y which contains the signal. For the purpose of estimating the nuance parameters, the signal is an interference. One model that one can play with is that in addition to Y, we also observe Z which is pure noise (for the purpose of estimating tilde{Delta} and g). A spiritually similar model is proposed and studied here: https://arxiv.org/abs/2211.00986. In any case, this goes well beyond the scope of this paper. My only point here is that the assumption that tilde{Delta} and g are known deserves a few sentences of remark. Q12: This motivation makes sense. If space permitted, please consider adding a line or two discussing the choice of linear denoiser. Q14: Thanks for the reply. I agree that this in general looks difficult. Overall, my evaluation remains the same -- this paper is sufficiently interesting for NeurIPS.

Reply to authors' rebuttal

I would like to thank the authors for their reply. My assessment of the paper remains positive.