t30mm c 14mm14mm c0mm

# A multiscale cavity method for
sublinear-rank symmetric matrix factorization

Jean Barbier1, Justin Ko2, and Anas A. Rahman1  1The Abdus Salam International
Centre for Theoretical Physics, Trieste, Italy  2University of Waterloo,
Canada and ENS Lyon, France
{jbarbier<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We consider a statistical model for symmetric matrix factorization with
additive Gaussian noise in the high-dimensional regime where the rank $M$ of
the signal matrix to infer scales with its size $N$ as $M={\rm o}(N^{1/10})$.
Allowing for an $N$-dependent rank offers new challenges and requires new
methods. Working in the Bayes-optimal setting, we show that whenever the
signal has i.i.d. entries the limiting mutual information between signal and
data is given by a variational formula involving a rank-_one_ replica
symmetric potential. In other words, from the information-theoretic
perspective, the case of a (slowly) growing rank is the same as when $M=1$
(namely, the standard spiked Wigner model). The proof is primarily based on a
novel _multiscale cavity method_ allowing for growing rank along with some
information-theoretic identities on worst noise for the Gaussian vector
channel. We believe that the cavity method developed here will play a role in
the analysis of a broader class of inference and spin models where the degrees
of freedom are large arrays instead of vectors.

##  I Introduction

Reconstructing a low-rank signal matrix observed through a noisy channel with
highest possible accuracy is of fundamental importance across a range of
disciplines including statistical inference, machine learning, signal
processing, and information theory. This task encompasses a variety of models
that have attracted considerable attention over the last decade, such as
sparse principal components analysis and $\mathbb{Z}$-2 synchronization [1,
2], the stochastic block model for community detection [3, 4], or submatrix
localization [5, 6], just to cite a few. A common theme unifying these models
is that they are either examples of, or are otherwise closely related to, the
general notion of spiked matrix models [7, 8, 9] of the form “signal plus
noise” that were introduced at the turn of this century.

In this work, we consider the archetypal spiked Wigner model, where one
observes a symmetric deformation of a standard Wigner matrix. The data is
generated as

$\bm{Y}=\sqrt{\frac{\lambda}{N}}\bm{X}_{0}\bm{X}_{0}^{\intercal}+\bm{Z},$ (1)

where $\bm{X}_{0}\in\mathbb{R}^{N\times M}$ is the signal matrix distributed
according to some prior distribution $\operatorname{\mathbb{P}}_{X,N,M}$,
$\bm{Z}\in\mathbb{R}^{N\times N}$ is a standard Wigner matrix with
$\bm{Z}_{ii}\sim\mathcal{N}(0,2)$ ($1\leq i\leq N)$ and
$\bm{Z}_{ij}=\bm{Z}_{ji}\sim\mathcal{N}(0,1)$ ($1\leq i<j\leq N$)
independently and identically distributed (i.i.d.), $\lambda\geq 0$ is the
signal to noise ratio (SNR), and the scaling by $\sqrt{N}$ is such that the
signal and noise are of comparable magnitudes. From another perspective, we
may say that we observe the spike $\bm{X}_{0}$ corrupted by additive Gaussian
noise — note that results concerning this model extend to a wide range of
noisy observation channels due to recently proven universality principles [10,
11, 12, 13]. We study the free entropy (equivalently, up to a simple additive
term, the mutual information $I(\bm{X}_{0};\bm{Y})$, see, e.g., [14])

$\displaystyle
F_{N,M}(\lambda)=F_{N}(\lambda):=\frac{1}{NM}\mathbb{E}_{\bm{Z},\bm{X}_{0}}\ln
Z_{N,M}$ (2)

of this model in the thermodynamic limit $N,M\to\infty$ with the rank
$M=M_{N}$ growing sufficiently slowly (but polynomially) with $N$. Here,

$Z_{N,M}:=\int_{\mathbb{R}^{N\times
M}}e^{H_{N}(\bm{X})}\,d\operatorname{\mathbb{P}}_{X,N,M}(\bm{X})$ (3)

denotes the partition function associated with the Hamiltonian

$H_{N}(\bm{X}):=\frac{1}{2}\operatorname{Tr}\Big{(}\sqrt{\frac{\lambda}{N}}\bm{Z}\bm{X}\bm{X}^{\intercal}+\frac{\lambda}{N}\bm{X}_{0}\bm{X}_{0}^{\intercal}\bm{X}\bm{X}^{\intercal}\\\
-\frac{\lambda}{2N}\bm{X}\bm{X}^{\intercal}\bm{X}\bm{X}^{\intercal}\Big{)}.$
(4)

In the language of Bayesian inference rather than statistical physics, the
partition function is simply the normalization of the posterior distribution
$d\operatorname{\mathbb{P}}_{X,N,M}(\bm{X}\mid\bm{Y}(\bm{X}_{0},\bm{Z}))$ and
the Hamiltonian is the log-likelihood. In order to take advantage of replica
symmetry (i.e., concentration-of-measure) [14, 15, 16], we moreover work in
the Bayes-optimal setting, which means that in addition to the observed data
$\bm{Y}$, the statistician charged with reconstructing $\bm{X}_{0}$ from
$\bm{Y}$ also has knowledge of the form (1) of $\bm{Y}$, the prior
distribution $\operatorname{\mathbb{P}}_{X,N,M}$ of the signal $\bm{X}_{0}$,
the SNR $\lambda$, and the rank $M$ of $\bm{X}_{0}\bm{X}_{0}^{\intercal}$.

Focusing on the Bayesian viewpoint, various applications of (the adaptive)
interpolation methods, the cavity method, and the Approximate Message Passing
(AMP) algorithm have been used to study the spiked Wigner model and its
generalizations. Studies commenced in the rank $M=1$ case [17, 11, 3, 18, 19]
before progressing to the low-rank (i.e., finite rank) case [14, 20], with
recent studies venturing into the regime of growing rank [21, 22, 23, 24]. In
particular, an $M$-dimensional variational formula for the limiting free
entropy $\lim_{N\to\infty}F_{N}(\lambda)$ can be surmised from [21] when
$M={\rm o}(N^{1/20})$. Our present goal is to continue this line of research
by proving a scalar equivalent of the aforementioned formula (thereby
circumventing the intractability of the $M$-dependence seen therein) and
extending the regime of veracity to $M={\rm o}(N^{1/10})$ — this is a
significant milestone towards understanding the recent conjecture based on the
replica method of [25] that the rank-$M$ spiked Wigner model should behave as
its rank-one counterpart, so long as the rank is sublinear $M={\rm o}(N)$.

It has long been known and utilized that there is a close interplay between
statistical inference and the theory of spin glasses. In particular, the free
entropy of the finite rank spiked Wigner model is closely related to the free
energies of vector spin glass models. Variational formulae for the latter have
been proven using synchronization of matrix overlaps [26, 27, 28, 29, 30, 31]
and Hamilton–Jacobi equations [32, 33, 34, 35]. Such formulae have moreover
been recently analyzed and simplified in [36, 37, 38]. Our main technical
contribution in this line of work is a generalization of the
Aizenman–Sims–Starr scheme [39] to multiscale mean field models, which in this
context are vector spin glass models with dimension-dependent vector spin
coordinates. Our secondary contribution is a proof of the fact that our
variational formula for the limiting free entropy reduces to that of the rank-
one spiked Wigner model, owing to a set of simple information-theoretic
inequalities. Said identities are, to the best of our knowledge, not in the
literature and we expect Corollary 1, say, to be a valuable addition to the
literature on worst noises [40, 41, 42].

We expect our methods to extend to a variety of related problems, see Section
VI. Proofs are trimmed or omitted in the following and are to appear in full
in an upcoming paper.

##  II Setting and main result

We study the free entropy $F_{N}(\lambda)$ (2) of the spiked Wigner model (1)
in the $N\to\infty$ regime with rank $M={\rm o}(N^{1/10})$ and i.i.d. signal
$\bm{X}_{0}=(\bm{x}_{0,i}\in\mathbb{R}^{M})_{i\leq
N}=(\bm{x}_{0,ij}\in\mathbb{R})_{i\leq N,j\leq M}$, i.e., the prior
distribution $\operatorname{\mathbb{P}}_{X,N,M}$ on $\bm{X}_{0}$ fully
factorizes:

$\operatorname{\mathbb{P}}_{X,N,M}(\bm{X}_{0})=\prod_{i=1}^{N}\operatorname{\mathbb{P}}_{X,M}(\bm{x}_{0,i})=\prod_{i=1}^{N}\prod_{j=1}^{M}\operatorname{\mathbb{P}}_{X}(\bm{x}_{0,ij}).$
(5)

In addition, we take $\operatorname{\mathbb{P}}_{X}$ to be a centered
distribution with $D$-bounded support:
$\mathrm{supp}\,\operatorname{\mathbb{P}}_{X}\subseteq[-D,D]$ for some $0\leq
D<\infty$.

An application of the (non-rigorous) replica method [43] suggests that
$\lim_{N\to\infty}F_{N}(\lambda)$ is given by a variational formula written in
terms of the rank-$M$ replica symmetric potential $F^{\rm
RS}_{M}:\mathcal{S}_{M}\times\mathbb{R}_{+}\mapsto\mathbb{R}$ defined by (with
$\mathcal{S}_{M}$ the set of symmetric positive semidefinite $M\times M$
matrices)

$\displaystyle F^{\rm RS}_{M}(\bm{Q},\lambda)$
$\displaystyle:=\frac{1}{M}\mathbb{E}_{\bm{z},\bm{x}_{0}}\ln Z_{M}^{\rm
RS}-\frac{\lambda}{4M}\operatorname{Tr}\bm{Q}^{2},$ (6) $\displaystyle
Z_{M}^{\rm RS}$ $\displaystyle:=\int
e^{\sqrt{\lambda}\bm{x}^{\intercal}\sqrt{\bm{Q}}\bm{z}+\lambda\bm{x}_{0}^{\intercal}\bm{Q}\bm{x}-\frac{\lambda}{2}\bm{x}^{\intercal}\bm{Q}\bm{x}}\,d\operatorname{\mathbb{P}}_{X,M}(\bm{x}),$

where $\bm{x}\in\mathbb{R}^{M}$, $\bm{z}\in\mathbb{R}^{M}$ is a standard
Gaussian vector, and $\bm{x}_{0}\sim\operatorname{\mathbb{P}}_{X,M}$ [19, 20].
However, we find that it is instead given by a formula in terms of the simpler
rank-one analogue

$\displaystyle F_{1}^{\rm RS}(q,\lambda)$
$\displaystyle:=\mathbb{E}_{z,x_{0}}\ln Z_{1}^{\rm
RS}-\frac{\lambda}{4}q^{2},$ (7) $\displaystyle Z_{1}^{\rm RS}$
$\displaystyle:=\int e^{\sqrt{\lambda q}zx+\lambda qx_{0}x-\frac{1}{2}\lambda
qx^{2}}\,d\operatorname{\mathbb{P}}_{X}(x),$

with $z\sim\mathcal{N}(0,1)$ and $x_{0}\sim\operatorname{\mathbb{P}}_{X}$.
Thus, we have as our main result that, under our hypotheses above in addition
to a further hypothesis on the number of non-analytic points (phase
transitions) in $\lambda$ of $\sup_{\bm{Q}\in\mathcal{S}_{M}}F_{M}^{\rm
RS}(\bm{Q},\lambda)$, the $N\to\infty$ limit of the free entropy
$F_{N}(\lambda)$ is given by the rank-one replica symmetric potential
$F_{1}^{\rm RS}(q,\lambda)$ at its supremum over $q$.

######  Theorem 1 (Rank-one replica formula for the growing-rank spiked Wigner
model).

