Optimal Algorithms for the Inhomogeneous Spiked Wigner Model
Authors: Alexander Pak
Justin Ko
Florent Krzakala
Venue: NeurIPS 2023 poster (2023)
Keywords: Spectral Method
Community detection
Wigner Spike model
Random Matrix
BBP transition
Approximate Message Passing
Spin glasses
Statistical Physics
TL;DR: To get a BBP transition in the spike model with Inhomogeneous noise, you should do PCA on *this* matrix, not the original one!

Abstract: We study a spiked Wigner problem with an inhomogeneous noise profile. Our aim in this problem is to recover the signal passed through an inhomogeneous low-rank matrix channel. While the information-theoretic performances are well-known, we focus on the algorithmic problem. First, we derive an approximate message-passing algorithm (AMP) for the inhomogeneous problem and show that its rigorous state evolution coincides with the information-theoretic optimal Bayes fixed-point equations. Second, we deduce a simple and efficient spectral method that outperforms PCA and is shown to match the information-theoretic transition.

Optimal Algorithms for the Inhomogeneous Spiked Wigner model
Justin Ko ENS de Lyon justin. kolens-ynnn. fr
Florent Krzakala
EPFL
florent. florent.krrakeeeefff.cc
Aleksandr Pak
ENS de Lyon, EPFL aleksandr, pak@epfl.ch
Abstract
We study a spiked Wigner problem with inhomogeneous noise profile. Our aim in this problem is to recover the signal passed through an inhomogeneous low-rank matrix channel. While the anformation-theoreee known, we focus on the algorithmic problem. First, we derive an approximate pressage-passingg algorithm (AMP) for the inhomogeneous problem and show that its rigorous state evolution coincides with the fixed-point equations satisfied by the Bayes-optimal estimator. Second, we deduce a simple and efficient spectral method that outperforms PCA and is shown to match the information-theorrticc transition.
performances are well-
Low-rank information extraction from a noisy data matrix is crucial statistical challenge. The spiked random matrix models have recently gained extensive interest in the fields of statistics, probability, and machine learning, serving as a valuable platform for exploring this issue Donoho and Johnstone [1995]. Péché [2014], Baik et al. [2005]. A prominent example is the spiked Wigner model, where rank one matrix is observed through component-ww wisse wise homogeneous noise.
Here we consider the inhomogeneous version of the model which has been recently introduced in series of papers Barbier and Reeves [2020], Behne and Reeves [2022], Alberici al. [2021a, 2022] and naturally arises in different contexts such as community detection Behne and Reeves [2022]. deep Boltzmann machines Alberici al. [2021b] etc. In particular, it corresponds the dense limit of the degree-corrected stochastic block model Karrer and Newman [2011] (see the explicit mapping Guionnet et al. [2022]). In this model the signal is observed through an inhomogeneous Gaussian noise with block-constant variance profile. Such block-constant noise naturally arises in settings such as community detection and stochastic-bles block models. The assumption for the noise to be Gaussian universality result in Guionnet al. [2022] shows that an entrywise
is in way restrictive transformation of data generated from a general inhomogencous inference problem reduces any probabilistic noise to the spiked Wigner problem with Gaussian data. This generality is what makes the model appealing.
We now define the model: Consider a partition (1..... N)= = [N] into disjoint groups C U...U
CAN []. This partition is encoded by function g [N] - [q] which maps each index [N]
into its group g(i) e [q]. Let À e 1R be symmetric matrix encoding block-constant symmetric
matrix
A.j g()))())
We assume both the noise profile Á and the partition function y be known. This is often the case in practical applications, such as the degree-corrected block model, Karrer and Newman [2011]
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Additionally, in practical applications where the noise profile is not known, one can often empirically estimate the noise profile and assign group membership according to the empirical variances. Such an approach is likely to yield good results but lies outside the scope of the present work.
We observe the signal x² RN which is assumed have independent identically distributed coordinates generated from some prior distribution Pu (i.e. P(x* x) I[ Po(æ x2))
through noisy measurements:
Y Y= xx'))" A
(2)
Here and throughout the article O denotes the Hadamard product, V is the Hadamard square-root of A and A is real-valued symmetric GOE matrix with off-diagonal elements of unit variance. The Bayes-optimal performance of this model in the asymptotic limit N + co was studied rigorously in Guionnet et al. [2022], Behne and Reeves [2022]. Chen and Xia [2022], Chen al. [2021] who characterized the fundamental information-theoretic limit of reconstruction in this model.
Here we focus instead on the algorithmic problem of reconstructing the (hidden) spike. Our contributions are many-fold:
We show how one can construct an Approximate Message Passing (AMP) algorithm for the inhomogeneous Wigner problem, whose asymptotic performance can be tracked by rigorous state evolution, generalizing the homogeneous version of the algorithm for low-rank factorization [Bayati and Montanari, 2011, I, Deshpande et al., 2015, Lesieur et al., 2017].
We derive fixed-point equation for AMP and show that it coincides with the fixed-point equation for the Bayes-optimal estimator obtained in Guionnet et al. [2022]
Finally, we present linear version of AMP [Maillard al., 2022], that is equivalent to a spectral method. We conjecture it to be optimal in the sense that can detect the presence of the spike in the same region as AMP. This is quite remarkable since, as shown in [Guionnet et al., 2022, Section 2.4), the standard spectral method (PCA) fails to do so.
Related work The class of approximate message passing algorithms (AMP) has attracted a lot of attention in the high- -igeniimeniioall statis- ties and machine learning community, see c.g. [Donoho al., 2009, Bayati and Montanari, 2011, Rangan, 2011, Deshpande et al., 2015, Lesieur et al., 2017, Gerbelot and Berthier, 2021, Feng et al., 2022]. The ideas behind this al- gorithm have roots in physics of spin glasses Mézard et al. [1987], Bolthausen [2014], Zde- borová and Krzakala [2016]. AMP algorithms are optimal among first order methods [Ce- lentano al., 2020], thus their reconstruction threshold provides bound on the algorithmic complexity in our model. Our approach to the inhomogeneous version of AMP relies on sev- eral refinements of AMP methods to handle the full complexity of the problem, notably the spa- tial coupling technique Kızakala et al. [2012], Donoho et al. [2013], Javanmard and Montanari [2013], Gerbelot and Berthier [2021], l]. Rossetti and Reeves [2023].
AMP
10
optimal
0.9
0.8
0.7
0.5
0.4
0.5
100
1.5
2.0
25
3.0
SNR
Figure 1:
Performance of the inhomoge-
neous AMP algorithm against the information- theoretical optimal MMSE. The variance profile
is proportional to Á 1 3
2 with two equally
3
sized blocks with standard Gaussian prior when N = 500 at various snr.
Factorizing low-rank matrices is a ubiquitous problem with many applications in machine learning and statistics, ranging from sparse PCA to community detection and sub- matrix localization. Many variants of the homogeneous problem have been studied in the high-dimensional limit [Deshpande et al., 2015, Lesieur et al., 2017, Barbier et al., 2018, Lesieur et al., 2017, Alaoui et al., 2020, Lelarge and Miolane, 2019, Louart and Couillet, 2018 8, Barbier and Reeves, 2020]. The inhomogeneous version was discussed in detail in Guionnet et al. [2022], Behne and Reeves [2022]. Alberici et al. [2021a]. Spectral methods are very popular tool to solve fank-factorization problems [Donoho and Johnstone, 1995, Péché, 2014, Baik et al., 2005]. Using AMP as an inspiration for deriving

