The price of ignorance: how much does it cost to forget noise structure in low-rank matrix estimation?
Authors: Jean Barbier
TianQi Hou
Marco Mondelli
Manuel Saenz
Venue: NeurIPS 2022 Accept (2022)
Keywords: low-rank matrix estimation
mismatch
Bayes estimator
Approximate Message Passing
state evolution
spectral method

Abstract: We consider the problem of estimating a rank-$1$ signal corrupted by structured rotationally invariant noise, and address the following question: \emph{how well do inference algorithms perform when the noise statistics is unknown and hence Gaussian noise is assumed?} While the matched Bayes-optimal setting with unstructured noise is well understood, the analysis of this mismatched problem is only at its premises. In this paper, we make a step towards understanding the effect of the strong source of mismatch which is the noise statistics. Our main technical contribution is the rigorous analysis of a Bayes estimator and of an approximate message passing (AMP) algorithm, both of which incorrectly assume a Gaussian setup. The first result exploits the theory of spherical integrals and of low-rank matrix perturbations; the idea behind the second one is to design and analyze an artificial AMP which, by taking advantage of the flexibility in the denoisers, is able to "correct" the mismatch. Armed with these sharp asymptotic characterizations, we unveil a rich and often unexpected phenomenology. For example, despite AMP is in principle designed to efficiently compute the Bayes estimator, the former is \emph{outperformed} by the latter in terms of mean-square error. We show that this performance gap is due to an incorrect estimation of the signal norm. In fact, when the SNR is large enough, the overlaps of the AMP and the Bayes estimator coincide, and they even match those of optimal estimators taking into account the structure of the noise. 


The price of ignorance: how much does it cost to forget noise structure in low-rank matrix estimation?
Jean Barbier'
Tianqi Hou Huawei thou@connect. ust.hk
International Center for Theoretical Physics jbarbierOictp.i.
Marco Mondelli
Manuel Sáenz"
Institute of Science and Technology Austria marco. mondelli@ist. ac.at
International Center for Theoretical Physics
msaenz@ictp.ir
Abstract
We consider the problem of estimating a rank-1 signal corrupted by structured rota- tionally invariant noise, and address the following question: how well do inference algorithms perform when the noise statistics is unknown and hence Gaussian noise is assumed? While the matched Bayes-optimal setting with unstructured noise is well understood, the analysis of this mismatched problem is only at its premises. In this paper, we make step towards understanding the effect of the strong source of mismatch which is the noise statistics. Our main technical contribution is the rigorous analysis of a Bayes estimator and of an approximate message passing (AMP) algorithm, both of which incorrectly assume Gaussian setup. The first result exploits the theory of spherical integrals and of low-rank matrix perturba- tions; the idea behind the second one is to design and analyze artificial AMP which, by taking advantage of the flexibility in the denoisers, is able "correct" the mismatch. Armed with these sharp asymptotic characterizations, we unveil rich and often unexpected phenomenology. For example, despite AMP is in principle designed to efficiently compute the Bayes estimator, the former is outperformed by the latter terms of mean-square error. We show that this performance gap is due to incorrect estimation of the signal norm. In fact, when the SNR is large enough, the overlaps of the AMP and the Bayes estimator coincide, and they even match those of optimal estimators taking into account the structure of the noise.
1 Introduction
The estimation low-rank matrix from noisy data is a central problem machine learning, and appears, e.g., sparse principal component analysis (PCA) [50 88), community detection (2]. and group synchronization [69]. In this paper, we consider the prototypical task of recovering symmetric rank-1 matrix X X from noisy observations of the form
Y XX Z R-NN
N
Here, A 0 is the signal-to-noiss ratio (SNR) which quantifies the signal strength, and Z IR NxN is a random matrix that captures the noise. A natural estimator X is given by the principal eigenvector of Y. Its performance and, more generally, the behavior of the eigenvalues and eigenvectors of has been studied in exquisite detail in statistics [49 68) and random matrix theory 7 g 21 22 26
52 6).
Going beyond the spectral estimator given by the principal eigenvector, approximate message
36th Conference on Neural Information Processing Systems (NeurIPS 2022).
"quual contribution

---