Let $\mathbb{N}\ni M=M_{N}={\rm o}(N^{1/10})$, let the prior distribution on
$\bm{X}_{0}$ fully factorize according to (5), set
$\rho:=\mathbb{E}_{\operatorname{\mathbb{P}}_{X}}X^{2}$, and take
$\operatorname{\mathbb{P}}_{X}$ to be a centered distribution with $D$-bounded
support. Moreover, assume that $\operatorname{\mathbb{P}}_{X}$ is such that
for all $m\leq M$, $\sup_{\bm{Q}\in\mathcal{S}_{m}}F_{m}^{\rm
RS}(\bm{Q},\lambda)$ is analytic in $\lambda$ on $[0,\infty)$ except for
possibly one critical point $0<\lambda_{c,m}<\infty$. Then, the limiting free
entropy (2) of the spiked Wigner model (1) is given in terms of the replica
symmetric potential (7) by

$\lim_{N\to\infty}F_{N,M_{N}}(\lambda)=\sup_{q\in[0,\rho]}F_{1}^{\rm
RS}(q,\lambda).$ (8)

As a consequence we have the following formula for the minimum mean-square
error for any $\lambda$ such that the maximizer $q^{*}(\lambda):={\rm
argmax}_{q\in[0,\rho]}F_{1}^{\rm RS}(q,\lambda)$ is unique:

$\displaystyle\lim_{N\to\infty}\frac{1}{N^{2}M_{N}}\mathbb{E}\|\bm{X}_{0}\bm{X}_{0}^{\intercal}-\mathbb{E}[\bm{X}_{0}\bm{X}_{0}^{\intercal}\mid\bm{Y}]\|_{\rm
F}^{2}=\rho^{2}-q^{*}(\lambda)^{2}.$

The statement on the minimum mean-square error follows from the I-MMSE formula
[44] and the arguments of [14].

We comment on our hypotheses:

  * •

We require $M={\rm o}(N^{1/10})$ to achieve concentration of the overlap
matrix $\bm{R}_{10}:=\frac{1}{N}\bm{X}^{\intercal}\bm{X}_{0}$ w.r.t. the
posterior law of the signal and so that error terms arising from the cavity
computation vanish in the large $N$ limit. We believe that this growth rate
for the rank is not fundamental and is rather a limitation of the
concentration proofs. We conjecture that Theorem 1 holds for
$M=N^{\alpha},\alpha<1$.

  * •

Symmetry properties of $\operatorname{\mathbb{P}}_{X,N,M}$ owing to its
factorized nature encourage the thermal concentration of $\bm{R}_{10}$ onto a
scalar multiple of the identity, which will in turn induce an equivalence
between $\sup_{q\in[0,\rho]}F_{M}^{\rm RS}(qI_{M},\lambda)$ and
$\sup_{q\in[0,\rho]}F_{1}^{\rm RS}(q,\lambda)$. The factorization of the prior
is thus key to reduce the dimensionality of the variational formula.

  * •

Requiring $\operatorname{\mathbb{P}}_{X}$ to have $D$-bounded support is not
very restrictive and is only a technical constraint; prior distributions
$\operatorname{\mathbb{P}}_{X}$ with unbounded support can be treated by
truncating them to be $D$-bounded, working in the finite $D$ regime as in this
paper, and then taking $D\to\infty$ at the final stage, see, e.g., [14, 20].

  * •

It is believed that $\lim_{N\to\infty}F_{N}(\lambda)$ exhibits one phase
transition for many natural choices of prior $\operatorname{\mathbb{P}}_{X}$,
see [45] and references therein. This corresponds to a unique non-analytic
point $\lambda$. We translate this assumption on the model onto one for the
replica formula $\sup_{\bm{Q}}F_{M}^{\rm RS}(\bm{Q},\lambda)$.

Theorem 1 clearly manifests equivalence with its rank-one analogue, rigorously
analyzed in [18, 14, 20], due to the $M$-independence of the right-hand side
of (8). Results of the same nature stating that “sub-linear rank behaves as
finite rank” exist for mesoscopic spiked perturbations of random matrices [46]
and for spherical integrals [22]. Our results complement these in the context
of Bayesian inference.

In the remainder of this paper, we summarize four key ingredients that
constitute a proof of Theorem 1. In Section III, we show how the rank-$M$ and
rank-one replica symmetric potentials are related. Then, in Section IV, we
show how an interpolation argument gives a lower bound on $F_{N}(\lambda)$.
The corresponding upper bound is derived in Section V, wherein we show
concentration of the overlap matrix $\bm{R}_{10}$ and use this result to carry
out a multiscale application of the cavity method prescribed by the
Aizenman–Sims–Starr scheme. Namely, we are able to treat sequences $F_{N,M}$
indexed by _two_ growing dimensions instead of one, as is usually the case.

For convenience of later analysis, it is helpful to re-express the replica
symmetric potential in terms of the mutual information of the $M$-dimensional
vector Gaussian channel:

$F^{\rm
RS}_{M}(\bm{Q},\lambda)=-\frac{1}{M}I(\bm{x}_{0};\sqrt{\lambda\bm{Q}}\bm{x}_{0}+\bm{z})\\\
-\frac{\lambda}{4M}\|\bm{Q}-\rho I_{M}\|_{\rm
F}^{2}+\frac{\lambda\rho^{2}}{4},$ (9)

where $\|\cdot\|_{\rm F}$ is the Frobenius norm,
$\bm{z}\sim\mathcal{N}(0,I_{M})$ is standard Gaussian noise, and
$\bm{x}_{0}\sim\operatorname{\mathbb{P}}_{X,M}$.

######  Remark 1 (Properties of the replica potential).

We are going to use that the mutual information
$I(\bm{x}_{0};\sqrt{\lambda\bm{Q}}\bm{x}_{0}+\bm{z})$ is, in a well-defined
sense, a concave, non-decreasing monotone function of $\bm{Q}$ [44, 47], while
$\|\bm{Q}-\rho I_{M}\|^{2}_{\rm F}$ is a convex paraboloid with minimum at
$\bm{Q}=\rho I_{M}$ — the problem of maximizing $F_{M}^{\rm
RS}(\bm{Q},\lambda)$ over $\bm{Q}$ translates to one of comparing these two
competing terms. As a function of $\lambda$, $F_{M}^{\rm
RS}(\bm{Q},\lambda)-\lambda\rho^{2}/4$ is non-increasing, monotone,
continuous, and convex for each $\bm{Q}\in\mathcal{S}_{M}$. Thus, so too is
$\sup_{\bm{Q}\in\mathcal{S}_{M}}F_{M}^{\rm
RS}(\bm{Q},\lambda)-\lambda\rho^{2}/4$. This is true for any $M$ including
$M=1$.

##  III From rank-$M$ to rank-one potential

We link the supremum of the rank-$M$ replica symmetric potential $F_{M}^{\rm
RS}(\bm{Q},\lambda)$ to its rank-one equivalent through a series of
intermediary results. The first two are of particular interest due to their
being a statement on the worst possible additive Gaussian noise in a vector
channel with i.i.d. inputs.

######  Lemma 1 (Trimming the off-diagonal part of the noise covariance
reduces information).