---

new spectral methods was discussed, for instance, in Saade et al. [2014], Lesieur et al. [2017]. Aubin al. [2019], Mondelli and Montanari [2018], Mondelli et al. [2022]. Maillard al. [2022]. Venkataramanan et al. [2022].
Main results
Message passing algorithm- For each 2 let (fZ)ac(d) be a collection of Lipschitz functions from R, and define for t N ft RN + RN by
f((z) = (f2 (EN)) E..
These functions are often called denoiser functions and can be chosen amongst several options, such as the Bayes optimal denoisers for practical applications (see Section 2), or even linear denoisers (see Section 3). We shall consider the following AMP recursion
x
VNA
fi (x') - -b. 0 (x'-1)
(3)
1 with the so-called Onsager term b. = NA f1(x²) E R.N. where 1 is the Hadamard inverse of and fi is the vector of coordinate wise derivatives.
In practical implementations, we initialize the algorithm with some non-null x and let run for certain number of iterations. One efficient way to do this is the spectral initialization [Mondelli and Venkataramanan, 2021] with the method described in sec. 3. In Figure we provide an example of the performance of the AMP together with the Bayes-optimal estimator predicted by the asymptotic theory. Even at very moderate sizes, the agreement between theory and simulation is clear.
State evolution - AMP was the basis of many works for the homogeneous case e.g. Deshpande et al. [2015], Lesieur et al. [2017]. Our first contribution is the introduction of an AMP and of its rigorous state evolution [Javanmard and Montanari, 2013, Theorem 1] in the inhomogeneous setting. To state well-defined limit of the AMP, have the following assumptions.
Assumption 1.1. To ensure that inhomogeneous AMP has well-defined limit, we assume that
1. For each E [g], we have
ICN
lim -
ca E (0.
For each & [N] and [g], both (St) and (SeY are Lipschitz.
3. For each E [g), there exists (o%)² E B such that, in probubility.
lim -0000
Σ (60)))(()) - (o9)² LECH
CN
Our first result describes the distribution of the iterates in the limit. Our mode of convergence will be with respect to L-pseudo-Lipschitz test functions Φ M + R satisfying
(xxx) - Φ(y)1 < T.(1 + ||>||| + ||vli)] vll
for all x, y E M.
(4)
We define the following state evolution parameters μ and of for b E [g] through the recursion
++1
Co Bug z Zlg (ui=g + dzZ)] with zi Po. ~ N(0
1b
aE !
ah
(5)
(o
Ca
Bug.2
[IF (ph + o 2) with 25 ~ Pa. 2 ~ NNO,
where zg and 7 are independent. We prove that the iterates on are asymptotically equal in distribution to ut 20 + tf 2'0) where zi ~ Po and Z is independent standard Gaussian.

---

Theorem 1.2 (State evolution of AMP iterates in the inhomogeneous setting). Suppose that Assump- tion 1.1 holds, and that P. has bounded second moment. Let R R be a 2-pseudo-Lipschite test functions satisfying (4). For any [q], the following limit holds almost surely
lim
Σ
=
CN
LECO
where Z a standard Gaussian independent from all other variables.
Remark 1.3. The notion of convergence under the 1-pseudo-Lipschie test functions induces topology that is equivalent the one generated by the L-Wasserstein topology [Feng al., 2022, Remark 7.18J. We can strengthen the second moment assumption on IP to finite kth moment, but the induced topology will then change to the k- --Wsssesstiin topology, see JJvannard and Montanari, 2013, Theorem 1].
Even though the theoretical result above applies in the high-dimensional limit, numerical simulations show that even for medium-sized N (around 500), the behaviour of the iterates is well described by state evolution parameters. Through the state evolution equations (5) we are able to track iterates of the AMP iteration with just two vectors of parameters obeying the state evolution recursion:
the overlap with the true signal (μ², (a]j) and its variance (o (o')aelg' We next obtain the following necessary and sufficient condition for the overlaps of a fixed point of the iteration (2):
Theorem 1.4 (Bayes- Oattial fixed point). Assume AMP satisfies Assumption 1.1 and let the denois- ing functions be the Bayes ones (32). Then the overlaps = (Pa)oElo) in (5) satisfy the following fixed point equation
Ph Σ
Aub Eogg
Ca
B posttrrior Mo + v P Z]}.
aE[a]
Remark 1.5. The state evolution fixed point equation above coincides with the fixed point equation satisfied by the Bayes optimal estimator in [Guionnet et al., 2022, Equation 14).
spectral method-
Given the matrix Y defined in (2) we consider the transformed matrix
Ban (=n))
O
Eug [11)) diag
NA
N A
Let (Ca)ae(v)- We define the inhomogeneous signal-to-noin (SNR) ratio of such model by
1
SNR(A) A(A) = Em;((<)) diag( (Vc) diag Vc op
(8)
The top eigenvalue of separates from the bulk if and only if the signal to noise ratio A(A) > 1. In particular, if is the top eigenvector of Y then if and only if ((A) < we have:
Conjecture 1.6.
x= x
lim +0
0.
The conjecture is based on heuristic arguments identifying the fixed point of AMP with spectral method, This matches precisely the recovery transition in [Guionnet et al., 2022, Lemma 2.15 Part (b)]. In this paper, we rigorously show that with SNR(A) our proposed spectral method fails to recover the signal. We illustrate the eigenvalue BBP-like transition in Fig.2.
The inhomogeneous AMP algorithm
In this section, we derive the formula for the inhomogeneous AMP iteration (25). We first recall the general matrix framework of AMP from [Javanmard and Montanari, 2013]:

---

Figure 2: Illustration of the spectrum of Y x100 evaluated noise profiles with X 0.7 (left, before the transition) and 1.8 (right, after the transition), with the outlying eigenvector correlated with the spike arises eigenvalue one.
Matrix AMP (R?) N
the matrix setting an AMP algorithm operates on the vector space Vg.N = R gxx Each element of v UN)) E Va.N will be regarded as N-vector with entries U, E R7.
Definition 2.1 (AMP). A matrix AMP acting on this space is represented by (A,F, v²), where:
G GT, where G E ENNN has iid entries Gig (0, Lipschitz.functions
F is a family of N Lipschitz functions fi + R9, E [N] indexed by time I N. The family
F encodes a function Js. VA,N + Vq.N that acts separately each coordinate új E R2,
f((v) (f)())..... St (UN) Vg.N.
(9)
00 E Vy.N is a starting condition.
The algorithm itself is sequence of iterates generated by:
A
[+1
Je (v') - fi-1 (1-
(10)
where B, is the q x Onsager matrix given by
B, Σ (o))
(1I)
where of? denotes the Jacobian matrix of f. The limiting properties of the AMP sequences are well known and can be found in [Javanmard and Montanari, 2013, Theorem I].
The inhomogeneous AMP We now define an inhomogeneous AMP iteration which takes into account the block-constam structure of the noise:
Definition 2.2. An inhomogeneous AMP on VI,N = TRN is represented by (A,F, x A), where the terms A, F, x are defined in Definition 2.1 and A is the N x N variance profile encoded by Á IRa8 and grouping g [N] + qg] defined by (1), We further assume that the family of functions F is encoded by functions f R + IR for E [g] which define the group dependent function
fe(z) = (1) (x1) (x1)...., (g(N) (IN)) E N.
(12)
The sequence of iterates
x' N of the (A,F, vo, A) are defined as follows:
x ++1
b, O fr- f--1(00 (2² V AA fo fx()) (x')
(13)
5

---

where 1 is the Hadamard inverse square root of the noise, and the Onsager term b, has the following form
VA
A.1 ((x))
BIN (
+
1 b, ANI ((a))
1 NA ((()))) (14)
N
ANN (fa
State evolution of the inhomogeneous AMP Through a continuous embedding, we will reduce our inhomogeneous AMP to the matrix AMP framework, and recover the state evolution of the inhomogeneous AMP. We define the diagonal matrix operator blockdiag : RN + Vg,N which outputs block diagonal matrix according to the block structure of our discretization of [N]:
Ui {0
g()) = otherwise.
blockdiag(1) = M where Mij
Likewise, define the projection operator blockproj : Vg.N N from a N x g according to the block structure of [N] by
TR.. which extracts vector of size
blockproj (MinG)) E RR
Under these changes of variables, we define
r' blockdiag(a")) Va,1r
for 0
and fo: (R2) ( by
(F((*) ij V
1
1e (x!)
for E [N] [a]-
(15)
We encode the family of functions fo by F(D). Lemma 2.3. Let x' be iterates from the AMP (A.F, A). Then the iterates r = blockdiag(#2 (xx) follow the generalized matrix AMP (A, F(A),,)
Proof. We will show that the projection of the iterates r² from (A, ((A), r0) are the iterates from (A,F, v0 A). It is easy to check that
A
f f((x)) blockproj
VN F((r'))
A
(16)
N
Next, notice that Jacobian is given by
(1(0))()))
V
of((!) =
(1())()))
V
which is matrix where only the column number g()) has non-zero elements. Applying (11), we thus get for a, b E [g] [q]
(Bi)ad A i:9(1==
E (f:)
(17)
follows that
by 2 ft-1(x blockproj (fr-1(r'-1)B!)

---

As consequence, the inhomogeneous state evolution equations in Theorem 1.2 follow immediately from the state evolution equations of (A,F(A ). r²) discussed in [Javanmard and Montanari, 2013, Section 2.1]. This follows from the observation that given the law of r' in the high dimensional limit, the law of x² blockproj(r") is straightforward to compute. We define
(o (
E (()))
(18)
ab
We will show that the distribution of the iterate æf is asymptotically normal with mean 0 and variance (o s(t))
Lemma 2.4 (Behavior of the inhomogeneous AMP iterates). Suppose that Assumption 1.1 holds, and that PP has bounded second moment. Let Φ TR2 - R be 1-pseudo-LLpschhe test function satisfying (4). For any a [g), then the following limit holds almost surely
lim -0000
o()),2)) E2g. 2,,0"
C221
iECN
where Z is an independent standard Gaussian.
Proof. In matrix-AMP [Javanmard and Montanari, 2013, Th. 1]. the marginals of the iterates rf from (A, F(A), ))) are approximately Gaussian and encoded by the positive definite matrices
E =
fi =
[z') "
for all i E C.N.
(19)
with Z' ~ N(0, E`) and E1+1
St
(20)
am
We now show that a E [g] and i E C... Et depends only on (o Ey Indeed, by the definition of fi we have
(k, = [ ( (Z))) =
1
1 (Z,))
(21)
Aak nk Aal
where 2E ~ (o:))) is the ath component of the Gaussian vector Z, The key observation here is that by construction our function fi, R2 + I2' depends only on the ith component Z of the Gaussian vector Z To characterize the limiting distribution of xx blockproj(r"). we only need to keep track of the variances (o))², E [N]. Using (21), for a given a E [q] and E C.
we write
((O.000 = = E (J z Des (i (z))
1
R [(
(22)
Aggt)
Finally, with (20) we get that for any b E [q] and any C. using Za N(0, (ot))
4
10 E(+1
ca (.(00).00)
Ca E (J/
(23)
ag(s)
The inhomogeneous spiked Wigner model in the light of the AMP approach - We now generalize the state evolution equations from Lemma 2.4 to spiked matrices with an inhomogenous noise profile as was stated in Theorem 1.2. This reduction via change of variables is standard, see for example [Deshpande et al., 2015, Lemma 4.4]. Remember that in the inhomogeneous version of the spiked Wigner model we observe the signal x* through an inhomogeneous channel:
Y I (x')T + A
(24)
7

---

Our AMP algorithm is defined with the following recursion:
1 .Y (x (zx)
be 2 S-- (a'-1)
(25)
where b, NA (i and ff is encoded by the family of functions in Definition 2.2. The main difference in contrast to the iteration (13) is that our data matrix is no longer a centered matrix, iteration of the form (13) with respect to
while VA ② A is. We would like reduce (25)
different parameter s' which is uniquely determined by xt
8
VNVA A
ft (8') b, o fi-1 (s'
Doing will allow to recover the limiting laws of the iterates from Lemma 2.4. This done via standard change of variables to recenter Y. We will sketch the argument in this section, and defer the full proof of Theorem 1.2 the Appendix A in the Supplementary Material.
To simplify notation,let us denote fi(x') := S.. We proceed following the approach of [Deshpande et al., 2015, Lemma 4.4]. We rewrite (25) using the definition of Y to get
x
Y
b C GC-1
VNA
A
(26)
+ (VI
(x+)T)
(x*)
(VNVA
b, 1011
N
indices are independent, then by the strong law of large numbers one would expect that
((N'
1 O x= (x*))²
Σ N A
1 mf
Σ Ca
E| jia
(27)
sEleliEcy
aE|9
where ia is some index belonging to the group C.N and æp is a random variable distributed according to the prior distribution Po. For b E !g] and C,N. we define the block overlap μá using the recursion
= 1b
Σ aE(1)
Ca Aab
Eng zo (M + o2
(28)
where Z is a standard Gaussian random variable independent from all others sources of randomness. Notice that (28) is precisely the asymptotic behavior of the summation appearing in (27).
We now make a change of variables and track the iterates
=
1 C xt"
x
11
②
x,, 1 121
(29)
where μ is the vector of block overlaps of the initial condition x with the truth. We reduced the (25) iteration the following iteration in which we easily recognize a version of (13):
1+1
A
fe (s
xx)) - b, @ fo (s" + t o x²)
(30)
V
with the initial condition 8
x
1 xx and the Onsager term taken from (14) is given by
b,
NA f(s
1
xx))
(31)
Using Lemma 2.4, we can recover the asymptotic behavior of the iterates x' given in (25) by computing the iterates sf dr C xx where s' follows (30) and μ4 satisfies (28), From this reduction we obtain the following state evolution equations describing the behaviour of (25):
1. 2 ~ 20 +002 for E [N], where Z ~ (0,
2. (+1 E.Elo) A.s Eyg, 2 A (n/,0 + 2) with zi Po. Z ~ A0
3. 11 Ei A.b Ezg.2 [fr (1/, 0f 2 with zj ~ Pu. Z ~ NO.
This (informally) characterizes the limiting distribution of the state evolution of the iterates from the inhomogeneous AMP stated in Theorem 1.2.

---

Fixed-poiee point equation of state evolution in the Bayes-optimal setting Suppose that we know the prior distribution Po of zó- The Bayes-optimal choice for the denoising functions fi j E [N] is simply the expectation of 26 with respect the posterior distribution,
(r) 5e (r) Eposterior (G) % 2 == r].
(32)
Under this Bayes-optimal setting, we can simplify the equations obtained in the previous section and see that AMP estimator is indeed an optimal one by studying its fixed point.
Proof of Theorem I.4. For this choice of f the Nishimori identity (see for example [Lelarge and Miolane, 2019, Proposition 16]) states that for [q] and j C.a
pha = Exg ( (ua00 - o Z) = E [(F (uA + o. 2)
(33)
In this setting, the state evolution equations from Theorem 1.2 reduce to
jig Eug.2 200 + Z) 1b = Ene(yl cu Pa b E [q]
(34)
(0) = Ene(al ea F [g].
Ant
Remarkably with the Bayes-optine choice of the denoising functions we have that for t 2 for each block b E [g]. 14,- 13 Therefore necessary and sufficient condition for an estimator to be a fixed point of the state evolution is to simply have its overlaps já unchanged by an iteration of the state evolution. This translates into the following equation for the overlaps μb, E [q]
Σ aE|g]
Ca Anb
12 (Ti vPa2]].
(35)
The result Theorem 1.4 now follows immediately.
3 A spectral method adapted to the inhomogeneous spiked Wigner model
From AMP to a spectral method - Remarkably, AMP and the state evolution machinery associated with it help us design simple spectral algorithm that matches the information- theoretic phase transition [Guionnet et al., 2022, Remark 2. 2.16]. Recall that Theorem 1.2 does not require the denoising functions fe be Bayes-optimal, but can be applied any Lipschitz family of functions. In this section, we analyze the state evolution for the family of identity functions, intuition motivating such choice by considering simple priors,
fe(x)) x. We can gain such as the Rademacher prior. In the case of the Rademacher prior simple computation shows that the Bayes-optimal choice of the denoising functions yields fl (*) tanh(*). In the first order approximation we have tanh(x) z. Thus, at least for the Rademacher prior, the choice of identity functions as denoising functions corresponds to the first order approximation of the Bayes-optimal choice. By Remark 3.1, we can assume that the entries x have unit variance. With this choice of denoising functions the AMP iteration will simply become:
1
x ++1
.Y x - -b, O x
where
b
(36)
VNN A
NA
NA
we denote B; diag(b;)
easy to see that the fixed point this iteration yields
x
Y
x
B.
(37)
VNA
so any æ fixed by the AMP iteration (36) must be an eigenvector of the matrix
-- B,
(--1111 1
(V1
V =
VNA oo
о Y - diag
(38)
VNA
N
A
A simple spectral method consists in taking the principal eigenvector (associated to the largest eigenvalue) of the matrix Y VNA B.

---

Analysis of the spectral method using state evolution The spectral algorithm described above behaves like the AMP iteration with identity denoising functions around its fixed point. Therefore we can analyze this spectral algorithm using state evolution machinery for the AMP iteration. In the case of identity functions we have (x) = x for all a [4],
E z Lvosi ( o Eug 2 12 ( +
- p/ 2) - (m() (a
(39)
Exg:2 x (0 (1 + of 2)) Eug. (1
(40)
which transforms state evolution equations (5) into the following simple form:
Ca P and ba
(aft1)2=
((Ha) (o
(41)
bo
aEly]
aEigl
Rewriting the overlap state evolution in a matrix form we get for c= (ca)as(u! that
Blag(Ve)p'=1 diag( vc) diag(ve (diag( (diag(ve))')) ve)
(42)
The special form of state evolution above is rather informative and we can interpret as follows. First of all, in the regime where ((A)= [ddag((C) A diag(v/) < 1, we can see from (42) that any iteration of the AMP recursion (36) contracts the vector overlap (multiplying it by matrix with the operator norm smaller than 1). Thus the only possible overlap of a fixed point of (36) is O. Moreover, we have defined the matrix Y in a way that any cigenvector of this matrix is fixed point of the AMP recursion (36). Thus any cigenvector of Y must have zero expected overlap with the signal, meaning that the spectral method is uninformative in the regime X(A)
Second of all, even though we cannot say anything rigorous in the regime X(A) > 1, looking at state evolution equations of the AMP recursion (36), we see instability (overlap blows up but does the variance). We conjecture that the principal eigenvector of Y correlates with the signal exactly in the regime X(A) > which would imply that the BBP transition happens precisely at A(A) = 1. Remark 3.1. In general, we can les T = Eu; [(x]]] and consider the normalized matrix
T Tx+((x" (x='T + +AO
VA = - =
Y
for x the transition of the transformation in (38) applied to Y, which appears in (7), has transition at
2 and A 3o. Notice that the entries of x now have unit variance. Under this setting, J
1 diag( v2)
A( = diag( Vc)
diag( vo) = =Eg;
diag( (ee)
<1
A
op
which is the generalized SNR defined in (8).
Acknowledgments and Disclosure of Funding
We thank Alice Guionnet and Lenka Zdeborova for valuable discussions. We acknowledge funding from the ERC Project LDRAM: ERC-2019-ADG Project 884584, and by the Swiss National Science Foundation grant SNES OperaGOST, 200021 200390
10

---

References
David L. Donoho and lain M Johnstone. Adapting to unknown smoothness via wavelet shrinkage. Journal of the american statistical association, 90(432):1200-122) 1995.
Sandrine Péché. Deformed ensembles of random matrices. In Proceedings of the International Congress of Mathematicians, Seoul, volume 3, pages 1059-1174, 2014.
Jinho Baik, Gérard Ben Arous, and Sandrine Péché. Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices. Ann. Probab. 33(5):1643-110 2005. ISSN 0091-1798. doi:
URL http: dx doi wwwpoooo.....oo../ooo/eeo..o.eee 1214/
00911790500 00911790500000023.
Jean Barbier and Galen Reeves. Information information-thcoretic limits of multiview low-rank symmetric spiked matrix model. In 2020 IEEE International Symposium on Information Theory (ISIT), pages 2771-2776. IEEE, 2020.
Joshua K Behne and Galen Reeves. Fundamental limits for rank-one matrix estimation with groupwise heteroskedasticity. In International Conference on Artificial Intelligence and Statistics, pages 8650-8672. PMLR, 2022.
Diego Alberici, Francesco Camilli, Pierluigi Contucci, and Emanuele Mingione. The multi-species mean-field spin-glass on the nishimori line. Journal of Statistical Physics, 182:1-20, 2021a.
Diego Alberici, Francesco Camilli, Pierluigi Contucci, and Emanuele Mingione. A statistical physics approach a multi-channel wigner spiked model. Europhysics Letters, 136(():4800)) 2022.
Diego Alberici, Francesco Camilli, Pierluigi Contucci, and Emanuele Mingione. The solution of the deep Boltzmann machine on the Nishimori line. Comm. Math. Phys., 387(2):1191-1214 2021b. ISSN 0010-3616. doi: 10. (0.1007/002200021 -21-000010----00 URL https: http://ooo.ooo////////// s0C220- 021
04165-0.
Brian Karrer and Mark EJ Newman. Stochastic blockmodels and community structure in networks. Physical review E, 83(1)0016107 2011.
Alice Guionnet, Justin Ko, Florent Krzakala, and Lenka Zdeborová. Low-rank matrix estimation with inhomogeneous noise. arXiv preprint 220.:::222000009/// 2022.
Hong-Bin Bin Chen and Jiaming Xia. Hamiloon-Jccobi equations for inference matrix tensor products. Ann. Inst. Henri Poincaré Probab. Stat., 58(2):755-793, 2022. ISSN 0246-0203. doi: 10.1214/ 21 21-aihp1188 183.. URL https: /oo. htt../gggg...12222/1--hhh11111
Hong-Bin Bin Chen, Jean-Christophe Mourrat, and Jiaming Xia. Statistical inference of finite-rank tensors, 2021. URL
05360.
Mohsen Bayati and Andrea Montanari. The dynamics of message passing on dense graphs, with applications to compressed sensing. IEEE Transactions on Information Theory, 57(2):764-785, 2011. doi: 10.1 10.119/TTT22110229444
Yash Deshpande, Emmanuel Abbe, and Andrea Montanari. Asymptotic mutual information for the two-groups stochastic block model. CoRR, abs/1507.08685. 2015. URL http: / http::///xxiiv.r////// abs/1507. 686
Thibault Lesieur, Florent Krzakala, and Lenka Zdeborová. Constrained low-rank matrix estimation: Phase transitions, approximate message passing and applications. Journal of Statistical Mechanics: Theory and Experiment, 2017(7):073403, 2017.
Antoine Maillard, Florent Krzakala, Yue M Lu, and Lenka Zdeborová. Construction of optimal spectral methods in phase retrieval. In Mathematical and Scientific Machine Learning, pages 693-720. PMLR, 2022.
David I. Donoho, Arian Maleki, and Andrea Montanari. Message- passagg algorithms for compressed sensing. Proceedings of the National Academy of Sciences, 18944-)):111418991 2009.

---

Sundeep Rangan. Generalized approximate message passing for estimation with random linear mixing. 2011 IEEE International Symposium on Information Theory Proceedings, pages 11722172. IEEE, 2011.
Cédric Gerbelot and Raphaël Berthier. Graph-based approximate message passing iterations. arXiv preprint arXiv:21099 1905, 2021.
Oliver Y Feng, Ramji Venkataramanan. Cynthia Rush, Richard Samworth, al. A unifying tutorial on approximate message passing. Foundations and Trends@ in Machine Learning, 15(4):335 2022.
Mare Mézard, Giorgio Parisi, and Miguel Angel Virasoro. Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications, volume 9. World Scientific Publishing Company, 1987.
Erwin Bolthausen. An iterative construction of solutions of the tap equations for the sherrington- kirkpatrick model. Communications Mathematical Physics, 325(1):3333366 2014.
Lenka Zdeborová and Florent Krzakala. Statistical physics of inference: Thresholds and algorithms. Advances in Physics, 65(5):453-552, 2016.
Michael Celentano, Andrea Montanari, and Yuchen Wu. The estimation error of general first order methods. In Conference on Learning Theory, pages 1078-1141. PMLR, 2020.
Florent Krzakala, Marc Mézard, Francois Sausset, Yifan Sun, and Lenka Zdeborová. Probabilistic reconstruction in compressed sensing: algorithms, phase diagrams, and threshold achieving matrices. Journal of Statistical Mechanics: Theory and Experiment, 2012(08):P08009, 2012.
David L Donoho, Adel Javanmard, and Andrea Montanari. Information-theerrtiialll optimal compressed sensing via spatial coupling and approximate message passing. IEEE transactions on information theory, 59 1):7444-7466, 2013.
Adel Javanmard and Andrea Montanari. State evolution for general approximate message passing algorithms, with applications to spatial coupling. Information and Inference: A Journal of the IMA, 2(2):115-144 144, 2013. doi: 10. 10.1093/iaiia//at0004
Riccardo Rossetti and Galen Reeves. Approximate message passing for the matrix tensor product model, 2023.
Jean Barbier, Mohamad Dia. Nicolas Macris, Florent Krzakala, and Lenka Zdeborová. Rank-one matrix estimation: analysis of algorithmic and information theoretic limits by the spatial coupling method. arXiv preprint /r12v:/8/2.00255 2018
Ahmed EI Alaoui, Florent Krzakala, and Michael Jordan. Fundamental limits of detection in the spiked Wigner model. The Annals of Statistics, 48(2):863 885, 2020. doi: 10.1214/1--00S1826 URL https::////o / tttp///oooooooo///////ooo/ooo ott.o...1/////1111........ /214/19 A051826.
Marc Lelarge and Léo Miolane. Fundamental limits of symmetric low-rank matrix estimation. Probab. Theory Related Fields, 173(3-4):859-929, 2019. ISSN 0178-8051. doi: 10.1007/
s00440-018-08 0084--x8
URL https: /tt::://oooiio /tt.//ii.ooo...//////oo////.. 1007
Cosme Louart and Romain Couillet. Concentration of measure and large random matrices with an application to sample covariance matrices. arXiv preprint arXiv: 18805088955 2018.
Alaa Saade, Florent Krzakala, and Lenka Zdeborová. Spectral clustering of graphs with the bethe hessian. Advances in Neural Information Processing Systems, 27, 2014.
Benjamin Aubin, Bruno Loureiro, Antoine Maillard, Florent Krzakala, and Lenka Zdeborová. The spiked matrix model with generative priors. Advances in Neural Information Processing Systems, 32, 2019.
Marco Mondelli and Andrea Montanari. Fundamental limits of weak recovery with applications to phase retrieval. In Conference On Learning Theory, pages 1445-1450. PMLR, 2018.
12

---

Marco Mondelli, Christos Thrampoulidis, and Ramji Venkataramanan. Optimal combination of linear and spectral estimators for generalized linear models. Foundations of Computaaional Mathematics, 22(5):15331166, 2022.
Ramji Venkataramanan, Kevin Kögler, and Marco Mondelli. Estimation in rotationally invariant generalized linear models via approximate message passing. In International Conference on Machine Learning, pages 22 1200221144 PMLR, 2022.
Marco Mondelli and Ramji Venkataramanan. Approximate message passing with spectral initial- ization for generalized linear models. In International Conference on Artificial Intelligence and Statistics, pages 397-405. PMLR, 2021.
Greg W. Anderson, Alice Guionnet, and Ofer Zeitouni. An introduction random matrices, volume 118 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2010. ISBN 778-0-521-19452.55
13

---

A Proof of Theorem 1.2
We now provide rigorous proof of the result that sketched in Section 2. This proof is essentially identical to [Deshpande et al., 2015, Lemma 4.4]. Recall the iterates (30) given by 8 = x - ox and
8 - ( VNVA oA) fe (s' x'"""" xx)) b, fi-1 (8 x xx)), (43)
where jt' (KE)igN is given by the recursion
Σ 0E
Ca
Eng.zlo0i (1 + oz
9(()
A ag((i)
and x= = (a])) is a vector with independent coordinates distributed according to Fo- By
Lemma 2.4, for each a E lgl. and any pseudo-Lipschil function Φ + + we have that almost surely
lim +00
Σ
((s xt)) Eng 20
(44)
CN
iECN
where
(o 1o
Co Ez [f.t (z)))
A ab
4=1
as was defined (18). For any ppeudo-Lipschite function &b - R, we have ((2,0) = 6(x play) is also Pseudo-Lipschitz, so (44) implies that
lim N
v0s + ((27) = Eng Eug.zubo'' +1a=5)
(45)
CNN
IECN
almost surely.
Now let x' be the iterates from the spiked AMP iteration for the inhomogeneous Wigner matrix (24) we derived (26)
(1 1 2 (x+)))
x r+1
8² VNVA @ A ø' b, 3 d'-1
(46)
NA
It now suffices show that for fixed and all [q] that
lim N
Σ (v(s) + - b{xa))
(47)
CN
iEON
almost surely. This will imply that of + 2 and of have the same asymptotic distribution which finish the proof of Theorem 1.2 by (45).
We now prove (47). Since &b is L-pseudo-Lipschizz we have [s(s) + m4a7)) (xx)) < I(1 + |st + uhail |att)(st + m/ag az1
< 2L + - 211(1 + |st + wha 21 + |ot + - x²().
The (wist + ((a;7) - *((+5))
inequality implies that
CN
RECN
2L CN
< (V CN + u::= - ætile + ||s + "o + + - -x1 + ||5² + pha =2
where 8 = (sx) E IRINN xt = (af)sEnN E RRI Therefore, to prove (47) it suffices to prove that for all 1. 200
lim CN
|| + p xt'12 0
(48)
limsup sup C No
|| + x +
(49)
14

---

Clearly, if we initialize x", 8 at zero then (48) and (49) are satisfied by our state evolution equations (5). Notice that (49) follows directly from (45) applied the square function. We use here that we assumed that the second moment of x' is finite.
We now focus on proving (48) through strong induction. By definition of the iterates (43) and (46), (s)2 + 1a
( + A 0 f1-1(2(-1)
ft-1 (s- + 4 -xx)== OA
(
V
O xx'()") ft f(-1(x='11
NA
- - O f1-2(x²-2) - 1 fi-2 2 4²~² @ xx))
SEC
where Fl corresponds to the ith row vector and b and by are the Onsager terms defined in (14) with respect to x' and s'~1 respectively. The Cauchy-Schhee Schharr inequality and Jensen's s inequality imply that there exists some universal constant C' such that
|18 +
CN
1
1
1 Ille-1 (s" + u==1xxx) - fi--1x""-11
CN
N
A
iECS
(x' 2- 1 (1 (000)) 2 (xt)²
+
Σ
M/
(ʃ- (fr-
0
CN
NA
IECN
C
(bb-1); .): [b 11:1) (1)) 2(8 2(8 + +1 1 ① x²)
CN
IECN
Σ
b Di 2)1 1f--(68'2 2² + x x)))))2
CC
SECN
We now control each term separately.
1. To control the first term, notice that the matrix N VA C A has iid entries within blocks
and the sizes of the blocks diverge with the dimension, so we can control the sums of the squares of within each block using standard operator norm bounds Anderson al. [2010]. The first term vanishes in the limit because f pscudo-Lipschitz so we can apply the induction hypothesis bound which controls (48) at time f-
2. To control the second term, notice that for i E C by Lemma 2.4 applied to the pseudo- Lipschitz function y that
1 NA
(fc-1
xx)
Pa
almost surely. This implies that the average of such terms vanishes since we assumed that the second moment E[x:]² finite.
3. To control the third and fourth terms, can expand the definition of the Onsager terms and use the assumption that f' is pseudo-Lipschite and almost surely bounded. Both terms vanish because our strong induction hypothesis gives control of (48) at time - 2.
Since all terms vanish in the limit, we have proven (48) for all E [g]. which finishes the proof of statement (47) and the proof of Theorem 1.2.
B Comparison with a naive PCA spectral method
In this appendix, we wish to show how the spectral method we propose differs, in practice, from naive PCA. We provide example of the spectrums of Y and Y before and after the transition at
15

---

35
30
25
20
20
10
5
-150 -100 -50
100 150
-100
-75
-50
25
25
50
75
100
Figure 3: Illustration of the spectrum of Y E
R2500x2500 evaluated at noise profiles with snr X(A) 0.7 (left, before the transition) and on the left and 1.8 the right (after the transition). There is no outlying eigenvalue in contrast to the transformed matrix: the transition for a naive spectral method is sub-optimal.
35
30
30
25
20
15
15
10
5
255 220
15
1.0
-05
0.0
0.5 1.0 -5
Figure 4: Illustration of the spectrum of Ý X evaluated noise profiles with
A(A) = 0.7 (left, before the transition) and on the left and 1.8 on the right (after the transition), with the outlying eigenvector correlated with the spike arises eigenvalue one. This is at variance with the results of the naive method in Fig.3
(NR(A) 1. In Figure 3 there is clear separation of the extremal eigenvalue of Y from the bulk around this transition. This in contrast Figure 4 where there is extremal eigenvalue of Y appearing at value one.
16


Reviews:
[{"review_id": "yzmwtjHmta", "reviewer": "Reviewer_R9KJ", "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.\n\nThe authors have made several contributions in this paper:\n1. They have derived the AMP recursions to solve the spiked Wigner problem.\n2. 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.\n3. 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.", "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.\n- 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.", "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.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper considers an interesting problem with many applications. \n- The authors derive an AMP method to solve this problem.\n- 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\n- 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.\n- Finally, the authors analyze the linear version of the AMP algorithm and show it is equivalent to spectral method for a specific matrix.\n\nTo 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:\n- 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.\n- 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.\n- 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.\n\n## Minor comments\nI 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our gratitude to the reviewer for their insightful comments and valuable suggestions. We will incorporate all the suggestions into the final version, regardless of acceptance.\n\n• Weaknesses: We acknowledge that we did not delve into potential stability issues or convergence problems that our AMP algorithm might encounter. Such challenges are indeed common to many similar algorithms and addressing them lies beyond the scope of our current work. Nevertheless, in our specific case, the AMP is Bayes-optimal, which typically exhibits strong convergence properties.\n\nAdditionally, while we recognize these concerns, they are precisely the reason we introduced the (AMP-inspired) spectral method in Section 3. This method can be formulated and solved using an off-the-shelf Python solver in just a few lines. We wish to highlight that this spectral algorithm achieves performance close to that of AMP without any associated algorithmic issues.\n\nIn response to the second point, we concur and plan to comment on it in an updated version.\n   \n• Questions: To begin with, our AMP does indeed provide the Bayes-optimal MMSE performance by computing the posterior mean. From the Bayesian statistics perspective, this is a classical estimator, and we will elucidate this in the revised version.\n\nFurthermore, our AMP and its state evolution can be seamlessly adapted to examine M-estimators for this challenge, in the same vein as the standard AMP. Here, the denoiser will simply transition to the corresponding convex proximal operator. This is well-documented in sources such as \"Generalized Approximate Message Passing for Estimation with Random Linear Mixing\" by Rangan (2012) and \"High Dimensional Robust M-Estimation: Asymptotic Variance via Approximate Message Passing\" by Montanari and Donoho (2013). For M-estimation, our strategy in section 3 pertaining to the spectral method can be perceived in a similar light. We modify the AMP to develop a spectral method, which could also be interpreted as minimizing a tailored M-estimator. We will provide clarity on this aspect in the forthcoming version.\n"}, {"review_id": "aO6lf7GMrm", "reviewer": "Reviewer_kH5e", "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.\n\nThe 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.", "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?", "limitations": "No concerns regarding potential societal impact of this work.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "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:\n- 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.\n- 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}$?\n- Page 2, line 83: If $f_t^a$ are general Lipschitz functions, it is not clear to me why $f_t$ is linear.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe express our gratitude to the reviewer for their insightful comments and valuable suggestions. We will incorporate all the suggestions into the final version, regardless of acceptance.\n\nWeakness, Page 1: Indeed the matrix $\\tilde{\\Delta}$ and the partition function $g$ are assumed to be known. Note however, that this does not have to be a limitation.\n    \nIn the degree-corrected block model Karrer and Newman (2011), for instance, the noise profile is perfectly known and given by the degrees of nodes in the graph. Additionally, for practical applications, one can empirically estimate the variance profile and assign group membership according to the empirical variances. We can first estimate both $\\tilde{\\Delta}$ and $g$ without knowing either of them in advance. Then we can work with the estimators rather than with the true quantities. We did not explore this any further in this work. An interesting direction for future work would be to see how AMP which uses estimators instead of the true $\\tilde{\\Delta}$ and $g$ performs and quantify how the lack of information impacts the performance of the algorithm, for instance using the Expectation Maximization framework in AMP (e.g. as in Expectation-Maximization Gaussian-Mixture Approximate Message Passing,  Vila \\& Schniter 2013)\n\nWeakness, Line 82: It is true that the definition is a bit confusing. We meant $t$ to be an integer and for each $t \\in \\mathbb{N}$ $f_{t}$ is a function $\\mathbb{R}^{N} \\rightarrow \\mathbb{R}^{N}$.\n\nWeakness, Line 83: The word linear is a mistake here and should be left out.\n\nWeakness, Line 112: You are right, the right word is strengthen.\n\nQuestion: This is indeed correct and we will clarify this. The method we use to show the weak recovery at the sharp transition used a heuristic argument from State Evolution/AMP theory. While the argument is mathematically solid (see e.g. Maillard, Krzakala, Lu and Zdeborova [2021], or Venkataramanan, Kogler, and Mondelli [2022]) and backed by numerical simulations, it is not fully rigorous. A direct rigorous treatment of the spectral method directly from random matrix theory is a challenging but interesting open problem in random matrix theory."}, {"review_id": "C9Xi8O3TS7", "reviewer": "Reviewer_qRVY", "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. \nThis paper proposes an approximate message passing (AMP) algorithm and shows the corresponding state evolution result. \nAnother piece of contribution is the design of a spectral algorithm that outputs the principal eigenvector of a rescaled and recentered matrix. \nNumerics suggest that this outperforms the naive estimator of the principal eigenvector of the data matrix per se. ", "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\". \n\n1. Line 17, replace \"etc...\" with \"etc.\"\n\n2. 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. \n\n3. 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. \n\n3. I couldn't parse the grammar of 2. of Assumption 1.1.\n\n5. 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. \n\n5. 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. \n\n5. In Equation (6), has the notation E_{posterior} been defined? If not, then this notation is definitely too sloppy. \n\n5. Line 137, there are redundant spaces in \"N - vector\". \n\n5. Line 141, please explicitly write i in [N] when introducing the notation f_t^i. \n\n5. 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)?\n\n5. 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. \n\n4. This paper handles heterogeneous noise. Is it true that with essentially no additional effort, heterogeneous prior can also be handled?\nAt least when the partition for the prior is the same as that for the noise? \nI didn't check the details and may be wrong. \n\n5. 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?", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "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. \nAs the authors commented, this estimator outperforms (at least numerically) the naive one corresponding to the original matrix Y. \n\nAnother 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. \n\n2. Section 3 is interesting at a heuristic level. However, I have a doubt regarding the authors' claim. \n\nIn 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. \nIt 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. \nThe 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. \nWhen SNR<1, there is no spectral gap and it is unclear how the iterate of linearized AMP is related to the principal eigenvector. \nIt may converge to some other vector, depending on the initialization. \nIn fact, rigorously speaking, I think it's fundamentally unlikely to prove subcritical behaviour by exploiting linearized AMP. \nThe analysis only proves the attraction of 0 when SNR<1, which is an *evidence* that the phase transition threshold is 1.\nHowever, this implies neither \"spectral fails when SNR<1\" nor \"spectral works when SNR>1\". \n\n3. 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. \nIn that case the Bayes-AMP is no longer a practical algorithm (even with warm start) and the spectral algorithm is also not computable. \nIn fact, is it fair to say that the proposed spectral algorithm outperforms the naive one *because* it uses Delta information?\nCan the price of lacking the knowledge of Delta be quantified?\nI know this may go beyond the scope of the present paper. \nBut it seems to be an interesting nontrivial point that's worth mentioning/discussing. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our gratitude to the reviewer for their insightful comments and valuable suggestions. We will incorporate all the suggestions into the final version, regardless of acceptance.\n\nWeakness 2: From the information theoretical analysis for these models, no recovery of the hidden truth is possible (no matter the algorithm) when the SNR $< 1$. We have shown that when the SNR $< 1$ any fixed point of the AMP recursion must have zero expected overlap with the true signal. One way of seeing it is that for SNR $< 1$ state evolution implies that any iteration of the AMP recursion contracts the vector overlap (it is being multiplied by a matrix with the operator norm smaller than 1), thus the only possible overlap of a fixed point is 0. Since any eigenvector of the matrix $\\tilde{\\boldsymbol{Y}}$ obtained by linearizing AMP is a fixed point of AMP, it must also have zero expected overlap with the signal. This subtlety should be further explained in Section 3.\n    \nWe believe indeed that there are subtle points for a fully rigorous AMP proof of the spectral method performance. We have only shown that the linear AMP is uninformative in this regime, but the performance of the spectral method still remains open. We are confident, however, that we have recovered the right matrix to analyze for such a spectral approach because it is based on a mathematically solid framework (see e.g. Maillard, Krzakala, Lu and Zdeborova [2021], or Venkataramanan, Kogler, and Mondelli [2022]) and backed by numerical simulations. A rigorous argument would require fine control of the convergence of the linear AMP, see e.g. High Dimensional Robust M-Estimation: Asymptotic Variance via Approximate Message Passing by Montanari and Donoho (2013) or the more recent, Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensions by Loureiro et al.) Alternatively, a direct rigorous treatment of the spectral method directly from random matrix theory is a challenging but interesting open problem.    \n\nWeakness 3: Indeed the matrix $\\tilde{\\Delta}$ and the partition function $g$ are assumed to be known. Note, however, that this does not have to be a limitation.\n\nIn the degree-corrected block model Karrer and Newman (2011), for instance, the noise profile is perfectly known and given by the degrees of nodes in the graph. Similarly , for practical applications, one can empirically estimate the variance profile and assign group membership according to the empirical variances. We can first estimate both $\\tilde{\\Delta}$ and $g$ without knowing either of them in advance. Then we can work with the estimators rather than with the true quantities. An interesting direction for future work would be to see how AMP which uses estimators instead of the true $\\tilde{\\Delta}$ and $g$ performs and quantify how the lack of information impacts the performance of the algorithm, for instance using the Expectation Maximization framework in AMP (e.g. as in Expectation-Maximization Gaussian-Mixture Approximate Message Passing,  Vila \\& Schniter 2013).\n\nQuestion 1: This indeed would be a better phrasing.\n\nQuestion 2: Fixed.\n\nQuestion 3: Gaussian noise with block-constant variance profile is a better term.\n\nQuestion 4: Yes, detect in the context of line 46 refers to weak recovery\n\nQuestion 5: Line 99 should be replaced by: \"For each $t \\in [N], a \\in [q]$\" $f_{t}^{a}$ and $(f_{t}^{a})^{\\prime}$ are Lipschitz.\"\n\nQuestion 6: Theorem 1 should be stated to apply to $2$--Pseudo Lipschitz functions, but can be generalized to a larger class of functions if we assume more moments on the prior. We have corrected this.\n\nQuestion 7: Fixed.\n\nQuestion 8: The notation $\\mathbb{E}_{\\text{posterior}}$ stands for the expected value with the respect to the posterior distribution. \n\nQuestion 9: Fixed.\n\nQuestion 10: We will add $i \\in [N]$.\n\nQuestion 11: Nishimori identity is indeed just a clever rewriting of the law of total expectation.\n\nQuestion 12: We can gain some intuition motivating the choice $f_{t}(x) = x$ by considering simple priors, such as the Rademacher prior. In the case of the Rademacher prior a simple computation shows that the Bayes-optimal choice of the denoising functions yields $f_{t}^{j}(\\star) = tanh(\\star)$. In the first order approximation we have $tanh(x) \\approx x$. Thus, at least for the Rademacher prior, the choice of identity functions as denoising functions corresponds to the first order approximation of the Bayes-optimal choice. \n\nQuestion 13: Heterogeneous prior can be handled as long as the coordinates are independent and the partition for the prior corresponds to the block structure of the variance profile. Although for the Bayes-optimal choice of denoising functions $f_{t}^{j}$ in the AMP different priors would certainly impact the calculation of the posterior mean in the following definition (eq. 32 of the article) as long as the prior stays the same within a block, the denoising function $f_{t}^{j} = f_{t}^{g(j)}, t \\in [N], j \\in [q]$ also remains the same within a given block.\n\nQuestion 14: This is a very interesting comment, but it is also unknown what happens for these models when the number of blocks varies depending on $N$ algorithmically nor from the information theoretic point of view. One obstacle is that the fixed point equations for the optimal estimators in the large $N$ limit depends on the $q$, so making sense of even classifying an optimal estimator is non-trivial in this setting. It remains a nice problem to explore in the future.\n"}, {"review_id": "zea93qCRRB", "reviewer": "Reviewer_ifZx", "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$.   \n\nThe number of blocks $q$ appears to bounded independent of matrix size, and it is assumed one has access to the scale matrix Delta.\n\nThe 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).  \n\nThe 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.  ", "questions": "Major:\n\n0) 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.\n1) 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.   \n2) 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.\n3) 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? \n4) 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.\n\nMinor:\n* What is t in Assumption 1.1 part 2.  Does the family include all t?  Also this sentence is malformed.  What is the assumption? \n* What is M in (4)?\n* Eq (11) contains an $x_j$ as yet unused?", "limitations": "The assumptions are clear.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "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.\n2) The paper presents an algorithm which is optimal for the problem posed.  The algorithm is part of a larger well-studied class.\n3) The performance of the algorithm is illustrated numerically in a simple case.\n4) 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.  \n1) 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).\n2) 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our gratitude to the reviewer for their insightful comments and valuable suggestions. We will incorporate all the suggestions into the final version, regardless of acceptance.\n\n• Weakness 0: The main motivation of this paper was to approach the analysis of an inhomogeneous spiked Wigner model from an algorithmic point of view to complement the already extensive informational theoretical analysis of such models in Barbier and Reeves (2020); Behne and Reeves (2022); Alberici et al. (2022a,b); Guionnet et al. (2022). Through this process, we discovered that a linearization of the AMP algorithm implied that a simple spectral method applied on a transformed matrix will achieve weak recovery. The weak recovery transition of this spectral method is conjectured to coincide with the information theoretic transition for weak recovery.\n\n• Weakness 1: While our proof uses a reduction to a known theorem, we fail to see how it is a weakness. By connecting with an existing framework, existing algorithms can also be simply extended to the inhomogeneous framework.\n\nAdditionally, the derivation of the inhomogeneous AMP in (3.5) is a technical non-trivial contribution as it involves a balanced normalization of the matrix by the variance, which is not an obvious choice. A more natural normalization by the standard deviation was proven to be suboptimal in Guionnet et al. (2022), and applying the classical AMP for the spiked Wigner model for this matrix led to very poor results. Recasting the AMP provided a simple proof in the end, but finding the correct embedding essentially required us to derive an AMP from scratch. Furthermore, local analysis of the inhomogeneous AMP led to an interesting novel conjecture in random matrix theory, which states that the spectral method applied to a transformed matrix in (2.5) achieves the BBP transition at the optimal SNR.\n\n• Weakness 2: While the final result is left as a conjecture, it rests on solid and time-tested heuristic methods (see e.g. Maillard, Krzakala, Lu and Zdeborova [2021], or Venkataramanan, Kogler, and Mondelli [2022]) and is backed by numerical simulations.\n\nA direct rigorous treatment of this spectral method is a hard open problem in random matrix theory. Tools have been developed for matrices with noise profiles, but very few explicit formulas exist in comparison to Wigner matrices. More intuitive guesses for an optimal matrix were proposed in Guionnet et al. [2022], but were proven to be incorrect. In general, characterizations of outlying eigenvalues are given implicitly for inhomogeneous matrices, so guessing the correct optimal matrix is completely non-trivial. The linearization of the fixed point of an AMP in this work led us to recover the optimal matrix (7). Our intuition gained from the AMP is a significant step towards a rigorous treatment of the spectral method, that will likely require a very fine analysis.\n\n• Question 0: a) The model has been introduced (and its information-theoretic properties characterized) in Guionnet et al. [2022], Behne and Reeves [2022], Chen et al. [2021], Alberici et al [2022] (see line 34-36), motivated by the inhomogenous version of low-rank factorization problems (see line 14-24)\n\nb) The surprise for the linear method lies in the fact that existing methods, such as PCA or reweighted PCA, fail in this and other inhomogeneous models, see e.g. Guionnet et al. [2022]. Finding a successful spectral method was an open question.\n\nOur algorithmic point of view was used to tackle a peculiarity that was seen in the information theoretic recovery phase transitions. In Guionnet et al. [2022], an intuitive ”homogenization” of the noise resulted in a BBP phase transition at a non-optimal signal to noise ratio. We wanted to use approximate message passing and an analysis of a linearization around the fixed points of this AMP to find the correct way to transform the noise profile, which is defined on equation (7). Conjecture 1.6 on the optimality of the spectral method is also a nice conjecture in RMT that can be solved by studying a difficult system of quadratic vector equations. Our algorithmic point of view provided a nice conjecture that is supported by the stability and convergence of numerical simulations.\n\n• Question 1: We agree that the spectral method proposed at the end is a remarkable approach, and certainly simpler than AMP. However, there is no way to guess the form of the operator without deriving AMP in the first place! The derivation of AMP and its linearization to obtain the spectral method is our contribution. The spectral method is conjectured to achieve weak recovery of the prior in the theoretical detectability regime. The full AMP algorithm is shown to approach the optimal MMSE.\n\n• Question 2: In this model, the information theory analysis indicates that no recovery of the hidden truth is possible (no matter the algorithm) as long as SNR < 1. If SNR > 1, however, it is possible to recover a noisy version of the hidden truth. This is called ”weak recovery” in information theory, see Guionnet et al. [2022], Behne and Reeves [2022]. Our AMP is shown to be (asymptotically) able to perform weak recovery in practice (and in fact recover the MMSE estimator in linear time, a task that in principle requires sampling a high-dimensional distribution).\n\n• Question 3: We present these conditions for the mathematically minded audience. In practice, it suffices to use either spectral or random initializations to achieve good results numerically. \n\n• Question 4: AMP can be easily implemented in python, see for example the github repositories by Takashi Takahashi or Kuan Hsieh. Our AMP is very close to the spatially coupled AMP that is being used in error-correcting-codes, see e.g. Barbier, & Krzakala. (2017) or Barbier; Dia; Macris (2019)."}]

Author rebuttal:

Meta-review: While there were some initial concerns about the balance between technical content and more accessible material, these were generally alleviated following the rebuttal, and no major concerns remain.  The consensus is acceptance, though the reviewer’s comments and suggestions should still be carefully incorporated into the camera-ready versions.
Decision: Accept (poster)