passing (AMP) constitutes popular family of iterative algorithms. The reason for this popularity lies two especially attractive features: (i) AMP algorithms can be tailored to exploit knowledge on the structure of the signal; and (ii) under suitable assumptions, their performance in the high-dimensional
limit accurately tracked by deterministic recursion known as state evolution [T8] 24 48) Using
the state evolution machinery, it has been showed that AMP achieves Bayes-optimal performance
in some Gaussian models [29] 30 61 [3], and a bold conjecture from statistical physics is that AMP is optimal in the class of polynomial-time algorithms for large class of inference problems with random design. AMP algorithms have been recently considered for several practical scenarios, including genetics [86), inpainting [66] and MRI image recovery [76].
A general class of noise models that has received attention in the literature is given by the family of rotationally invariant matrices. This is much milder than requiring Z to be Gaussian: it only imposes that the matrix of eigenvectors is uniformly random, and allows for an arbitrary spectrum. Hence, Z can capture the complex correlation structure which often occurs in applications (e.g., recommender systems [20] and bioinformatics 722). However, estimating noise statistics from data is costly or, for problems involving large-scale datasets (computational genomics is a paradigmatic example [36]] ( may be impossible. Thus, one natural idea is to simply assume Gaussian statistics for Z. The case in which Z is actually Gaussian has been thoroughly studied (53 28
55 (5 [1] Beyond Gaussianity,
a rapidly growing literature is focusing on rotationally invariant models assuming perfect knowledge of the statistics of the structured matrix appearing in the problem (such as noise inference, sensing, data, or coding matrix in regression tasks, weight matrices in neural networks, or matrix
of interactions spin glass models) 67 23 37
65 56 57
14 78 79
I6
66
47).
However, despite this impressive progress when the noise statistics is known, low-rank estimation in a mismatched setting with partial to no knowledge of the statistics of the rotationally invariant noise matrix remains poorly understood. The goal of this work is thus to shed light into the following fundamental question:
Suppose that the noise statistics is unknown or unreacheable, and hence Gaussian noise is naively assumed. What is the impact of this mismatch on the overall performance of inference methods?
1.1 Summary of contributions
In this paper, we provide rigorous performance guarantees for two inference methods which in- correctly assume Gaussian noise statistics: a Bayes estimator, and an AMP algorithm. Then, by exploiting these sharp analytical characterivations, we describe a number surprising effects coming from numerical simulations. Our main findings are detailed below.
Theoretical results. (i) We give a closed-form expression for the mean-square error (MSE) of the Bayes estimator which samples from the mismatched posterior (cf. Theorem []. Under a certain concentration assumption, we also present an asymptotic result on the overlap of such estimator. (ii) We provide a state evolution analysis (cf. Theorem 2 for the Gaussian AMP algorithm which is designed for Gaussian noise.
Numerical results. The mismatched Bayes and AMP estimators display surprising behaviors already for the case of spherically distributed signal - and the two performance metrics (MSE and overlap) exhibit remarkably different phenomenology: (i) As for the MSE, the Gaussian AMP is outperformed by the Bayes estimator. Here, the surprise comes from the fact that AMP algorithms are, in principle, designed to sample from the posterior distribution (and this is often what happens in the matched case). (ii In contrast, when the SNR is large enough, the overlaps of the two mismatched estimators coincide, and they even match the overlap of estimators which exploit the noise statistics, namely the optimal spectral method which minimizes the MSE and the correct AMP designed in 37.. (iii) Under certain conditions, the MSE of the mismatched Bayes estimator matches that of Gaussian spectral method with no information on the noise structure. (iv) The mismatched estimators ouiperformed in terms of MSE by the optimal spectral method and the correct AMP, whose performance coincide. (v) Finally, the MSE curves of the Bayes and Gaussian spectral methods exhibit a striking non- mo-mootooe behavior.
1.2 Related work
The impact of mismatch. Given the practical relevance of understanding the effect of mismatch in statistical inference, line of work has approached the issue from various angles. Regression being

---

probably the most paradigmatic model of inference task, mismatch has been thoroughly studied in this context. In information theory, the trend was initiated in [8 85 Studies for M-estimation and robust statistics followed based on statistical mechanics approaches
3 on the analysis of approximate
message passing algorithms [25] 77
32
43 on Gordon's 's convex min-max theorem [8] 80] and the
leave-one-out method [3] (3). Concerning the analysis of Bayesian approaches to mismatched linear
regression, we refer to [2 63 75
M or [ for a review.
In contrast, the problem studied in the present paper, namely low-rank matrix inference with mismatch, has received attention only recently. It is clear that in some way, related questions were analyzed in the aforementioned random matrix theory literature, although from rather different perspective. Concerning the precise issue of the performance degradation due to mismatch in Bayesian inference, an exception (and inspiration for work) is the recent paper 771. However, the authors of [71] focus on mismatch in the signal-to-nois ratio for the Gaussian noise setting: their results can thus be recovered special case of the present ones. To the best of our knowledge, this is the first work that considers mismatch in the noise statistics for low-rank matrix estimation.
Approximate message passing. AMP algorithms have been applied to wide range of inference problems. Examples include estimation in linear models [19] [8]
31, generalized linear models
13 58 [59] and low-rank matrix recovery with Gaussian noise 17
29 41
51 [55] 61]. also
the survey 39 A general AMP iteration for rotationally invariant matrices has been recently analyzed in [37 871. and by providing suitable instances of this abstract iteration, AMP algorithms have been developed for low-rank [3 87 60) and generalized linear models [82]. Furthermore, an AMP-basce method which uses the classical idea of empirical Bayes reduce the high-dimensional noise in PCA is proposed in (86), which also provides applications to genetics. However, the existing results cannot be applied the mismatched setting considered in this work, since the Gaussian AMP does not contain the right Onsager corrections. In fact, the algorithm designer assumes Gaussian statistics for the noise and, therefore, constructs an AMP algorithm with the Onsager correction suitable for Gaussian noise. Finally, we remark that the performance of the Gaussian AMP is numerically compared with that of the correct AMP (exploiting the knowledge of noise statistics) in (87. Our Theorem 2 provides rigorous foundations for such comparison.
2 Setup of the problem
2.1 Random matrix theory preliminaries
We start with some useful notions of random matrix theory. Given probability measure p of compact support K s R. we let Hp RKK + RR be the Hilbert transform of p: Hz) == JK ((d))(= (=->)))>))))))) We define 7 == max K, 1 == min K, h == lim..1 Hz(²) and h := lim=t? H=):). where the limits exist due to the monotonicity of H, but may be infinite. As H is a bijection between K\K and its image (h, h) M)0). its inverse exists and it is denoted by K, (h, h) [)) - K. The R-transform of p is Ro: : (h, [O) - K given by (²(x) == K2(x) - 1/z. The coefficients {Rx] kea of the Taylor series of R2 are the free cumulants associated to p, i.e., R. (z) = Σ kK+10* and they can be computed from the moments of p. see e.g. Section 2.5 of [64]. Furthermore, (x(x) and H', (2) denote the derivatives of the R-transform and the Hilbert transform of p. respectively.
2.2 Model of mismatched low-rank matrix estimation
We consider the problem of estimating rank-one informative spike X X corrupted by an ad- ditive symmetric noise matrix Z ε NxN from data Y generated as in (T). The scalar X, Rg the signal-to-noise ratio (SNR), and the noise Z can be decomposed as Z OΣOT, where E = diag(?....,, 7N) IR N=N is a diagonal matrix containing the eigenvalues of Z and O is some orthogonal matrix. We also denote by TN and Y respectively max(7)..... 7N3 and min(7,..... } Similarly, VN and VN denote the largest and smallest eigenvalues of the data matrix Y. Throughout the paper, the main technical assumption will be the following.
Assumption 1. and is independent of X. Moreover, the empirical measure N E'EN dy, of eigenvalues of Z converges weakly towards a limiting measure p of compuct support K S R. Finally, I and IN converge a.s. to 7 max K and y min K, respectively.
The signal X has norm VN. The random noise matrix Z is rotationally invariant
3

---

The noise matrix Z being rotationally invariant means that O is a random orthogonal matrix (i.e., sampled from the Haar measure) independent of Σ. Under Assumption [ we have that V and Σn converge a.s. to finite limits, which we denote by D and v, respectively. These have explicit form in terms of p and X given in [2] Theorem 2.1] and which we reproduce for convenience in Appendix A We remark that the assumption on the ground-trute signal is rather mild: X can have any distribution over the sphere of radius VN, and it might even be deterministic. For example, X (-1, could be uniform vector
the centred N- N-dimensional hyper-cube of sides 2/N.
For the analysis of the Bayes estimator, we require a second assumption on the asymptotic eigenvalue distribution p. This ensures that the limit for the overlap of the spectral estimators with the signal is continuous in the SNR, whenever a small additive Wigner noise of variance é 2 0 is added to Y.
Assumption 2. Let Pe be the spectral density of the free convolution of p and semicircle law of radius 2E 2 O. Let H., be the associated Hilbert transform and 7e the rightmost point of the support of Pe. Then, we assume that limery. H (z) -00 for all 0.
For the definition of the free convolution and its link random matrix theory, we refer the reader to [4, 70). We remark that Assumption 2 satisfied by wide class of random matrices. In particular, by combining Theorem 2.2 of [O] with Proposition 2.4 of 22] it suffices that the support of the limiting spectral measure is (i) compact, (ii) connected, and (iii) it has proper decay rate at its edges (i.e., P is of Jacobi type), see Assumption 2.1 of [0]. These conditions can be easily checked for many random matrix models, including the ones discussed in the examples of Section 4
Note that, if p the semicirele law of radius 2, the noise is asymptotically equal in distribution standard Wigner matrix W with density
As the elements of this type of symmetric matrices are i.i.d. Gaussian, in this case we say that there is Gaussian noise. For other limiting p. the elements of Z + W remain correlated and we say that there structured noise. We denote by W sequence of standard Wigner matrices while we reserve Z for generic sequence of rotationally invariant matrices.
Sources of mismatch. In this paper, consider what happens when there is mismatch between the true noise statistics and the assumptions on the noise statistics made in the inference algorithm. In particular, we study the case in which the noise is assumed to be Gaussian. Gaussianity is in fact the most standard assumption made when precise knowledge of the noise structure is lacking. We also consider the case in which the SNR is estimated incorrectly, i.e., the statistician assumes that the data generated according to (VT/N) X X W, where 4 X, and A, is the correct SNR present in (T. Our goal is to quantify how these sources of ignorance affect the algorithmic performance.
2.3 Three classes of inference procedures for PCA
Mismatched Bayes estimator. The statistician assumes Gaussian noise and that the signal X has no specific structure, i.e., it is uniformly distributed on the N N-dimensional sphere N (V-N) The mismatched posterior distribution reads, using the Gaussian log-likelihood NN Tr N xxx)²
Vx
Pmiis da Y) = 1 (Y) exp
( (2x (x, Yx)))u((d)) (dx),,
(2)
where (Y) is the normalization constant and JN is the uniform measure over NN (VN). In case the signal X lies on the sphere (by Assumption I] but is not uniformly distributed on it, then this leads third source of mismatch. However, the MSE formula of Theorem I does not depend on it; e.g. if X E {- the error remains the same. The origin of this is the uniformly spherical which is the most uninformative one.
prior used the posterior 4
The Bayes estimators we analyze are obtained as the posterior means
Mmia (Y) == f |xx' P (dx Y),
(3)
which may not be practical to compute. Notice that, if the noise is Wigner, then the likelihood exp(...) in (2 is correct. This Bayes-optimal case has already been rigorously characterized (see, for example, (4)), and it will serve us base case for comparison with our mismatched setting.
12

---

The performance of sequence of estimators My E R Nx.N of the spike X is quantified via the asymptotic mean- -qqure error (MSE):
MSF(M) = lim 1
XXX Mv
N
2N
where 1 denotes the Frobenius norm and E the expectation over the spike x and the noise Z. We also consider another performance measure which is insensitive to the norm of estimator it of X, namely, the rescaled overlap:
(X,&(Y) ((Y)) ||]
Overlap(ã) lim No++00
(5)
where XX| VN due to the spherical constraint. This alignment measure is sometimes also referred to as cosine distance. For both AMP and spectral estimators, this overlap will almost surely be deterministic. If the norm of the estimator vanishes, by convention we fix the overlap to zero. Note that the definition (5) is not meaningful for the Bayes case. In fact, if one defines imis : f /
mimmmmsd (dæ Y), then this quantity zero by sign symmetry (+æ have the same posterior weight). Thus, the correct definition of the overlap for the mismatched Bayes estimator is
Overlapmis lim NN [.Miiss())) S Pmii(dde (dx ()), 2)) 1/2
1
(6)
No++00
while for the "one-shot" AMP and spectral estimators we use the former definition
Approximate message passing. We remark that, opposed to analysis of the Bayes estimator, the state evolution characterization of AMP (Theorem 2 does not require X to be uniformly distributed on g (VNN. The AMP analysis can accomodate more generic (potentially mismatched) prior distributions and, in fact, AMP algorithms are well equipped exploit structure the signal. For simplicity, we assume to have access to an initialization a RN,, which is independent of the noise Z and has a strictly positive correlation with X, i.c..
(x,+') W (1, [[x2)==E>0 5
where (x.#") Wg
(X, ) denotes convergence of the joint empirical distribution of (X, .²) to the random variable (X, Wasserstein-22 (W₂) distance. Then, for 2 1 the AMP iteration reads
z'=Ya'- -B,t"', 1=*1 -h--1 (x=))
(8)
where we assume that _0 O. Here, the function he+1 RR TR is applied component-wise, and can be chosen in order to exploit prior information about the signal: 19 O and, for / 2, 8, = (M((x=")) )), where NG denotes the derivative of h4. The AMP estimator of X is a., and the one of the spike XX" Gaussian AMP, since this is the AMP that is
is M ' ( We refer to this algorithm implemented for Gaussian noise (and known SNR). For a discussion on how 8 can be derived, we refer the interested reader to the review [39]. We note that the initialization one can design AMP iterations which are initialized with the eigenvector U of the data matrix Y associated to the largest eigenvalue VN. see [61 60 87). We also able provide state evolution result for the Gaussian AMP with spectral initialization, and this is discussed in Appendix (C.4.
is impractical and
Spectral estimators. Finally, we consider spectral estimators of the form CUNUY where UN is the unit-norm eigenvector associated to the largest eigenvalue n (Y) and C' 0 is a scaling constant taking into account the spectrum of the data matrix. The asymptotic description of Ux and VN for additive and multiplicatiie low- www-rank perturbations of rotationally invariant matrices has been obtained in [1] 22 6). In particular, by Theorem 2.2 of (22), the squared overlap (X, U u )² / converges a.s.
to constant C'pp, A,), ), whose explicit expression is recalled in Appendix A We study two variants:
The optimal spectral estimator (OptSpee) is given by Mos Cosu vyy, where (ps(p,)) Ax) == C( Aa) is the optimal scaling that minimizes the MSE.
The Gaussian mismatched spectral estimator (GauSpec) is given by MGs == UG where Cas is the optimal scaling if the noise was Gaussian and the SNR was equal to X > O. By letting Psc be the standard semi-cirele law, we have CGs(A) == C(psc. A)
1/2
For both OptSpec and GauSpec, the estimator of X is given by âas = #os Spee == VNTN. Notice that, while OptSpec requires knowing exactly the statistics of the noise and the SNR, GauSpec
5

---

represents the spectral estimator that would be used by statistician who assumes the noise to be Gaussian and the SNR À (instead of X,). An upplication of Theorem 2.2 [2] gives that
MSE(Mos) -1- (p.x.))),,)),, and MsE(M (1 (1+ -001-010010
Furthermore, the respective overlaps coincide and are given by vCos. Note that MSE MSS((Mss) (C,, (1
1/ Thus, as expected, we have MSF(Mos) s (ISF(MMs) We also remark that, as the noise matrix is rotationally invariant, both the MSE and the overlap of the spectral estimators do not depend on the ground-truth signal distribution.
Main results: performance of inference algorithms
3.1 Mismatched Bayes estimator
Consider the following functions of X, A, > 0 and of the asymptotic spectral noise density p:
1
M(A,
AA X
Q(A, = (1- AA
1
IrAA > 2
11) + 3 2 (1 1IVA
where 1 (E) stands for the indicator function of the event F. The idea is that Q(1, and M(), X.) represent the squared norm of the mismatched Bayes estimator and its inner product with the signal, respectively. This leads to our main result on the mismatched Bayes MSE, which is stated below.
Theorem (Performance of mismatched Bayes estimator). Consider a spiked model (T). Let As- sumptions 7 and hold. Then, the MSE of the mismatched Bayes estimator 33 is given by
MSE(M 21 ((2,,A))-2(AA..))
(10)
As a consequence of the auxiliary lemmas used in the proof of Theorem T and presented Ap- pendix B we have that N-2 Pmis (dæ ()(X, x²)² converges almost surely to (A, Further- more, for noise matrices regularized by arbitrarily small Wigner matrices, by using similar techniques as in [SS we can prove that || Miis ///N converges almost surely (*/2(A, X.). We conjecture that
this convergence holds even without the Wigner regularization. By assuming this conjecture, we have the following almost sure convergence result for the overlap:
M 12,2(,,
Overlapmis
(11)
Q1)7(x,.))
which holds whenever the denominator is non-zero. When comparing the overlaps of different methods in Section [ we will use (1I) for the mismatched Bayes estimator.
Let us highlight the following property of the MSE (00) when there is no mismatch in the SNR:
If x X, and h 2 1, then MSE(Mais) = MSE (Ms).
(12)
However, in general MSE Manis) and MSE differ. E.g., when the assumed SNR À is different
from the real one X. the norm of Minis incorporates information about x. while the one for Mos only depends on A. Finally, we note that, from a statistical view-point, Assumption [ [ean be replaced
by the following: X is uniformly distributed on NN-1(V/)) and is independent of Z, which may be generic symmetric matrix with converging empirical spectral density.
Sketch of the proof of Theorem I The goal is to evaluate the asymptotic values of EJ Mais 11? and + X"), from which both the MSE and the mean overlap of the Bayes estimator can be obtained. Our strategy is to first compute the log-moment generating function fiis of the mismatched Bayes model. Then, the above quantities of interest can be accessed by taking derivatives of fuis with respect to appropriate parameters. However, as the noise in the inference model is not Gaussian, El l cannot be computed in the standard way using an "I-MMSE" type of formula [46] (like is done, e.g., in (71)). To address this issue, we introduce generalized model for which the noise matrix given by the original one plus an independent Wigner matrix multiplied by a small parameter
We then compute the log- log-moment generating function of this generalized model using the theory of low-rank perturbations of rotationally invariant random matrices (2] and of the low-rank spherical integral [45). Finally, the desired results obtained by a limiting argument in + 0.

---

3.2 Approximate message passing
Our main result is a characterization of the iterates (8) in the high-dimensional limit. We show that the joint empirical distribution of (æ' ..... x", at ................................ xl+1) converges (in W2) to the random vector (#1..... It, 21...., ,1t...,ftt1). . The law the random vector (Z1....,Its, It, 2i,... ;f++1) is captured by be expressed via sequence of vectors
deterministic state evolution (SE) recursion, which tx defined as follows. We start with the initialization
He (H1,...., (4) and matrices Σg. A,, B, E IR
M1 = ARE, =1= = R2B[
A[=
=1=
(13)
where Xa is the true SNR (see (I), and (2 are the free cumulants associated to the asymptotic spectral measure of the noise p. For t 2 L, given Me, Ex A., B,, let
(EI,..., 21) (0, 2.) and independent of xx, Ft = 24 + P2 3,8x-1 + 1 (B.),, 0(+1 he+1 (xx),
(14)
where we have defined un 0, 31 0, and for t 2 2, B, [[)((x+-1]- Then, the parameter Jr+1
pl+1 = VX $.
(15)
Next, we compute the matrices A+t1 and B++1 as (A+t))i = [z] 1 1si,jttl, Bu. EEjo //1 where ( (P21))ss 0ifis j, and (f.-1) = [[Ora:] if j.
(16)
where 8jē; denotes the partial derivative 02 0,,h1(zz11 Pi-1 3-- E (B.) Finally, we define the covariance matrix E..1 as
Σ+I = Σ R2+2
with
O t+1 1=0
( e-1 ( (o)
(17)
4+1
Note that the top left sub-matrices of E,,1, A.+1 and B are given by Σ,, A, and B, At
this point, we are ready to state our state evolution characterization of the AMP algorithm (
The result is presented in terms of Liischhti test functions. A function vb : R + R is
pseudo-Lipschitz of order 2, i... & PL((), if there is a constant C' > 0 such that [0<(x) ((v)
C(1+ ||=]|| + yyl) x ylI. We also make the following assumption on the functions (14t)
Assumption 3. The function h+11 R + R is Lipschitz, and the partial derivatives
On h4+1 (2 + PiX B,
Σ E(BOL,& k=1
are continuous on a set of probability 1, under the laws of (31 (3)...,2)) 21) and ($1...., .t) given in (4.
This requirement covers most practically relevant choices of h1+1 (e.g., soft-thresholding or ReLU), and it rather standard in the AMP literature, see e.g. 39
82 87
Theorem 2 (State evolution of Gaussian AMP). Consider spiked model ① and the AMP algorithm
initialized as in (7). Let Assumptions ] Jand3 hold, and let tb R R be any pseudo-Lipschit.
functions of order 2. Then, for each 2 I, we almost surely have that, as N + +00,
N M ((E))))....(E")))) (+' ))...., (w* (X):) + Ed(x It. 21 $.1.)) (18)
where the random variables on the right are defined in (1).
By using Definition 6.7 and Theorem 6.8 of 84], one readily obtains that 18 is equivalent to
the convergence of (x''. (x'......""" x², ......" _ X) to (æ1,...... Lt. #1, Ze+1 X in W2 distance. Applying (8) to the pseudo-Lipschitz functions vo (fr+11, X) = (#+-1 x)² 1/ (#++1. X) = f+-1 X
and vi (f++1. X)= (2 we obtain high-dim ditenmmimniiilll characterization of the AMP performance.
Corollary 1. Consider the setting of Theorem 2
Then, for each 1 2 1, we almost surely have that
MSE MSE(MAMR := lim No
E.
X
(1 2 (B x1)² (B(()))))))).
2N2
X
B[ -X]
Overlap(#*) := lim
No
X
[E(()))
7

---

Sketch of the proof of Theorem 2 The key insight is to exploit the flexibility given by the denoisers of the abstract AMP iteration [8 to "correct" the mismatch. These denoisers are denoted by {he ) (see (33) and (34) in Appendix C.I and they serve solely as proof technique, hence they do not have an impact on the practicality of the algorithm; in contrast, the denoisers {he)ra2 (see (8) can be chosen by the algorithm designer to take advantage of the information available about the signal. Thus, we can design an auxiliary AMP such that (i) it admits a state evolution characterization, and (ii) its iterates are close to (8) This requires the delicate induction argument in Appendix [ in Appendix C.T we define the auxiliary AMP; in Appendix C.2 we prove a state evolution result for it; in Appendix C.3 show by induction that (i) the state evolution parameters of the auxiliary AMP coincide with those defined in this section, and (ii) the iterates of the auxiliary AMP are close (in lz norm) to the iterates of the AMP (8) thus concluding the proof of Theorem
Numerical results and discussion
In all experiments, the density p of the eigenvalues of the noise has unit variance and the distribution of the ground-truth signal is uniform on the sphere of radius N. For the sake of simplicity, we decouple the effect of the mismatch in (i) the noise statistics and (ii) the SNR. More specifically, in the first two examples, we set X., so that only mismatch in the noise statistics present; and in the last example, the noise is Gaussian, so that there is only SNR mismatch. Additional results when Z is the free convolution of Rademacher and semicirele spectra are reported in Appendix [33
Models of mismatch. (a) Marcenko- Pasttur spectrum. An example of non-symmetric density is the Marcenko-Pasteee law p(z) = VI(4- x) ((Txx) 1(x e [0, 4]). The R-transform is (x)
1/(1- ([1xxx), and the results are displayed in Fig. Ia (the same formulas apply if the law is centered).
(b) Uniform spectrum. We let be the uniform distribution 4[-/3, v3]. In this case, we have
(x(x) = /3/ lanh( /3x) - 1/2r, and the results are in Fig. lb
(c) Wigner matrix/semicircle spectrum with mismatched SNR. We consider a Gaussian noise matrix
W (as assumed by the statistician), but with mismatched SNR by setting À = 4)., see Fig. Ic
We remark that Assumption is verified for all models. Furthermore, in all the three cases, the support of p is a single non-empty interval. Hence, Theorem 2.2 of [10] and Proposition 2.4 of [1 can be used to show that Assumption 2 holds.
Inference algorithms and set-up. The estimators of the spike X XXT T are compared in terms of the MSE (4) (plots on the left). The AMP and spectral estimators of X are compared in terms of the overlap (5) and the Bayes estimator of X in terms of the overlap (6) (plots the right). We evaluate those formulas at N = 8000 for the various algorithms, and in the N + +o0 limit for the theoretical predictions. The correct AMP (together with its own SE) is in red. This AMP is correct in the sense that the statistician is aware of the noise statistics and, thus, incorporates the right Onsager corrections. The form of the correct AMP and the corresponding state evolution are readily obtained from the results in [37 87 and, for the reader's ' convenience, they are recalled in Appendix [DI] As noneaiiras,sies, we use the posterior mean denoising functions of Section 5.1 in 87 and we estimate the SE parameters consistently from data (see Appendix D.2). The Gaussian AMP (together with its own SE) in blue. This is the AMP algorithm (8), which is chosen when the noise statistics or the SNR are unknown (as it would be optimal for Gaussian noise and known SNR). Its state evolution given by Theorem 2 As
linearities (1u+1))21 we use again the posterior-ment mean denoising functions, and estimate consistently the state evolution parameters from data (see Appendix D.2). We note that the denoisers of the Gaussian AMP depend only on a single iterate, while the denoisers of the correct AMP incorporate all the past iterates. In contrast, the state evolution parameters of the Gaussian AMP at time depend on all the past, in order to correct for the mismatch. The mismatched Bayes estimator is plotted in green. Its MSE and overlap
given by (0) and ITI respectively. The optimal spectral estimator (OptSpec) is plotted in black, and the Gaussian mismatched spectral estimator (GauSpec) is plotted in yellow in Fig. and Ic| (where it differs from Bayes) or in green in Fig. Tb (where it coincides with Bayes). The performance measures of both variants of spectral estimators given the end of Section 2.3 Each experiment is repeated for 10 independent runs. We report the average and error bars at 1 standard deviation.
rich and surprising phenomenology. (i) An intriguing phenomenon is that, in terms of MSE, the Gaussian AMP does not perform as well as the mismatched Bayes estimator. This effect occurs
8

---

A&GP
0.8
KI Eores
ANP Gres
OhySppc
Overlop
MSE
0.
Guudyeo
GauBpec (heap))
(theary)
0.8
Sit comert
AMP everet
0.4
Higes
Gazas
0.2
Dagge
Spriteal (Choees)
X
A
(a) Marcenko PPattur noise.
0.5
SE
AMd cornect
Class
Overlap
MSD
0.35
Dytiqpo Doutyct
0.5
Bayo
AMP exeret
KS Grea
Elvves
0.2
0.15
A
A.
(h) Uniform eigenvalues distribution in [-V3,
eormet
0.8
0.8
AMP forme
OptSppx
Opt8gn (Nanny)
Overlap
6.6
MSC
Garctipuc
(Reorr)
0.4
36 ovenct
0.4
AMP Gasa
Specrral
Speerial (theor)
Bayr
0.2
X
Wigner matrix/semicircle spectrum with mismatched SNR 4A.
Figure 1: MSE (on the left) and overlap (on the right), as a function of the true SNR X2 in three mismatched settings.
in all our settings, and it is surprising the Gaussian AMP (8) is precisely designed to efficiently compute the Bayes estimator (3). In the Bayes-optimal case, does so (outside of its computational gap) [12). However, if there is mismatch, AMP does not compute the (mismatched) posterior mean. This finding adds to the already existing evidence [5] that AMP poorly understood, and studying the fundamental reasons behind this behavior is an exciting avenue for future research.
(ii) By comparing MSE and overlap curves, we understand that the discrepancy between Gaussian AMP and Bayes comes from incorrect estimation of the signal norm. In fact, at large enough SNR, the overlaps of Bayes and Gaussian AMP match, and they even coincide with the overlaps of optimal algorithms (correct AMP and OptSpec), which exploit knowledge about the noise structure. Understanding the origin of the MSE discrepancy (namely, a wrong estimate of the signal length) can potentially lead procedures which correct for this effect and, hence, reduce the MSE
(iii When there no SNR mismatch and 1 2 (cf. (12)). the MSEs of the Bayes and Gaussian spectral estimators match (see Fig. [b). Both have information about the noise structure and about the signal distribution. Yet, this equality is remarkable given that the spectral estimator is the solution of an optimization problem (it is "zero temperature" estimator in physics parlance), while the Bayes
"The MSE is constructed from the (Y) I| and the inner product (rE X

---

estimator aims at computing the mean of a certain posterior distribution (it is "finite temperature" estimator).
(iv) All mismatched estimators are outperformed by the optimal spectral method and the correct AMP. Both these algorithms take advantage of the noise statisties and achieve the same MSE. This suggests that the Iwo estimators are Bayes-optimal. We remark that solving this conjecture would require understanding the information-theoretie limits of low-rank estimation with structured noise.
(v) Finally, striking phenomenon first observed in [71] is that the Bayes and Gaussian spectral MSE curves may be non-decreasing with the true SNR X see Figs. La and Ic Going beyond the analysis in 771], we remark that, for large enough SNR, all estimators yield the same overlap and therefore all "point in the correct direction" given by the leading eigenvector, see also part (ii) of this discussion. This links the initial MSE increase to wrong estimation of the signal's 's norm, due an over-confidence in the data quality (recall that the assumed SNR À is equal to 4A, in Fig. Ic
Acknowledgements
M. Mondelli was partially supported by the 2019 Lopez-Loreta Prize. The authors acknowledge discussions with A. Krajenbrink, M. Robinson, A. Depope, N. Macris and F. Pourkamali.
References
[1] Emmanuel Abbe. Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, 18(1):6446-653) 2017.
[2] Gad Abraham, Yixuan Qiu, and Michael Inouye. Flashpca2: principal component analysis of biobank-scale genotype datasets. Bioinformatics, 2017.
[3] Madhu Advani and Surya Ganguli. Statistical mechanics of optimal convex inference high dimensions. Physical Review X, 6(3):031034, 2016.
[4] Greg W. Anderson, Alice Guionnet, and Ofer Zeitouni. An introduction to random matrices. Cambridge university press, 2010.
[5] Fabrizio Antenucci, Silvio Franz, Pierfrancesco Urbani, and Lenka Zdeborová. Glassy nature of the hard phase in inference problems. Phys. Rev. X, 9, Jan. 2019.
[6] Zhidong Bai and Jianfeng Yao. On sample eigenvalues in a generalized spiked population model. Journal of Multivariate Analysis, 106:167-177, 2012.
[7] Jinho Baik, Gérard Ben Arous, and Sandrine Péché, Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices. The Annals of Probability, 3345)11643-1697, 2005.
[8] Jinho Baik and Jack W. Silverstein. Eigenvalues of large sample covariance matrices of spiked population models. Journal of multivariate analysis, 17(62)3382221 1408, 2006.
[9] Sayantan Banerjee, Ismaël Castillo, and Subhashis Ghosal. Bayesian inference in high- dimensional models, 2021. arXiv:21011 210::.1111.........
[10] Zhigang Bao, László Erdós, and Kevin Schnelli. On the support of the free additive convolution. Journal d' Analyse Mathématique, (2(11)323-344, 2020.
[11] Jean Barbier, Wei-Kuo Chen, Dmitry Panchenko, and Manuel Sáenz. Performance of bayesian linear regression in model with mismatch, 2021. arXiv:2107 267.:2307.06636.
[12] Jean Barbier, Mohamad Dia, Nicolas Macris, Florent Krzakala, Thibault Lesieur, and Lenka Zdeborová. Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula. In Advances in Neural Information Processing Systems, 2016.
[13] Jean Barbier, Florent Krzakala, Nicolas Macris, Léo Miolane, and Lenka Zdeborová. Optimal enrors and phase transitions high-dimensional generalized linear models. Proceedings of the National Academy of Sciences, 116(12):5551-440) 2019.
10

---

[14] Jean Barbier and Nicolas Macris. The adaptive interpolation method: a simple scheme to prove replica formulas in bayesian inference. Probability theory and related fields, 173(3):1133-111) 2019.
[15] Jean Barbier and Nicolas Macris. The adaptive interpolation method for proving replica formulas. Applications to the Curie-Weiss and Wigner spike models. Journal of Physies A: Mathematical and Theoretical, 52(29):294002, 2019.
[16] Jean Barbier, Nicolas Macris, Antoine Maillard, and Florent Krzakala. The mutual information in random linear estimation beyond i..d. matrices. In International Symposium on Information Theory, pages 1390-1399 2018.
[17] Jean Barbier, Nicolas Macris, and Cynthia Rush. All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation. In Advances in Neural Information Processing Systems, 2020.
[18] Mohsen Bayati and Andrea Montanari. The dynamics of message passing on dense graphs, with applications compressed sensing. IEEE Transactions Information Theory, 57(2):764-775, 2011.
[19] Mohsen Bayati and Andrea Montanari. The LASSO risk for gaussian matrices. IEEE Transac- fions on Information Theory, 58(4):1997-2011 2012.
[20] Robert M Bell and Yehuda Koren. Lessons from the netflix prize challenge. Acm Sigkdd Explorations Newsletter, 9())75-79, 2007.
[21] Florent Benaych-Geeoges and Raj Rao Nadakuditi. The eigenvalues and eigenvectors finite, low rank perturbations of large random matrices. Advances in Mathematics, 227(1):494-521, 2011.
[22] Florent Benaych-Georger and Raj Rao Nadakuditi. The singular values and vectors of low rank perturbations of large rectangular random matrices. Journal of Multivariate Analysis, 111:120-135, 2012.
[23] Bhaswar B. Bhattacharya and Subhabrata Sen. High temperature asymptotics of orthogonal mean-field spin glasses. Journal of Statistical Physics, 162(():63 80, 2016.
[24] Erwin Bolthausen. An iterative construction of solutions of the TAP equations for the SherrintoonKKikpattrck model. Communications Mathematical Physics, 323(1):333-366 2014.
[25] Jelena Bradic. Robustness in sparse high-dimensional linear models: relative efficiency and robust approximate message passing. Electronic Journal of Statistics, 10(2):38943333 3944, 2016.
[26] Mireille Capitaine, Catherine Donati-Martin, and Delphine Féral. The largest eigenvalues of finite rank deformation of large Wigner matrices: convergence and nonuniversality of the fluctuations. The Annals of Probability, 37(1): 2009.
[27] Ismaël Castillo, Johannes Schmidt-Hieber, and Aad Van der Vaart. Bayesian linear regression with sparse priors. The Annals of Statistics, (385))19866220
2015.
[28] Yash Deshpande, Emmanuel Abbe, and Andrea Montanari. Asymptotic mutual information for the balanced binary stochastic block model. Information and Inference: A Journal of the IMA, 6(2):125-170, 2017.
[29] Yash Deshpande and Andrea Montanari. Information-theorrtiaallly optimal sparse PCA. In IEEE International Symposium on Information Theory, pages 2197-2201, 2014.
[30] David L. Donoho, Adel Javanmard, and Andrea Montanari. cooomatioontthoreticaa optimal compressed sensing via spatial coupling and approximate message passing. IEEE Transactions on Information Theory, 59(11):7434-746) 2013.
[31] David L. Donoho, Arian Maleki, and Andrea Montanari. Message-passing algorithms for compressed sensing. Proceedings of the National Academy of Sciences, 189145):18914-1891, 2009.
11

---

[32] David L. Donoho and Andrea Montanari. High dimensional robust M-estimation: asymptotic variance via approximate message passing. Probability Theory and Related Fields, 166(3- 4):935-969, 2016.
[33] Rishabh Dudeja, Junjie Ma, and Arian Maleki, Information theoretic limits for phase retrieval with subsampled haar sensing matrices. IEEE Transactions on Information Theory, (6(1))666))))))))))))) 20:0002- 8045, 2020.
[34] Noureddine EI Karoui. On the impact of predictor geometry the performance high- generalized robust regression estimators. Probability Theory and Related Fields, 170(1-2):95-177 2018.
dimensional
[35] Noureddine El Karoui, Derek Bean, Peter J. Bickel, Chinghway Lim, and Bin Yu. On robust regression with high-dimensional predictors. Proceedings of the National Academy of Sciences, 11003)):4557-114522 2013.
[36] Barbara E. Engelhardt and Matthew Stephens. Analysis of population structure: unifying framework and novel methods based on sparse factor analysis. PLoS genetics, 6(9)e 17, 2010.
[37] Zhou Fan. Approximate message passing algorithms for rotationally invariant matrices. The Annals of Statistics, 50(1)2197-224, 2022.
[38] Zhou Fan and Yihong Wu. The replica-symmetric free energy for ising spin glasses with orthogonally invariant couplings, 2021. arXiv:2105. 02797.
[39] Oliver Y. Feng. Ramji Venkataramanan, Cynthia Rush, and Richard J. Samworth. A unifying tutorial on Approximate Message Passing, 2021. arXiv:2105. 02180.
[40] Delphine Féral and Sandrine Péché. The largest eigenvalue of rank one deformation of large Wigner matrices. Communications mathematical physics, (72(1):188, 272(1):185-228, 2007.
[41] Alyson K. Fletcher and Sundeep Rangan. Iterative reconstruction of rank-one matrices in noise. Information and Inference: A Journal of the IMA, 7(3):531-562, 2018.
[42] Marylou Gabrié, Andre Manoel, Clément Luneau, Jean Barbier, Nicolas Macris, Florent Krza- kala, and Lenka Zdeborová. Entropy and mutual information in models of deep neural networks. Journal of Statistical Mechanics: Theory and Experiment, 2019(12), (0)))111) 2019.
[43] Cedric Gerbelot, Alia Abbara, and Florent Krzakala. Asymptotic errors for teacher-student convex generalized linear models (or: how to prove Kabashima's 's replica formula), 2020. arXiv:2006. 06581
[44] Alice Guionnet and Jiaoyang Huang. Large deviations asymptotics of rectangular spherical integral, 2021. arXiv: 2et.:21100.0620 07146.
[45] Alice Guionnet and Mylène Maida. A Fourier view on the R-transform and related asymptotics of spherical integrals. Journal of Functional Analysis, 222(():435 4900 2005.
[46] Dongning Guo, Shlomo Shamai, and Sergio Verdú. Mutual information and minimum mean- square error in gaussian channels. IEEE Transactions on Information Theory, 1214)122111228 2005.
[47] TianQi Hou, YuHao Liu, Teng Fu, and Jean Barbier. Sparse superposition codes under VAMP decoding with generic rotational invariant coding matrices, 2022. 220.:::2222.0455
[48] Adel Javanmard and Andrea Montanari. State evolution for general approximate message passing algorithms, with applications to spatial coupling. Information and Inference: Journal of the IMA, 125):115-144, 144, 2013.
[49] lain M. Johnstone. the distribution of the largest eigenvalue in principal components analysis. The Annals of statistics, 29(2)2295-327, 2001.
12

---

[50] lain M. Johnstone and Arthur Yu Lu. On consistency and sparsity for principal components analysis high dimensions. Journal of the American Statistical Association, 104(486):682-69) 693, 2009.
[51] Yoshiyuki Kabashima, Florent Krzakala, Mare Mézard, Ayaka Sakata, and Lenka Zdeborová. Phase transitions and sample complexity in bayes-optimal matrix factorization. IEEE Transac- tions on Information Theory, 62(7))4228 42088,42655050 2016.
[52] Antti Knowles and Jun Yin. The isotropic semicirele law and deformation of Wigner matrices. Communications on Pure and Applied Mathematics, 1613:166666144999 2013.
[53] Satish Babu Korada and Nicolas Macris. Exact solution of the gauge symmetric p-spin glass model on a complete graph. Journal of Statistical Physics, 136(2):205-230, 2009.
[54] Mare Lelarge and Léo Miolane. Fundamental limits of symmetric low-rank matrix estimation. Probability Theory and Related Fields, (73(3-4):859-9299 2018.
[55] Thibault Lesieur. Florent Krzakala, and Lenka Zdeborová. Constrained low-rank matrix estima- tion: Phase transitions, approximate message passing and applications. Journal of Statistical Mechanics: Theory and Experiment, 2017(7):073403, 2017.
[56] Junjie Ma, Ji Xu, and Arian Maleki. Analysis of sensing spectral for signal recovery under a generalized linear model. In Advances in Neural Information Processing Systems, 2021.
[57] Antoine Maillard, Laura Foini, Alejandro Lage Castellanos, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. High-tene tigpeeeeperr expansions and message passing algorithms. Journal of Statistical Mechanics: Theory and Experiment, 2019(11): 2019.
[58] Antoine Maillard, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Phase retrieval in high dimensions: Statistical and computational phase transitions. In Advances in Neural Information Processing Systems, 2020.
[59] Marco Mondelli and Ramji Venkataramanan. Approximate message passing with spectral initialization for generalized linear models. In International Conference on Artificial Intelligence and Statistics, 2021.
[60] Marco Mondelli and Ramji Venkataramanan. PCA initialization for approximate message passing in rotationally invariant models. Neural Information Processing Systems, 2021.
[61] Andrea Montanari and Ramji Venkataramanan. Estimation of low-rank matrices via approximate message passing. Annals of Statistics, 45(1):3113345, 2021.
[62] Cristopher Moore. The computer science and physics of community detection: landscapes, phase transitions, and hardness, 2017. arXiv:1702 00467.
[63] Sumit Mukherjee and Subhabrata Sen. Variational inference in high-dimensional linear regres- sion, 2021. arXiv:2204 12232.
[64] Jonathan Novak. Three lectures on free probability. Random matrix theory, interacting particle systems, and integrable systems, 65(309-383):13, 2014.
[65] Manfred Opper, Burak Cakmak, and Ole Winther. theory of solving tap equations for ising models with general invariant random matrices. Journal of Physics A: Mathematical and Theoretical, 19:11): 14002, 2016.
[66] Parthe Pandit, Mojtaba Ardakan, Sundeep Rangan, Philip Schniter, and Alyson K Fletcher. Inference with deep generative priors in high dimensions. IEEE Journal on Selected Areas in Information Theory, 1(1):336-33 347, 2020.
[67] Giorgio Parisi and Mare Potters. Mean-field equations for spin models with orthogonal interac- tion matrices. Journal of Physics A: Mathematical and General, 28(18)5226, 1995.
[68] Debashis Paul. Asymptotics of sample eigenstructure for a large dimensional spiked covariance model. Statistica Sinica, pages 1617-1642, 2007.
13

---

[69] Amelia Perry, Alexander S. Wein, Afonso S. Bandeira, and Ankur Moitra. Message- gassinng algorithms for synchronization problems over compact groups. Communications on Pure and Applied Mathematics, 71(11):2275-222) 2018.
[70] Mare Potters and Jean-Philippe Bouchaud. A first course in random matrix theory. Cambridge University Press, 2021.
[71] Farzad Pourkamali and Nicolas Macris. Mismatched estimation of rank-one symmetric matrices under gaussian noise, 2021, arXiv arXiv:2107 08927.
[72] Alkes L. Price, Nick J. Patterson, Robert M. Plenge, Michael E. Weinblatt, Nancy A. Shadick, and David Reich. Principal components analysis corrects for stratification in genome-wide association studies. Nature genetics, 38(8))904-900) 2006.
[73] Sundeep Rangan. Generalized approximate message passing for estimation with random linear mixing. In International Symposium on Information Theory, pages 2168-2172, 2011.
[74] Sundeep Rangan, Philip Schniter, and Alyson K Fletcher. Vector approximate message passing. IEEE Transactions on Information Theory, 65(10))6644-6684, 2019.
[75] Kolyan Ray and Botond Szabó. Variational Bayes for high-dimensional linear regression with sparse priors. Journal of the American Statistical Association, pages 1-12, 2021.
[76] Subrata Sarkar, Rizwan Ahmad, and Philip Schniter. MRI image recovery using damped denoising vector AMP. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1108-8112 2021.
[77] Pragya Sur and Emmanuel Candès. A modern maximum-likelihood theory for high- dimensional logistic regression. Proceedings of the National Academy of Sciences, 116629):1511--44555, 2019.
[78] Takashi Takahashi and Yoshiyuki Kabashima. Macroscopic analysis of vector approximate message passing in a model mismatch setting. In International Symposium on Information Theory, pages 1403-1408, 2020.
[79] Koujin Takeda, Shinsuke Uda, and Yoshiyuki Kabashima. Analysis of CDMA systems that are characterized by eigenvalue spectrum. EPL (Europhysics Letters), 76(6):1192 193, 2006.
[80] Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi. Precise error analysis of regularized M-estimators in high dimensions. IEEE Transactions on Information Theory, 64(8):5592-5622 2018.
[81] Christos Thrampoulidis, Samet Oymak, and Babak Hassibi. Regularized linear regression: A precise analysis of the estimation error. In Conference Learning Theory, 2015.
[82] Ramji Venkataramanan, Kevin Kögler, and Marco Mondelli, Estimation in rotationally invariant generalized línear models via approximate message passing, 2021. arXiv: 04330.
[83] Sergio Verdú. Mismatched estimation and relative entropy. IEEE Transactions on Information Theory, 56(8):3712-3720, 2010.
[84] Cédric Villani. Optimal transport: Old and new, volume 338. Springer Science & Business Media, 2008
[85] Tsachy Weissman. The relationship between causal and noncausal mismatched estimation in continuousttima awgn channels. IEEE Transactions on Information Theory, 56(9))4256-4277 2010.
[86] Xinyi Zhong, Chang Su, and Zhou Fan. Empirical bayes PCA in high dimensions, 2020. 2012: 11676.
[87] Xinyi Zhong, Tianhao Wang, and Zhou Fan. Approximate message passing for orthog- onally invariant ensembles: Multivariate non-linearities and spectral initialization, 2021. arXiv:2110 2110.02110.00 21111.111111....
[88] Hui Zou, Trevor Hastie, and Robert Tibshirani. Sparse principal component analysis. Journal of computational and graphical statistics, 15(2):265-286 2006.
14

---

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] Our model assumptions clearly explained in Assumptions [ 2 and To obtain the overlap of the mismatched Bayes
estimator, make conjecture the convergence of || /N (see the discussion right after the statement of Theorem
(c) Did you discuss any potential negative societal impacts of your work? [N/A] We do not direct paths to applications with negative societal impacts.
(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] Our model assumptions are clearly explained in Assumptions [ and [3] To obtain the overlap of the mismatched Bayes estimator, we make a conjecture on the convergence of
Mmmis|lr/ /N (see the discussion right after the statement of Theorem I.
(b) Did you include complete proofs of all theoretical results? [Yes] Proof sketches are
included right after the corresponding statements. The full proofs of Theorem 1 and
are in Appendices and C respectively.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as a URL)? [Yes] In Section 4 we describe the experimental setup containing the instructions to reproduce the results of Figure I (and of Figure contained in Appendix D.3 as well). Additional details are given in Appendices D.I D.2 The code that implements the various algorithms is included the supplementary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] All details of the experimental setup are described in Section and in Appendices Ind D.2]
and
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] Each experiment is repeated for 10 independent runs, and we report the average together with the confidence interval at standard deviation.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A] We did not perform large scale experiments that required to specify this type of details.
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] We are not using existing assets curating/releasing new assets.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A] We did not use crowdsourcing or conducted research with human subjects.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, 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": "RicTV0sC2p", "reviewer": "Reviewer_RAkD", "summary": "The authors considered the problem of rank-one signal estimation corrupted by structured rotationally invariant noise, and studied the situation when the actual noise statistics deviates from the Gaussian assumption. Three estimation procedures were proposed and discussed: mismatched Bayes estimator, approximate message passing, and spectral estimators. Both theoretical analysis and simulation experiments were provided to compare these different methods, together with reasonable conclusions and interesting insights.", "questions": "The authors mentioned that the performance gap between the AMP algorithm and the Bayes estimator is due to an incorrect estimation of the signal norm. A natural question is whether the AMP algorithm could be modified accordingly, so that a better estimation of signal norm can be achieved, so as to narrow down the gap to the Bayes estimator.", "limitations": "The paper focused on theoretical analysis and simulated experiments. It would be nice if the authors can relate the research to some real world scenarios, and show some experimental results on real data.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1) A thorough study on the mismatched estimation problem for rank-one matrices was provided, with in-depth theoretical analysis and interesting empirical findings.\n2) Different estimation methods were proposed and compared, showing the strengths and weaknesses of each method.\n3) An interesting phenomenon was identified that Gaussian AMP does not perform as well as the mismatched Bayes estimator. Discussions were provided on potential causes of this phenomenon.\n\nWeaknesses:\n1) The Gausian AMP algorithm was provided in equation (8), but not much details were provided on how it is derived. It is unclear what objective function this procedure is optimizing. More technical details would help the readers to better understand the algorithm.\n2) Similarly, the mismatch performance metrics were provided in equation (9), but not much details were provided on the meaning of these metrics. Better explanations of these metrics may help the readers to better understand the motivations behind the equations.", "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": "HpDDQeOazel", "reviewer": "Reviewer_MSna", "summary": "This paper studies rank-1 matrix estimation and provides performance guarantees for two inference methods, a Bayes estimator and an AMP algorithm. ", "questions": "See \"Strengths And Weaknesses\".", "limitations": "See \"Strengths And Weaknesses\".", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. The author should comment on whether Assumption 3 holds for some representative examples like soft-thresholding function under the setting considered in this paper.\n2. The results and quantities mentioned below Theorem 2 should be formalized into a theorem or corollary.\n3. How crucial does Theorem 1 depend on the prior distribution on the signal X (line 163)? Given that the topic of this paper is to study whether these estimators are robust to wrong noise distributional assumption, it doesn't make sense if the result relies highly on the distributional assumption on the signal X (which seems to be an even stronger assumption that might not be correct).\n4. When analyzing AMP, the authors assume access to an initialization that is independent of the noise and satisfy certain probabilistic condition (line 186). The authors also claim that in prior literature it is possible to analyze AMP with a practical spectral initialization (line 190). Given the assumed model is already simple enough (rank-1 spiked model), I recommend the authors to improve their analysis to adapt to such a practical initialization scheme.\n5. I suggest the authors to make effort discussing their theoretical result in more detail and show how they are related to the main topic of the paper. Currently it is difficult to see this from Theorem 1 and 2.\n6. If I am not missing something, the main result for spectral estimators is missing, although from Section 2.3 it seems that there should be some theory for spectral estimators.", "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": "FaWi64Mr-og", "reviewer": "Reviewer_ggxP", "summary": "The paper considers the penalty to be paid when recovering a rank-1 matrix from noisy partial observations when the noise is assumed to be Gaussian in the case where the noise isn't so. The paper's analysis considers two algorithms and regimes: a Bayes estimator in an asymptotic regime and an approximate message passing algorithm in a state evolution regime. The analysis finds a gap in the performance of the two estimators that depends on the level of noise due to an inaccurate estimation of the signal norm in AMP.\n", "questions": "For the rescaled overlap measure (5), is it the same as the asymptotic the cosine distance between $\\bf X$ and $\\bf{\\hat{x}}({\\bf Y})$? If yes, this may be easier to describe. Additionally, the concern on the Bayes estimator in line 179 seems to be independent of the overlap measure - would it not also apply to the MSE?\n\nWhere is the function ht in (8) described? The sketch of the proof of Theorem 2 refers to \"choosing denoisers carefully\". Can there be a more explicit discussion of what \"carefully\" choosing denoisers entails in practice?\n\nIn line 254, should \"converges... to the random vector\" be \"converges... to that of the random vector\"? It may help with clarity to state at this point that the second random vector provide the state evolution for this AMP analysis.", "limitations": "The paper could use a more detailed discussion on the applicability of Assumptions 1, 2, and 3 in practical settings.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The experimental results show a good match between the performance predictions of the analytical results and the true performance levels from the numerical simulations, and f the dependence of the performance gap between the algorithms on the SNR and noise model mismatch level.\n\nSome instances of simplified notation do not seem necessary, and can detract from clarity (e.g., dropping the index N in line 171, the lack of description of the terminology used in Assumption 2). \n\nThe discussion after Theorem 2 would be more clearly stated as a corollary: given that the statement of Theorem 2 appears to be very broad, the authors could provide a statement that is more relevant to assessing the performance of the estimators using metrics like those shown before.", "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": "5LuitNkWlVR", "reviewer": "Reviewer_oMyw", "summary": "This paper presents a theoretical analysis of the performance of two algorithms for rank-1 matrix recovery under mismatched noise. Specifically, a closed-form MSE for the Bayes estimator and a state evolution analysis of the AMP algorithm are provided. The paper also discusses some phenomena arising from numerical experiments regarding these algorithms under two different performance metrics.", "questions": "The discussion about Bayes estimator and AMP from the numerical results is interesting, but it might be helpful to provide more insights into the performance gap of AMP and Bayes in this problem setup, in addition to this phenomenon itself.\n\nI understand that this is a theoretical work and if the authors think these are out of scope for this work, but I'd appreciate it if the authors can provide some comments about the applicability of the algorithms discussed in this paper. Under what type of scenarios might one favor one approach over the other?\n", "limitations": "While this is very theoretical work that proves performance guarantees, a dedicated discussion of the limitations of the scope and applicability of the results might still be helpful.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- This paper gives theoretically solid performance guarantees for the Bayes estimator and AMP algorithm for mismatched rank-1 matrix recovery. Settings with unknown noise distributions are common in real-world applications, where this work helps to understand the effect of these algorithms under mismatched noise. \n- Numerical experiments comparing the theoretical, experimental, and noise-aware performances are presented, which corroborate the results of this paper and shed light on the points of discussion.\n- The writing and presentation of this paper is clear.\n\nWeaknesses:\n- Aside from the technical contributions, I am not fully convinced of the level of impact that this paper makes. This paper analyzes two existing algorithms with mismatched spherically symmetric noise, which is a step up from the analysis in [71] of mismatched Gaussian SNR, but might not suffice for this venue. Would consider raising the score if this concern is properly addressed.", "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