Let $\operatorname{\mathbb{P}}_{X,M}=\operatorname{\mathbb{P}}_{X}^{\otimes
M}$, $\bm{x}_{0}\sim\operatorname{\mathbb{P}}_{X,M}$,
$x_{0}\sim\operatorname{\mathbb{P}}_{X}$, $\bm{z}\sim\mathcal{N}(0,I_{M})$,
and $z\sim\mathcal{N}(0,1)$. Then, for $\bm{\Sigma}\in\mathcal{S}_{M}$,

$I(\bm{x}_{0};\bm{x}_{0}+\bm{\Sigma}^{1/2}\bm{z})\geq\sum_{i=1}^{M}I(x_{0};x_{0}+\sqrt{\bm{\Sigma}_{ii}}z).$
(10)

This inequality is an equality if $\bm{\Sigma}$ is diagonal.

###### Proof.

The chain rule for mutual information, the independence of the entries of
$\bm{x}_{0},\bm{z}$, and the definition of conditional entropy implies that

$I(\bm{x}_{0};\bm{x}_{0}+\bm{\Sigma}^{1/2}\bm{z})\geq\sum_{i=1}^{M}I(\bm{x}_{0,i};\bm{x}_{0,i}+(\bm{\Sigma}^{1/2}\bm{z})_{i}).$

As $\bm{\Sigma}\in\mathcal{S}_{M}$, we may diagonalize it as
$\bm{\Sigma}=\bm{O}\bm{\sigma}\bm{O}^{\intercal}$ with $\bm{\sigma}={\rm
diag}(\sigma_{1},\ldots,\sigma_{M})$. Then, we have in law that

$(\bm{\Sigma}^{1/2}\bm{z})_{i}\overset{\rm
d}{=}\Big{(}\sum_{j=1}^{M}O_{ij}^{2}\sigma_{j}\Big{)}^{1/2}z=\sqrt{\bm{\Sigma}_{ii}}z.$

Observing also that $\bm{x}_{0,i}\overset{\rm d}{=}x_{0}$, we obtain the
result. ∎

######  Corollary 1 (Worst Gaussian noise with fixed covariance trace).

Let $\bm{\Sigma}\in\mathcal{S}_{M}$ be such that $\bm{\Sigma}_{ii}\geq D^{2}$
for each $1\leq i\leq M$ and denote its normalized trace by
$\sigma:=\operatorname{Tr}\bm{\Sigma}/M$. Then, in the setting of Lemma 1, we
have that

$I(\bm{x}_{0};\bm{x}_{0}+\bm{\Sigma}^{1/2}\bm{z})\geq
MI(x_{0};x_{0}+\sqrt{\sigma}z).$ (11)

This inequality is an equality if $\bm{\Sigma}=\sigma I_{M}$.

###### Proof.

As $\operatorname{\mathbb{P}}_{X}$ has $D$-bounded support, we have from [48]
that $I(x_{0};x_{0}+\sqrt{t}z)$ is a convex function of $t$ for all $t\geq
D^{2}$. Thus, the result follows from applying Jensen’s inequality to the RHS
of (10) in order to bring the sum under the square root. ∎

Now, to maximize $F_{M}^{\rm RS}(\bm{Q},\lambda)$ over $\bm{Q}$, it is
essential to note that we are allowed to restrict our search to points
satisfying a certain criticality condition.

######  Lemma 2 (A criticality condition).

Let $\operatorname{\mathbb{P}}_{X,M}=\operatorname{\mathbb{P}}_{X}^{\otimes
M}$ and diagonalize $\mathcal{S}_{M}\ni\bm{Q}=\bm{O}\bm{q}\bm{O}^{\intercal}$
with $\bm{q}={\rm diag}(q_{1},\ldots,q_{M})$. Then, any maximizer $\bm{Q}$ of
$F_{M}^{\rm RS}(\bm{Q},\lambda)$ must be such that the following system of
equations, solved in particular by any critical point of $F_{M}^{\rm
RS}(\bm{Q},\lambda)$, is satisfied:

$q_{i}^{1/2}\left(\bm{O}_{i}^{\intercal}\mathbb{E}_{\bm{z},\bm{x}_{0}}\langle\bm{x}\bm{x}_{0}^{\intercal}\rangle_{{\rm
RS},M}\bm{O}_{i}-q_{i}\right)=0,\quad 1\leq i\leq M,$ (12)

where $\bm{O}_{i}$ is the $i$th column of the orthogonal matrix $\bm{O}$ and

$\langle\,\cdot\,\rangle_{{\rm RS},M}:=\frac{1}{Z_{M}^{\rm
RS}}\int\,\cdot\,e^{\sqrt{\lambda}\bm{x}^{\intercal}\sqrt{\bm{Q}}\bm{z}+\lambda\bm{x}_{0}^{\intercal}\bm{Q}\bm{x}-\frac{\lambda}{2}\bm{x}^{\intercal}\bm{Q}\bm{x}}\,d\operatorname{\mathbb{P}}_{X,M}(\bm{x}).$
(13)

In particular, if $q_{1},\ldots,q_{M}>0$, this system simplifies to

$\bm{Q}=\mathbb{E}_{\bm{z},\bm{x}_{0}}\langle\bm{x}\bm{x}_{0}^{\intercal}\rangle_{{\rm
RS},M}(\bm{Q}),$ (14)

which corresponds to the criticality condition $\nabla_{\bm{Q}}F_{M}^{\rm
RS}=(0)$.

###### Proof.

Interpreting $F_{M}^{\rm RS}(\bm{Q},\lambda)$ as a function of the square
roots of the eigenvalues of $\bm{Q}$ at fixed eigenvectors and writing
$\bm{\gamma}=(\gamma_{1},\ldots,\gamma_{M})$, the $\sqrt{\bm{q}}$-derivative
of $F_{M}^{\rm RS}(\bm{Q},\lambda)$ in the direction of $\bm{\gamma}$ is

$\nabla_{\bm{\gamma}}F_{M}^{\rm
RS}(\bm{Q},\lambda)=\sum_{i=1}^{M}\gamma_{i}q_{i}^{1/2}\left(\bm{O}_{i}^{\intercal}\mathbb{E}_{\bm{z},\bm{x}_{0}}\langle\bm{x}\bm{x}_{0}^{\intercal}\rangle_{{\rm
RS},M}\bm{O}_{i}-q_{i}\right)$

for any $\bm{\gamma}$, so the criticality condition (12) holds for any
critical point. To discard the possibility of maxima on the boundary of
$\mathcal{S}_{M}$ that do not satisfy (12), note that being on the boundary
means that at least one of the $q_{i}$, say $q_{1}$, must either be zero or
tend to infinity. In the latter case, one can check from (9) that $F_{M}^{\rm
RS}(\bm{Q},\lambda)$ tends to $-\infty$. In the former, we note that
$\nabla_{(1,\ldots,1)}F_{M}^{\rm RS}(\bm{Q},\lambda)$ and
$\nabla_{(1,-1,\ldots,-1)}F_{M}^{\rm RS}(\bm{Q},\lambda)$ only agree in sign
if the system (12) is satisfied. ∎

Restricting our search to points satisfying the criticality condition (12)
allows us to write

$\sup_{\bm{Q}\in\mathcal{S}_{M}}F_{M}^{\rm
RS}(\bm{Q},\lambda)=\sup_{\bm{Q}\in\mathcal{S}_{M}(\mathcal{I})}F_{M}^{\rm
RS}(\bm{Q},\lambda),$

where $\mathcal{S}_{M}(\mathcal{I})$ is the set of symmetric positive
semidefinite $M\times M$ matrices with eigenvalues in
$\mathcal{I}\subseteq[0,\infty)$ and we may tune $\mathcal{I}$ by choosing to
work in either the high or low SNR regime. This is enabled by the following
lemma and corollary.

######  Lemma 3 (A continuity property).

Let $\operatorname{\mathbb{P}}_{X,M}=\operatorname{\mathbb{P}}_{X}^{\otimes
M}$ and define
$E_{i}(\lambda):=\bm{O}_{i}^{\intercal}\mathbb{E}_{\bm{z},\bm{x}_{0}}\langle\bm{x}\bm{x}_{0}^{\intercal}\rangle_{{\rm
RS},M}\bm{O}_{i}$ with $\bm{Q}$ in (13) set to be the maximizer of $F_{M}^{\rm
RS}(\bm{Q},\lambda)$. Then, for each $1\leq i\leq M$, $E_{i}(\lambda)$ is
continuous except possibly at $\lambda_{c,M}$ and

$E_{i}(0)=0,\qquad\lim_{\lambda\to\infty}E_{i}(\lambda)=\rho.$

###### Proof.

Continuity of $E_{i}(\lambda)$ follows from applying Lebesgue’s dominated
convergence theorem to $\langle\bm{x}\bm{x}_{0}^{\intercal}\rangle_{{\rm
RS},M}$ as specified by (13) — all potential discontinuities arise from the
(unique by hypothesis) phase transition of $F_{M}^{\rm RS}(\bm{Q},\lambda)$ at
$\lambda=\lambda_{c,M}$. At $\lambda=0$, there is no coupling between $\bm{x}$
and $\bm{x}_{0}$ in (13), so

$\mathbb{E}\langle\bm{x}\bm{x}_{0}^{\intercal}\rangle_{{\rm
RS},M}=\mathbb{E}_{\bm{z}}\langle\bm{x}\rangle_{{\rm
RS},M}\mathbb{E}\bm{x}_{0}^{\intercal}=\mathbf{0},$

because $\operatorname{\mathbb{P}}_{X}$ is centered. The $\lambda\to\infty$
limit of $E_{i}(\lambda)$ can be surmised from the finite rank analysis of
[14]. ∎

We are now in position to show that when the SNR is sufficiently low or high,
the eigenvalues of the maximizer of the potential can be restricted; this will
soon be crucial in order to exploit certain convexity properties of parts of
$F_{M}^{\rm RS}(\bm{Q},\lambda)$ holding only for these subsets of
$\mathcal{S}_{M}$.

######  Corollary 2 (Low and high SNR regimes).

In the setting of Lemma 3 with $\rho^{\prime}:=2\rho/3$,

$\sup_{\bm{Q}\in\mathcal{S}_{M}}F_{M}^{\rm
RS}(\bm{Q},\lambda)=\sup_{\bm{Q}\in\mathcal{S}_{M}[0,\rho]}F_{M}^{\rm
RS}(\bm{Q},\lambda)$ (15)

and, moreover, there exists $0<\lambda_{S},\lambda_{L}<\infty$ such that

$\sup_{\bm{Q}\in\mathcal{S}_{M}}F_{M}^{\rm
RS}(\bm{Q},\lambda)=\begin{cases}\sup\limits_{\bm{Q}\in\mathcal{S}_{M}[0,\rho^{\prime}]}F_{M}^{\rm
RS}(\bm{Q},\lambda),&\lambda<\lambda_{S},\\\
\sup\limits_{\bm{Q}\in\mathcal{S}_{M}[\rho^{\prime},\rho]}F_{M}^{\rm
RS}(\bm{Q},\lambda),&\lambda>\lambda_{L}.\end{cases}$

###### Proof.

Using the Cauchy-Schwarz inequality together with the tower rule for
conditional expectation (also known as the Nishimori identity, see, e.g.,
[14]) shows that $\mathbb{E}\langle\bm{x}\bm{x}_{0}^{\intercal}\rangle_{{\rm
RS},M}$ has eigenvalues bounded by $\rho$. By Lemma 2, any $\bm{Q}$ maximizing
$F_{M}^{\rm RS}(\bm{Q},\lambda)$ must have eigenvalues zero or in agreement
with those of $\mathbb{E}\langle\bm{x}\bm{x}_{0}^{\intercal}\rangle_{{\rm
RS},M}$, so such a $\bm{Q}$ must have eigenvalues in $[0,\rho]$. The existence
of a suitable $\lambda_{S}$ is established by observing that $E_{i}(0)=0$ and
$E_{i}(\lambda)$ is continuous away from $\lambda_{c,M}$. Likewise, when
$\lambda\to\infty$, the maximizer of $F_{M}^{\rm RS}(\bm{Q},\lambda)$ can be
shown to have non-zero eigenvalues, so combining (14) with Lemma 3 establishes
existence of $\lambda_{L}$. ∎

Now, since $\bm{Q}\in\mathcal{S}_{M}$, so too is $(\lambda\bm{Q})^{-1}$, which
we denote as $\bm{\Sigma}$ from here on out. It is then immediate that Lemma 1
induces decoupling in (9) when $\bm{\Sigma}$ has the form $\sigma I_{M}$. This
is indeed the form of $\bm{\Sigma}$ for which $F_{M}^{\rm RS}(\bm{Q},\lambda)$
is maximized. We first treat the low and high SNR regimes separately.

######  Lemma 4 (Low SNR rank-one reduction).

Let $\operatorname{\mathbb{P}}_{X,M}=\operatorname{\mathbb{P}}_{X}^{\otimes
M}$. For $\lambda<\min\\{D^{-2}/\rho,\lambda_{S}\\}$ we have

$\sup_{\bm{Q}\in\mathcal{S}_{M}}F_{M}^{\rm
RS}(\bm{Q},\lambda)=\sup_{q\in[0,\rho^{\prime}]}F_{1}^{\rm RS}(q,\lambda).$
(16)

###### Proof.

From (9), computing the left-hand side of (16) is equivalent to the
minimization problem

$\inf_{\bm{\Sigma}\in\mathcal{S}_{M}}\Big{\\{}I(\bm{x}_{0};\bm{x}_{0}+\bm{\Sigma}^{1/2}\bm{z})+\frac{\lambda}{4}\|\bm{\Sigma}^{-1}/\lambda-\rho
I_{M}\|^{2}_{\rm F}\Big{\\}},$

where $\bm{\Sigma}:=(\lambda\bm{Q})^{-1}$. As $\lambda<\lambda_{S}$, Corollary
2 says that the eigenvalues, hence diagonal entries
$\bm{\Sigma}_{ii}=\lambda^{-1}\sum_{j}\bm{O}_{ij}^{2}\tilde{q}_{j}$ (where we
write $\tilde{q}_{i}=q_{i}^{-1}$ for the inverses of the eigenvalues of
$\bm{Q}$), are bounded below by $1/(\lambda\rho^{\prime})$. Since we also have
that $\lambda<D^{-2}/\rho$, this means that
$\bm{\Sigma}_{ii}>D^{2}\rho/\rho^{\prime}>D^{2}$. Thus, by Corollary 1, the
above infimum is bounded below by

$\inf_{\tilde{q}_{1},\ldots,\tilde{q}_{M}\in[1/\rho^{\prime},\infty)}\Big{\\{}MI(x_{0};x_{0}+\sqrt{\sigma}z)+\frac{\lambda}{4}\sum_{i=1}^{M}(1/\tilde{q}_{i}-\rho)^{2}\Big{\\}},$

where $\sigma:=\sum_{i\leq M}\tilde{q}_{i}/(\lambda M)$. The critical points
(discarding the possibility of extrema on the boundary due to the same
reasoning as in the proof of Lemma 2) of the above symmetric expression w.r.t.
the $(\tilde{q}_{i})$ occur at solutions of

$\tilde{q}_{i}=\nu^{-1}\Big{(}\frac{1}{\lambda}\frac{\partial}{\partial\sigma}I(x_{0};x_{0}+\sqrt{\sigma}z)\Big{)},\quad
1\leq i\leq M,$

where $\nu(\tilde{q})=\lambda(\rho\tilde{q}-1)/(2\tilde{q}^{3})$ is a
bijection for $\tilde{q}\geq 1/\rho^{\prime}$ (thus the choice of
$\rho^{\prime}$). This system of equations is satisfied only if
$\tilde{q}_{1}=\cdots=\tilde{q}_{M}$, at which point our infimum decouples
over the $\tilde{q}_{1},\ldots,\tilde{q}_{M}$ into

$M\inf_{\tilde{q}\in[1/\rho^{\prime},\infty)}\Big{\\{}I(x_{0};x_{0}+\sqrt{\tilde{q}/\lambda}z)+\tfrac{\lambda}{4}(1/\tilde{q}-\rho)^{2}\Big{\\}}.$

Substituting this into the left-hand side of (16) and noting that the infimum
is attained at $\bm{Q}=I_{M}/\tilde{q}$ produces the right-hand side, as
desired. ∎

######  Lemma 5 (High SNR rank-one reduction).

Let $\operatorname{\mathbb{P}}_{X,M}=\operatorname{\mathbb{P}}_{X}^{\otimes
M}$. We have for $\lambda>\lambda_{L}$ that

$\sup_{\bm{Q}\in\mathcal{S}_{M}}F_{M}^{\rm
RS}(\bm{Q},\lambda)=\sup_{q\in[\rho^{\prime},\rho]}F_{1}^{\rm RS}(q,\lambda).$
(17)

###### Proof.

We are interested in the same minimization problem as before, but notice that
it is now bounded below by the infimum

$\inf_{\bm{\Sigma}\in\mathcal{S}_{M}[1/(\lambda\rho),1/(\lambda\rho^{\prime})]}\Big{\\{}\sum_{i=1}^{M}I(x_{0};x_{0}+\sqrt{\bm{\Sigma}_{ii}}z)\\\
+\frac{\lambda
M}{4}\Big{(}\frac{M}{\lambda\operatorname{Tr}\bm{\Sigma}}-\rho\Big{)}^{2}\Big{\\}},$

where we have used Lemma 1 to simplify the mutual information term and
Jensen’s inequality to simplify the squared Frobenius norm — the latter term
is a convex function of the eigenvalues of $\bm{\Sigma}$ for
$\bm{\Sigma}\in\mathcal{S}_{M}[1/(\lambda\rho),1/(\lambda\rho^{\prime})]$.
Interpreting this as the infimum of a symmetric function of the diagonal
entries $\bm{\Sigma}_{ii}$ of $\bm{\Sigma}$ and noting that
$\partial_{\bm{\Sigma}_{ii}}I(x_{0};x_{0}+\sqrt{\bm{\Sigma}_{ii}}z)$ is a
monotone function, we see that this infimum is attained at
$\bm{\Sigma}_{11}=\cdots=\bm{\Sigma}_{MM}$ and it therefore decouples as in
the proof of Lemma 4 so that the result follows. ∎

We point out that the proofs of lemmas 4 and 5 are somehow dual to each other.
In comparing the mutual information to the squared Frobenius norm, we require
one to be convex to form a trace and the other to have monotone derivative in
order to force decoupling over the relevant parameters. In the low SNR regime,
these parameters are the eigenvalues of $\lambda\bm{\Sigma}$, while in the
high SNR regime, we work with the diagonal entries of $\bm{\Sigma}$. Finally,
we use analytic continuation to extend these lemmas to the entire positive
real line.

######  Proposition 1 (Rank-one reduction for all non-negative SNR).

Let $\operatorname{\mathbb{P}}_{X,M}=\operatorname{\mathbb{P}}_{X}^{\otimes
M}$. We have for all $\lambda\geq 0$ that

$\sup_{\bm{Q}\in\mathcal{S}_{M}}F_{M}^{\rm
RS}(\bm{Q},\lambda)=\sup_{q\in[0,\rho]}F_{1}^{\rm RS}(q,\lambda).$ (18)

###### Proof.

That $\sup_{\bm{Q}\in\mathcal{S}_{M}}F_{M}^{\rm RS}(\bm{Q},\lambda)$ has one
non-analytic point $\lambda_{c,M}$ is a hypothesis of Theorem 1. Suppose,
without loss of generality, that the non-analytic point of
$\sup_{q\in[0,\rho]}F_{1}^{\rm RS}(q,\lambda)$ is at
$\lambda_{c,1}\leq\lambda_{c,M}$. Decreasing $\lambda_{S}$ (increasing
$\lambda_{L}$) if needed, we then have that these two suprema are analytic
functions of $\lambda$ on
$[0,\infty)\setminus\\{\lambda_{c,1},\lambda_{c,M}\\}$ that agree on
$[0,\lambda_{S})\cup(\lambda_{L},\infty)$. Thus, by analytic continuation,
they agree on $[0,\lambda_{c,1})\cup(\lambda_{c,M},\infty)$. By analyticity
and Remark 1, they must also agree on $(\lambda_{c,1},\lambda_{c,M})$, hence
on all of $[0,\infty)$. ∎

##  IV Free entropy lower bound: interpolation

The standard (finite rank) interpolation argument allows us to establish the
desired lower bound on the free entropy $F_{N}(\lambda)$.

######  Proposition 2 (Free entropy lower bound).

Under the assumptions of Theorem 1, but with $M,N\geq 1$ free, we have that

$F_{N}(\lambda)\geq\sup_{q\in[0,\rho]}F_{1}^{\rm RS}(q,\lambda).$ (19)

###### Proof.

This argument is standard and can be found in [14] (apart from the rank-one
reduction given by Proposition 1 used at the end). We recall the main ideas.
First, we compare $F_{N}(\lambda)$ to $F_{M}^{\rm RS}(\bm{Q},\lambda)$ by
introducing an appropriate interpolating Hamiltonian $H_{N}(\bm{X},t)$ such
that (cf. (6))

$\displaystyle H_{N}(\bm{X},0)$
$\displaystyle=\sum_{i=1}^{N}\sqrt{\lambda}\bm{x}_{i}^{\intercal}\sqrt{\bm{Q}}\bm{z}_{i}+\lambda\bm{x}_{0,i}^{\intercal}\bm{Q}\bm{x}_{i}-\frac{\lambda}{2}\bm{x}_{i}^{\intercal}\bm{Q}\bm{x}_{i},$
$\displaystyle H_{N}(\bm{X},1)$ $\displaystyle=H_{N}(\bm{X}),$

where each $\bm{x}_{i}\in\mathbb{R}^{M}$ is the $i\textsuperscript{th}$ row of
$\bm{X}$ and for $i=1,\ldots,N$, the $\bm{z}_{i}\sim\mathcal{N}(0,I_{M})$ are
i.i.d. vectors. Letting $\varphi(t)$ denote the corresponding interpolating
free entropy, applying Gaussian integration by parts and the Nishimori
identity shows that

$\varphi^{\prime}(t)\geq-\frac{\lambda}{4M}\operatorname{Tr}\bm{Q}^{2}.$

But then, for all $\bm{Q}\in\mathcal{S}_{M}$,

$F_{N}(\lambda)-F_{M}^{\rm
RS}(\bm{Q},\lambda)=\varphi(1)-\varphi(0)+\frac{\lambda}{4M}\operatorname{Tr}\bm{Q}^{2}\geq
0.$

Taking the supremum over $\bm{Q}\in\mathcal{S}_{M}$ and using Proposition 1 to
replace said supremum then completes the proof. ∎

##  V Free entropy upper bound:
the multiscale cavity method

The goal in this section is to show that

$\limsup_{N\to\infty}F_{N}(\lambda)\leq\sup_{q\in[0,\rho]}F_{1}^{\rm
RS}(q,\lambda).$

Combining this result with Proposition 2 would then prove Theorem 1. This
bound is obtained via an adaptation of the cavity method that allows for
increments in both $M$ and $N$. An essential result for carrying out said
cavity computation is the concentration of the overlap matrix.

###  V-A Concentration of the overlap matrix

Due to the symmetries of our model, we are able to add small side information
to induce concentration of the overlap matrix $\mathbb{R}^{M\times
M}\ni\bm{R}_{10}:=\frac{1}{N}\bm{X}^{\intercal}\bm{X}_{0}$. This side
information is negligible in the large $N$ limit and is incorporated through
the introduction of the perturbed Hamiltonian (cf. (4))

$\displaystyle H_{N}^{(\varepsilon)}(\bm{X})$ $\displaystyle:=H_{N+1}(\bm{X})$
$\displaystyle\quad+\operatorname{Tr}\Big{(}\sqrt{\varepsilon}\bm{X}^{\intercal}\tilde{\bm{Z}}+\varepsilon\bm{X}^{\intercal}\bm{X}_{0}-\frac{\varepsilon}{2}\bm{X}^{\intercal}\bm{X}\Big{)},$
(20)

where $\tilde{\bm{Z}}\in\mathbb{R}^{N\times M}$ is a standard Ginibre matrix
consisting of i.i.d. standard Gaussian entries independent of everything else
and $\varepsilon\in[s_{N},2s_{N}]$ is a perturbation parameter with
$(s_{N})_{N\geq 1}$ a decreasing sequence of real numbers in $(0,1)$ that tend
slowly to zero as $N\to\infty$; note the $(N+1)$-dependence of the first term
in the perturbed Hamiltonian. The perturbation Hamiltonian (trace term above)
can be understood as the log-likelihood corresponding to a side Gaussian
channel $\sqrt{\varepsilon}\bm{X}_{0}+\tilde{\bm{Z}}$. The resulting
$H_{N}^{(\varepsilon)}(\bm{X})$ thus still corresponds to the log-likelihood
of an inference problem in the Bayes-optimal setting and so-called Nishimori
identities hold which, in turn, induce concentration-of-measure [15, 16]. Note
the particularly simple form of side information/perturbation used here
compared to [15, 20, 21]. This is possible due the fact that in the cavity
method we only need concentration w.r.t. the posterior law conditional on the
data ($\langle\,\cdot\,\rangle_{N,\varepsilon}$ defined below) instead of the
stronger statements proved in the aforementioned references that include
concentration w.r.t. the data as well. Another key point of this simple
perturbation is that it maintains the exchangeability of the variables
$(\bm{x}_{ij})$ under the quenched Gibbs measure
$\mathbb{E}\langle\,\cdot\,\rangle_{N,\varepsilon}$: no statistical symmetries
present in the original model are broken by the perturbation apart from the
trivial sign ambiguity $\bm{X}\to-\bm{X}$. These two points allow us to obtain
concentration for higher regimes of rank than what we would obtain using more
complicated perturbations. As a concrete consequence, we are able to reach
$M={\rm o}(N^{1/10})$ compared to the $M={\rm o}(N^{1/20})$ obtained in [21].
Yet, there is room for improvement in order to reach $M=N^{\alpha}$ for any
$\alpha<1$, the regime for which we believe Theorem 1 to hold.

Let the partition function and Gibbs (posterior) average with respect to the
perturbed Hamiltonian be

$\displaystyle\tilde{Z}_{N,M}$ $\displaystyle:=\int
e^{H_{N}^{(\varepsilon)}(\bm{X})}\,d\operatorname{\mathbb{P}}_{X,N,M}(\bm{X}),$
$\displaystyle\langle\,\cdot\,\rangle_{N,\varepsilon}$
$\displaystyle:=\frac{1}{\tilde{Z}_{N,M}}\int\,\cdot\,e^{H_{N}^{(\varepsilon)}(\bm{X})}\,d\operatorname{\mathbb{P}}_{X,N,M}(\bm{X}).$

In analogy with (2), the perturbed free entropy reads

$\displaystyle\tilde{F}_{N}(\lambda)=\tilde{F}_{N,M}(\lambda):=\frac{1}{NM}\mathbb{E}_{\bm{Z},\bm{X}_{0}}\ln\tilde{Z}_{N,M}.$
(21)

######  Proposition 3 (Overlap concentration).

Under the assumptions of Theorem 1, there exists a constant $C$ depending only
on properties of $\operatorname{\mathbb{P}}_{X}$ such that

$\displaystyle\frac{1}{s_{N}}\int_{s_{N}}^{2s_{N}}d\varepsilon\,\mathbb{E}\langle\|\bm{R}_{10}-\langle\bm{R}_{10}\rangle_{N,\varepsilon}\|_{\rm
F}^{2}\rangle_{N,\varepsilon}\leq\Gamma_{N,M}:=\frac{CM^{2}}{\sqrt{Ns_{N}}}.$

This proposition follows from a modification of an argument of [20, 15],
whereby one uses Gaussian intergration by parts and the Nishimori identity to
observe that concentration of $\bm{R}_{10}$ is governed by the concentration
of the simpler auxiliary function
$\mathcal{L}:=-N^{-1}\partial_{\varepsilon}H_{N}^{(\varepsilon)}(\bm{X})$.

The negligibility of our side information is made precise in the following
lemma, which follows from an interpolation argument akin to the proof of
Proposition 2.

######  Lemma 6 (The perturbation is negligible).

Under the assumptions of Theorem 1, we have uniformly for
$\varepsilon\in[s_{N},2s_{N}]$ that

$F_{N}(\lambda)\leq\tilde{F}_{N}(\lambda)+{\rm O}(s_{N}).$

Due to this lemma, we may henceforth supplant our task of establishing an
upper bound on $F_{N}(\lambda)$ with that of bounding
$\tilde{F}_{N}(\lambda)$, which enables use of Proposition 3.

###  V-B Multiscale cavity method and proof of Theorem 1

The main methodological novelty starts now. In the multiscale setting, the
rank $M=M_{N}$ grows as a function of $N$. Therefore, there are two growing
interacting scales that need to be considered jointly: the row and column
dimensions. It is thus no longer amenable to the standard Aizenman–Sims–Starr
scheme [39, 14]. We show that in the multiscale setting, the free entropy can
be expressed as a convex combination of a normalization of the limits of the
finite differences

$\displaystyle\Delta_{N}(n,m)$
$\displaystyle:=\mathbb{E}\ln\tilde{Z}_{n+1,m}-\mathbb{E}\ln\tilde{Z}_{n,m},$
$\displaystyle\Delta_{M}(n,m)$
$\displaystyle:=\mathbb{E}\ln\tilde{Z}_{n,m+1}-\mathbb{E}\ln\tilde{Z}_{n,m}.$

To simplify notation, we define $\Delta_{N}:=\Delta_{N}(N,M_{N+1})$ and
$\Delta_{M}:=\Delta_{M}(N,M_{N})$. We now provide generic bounds for
multiscale free entropies indexed by two growing dimensions. Here, the
dependency between $M,N$ is generic.

######  Theorem 2 (Multiscale Aizenman–Sims–Starr identity).

Let $\alpha>0$, $\gamma\geq 0$, and $M=M_{N}=\lfloor\alpha N^{\gamma}\rfloor$.
Then,

$\limsup_{N\to\infty}\tilde{F}_{N}(\lambda)\leq\frac{1}{1+\gamma}\limsup_{N\to\infty}\frac{\Delta_{N}}{M}+\frac{\gamma}{1+\gamma}\limsup_{N\to\infty}\frac{\Delta_{M}}{N},$
$\liminf_{N\to\infty}\tilde{F}_{N}(\lambda)\geq\frac{1}{1+\gamma}\liminf_{N\to\infty}\frac{\Delta_{N}}{M}+\frac{\gamma}{1+\gamma}\liminf_{N\to\infty}\frac{\Delta_{M}}{N}.$

This result is sharp in the sense that if the limits on the right hand side
exist, then

$\lim_{N\to\infty}\tilde{F}_{N,M_{N}}=\frac{1}{1+\gamma}\lim_{N\to\infty}\frac{\Delta_{N}}{M}+\frac{\gamma}{1+\gamma}\lim_{N\to\infty}\frac{\Delta_{M}}{N}.$

###### Proof.

We focus on proving the upper bound, since the lower bound will follow from
obvious modifications. It also suffices to consider the case that
$0<\gamma\leq 1$, since the case $\gamma=0$ is the usual Aizenman–Sims–Starr
scheme and the $\gamma>1$ case can be deduced from the case when $\gamma\leq
1$ by interchanging the $N$ and $M$ indices.

Let $\epsilon>0$. We define

$m_{n}=\lfloor\alpha n^{\gamma}\rfloor\text{ and
}n_{m}=\lfloor\alpha^{-1}m^{\frac{1}{\gamma}}\rfloor$

to denote the $m$ index as a function of $n$ and the $n$ index as a function
of $m$; these dependencies are the same as between $M_{N}$ and $N$. We begin
as in the standard proof by expressing the log partition function as a
(truncated) telescoping sum,

$\displaystyle\tilde{F}_{N}(\lambda)$
$\displaystyle=\frac{1}{NM}\sum_{n=T}^{N-1}\Big{(}\mathbb{E}\ln\tilde{Z}_{n+1,m_{n+1}}-\mathbb{E}\ln\tilde{Z}_{n,m_{n}}\Big{)}\\!+\\!{\rm
o}_{N}(T)$
$\displaystyle=\frac{1}{NM}\Big{(}\sum_{n=T}^{N-1}\tilde{\Delta}_{N}(n)+\sum_{n=T}^{N-1}\tilde{\Delta}_{M}(n)\Big{)}\\!+\\!{\rm
o}_{N}(T),$

where

$\displaystyle\tilde{\Delta}_{N}(n)$
$\displaystyle:=\mathbb{E}\ln\tilde{Z}_{n+1,m_{n+1}}-\mathbb{E}\ln\tilde{Z}_{n,m_{n+1}},$
$\displaystyle\tilde{\Delta}_{M}(n)$
$\displaystyle:=\mathbb{E}\ln\tilde{Z}_{n,m_{n+1}}-\mathbb{E}\ln\tilde{Z}_{n,m_{n}},$

and the error term $o_{N}(T)$ tends to $0$ as $N\to\infty$ for any fixed $T$.
Notice that $\tilde{\Delta}_{M}(n)=0$ if $m_{n+1}=m_{n}$, so we only keep the
terms in the second sum when the $m_{n}$ coordinate increases. The truncation
$T=T(\epsilon)$ is chosen sufficiently large such that for all $n\geq T$,

$\frac{\tilde{\Delta}_{N}(n)}{m_{n}}\leq\limsup_{N\to\infty}\frac{\Delta_{N}}{M}+\epsilon$

and (considering only $n\geq T$ for which $m_{n+1}=m_{n}+1$)

$\frac{\tilde{\Delta}_{M}(n)}{n}\leq\limsup_{N\to\infty}\frac{\Delta_{M}}{N}+\epsilon.$

Substituting these bounds into the telescoping sum gives the upper bound

$\tilde{F}_{N}(\lambda)\leq\Big{(}\frac{\sum_{n=T}^{N-1}m_{n}}{NM}\Big{)}\Big{(}\limsup_{N\to\infty}\frac{\Delta_{N}}{M}+\epsilon\Big{)}\\\
\quad+\Big{(}\frac{\sum_{m=M_{T}}^{M_{N-1}}n_{m}}{NM}\Big{)}\Big{(}\limsup_{N\to\infty}\frac{\Delta_{M}}{N}+\epsilon\Big{)}+{\rm
o}_{N}(T).$ (22)

The desired upper bound now follows from the integral approximations

$\frac{\sum_{n=T}^{N-1}m_{n}}{NM}\leq\int_{T}^{N}\frac{\alpha
k^{\gamma}}{NM}\,dk=\frac{1}{1+\gamma}+{\rm o}_{N}(T)$

and

$\frac{\sum_{m=M_{T}}^{M_{N-1}}n_{m}}{NM}\leq\int_{M_{T}}^{M_{N-1}+1}\frac{\alpha^{-1}k^{\frac{1}{\gamma}}}{NM}\,dk=\frac{\gamma}{1+\gamma}+{\rm
o}_{N}(T).$

Taking the limit superior of both sides of (22) and then taking $\epsilon\to
0$ completes the proof of the upper bound.

It is worth mentioning that the integral approximations are asymptotically
sharp in the sense that

$\frac{\sum_{n=T}^{N-1}m_{n}}{NM}\geq\int_{T-1}^{N-1}\frac{\alpha
k^{\gamma}}{NM}\,dk\asymp\frac{1}{1+\gamma}$

and

$\frac{\sum_{m=M_{T}}^{M_{N-1}}n_{m}}{NM}\geq\int_{M_{T}-1}^{M_{N-1}-1}\frac{\alpha^{-1}k^{\frac{1}{\gamma}}}{NM}\,dk\asymp\frac{\gamma}{1+\gamma},$

so the lower bound of the theorem follows from a similar argument to that just
presented. ∎

Remarkably, thanks to the rank-one reduction described in Proposition 1, it
turns out that both of the limit suprema in the RHS of the upper bound in
Theorem 2 reduce to the RHS of (8). Hence, so too does their displayed convex
sum, as desired. This drastic simplification is however not expected to hold
in the linear scaling $M=\Theta(N)$.

We have stated here the multiscale Aizenman–Sims–Starr identity in terms of
the (perturbed) free entropy for convenience, but it actually holds for _any_
generic sequence with two growing indices. Indeed, it is a general fact about
sequences and uses no properties of the log partition function, as can be seen
from the proof. The parameter $\alpha$ does not appear in the convex
combinations displayed in Theorem 2, but it does appear in the $\Delta_{M}$
terms and can thus have an effect on the limit of the differences.
Furthermore, if $\tilde{F}_{N}$ remains finite in the limit, then $\Delta_{N}$
is an order $M$ quantity and $\Delta_{M}$ is an order $N$ quantity, so the
normalized differences in the spin and rank coordinates are both of constant
order and both have non-negligible contribution to the limiting value. In
other words, even if $M_{N}\ll N$ so that adding a column occurs much less
frequently than rows when the system size grows, the free entropy difference
due to column addition is much larger than the one due to row addition because
columns are of length $N$, while rows are of length $M$. These two effects
perfectly compensate each other so that both row and column addition
contributes the same order in the multiscale Aizenman–Sims–Starr scheme.

The multiscale cavity method is a powerful tool because the limit of a two-
indices sequence with nonlinear asymptotic growth rate can be computed by
finding the limits of the differences where one of the coordinates is _fixed_
, instead of having to deal with increments in both coordinates
simultaneously. In other words, the $\Delta_{N}$ and $\Delta_{M}$ can be
computed independently of one another to isolate the effects of adding one
spin or adding one rank coordinate. In statistical physics language, this
reduces the problem to computing a cavity in the spins for fixed rank
dimension and a cavity in the rank for fixed spin dimension in the
thermodynamic limit. The $\Delta_{N}$ is the standard cavity studied in
classical models, while $\Delta_{M}$ is a term that only appears when
examining multiscale models.

####  V-B1 The $\Delta_{N}$ cavity bound

Carrying out the standard Aizenman–Sims–Starr procedure [39], [14, Section
4.3], which relies crucially on the concentration of the overlap matrix given
in Proposition 3, yields the following.

######  Lemma 7 ($\Delta_{N}$ cavity bound).

For $M,N\geq 1$ and $\operatorname{\mathbb{P}}_{X,N,M}$ fully factorized with
$\rho<\infty$, we have that

$\frac{\Delta_{N}(N,M)}{M}\leq\sup_{q\in[0,\rho]}F_{1}^{\rm
RS}(q,\lambda)+{\rm O}(M\Gamma_{N,M})+{\rm o}_{N}(1).$ (23)

The error terms vanish as $N\to\infty$ when $M={\rm o}(N^{1/6})$.

####  V-B2 The $\Delta_{M}$ cavity bound

Recall $\Delta_{M}:=\Delta_{M}(N,M_{N})$. We now present the analogue of Lemma
7 for $\Delta_{M}$ with a shortened proof due to its novelty. We will do a
comparison of a rank $M+1$ and a rank $M$ system. The rank one equivalence of
the rank $M$ model (after normalization) suggests to write

$\displaystyle\frac{\Delta_{M}}{N}$
$\displaystyle=\frac{1}{N}\mathbb{E}\ln\tilde{Z}_{N,M_{N}+1}-\frac{1}{N}\mathbb{E}\ln\tilde{Z}_{N,M_{N}}$
$\displaystyle\approx(M_{N}+1)\sup_{q}F_{1}^{\rm RS}-M_{N}\sup_{q}F_{1}^{\rm
RS}=\sup_{q}F_{1}^{\rm RS}.$

This intuition is the correct one and is formalized as follows.

######  Lemma 8 ($\Delta_{M}$ cavity bound).

For $M_{N}={\rm o}(N^{1/10})$ and $\operatorname{\mathbb{P}}_{X,N,M}$ fully
factorized with $\rho<\infty$, we have that

$\limsup_{N\to\infty}\frac{\Delta_{M}}{N}\leq\sup_{q\in[0,\rho]}F_{1}^{\rm
RS}(q,\lambda).$

###### Proof.

Define

$\hat{\Delta}_{N}(n):=\Delta_{N}(n,M_{N}+1)$

in order to track the increment in the $N$ index with fixed $M_{N}+1$ index.
We treat the two terms in the definition of $\Delta_{M}=\Delta_{M}(N,M_{N})$
separately. For the first, we consider a telescoping series over the $N$-index
to see that

$\frac{\mathbb{E}\ln\tilde{Z}_{N,M_{N}+1}}{N}=\frac{1}{N}\sum_{n=T}^{N-1}\hat{\Delta}_{N}(n)+\frac{1}{N}\sum_{n=0}^{T-1}\hat{\Delta}_{N}(n)\\\
\leq\Big{(}1-\frac{T}{N}\Big{)}\sup_{n\geq
T}\hat{\Delta}_{N}(n)+\frac{T}{N}\sup_{n<T}\hat{\Delta}_{N}(n),$

where $T$ is a truncation parameter to be decided. Due to Lemma 7, the first
supremum is bounded above, up to an error term decreasing with $T$, by
$(M_{N}+1)\sup_{q\in[0,\rho]}F_{1}^{\rm RS}(q,\lambda)$. A cavity argument
shows that the second supremum is bounded above by $CM_{N}^{2}$ for some
constant $C$ depending only on $\lambda$ and $\operatorname{\mathbb{P}}_{X}$.
For the second term in the definition of $\Delta_{M}$, simply observe from
Proposition 2 that

$-\frac{\mathbb{E}\ln\tilde{Z}_{N,M_{N}}}{N}\leq-
M_{N}\sup_{q\in[0,\rho]}F_{1}^{\rm RS}(q,\lambda).$ (24)

Summing the two bounds thus gives

$\displaystyle\frac{\Delta_{M}}{N}\leq\sup_{q\in[0,\rho]}F_{1}^{\rm
RS}(q,\lambda)+{\rm error}(N,M_{N},T).$ (25)

Taking $T=N^{4/5-\epsilon(\gamma)}$ for some small constant $\epsilon(\gamma)$
and $M_{N}=o(N^{1/10})$ is sufficient for the combination of all error terms
in (25) to vanish when taking the limit superior. ∎

####  V-B3 Proof of Theorem 1

Combining the last two lemmas together with Theorem 2 (noting that setting
$M=M_{N+1}$ within (23) and multiplying both sides by $M_{N+1}/M_{N}$ shows
that $\Delta_{N}/M_{N}$ is bounded above by $\sup_{q\in[0,\rho]}F_{1}^{\rm
RS}(q,\lambda)$ plus error terms vanishing at large $N$) produces the upper
bound

$\limsup_{N\to\infty}\tilde{F}_{N}(\lambda)\leq\sup_{q\in[0,\rho]}F_{1}^{\rm
RS}(q,\lambda).$

Lemma 6 then shows that $\limsup_{N\to\infty}F_{N}(\lambda)$ obeys the same
upper bound. As this matches the lower bound of Proposition 2, we are done.

##  VI Conclusion

We studied the spiked Wigner model with growing rank $M={\rm o}(N^{1/10})$. We
have derived results on worst additive Gaussian noise and used them to show
equivalence between $\sup_{\bm{Q}\in\mathcal{S}_{M}}F_{M}^{\rm
RS}(\bm{Q},\lambda)$ and $\sup_{q\in[0,\rho]}F_{1}^{\rm RS}(q,\lambda)$. This
reduction was used inside a standard interpolation argument, followed by the
novel multiscale cavity method, in order to prove that the limiting free
entropy remains the same as in the case of rank equal to one for signals with
i.i.d. entries.

In terms of novelty, we used information-theoretic arguments to reduce our
rank-$M$ replica symmetric potential to its rank-one counterpart. In addition
to yielding a tractable final result, this allowed us to apply a
generalization of the Aizenman–Sims–Starr scheme. Using the cavity method
instead of, say, the adaptive interpolation method [20, 21] means that we
required only posterior concentration of the overlap rather than full
(quenched) concentration. This in turn enabled us to employ a scalar
perturbation parameter (as opposed to a matrix), leading to more tractable
computations and better rates of convergence.

The rank-one reduction follows from the factorized form of the prior and the
induced exchangeability, implying that $F_{M}^{\rm RS}(\bm{Q},\lambda)$ is
maximized at a matrix proportional to the identity. This is similar to recent
simplifications of vector spins Parisi formulae obtained in [36, 37] through
the utilization of underlying symmetries in the Potts spin glass. Combining
these simplifications with our multiscale cavity method has the potential to
extend the corresponding finite-rank vector spin models to sublinear-rank
multiscale models, which is a natural step towards understanding the
challenging extensive rank regime $M=\Theta(N)$, see [49, 23, 24, 25, 50, 51,
52]. In this vein, we foresee that the relative tractability of our
computations will also enable us to push the theory of tensor factorization
[53, 19, 20, 54, 55, 56] into the growing rank regime.

## Acknowledgments

J. Barbier and A. A. Rahman were funded by the European Union (ERC, CHORAL,
project number 101039794). J. Ko was funded by the European Union (ERC, LDRAM,
project number 884584) and the Natural Sciences and Engineering Research
Council of Canada (RGPIN-2020-04597). The authors acknowledge crucial
discussions with Francesco Camilli and Koki Okajima which led to the joint
development of the multiscale cavity method.

## References

  * [1] Y. Deshpande and A. Montanari, “Information-theoretically optimal sparse PCA,” in _2014 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2014, pp. 2197–2201.
  * [2] T. Lesieur, F. Krzakala, and L. Zdeborová, “Phase transitions in sparse PCA,” in _2015 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2015, pp. 1635–1639.
  * [3] Y. Deshpande, E. Abbe, and A. Montanari, “Asymptotic mutual information for the balanced binary stochastic block model,” _Information and Inference: A Journal of the IMA_ , vol. 6, no. 2, pp. 125–170, 2017.
  * [4] E. Abbe, “Community detection and stochastic block models: Recent developments,” _Journal of Machine Learning Research_ , vol. 18, no. 177, pp. 1–86, 2018.
  * [5] Y. Chen and J. Xu, “Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices,” _Journal of Machine Learning Research_ , vol. 17, no. 27, pp. 1–57, 2016.
  * [6] B. Hajek, Y. Wu, and J. Xu, “Submatrix localization via message passing,” _Journal of Machine Learning Research_ , vol. 18, no. 186, pp. 1–52, 2018\.
  * [7] I. M. Johnstone, “On the distribution of the largest eigenvalue in principal components analysis,” _Annals of Statistics_ , vol. 29, no. 2, pp. 295–327, 2001.
  * [8] J. Baik, G. Ben Arous, and S. Péché, “Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices,” _Annals of Probability_ , vol. 33, no. 5, pp. 1643–1697, 2005.
  * [9] S. Péché, “The largest eigenvalue of small rank perturbations of hermitian random matrices,” _Probability Theory and Related Fields_ , vol. 134, no. 1, pp. 127–173, 2006.
  * [10] T. Lesieur, F. Krzakala, and L. Zdeborová, “MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel,” in _53rd Annual Allerton Conference on Communication, Control, and Computing_. IEEE, 2015, pp. 680–687.
  * [11] F. Krzakala, J. Xu, and L. Zdeborová, “Mutual information in rank-one matrix estimation,” in _2016 IEEE Information Theory Workshop (ITW)_. IEEE, 2016, pp. 71–75.
  * [12] A. Guionnet, J. Ko, F. Krzakala, and L. Zdeborová, “Low-rank matrix estimation with inhomogeneous noise,” _arXiv preprint arXiv:2208.05918_ , 2022.
  * [13] A. Guionnet, J. Ko, F. Krzakala, and L. Zdeborová, “Estimating rank-one matrices with mismatched prior and noise: universality and large deviations,” _arXiv preprint arXiv:2306.09283_ , 2023.
  * [14] M. Lelarge and L. Miolane, “Fundamental limits of symmetric low-rank matrix estimation,” _Probability Theory and Related Fields_ , vol. 173, no. 3, pp. 859–929, 2019.
  * [15] J. Barbier, “Overlap matrix concentration in optimal bayesian inference,” _Information and Inference: A Journal of the IMA_ , vol. 10, no. 2, pp. 597–623, 2021.
  * [16] J. Barbier and D. Panchenko, “Strong replica symmetry in high-dimensional optimal bayesian inference,” _Communications in mathematical physics_ , vol. 393, no. 3, pp. 1199–1239, 2022.
  * [17] S. B. Korada and N. Macris, “Exact solution of the gauge symmetric p-spin glass model on a complete graph,” _Journal of Statistical Physics_ , vol. 136, pp. 205–230, 2009.
  * [18] J. Barbier, M. Dia, N. Macris, F. Krzakala, T. Lesieur, and L. Zdeborová, “Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula,” in _Advances in Neural Information Processing Systems 29_. NIPS, 2016, pp. 424–432.
  * [19] T. Lesieur, L. Miolane, M. Lelarge, F. Krzakala, and L. Zdeborová, “Statistical and computational phase transitions in spiked tensor estimation,” in _2017 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2017, pp. 511–515.
  * [20] C. Luneau, J. Barbier, and N. Macris, “Mutual information for low-rank even-order symmetric tensor estimation,” _Information and Inference: A Journal of the IMA_ , vol. 10, no. 4, pp. 1167–1207, 2021.
  * [21] G. Reeves, “Information-theoretic limits for the matrix tensor product,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 1, no. 3, pp. 777–798, 2020.
  * [22] J. Husson and J. Ko, “Spherical integrals of sublinear rank,” _arXiv preprint arXiv:2208.03642_ , 2023.
  * [23] A. Maillard, F. Krzakala, M. Mézard, and L. Zdeborová, “Perturbative construction of mean-field equations in extensive-rank matrix factorization and denoising,” _Journal of Statistical Mechanics: Theory and Experiment_ , vol. 2022, no. 8, p. 083301, 2022.
  * [24] A. Bodin and N. Macris, “Gradient flow on extensive-rank positive semi-definite matrix denoising,” _arXiv preprint arXiv:2303.09474_ , 2023\.
  * [25] F. Pourkamali, J. Barbier, and N. Macris, “Matrix inference in growing rank regimes,” _arXiv preprint arXiv:2306.01412_ , 2023.
  * [26] D. Panchenko, “Free energy in the mixed $p$-spin models with vector spins,” _Ann. Probab._ , vol. 46, no. 2, pp. 865–896, 2018.
  * [27] ——, “Free energy in the Potts spin glass,” _Ann. Probab._ , vol. 46, no. 2, pp. 829–864, 2018.
  * [28] J. Ko, “Free energy of multiple systems of spherical spin glasses with constrained overlaps,” _Electron. J. Probab._ , vol. 25, pp. Paper No. 28, 34, 2020.
  * [29] ——, “The Crisanti-Sommers Formula for Spherical Spin Glasses with Vector Spins,” _arXiv preprint arXiv:1911.04355_ , 2019.
  * [30] T. Dominguez, “The $\ell^{p}$-Gaussian-Grothendieck problem with vector spins,” _Electron. J. Probab._ , vol. 27, pp. Paper No. 70, 46, 2022.
  * [31] D. Belius, L. Fröber, and J. Ko, “TAP variational principle for the constrained overlap multiple spherical Sherrington-Kirkpatrick model,” _arXiv preprint arXiv:2304.04031_ , 2023.
  * [32] H.-B. Chen and J.-C. Mourrat, “On the free energy of vector spin glasses with non-convex interactions,” _arXiv preprint arXiv:2311.08980_ , 2023.
  * [33] J.-C. Mourrat, “Free energy upper bound for mean-field vector spin glasses,” _Ann. Inst. Henri Poincaré Probab. Stat._ , vol. 59, no. 3, pp. 1143–1182, 2023.
  * [34] H.-B. Chen, “On the self-overlap in vector spin glasses,” _arXiv preprint arXiv:2311.09880_ , 2023.
  * [35] ——, “Parisi PDE and convexity for vector spins,” _arXiv preprint arXiv:2311.10446_ , 2023.
  * [36] E. Bates and Y. Sohn, “Parisi formula for balanced Potts spin glass,” _arXiv preprint arXiv:2310.06745_ , 2023.
  * [37] H.-B. Chen, “On Parisi measures of Potts spin glasses with correction,” _arXiv preprint arXiv:2311.11699_ , 2023.
  * [38] A. Auffinger and Y. Zhou, “On properties of the spherical mixed vector $p$-spin model,” _Stochastic Process. Appl._ , vol. 146, pp. 382–413, 2022\.
  * [39] M. Aizenman, R. Sims, and S. L. Starr, “Extended variational principle for the Sherrington-Kirkpatrick spin-glass model,” _Phys. Rev. B_ , vol. 68, p. 214403, Dec 2003.
  * [40] S. N. Diggavi and T. M. Cover, “Is maximum entropy noise the worst?” in _1997 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 1997, p. 278.
  * [41] ——, “The worst additive noise under a covariance constraint,” _IEEE Transactions on Information Theory_ , vol. 47, no. 7, pp. 3072–3081, 2001.
  * [42] I. Shomorony and A. S. Avestimehr, “Is Gaussian noise the worst-case additive noise in wireless networks?” in _2012 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2012, pp. 214–218.
  * [43] M. Mézard, G. Parisi, and M. Virasoro, _Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications_. World Scientific Publishing Co Inc, 1987.
  * [44] D. Guo, S. Shamai, and S. Verdu, “Mutual information and minimum mean-square error in Gaussian channels,” _IEEE Transactions on Information Theory_ , vol. 51, no. 4, pp. 1261–1262, 2005.
  * [45] L. Miolane, “Phase transitions in spiked matrix estimation: information-theoretic analysis,” _arXiv preprint arXiv:1806.04343_ , 2019\.
  * [46] J. Huang, “Mesoscopic perturbations of large random matrices,” _Random Matrices: Theory and Applications_ , vol. 7, no. 02, p. 1850004, 2018.
  * [47] G. Reeves, H. D. Pfister, and A. Dytso, “Mutual Information as a Function of Matrix SNR for Linear Gaussian Channels,” in _2018 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2018, pp. 1754–1758.
  * [48] A. Wibisono and V. Jog, “Convexity of mutual information along the heat flow,” in _2018 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2018, pp. 1615–1619.
  * [49] S. Tarmoun, G. Franca, B. D. Haeffele, and R. Vidal, “Understanding the dynamics of gradient flow in overparameterized linear models,” in _Proceedings of the 38th International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, M. Meila and T. Zhang, Eds., vol. 139. PMLR, 18–24 Jul 2021, pp. 10 153–10 161. [Online]. Available: https://proceedings.mlr.press/v139/tarmoun21a.html
  * [50] J. Barbier and N. Macris, “Statistical limits of dictionary learning: Random matrix theory and the spectral replica method,” _Phys. Rev. E_ , vol. 106, no. 2, p. 024136, 2022.
  * [51] F. Camilli and M. Mézard, “Matrix factorization with neural networks,” _Physical Review E_ , vol. 107, no. 6, p. 064308, 2023.
  * [52] ——, “The decimation scheme for symmetric matrix factorization,” _Journal of Physics A: Mathematical and Theoretical_ , vol. 57, no. 8, p. 085002, 2024.
  * [53] A. Montanari and E. Richard, “A statistical model for tensor PCA,” in _Advances in Neural Information Processing Systems 27_. NIPS, 2014, pp. 2987–2905.
  * [54] A. Montanari and Y. Wu, “Fundamental Limits of Low-Rank Matrix Estimation with Diverging Aspect Ratios,” _arXiv preprint arXiv:2211.00488_ , 2022\.
  * [55] D. L. Donoho and M. J. Feldman, “Optimal Eigenvalue Shrinkage in the Semicircle Limit,” _arXiv preprint arXiv:2210.04488_ , 2023.
  * [56] M. J. Feldman, “Spiked Singular Values and Vectors under Extreme Aspect Ratios,” _Journal of Multivariate Analysis_ , vol. 196, p. 105187, 2023\.