$\displaystyle\lim_{a\searrow\sup\operatorname{supp}({\mathcal{T}}(\overline{Y}))}\varphi(a)$
$\displaystyle=\lim_{a\searrow\sup\operatorname{supp}({\mathcal{T}}(\overline{Y}))}\frac{a}{\mathbb{E}\left[\overline{\Sigma}\right]}\mathbb{E}\left[\frac{\overline{G}^{2}{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\mathbb{E}\left[\frac{\overline{\Sigma}^{2}}{\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}}\right]=\infty,$

since the middle term converges to $\infty$ by _(e)_ in Equation 2.9 and the
remaining terms are lower bounded by some positive constant as
$a\searrow\sup\operatorname{supp}({\mathcal{T}}(\overline{Y}))$.

##### Limiting values of $\zeta$.

By definition,

$\displaystyle\lim_{a\searrow\sup\operatorname{supp}({\mathcal{T}}(\overline{Y}))}\zeta(a)$
$\displaystyle=\zeta(a^{\circ})=\psi(a^{\circ})<\infty.$ (A.6)

On the other hand, using Equation A.2, we obtain

$\displaystyle\lim_{a\to\infty}\zeta(a)=\lim_{a\to\infty}\psi(a)=\lim_{a\to\infty}a\gamma(a)=\infty.$
(A.7)

Finally, combining Equations A.4, A.6 and A.7 gives Equation A.1 which
completes the proof of the proposition. ∎

######  Proposition A.2 (Property of $\varphi$).

Let Item (A6) hold. Suppose

$\displaystyle\inf_{y\in\operatorname{supp}(\overline{Y})}{\mathcal{T}}(y)\geq
0.$ (A.8)

Then the function $\varphi$ is strictly decreasing.

###### Proof.

We show that $\varphi$ is strictly decreasing by proving $\varphi^{\prime}<0$.
Let us start by computing $\varphi^{\prime}$. Recall

$\displaystyle\mathbb{E}\left[\overline{\Sigma}\right]\varphi(a)$
$\displaystyle=\mathbb{E}\left[\overline{G}^{2}\frac{a{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\mathbb{E}\left[\frac{\overline{\Sigma}^{2}}{\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}}\right].$

Using chain rule, we obtain:

$\displaystyle\mathbb{E}\left[\overline{\Sigma}\right]\varphi^{\prime}(a)$
$\displaystyle=-\mathbb{E}\left[\overline{G}^{2}\frac{{\mathcal{T}}(\overline{Y})^{2}}{\left(a-{\mathcal{T}}(\overline{Y})\right)^{2}}\right]\mathbb{E}\left[\frac{\overline{\Sigma}^{2}}{\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}}\right]$
$\displaystyle\phantom{=}~{}-\mathbb{E}\left[\overline{G}^{2}\frac{a{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\mathbb{E}\left[\frac{\overline{\Sigma}^{2}}{\left(\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}\right)^{2}}\left(\gamma^{\prime}(a)+\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{\left(a-{\mathcal{T}}(\overline{Y})\right)^{2}}\right]\overline{\Sigma}\right)\right].$
(A.9)

The derivative of $\gamma$ can be accessed via the implicit function theorem.
Let

$\displaystyle H(a,\gamma)$
$\displaystyle=\frac{1}{\delta}\mathbb{E}\left[\frac{\overline{\Sigma}}{\gamma-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}}\right]-1.$

Recalling Equation 3.3, we see that $\gamma(a)$ is the solution $\gamma$ to
the equation $H(a,\gamma)=0$. We have

$\displaystyle\frac{\partial}{\partial a}H(a,\gamma)$
$\displaystyle=\frac{1}{\delta}\mathbb{E}\left[\frac{-\overline{\Sigma}}{\left(\gamma-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}\right)^{2}}\cdot(-\overline{\Sigma})\cdot\mathbb{E}\left[\frac{-{\mathcal{T}}(\overline{Y})}{(a-{\mathcal{T}}(\overline{Y}))^{2}}\right]\right]$
$\displaystyle=-\frac{1}{\delta}\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{(a-{\mathcal{T}}(\overline{Y}))^{2}}\right]\mathbb{E}\left[\frac{\overline{\Sigma}^{2}}{\left(\gamma-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}\right)^{2}}\right],$

and

$\displaystyle\frac{\partial}{\partial\gamma}H(a,\gamma)$
$\displaystyle=-\frac{1}{\delta}\mathbb{E}\left[\frac{\overline{\Sigma}}{\left(\gamma-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}\right)^{2}}\right].$

By Proposition G.5,

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}a}\gamma(a)$
$\displaystyle=-\frac{\frac{\partial}{\partial
a}H(a,\gamma(a))}{\frac{\partial}{\partial\gamma}H(a,\gamma(a))}=-\frac{\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{(a-{\mathcal{T}}(\overline{Y}))^{2}}\right]\mathbb{E}\left[\frac{\overline{\Sigma}^{2}}{\left(\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}\right)^{2}}\right]}{\mathbb{E}\left[\frac{\overline{\Sigma}}{\left(\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}\right)^{2}}\right]}.$
(A.10)

Using this, we simplify the second term of Equation A.9:

$\displaystyle\phantom{=}~{}-\mathbb{E}\left[\overline{G}^{2}\frac{a{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\mathbb{E}\left[\frac{\overline{\Sigma}^{2}}{\left(\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}\right)^{2}}\left(\gamma^{\prime}(a)+\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{\left(a-{\mathcal{T}}(\overline{Y})\right)^{2}}\right]\overline{\Sigma}\right)\right]$
$\displaystyle=-\mathbb{E}\left[\overline{G}^{2}\frac{a{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\mathbb{E}\left[\frac{\overline{\Sigma}^{2}}{\left(\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}\right)^{2}}\right]\gamma^{\prime}(a)$
$\displaystyle\phantom{=}~{}-\mathbb{E}\left[\overline{G}^{2}\frac{a{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{\left(a-{\mathcal{T}}(\overline{Y})\right)^{2}}\right]\mathbb{E}\left[\frac{\overline{\Sigma}^{3}}{\left(\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}\right)^{2}}\right]$
$\displaystyle=\mathbb{E}\left[\overline{G}^{2}\frac{a{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\mathbb{E}\left[\frac{\overline{\Sigma}^{2}}{\left(\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}\right)^{2}}\right]^{2}\frac{\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{(a-{\mathcal{T}}(\overline{Y}))^{2}}\right]}{\mathbb{E}\left[\frac{\overline{\Sigma}}{\left(\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}\right)^{2}}\right]}$
$\displaystyle\phantom{=}~{}-\mathbb{E}\left[\overline{G}^{2}\frac{a{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{\left(a-{\mathcal{T}}(\overline{Y})\right)^{2}}\right]\mathbb{E}\left[\frac{\overline{\Sigma}^{3}}{\left(\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}\right)^{2}}\right].$
(A.11)

Let us argue that the right-hand side is negative. First note that since _(i)_
$a>\sup\operatorname{supp}({\mathcal{T}}(\overline{Y}))>0$, _(ii)_
$\inf\operatorname{supp}({\mathcal{T}}(\overline{Y}))\geq 0$ by Equation A.8,
_(iii)_ ${\mathcal{T}}(\overline{Y})$ is not almost surely zero by Item (A6),
the common factors are positive:

$\displaystyle\mathbb{E}\left[\overline{G}^{2}\frac{a{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{(a-{\mathcal{T}}(\overline{Y}))^{2}}\right]>0.$
(A.12)

Then we apply the Cauchy–Schwarz inequality to obtain:

$\displaystyle\mathbb{E}\left[\frac{\overline{\Sigma}^{2}}{\left(\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}\right)^{2}}\right]^{2}$
$\displaystyle=\mathbb{E}\left[\frac{\overline{\Sigma}^{1/2}}{\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}}\cdot\frac{\overline{\Sigma}^{3/2}}{\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}}\right]^{2}$
(A.13)
$\displaystyle\leq\mathbb{E}\left[\frac{\overline{\Sigma}}{\left(\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}\right)^{2}}\right]\mathbb{E}\left[\frac{\overline{\Sigma}^{3}}{\left(\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}\right)^{2}}\right].$
(A.14)

Equation A.13 is valid since $\overline{\Sigma}$ is a positive random variable
and $\gamma(a)>s(a)$. Equations A.12 and A.14 jointly imply that the right-
hand side of Equation A.11, i.e., the second term of Equation A.9, is non-
positive, as claimed.

Moreover, the first term of Equation A.9 is strictly negative. We therefore
conclude that $\varphi^{\prime}(a)<0$ for any
$a>\sup\operatorname{supp}({\mathcal{T}}(\overline{Y}))$. ∎

######  Remark A.1 (Monotonicity of $\varphi$).

The monotonicity property of $\varphi$ relies on the non-negativity of
${\mathcal{T}}$ in Equation A.8. We believe that this assumption is
unnecessary. In many practically relevant cases, numerical evidence suggests
that $\varphi$ is monotone. For instance, we report in Figure 5 that in the
setting of noiseless phase retrieval $q(g,\varepsilon)=\left|g\right|$ with
optimal preprocessing function ${\mathcal{T}}(y)=\max\left\\{1-\frac{1}{\delta
y^{2}},-10\right\\}$ (where $\delta=0.1$), the function $\varphi$ is strictly
decreasing and convex in $(1,\infty)$ (note that
$\sup\operatorname{supp}({\mathcal{T}}(\overline{Y}))=1$) when
$\overline{\Sigma}$ has density either the one in Section E.2 (with
$\rho=0.9$) or the one in Section E.3 (with $c_{0}=1,c_{1}=0.1,\ell=17$). Note
that the function ${\mathcal{T}}$ here is not everywhere non-negative.

(a) Toeplitz case.

(b) Circulant case.

Figure 5: Plots of the function $\varphi$ defined in Equation 3.2 with
parameters specified in Remark A.1.

######  Proposition A.3 (Uniqueness of $a^{*}$).

Let Item (A6) hold. Suppose that the function $\varphi$ is strictly
decreasing. Then, $\varphi(a^{*})=\zeta(a^{*})$ has a unique solution in
$(\sup\operatorname{supp}({\mathcal{T}}(\overline{Y})),\infty)$.

###### Proof.

The uniqueness of $a^{*}$ follows from several geometric properties that have
been proved for the functions $\varphi$ and $\zeta$. Recall the assumption
that $\varphi$ is strictly decreasing and that $\zeta$ is non-decreasing by
Proposition A.2. Furthermore, from the proof of Proposition A.1 (in particular
Equations A.4, A.6 and A.7), we know that in the interval
$(\sup\operatorname{supp}({\mathcal{T}}(\overline{Y})),\infty)$, $\varphi$
strictly decreases from $\infty$ to a finite constant, whereas $\zeta$
increases from a finite constant to $\infty$. By the intermediate value
theorem, the solution to $\varphi(a^{*})=\zeta(a^{*})$ must exist and is
unique. ∎

###  A.2 Equivalent definitions of $a^{\circ},a^{*}$

Let ${\mathcal{A}}\subset{\mathbb{R}}^{2}$ be the domain on which the
potential solutions to various self-consistent equations of interest are to be
considered:

$\displaystyle{\mathcal{A}}$
$\displaystyle\coloneqq\left\\{(a,\gamma):a>\sup\operatorname{supp}({\mathcal{T}}(\overline{Y})),\,\gamma>s(a)\right\\},$

where $s(a)$ is defined in Equation 3.1.

######  Proposition A.4 (Equivalent definitions of $a^{*}$).

  * •

In the domain ${\mathcal{A}}$, the unique solution
$(a^{\circ},\gamma^{\circ})$ to Equation 9.4 is the same as the unique
solution to the following equations:

$\displaystyle\psi^{\prime}(a^{\circ})$
$\displaystyle=0,\quad\gamma^{\circ}=\gamma(a^{\circ}).$ (A.15)

  * •

Let $(a^{*},\gamma^{*})$ be the solution in ${\mathcal{A}}$ to

$\displaystyle\zeta(a^{*})$
$\displaystyle=\varphi(a^{*}),\quad\gamma^{*}=\gamma(a^{*}),$ (A.16)

such that $a^{*}$ is the largest among all solutions. If $a^{*}>a^{\circ}$,
then $(a^{*},\gamma^{*})$ is also a solution to Equation 5.10.

###### Proof.

##### Equivalence between Equations A.15 and 9.4.

We will argue that $\psi^{\prime}(a)=0$ if and only if Equation 9.4 holds. The
derivative of $\psi^{\prime}$ is computed below:

$\displaystyle\psi^{\prime}(a)$
$\displaystyle=\gamma(a)+a\gamma^{\prime}(a)=\gamma(a)-a\cdot\frac{\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{(a-{\mathcal{T}}(\overline{Y}))^{2}}\right]\mathbb{E}\left[\frac{\overline{\Sigma}^{2}}{\left(\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}\right)^{2}}\right]}{\mathbb{E}\left[\frac{\overline{\Sigma}}{\left(\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}\right)^{2}}\right]},$
(A.17)

where the formula for $\gamma^{\prime}$ has been derived in Equation A.10.
Using the above expression and rearranging terms, we can write the equation
$\psi^{\prime}(a)=0$ as

$\displaystyle\mathbb{E}\left[\frac{\gamma(a)\overline{\Sigma}}{\left(\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}\right)^{2}}\right]$
$\displaystyle=\mathbb{E}\left[\frac{a{\mathcal{T}}(\overline{Y})}{(a-{\mathcal{T}}(\overline{Y}))^{2}}\right]\mathbb{E}\left[\frac{\overline{\Sigma}^{2}}{\left(\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}\right)^{2}}\right].$
(A.18)

We rewrite the first two terms in the above equation in the following way:

$\displaystyle\begin{split}\mathbb{E}\left[\frac{\gamma(a)\overline{\Sigma}}{\left(\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}\right)^{2}}\right]&=\mathbb{E}\left[\frac{\overline{\Sigma}}{\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}}\right]\\\
&\phantom{=}~{}+\mathbb{E}\left[\frac{\overline{\Sigma}^{2}}{\left(\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}\right)^{2}}\right]\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right],\\\
\mathbb{E}\left[\frac{a{\mathcal{T}}(\overline{Y})}{(a-{\mathcal{T}}(\overline{Y}))^{2}}\right]&=\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]+\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})^{2}}{(a-{\mathcal{T}}(\overline{Y}))^{2}}\right].\end{split}$
(A.19)

Using the right-hand sides above in place of the left-hand sides in Equation
A.18, we see that the term
$\mathbb{E}\left[\frac{\overline{\Sigma}^{2}}{\left(\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}\right)^{2}}\right]\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]$
cancels on both sides and Equation A.18 becomes

$\displaystyle\mathbb{E}\left[\frac{\overline{\Sigma}}{\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}}\right]$
$\displaystyle=\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})^{2}}{(a-{\mathcal{T}}(\overline{Y}))^{2}}\right]\mathbb{E}\left[\frac{\overline{\Sigma}^{2}}{\left(\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}\right)^{2}}\right].$

The left-hand side equals $\delta$ since $\gamma(a)$ satisfies Equation 3.3.
Therefore the above equation matches Equation 9.4.

##### Proof of Equation 5.10.

Assuming that Equation A.16 holds, we verify Equation 5.10. For any
$a>a^{\circ}$, $\zeta(a)=\psi(a)$, hence Equation A.16 can be written as

$\displaystyle\frac{1}{\mathbb{E}\left[\overline{\Sigma}\right]}\mathbb{E}\left[\frac{\overline{G}^{2}{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\mathbb{E}\left[\frac{\overline{\Sigma}^{2}}{\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}}\right]$
$\displaystyle=\gamma(a),$

or equivalently,

$\displaystyle\frac{1}{\mathbb{E}\left[\overline{\Sigma}\right]}\mathbb{E}\left[\frac{\delta}{\mathbb{E}\left[\overline{\Sigma}\right]}\overline{G}^{2}\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\mathbb{E}\left[\frac{\overline{\Sigma}^{2}}{\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}}\right]$
$\displaystyle=\frac{\delta\gamma(a)}{\mathbb{E}\left[\overline{\Sigma}\right]}.$

To show that the above equation is the same as Equation 5.10, it suffices to
verify

$\displaystyle\frac{\delta\gamma(a)}{\mathbb{E}\left[\overline{\Sigma}\right]}$
$\displaystyle=\frac{1}{\mathbb{E}\left[\overline{\Sigma}\right]}\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\mathbb{E}\left[\frac{\overline{\Sigma}^{2}}{\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}}\right]+1.$
(A.20)

We rewrite the first term on the right-hand side as

$\displaystyle\phantom{=}~{}\frac{1}{\mathbb{E}\left[\overline{\Sigma}\right]}\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\mathbb{E}\left[\frac{\overline{\Sigma}^{2}}{\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}}\right]$
$\displaystyle=\frac{1}{\mathbb{E}\left[\overline{\Sigma}\right]}\frac{1}{\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]}\left(\mathbb{E}\left[\frac{\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]^{2}\overline{\Sigma}^{2}-\gamma(a)\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}}{\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}}\right]+\mathbb{E}\left[\frac{\gamma(a)\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}}{\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}}\right]\right)$
$\displaystyle=\frac{1}{\mathbb{E}\left[\overline{\Sigma}\right]}\frac{1}{\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]}\left(-\mathbb{E}\left[\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}\right]+\gamma(a)\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\mathbb{E}\left[\frac{\overline{\Sigma}}{\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}}\right]\right)$
$\displaystyle=\frac{1}{\mathbb{E}\left[\overline{\Sigma}\right]}\left(\gamma(a)\mathbb{E}\left[\frac{\overline{\Sigma}}{\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}}\right]-\mathbb{E}\left[\overline{\Sigma}\right]\right)$
$\displaystyle=\frac{\gamma(a)}{\mathbb{E}\left[\overline{\Sigma}\right]}\mathbb{E}\left[\frac{\overline{\Sigma}}{\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}}\right]-1.$

Noting that $\gamma(a)$ satisfies Equation 3.3, we further obtain

$\displaystyle\frac{1}{\mathbb{E}\left[\overline{\Sigma}\right]}\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\mathbb{E}\left[\frac{\overline{\Sigma}^{2}}{\gamma(a)-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}}\right]$
$\displaystyle=\frac{\delta\gamma(a)}{\mathbb{E}\left[\overline{\Sigma}\right]}-1.$

This then implies Equation A.20 and hence Equation 5.10. ∎

###  A.3 Alternative formulations of $a^{*}>a^{\circ}$

The following proposition is a direct consequence of the monotonicity
properties of $\psi,\varphi$ (see Proposition A.2).

######  Proposition A.5.

The following conditions are equivalent.

  1. 1.

$a^{*}>a^{\circ}$;

  2. 2.

$\zeta(a^{*})>\zeta(a^{\circ})$;

  3. 3.

$\psi^{\prime}(a^{*})>0$, or more explicitly

$\displaystyle 1$
$\displaystyle>\frac{1}{\delta}\mathbb{E}\left[\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]\mathbb{E}\left[\frac{\overline{\Sigma}^{2}}{\left(\gamma^{*}-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a^{*}-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}\right)^{2}}\right],$
(A.21)

i.e., $1>x_{2}$ by recalling the definition of $x_{2}$ in Equation 3.10;

  4. 4.

If the function
$\varphi\colon(\sup\operatorname{supp}({\mathcal{T}}(\overline{Y})),\infty)\to{\mathbb{R}}$
defined in Equation 3.2 is strictly decreasing, the above conditions are
further equivalent to $\psi(a^{\circ})<\varphi(a^{\circ})$, or more explicitly

$\displaystyle 1$
$\displaystyle<\frac{1}{\mathbb{E}\left[\overline{\Sigma}\right]}\mathbb{E}\left[\left(\frac{\delta}{\mathbb{E}\left[\overline{\Sigma}\right]}\overline{G}^{2}-1\right)\frac{{\mathcal{T}}(\overline{Y})}{a^{\circ}-{\mathcal{T}}(\overline{Y})}\right]\mathbb{E}\left[\frac{\overline{\Sigma}^{2}}{\gamma^{\circ}-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a^{\circ}-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}}\right].$
(A.22)

##  Appendix B Removing Items (A7) and (A8)

We would like to show that the conclusions of Theorem 3.1 remain valid even if
$\Sigma$ and/or ${\mathcal{T}}$ fail to satisfy Item (A7) and/or (A8). To do
so, we create $\widetilde{\Sigma},\widetilde{{\mathcal{T}}}$ that closely
approximate $\Sigma,{\mathcal{T}}$ and satisfy Items (A7) and (A8). Theorem
3.1 then applies to $\widetilde{\Sigma},\widetilde{{\mathcal{T}}}$ and it
remains to perform a perturbation analysis to show that the same
characterizations also hold for $\Sigma,{\mathcal{T}}$ once the perturbation
is sent to zero. The detailed proof is presented below where we assume that
both Items (A7) and (A8) are violated. The proof when only one of them holds
is analogous and is omitted.

We first construct $\widetilde{\Sigma}$. Note that if

$\displaystyle\mathbb{P}\left(\overline{\Sigma}=\inf\operatorname{supp}(\overline{\Sigma})\right)>0,\quad\mathbb{P}\left(\overline{\Sigma}=\sup\operatorname{supp}(\overline{\Sigma})\right)>0,$
(B.1)

then Item (A7) is automatically satisfied and one can take
$\widetilde{\Sigma}=\Sigma$. In what follows, we assume that both
probabilities in Equation B.1 are zero. (Again, the case where exactly one of
the probabilities is zero can be handled verbatim and the details are
omitted.) Write the eigendecomposition of $\Sigma$ as

$\displaystyle\Sigma$
$\displaystyle=\sum_{i=1}^{d}\lambda_{i}(\Sigma)v_{i}(\Sigma)v_{i}(\Sigma)^{\top}.$

By the convergence of the empirical spectral distribution of $\Sigma$ (see
Item (A3)), we have that for any sufficiently small $\varsigma>0$, there
exists $\xi>0$ (depending on $\varsigma$) such that for every sufficiently
large $d$,

$\displaystyle\frac{1}{d}\left|\left\\{i\in[d]:\lambda_{i}(\Sigma)\geq\left(\sqrt{\lambda_{1}(\Sigma)}-\xi\right)^{2}\right\\}\right|$
$\displaystyle\in[\varsigma/2,\varsigma],$
$\displaystyle\frac{1}{d}\left|\left\\{i\in[d]:\lambda_{i}(\Sigma)\leq\left(\sqrt{\lambda_{d}(\Sigma)}+\xi\right)^{2}\right\\}\right|$
$\displaystyle\in[\varsigma/2,\varsigma].$

Let $\widetilde{\Sigma}\in{\mathbb{R}}^{d\times d}$ be the matrix obtained by
truncating the spectrum of $\Sigma$:

$\displaystyle\widetilde{\Sigma}$
$\displaystyle=\sum_{i=1}^{d}\lambda_{i}(\widetilde{\Sigma})v_{i}(\Sigma)v_{i}(\Sigma)^{\top},$

where

$\displaystyle\lambda_{i}(\widetilde{\Sigma})$
$\displaystyle=\begin{cases}\left(\sqrt{\lambda_{1}(\Sigma)}-\xi\right)^{2},&\lambda_{i}(\Sigma)\geq\left(\sqrt{\lambda_{1}(\Sigma)}-\xi\right)^{2}\\\
\left(\sqrt{\lambda_{d}(\Sigma)}+\xi\right)^{2},&\lambda_{i}(\Sigma)\leq\left(\sqrt{\lambda_{d}(\Sigma)}+\xi\right)^{2}\\\
\lambda_{i}(\Sigma),&\mathrm{otherwise}\end{cases}.$

It is easy to check that $\widetilde{\Sigma}$ still satisfies Item (A3) if
$\Sigma$ does. Moreover, upon truncation, the limiting spectral distribution
of $\widetilde{\Sigma}$ has positive mass on both the left and right edges and
hence obviously satisfies Item (A7).

Let us then construct $\widetilde{{\mathcal{T}}}$. Clearly, if

$\displaystyle\mathbb{P}\left({\mathcal{T}}(\overline{Y})=\sup\operatorname{supp}({\mathcal{T}}(\overline{Y}))\right)$
$\displaystyle>0,$ (B.2)

then Equation 2.9 is satisfied. We therefore assume that the above equation
holds with equality. In this case, we truncate ${\mathcal{T}}$ slightly below
its supremum to create $\widetilde{{\mathcal{T}}}$ which satisfies Equation
2.9. Specifically, for any $\varsigma>0$, there exists $\xi>0$ (depending on
$\varsigma$) such that

$\displaystyle\mathbb{P}\left({\mathcal{T}}(\overline{Y})\in[\sup\operatorname{supp}({\mathcal{T}}(\overline{Y}))-\xi,\sup\operatorname{supp}({\mathcal{T}}(\overline{Y}))]\right)$
$\displaystyle\in[\varsigma/2,\varsigma].$

Define $\widetilde{{\mathcal{T}}}$ as

$\displaystyle\widetilde{{\mathcal{T}}}(y)$
$\displaystyle\coloneqq\min\left\\{{\mathcal{T}}(y),\sup\operatorname{supp}({\mathcal{T}}(\overline{Y}))-\xi\right\\}.$
(B.3)

Note that $\widetilde{{\mathcal{T}}}$ depends on $\varsigma$. Also, it
satisfies Equation B.2 and therefore Equation 2.9. It is easy to see that Item
(A6) will not be violated after the truncation.

Now the conclusions of Theorem 3.1 hold for
$\widetilde{\Sigma},\widetilde{{\mathcal{T}}}$. In particular,
$\widetilde{a}^{*},\widetilde{a}^{\circ}$ can be defined using Equations 3.4
and 3.6 but with $\widetilde{{\mathcal{T}}}$ and the limiting spectral
distribution of $\widetilde{\Sigma}$. It then suffices to show that as long as
$\widetilde{a}^{*}>\widetilde{a}^{\circ}$, the difference between the spectral
statistics under $\Sigma,{\mathcal{T}}$ and those under
$\widetilde{\Sigma},\widetilde{{\mathcal{T}}}$ is vanishing as $\varsigma\to
0$. Let

$\displaystyle
D\coloneqq\Sigma^{1/2}\widetilde{A}^{\top}T\widetilde{A}\Sigma^{1/2},\quad\widetilde{D}\coloneqq\widetilde{\Sigma}^{1/2}\widetilde{A}^{\top}\widetilde{T}\widetilde{A}\widetilde{\Sigma}^{1/2},$

where

$\displaystyle T$
$\displaystyle\coloneqq\mathrm{diag}({\mathcal{T}}(y)),\quad\widetilde{T}\coloneqq\mathrm{diag}(\widetilde{{\mathcal{T}}}(y)).$

Then

$\displaystyle\left\|D-\widetilde{D}\right\|_{2}$
$\displaystyle=\left\|\Sigma^{1/2}\widetilde{A}^{\top}T\widetilde{A}\Sigma^{1/2}-\widetilde{\Sigma}^{1/2}\widetilde{A}^{\top}\widetilde{T}\widetilde{A}\widetilde{\Sigma}^{1/2}\right\|_{2}$
$\displaystyle\leq\left\|\Sigma^{1/2}\widetilde{A}^{\top}T\widetilde{A}\Sigma^{1/2}-\widetilde{\Sigma}^{1/2}\widetilde{A}^{\top}T\widetilde{A}\Sigma^{1/2}\right\|_{2}+\left\|\widetilde{\Sigma}^{1/2}\widetilde{A}^{\top}T\widetilde{A}\Sigma^{1/2}-\widetilde{\Sigma}^{1/2}\widetilde{A}^{\top}\widetilde{T}\widetilde{A}\Sigma^{1/2}\right\|_{2}$
$\displaystyle\phantom{=}~{}+\left\|\widetilde{\Sigma}^{1/2}\widetilde{A}^{\top}\widetilde{T}\widetilde{A}\Sigma^{1/2}-\widetilde{\Sigma}^{1/2}\widetilde{A}^{\top}\widetilde{T}\widetilde{A}\widetilde{\Sigma}^{1/2}\right\|_{2}$
$\displaystyle\leq\left\|\Sigma^{1/2}-\widetilde{\Sigma}^{1/2}\right\|_{2}\left\|\widetilde{A}\right\|_{2}^{2}\left\|T\right\|_{2}\left\|\Sigma^{1/2}\right\|_{2}+\left\|\widetilde{\Sigma}^{1/2}\right\|_{2}\left\|\widetilde{A}\right\|_{2}^{2}\left\|T-\widetilde{T}\right\|_{2}\left\|\Sigma^{1/2}\right\|_{2}$
$\displaystyle\phantom{=}~{}+\left\|\widetilde{\Sigma}^{1/2}\right\|_{2}\left\|\widetilde{A}\right\|_{2}^{2}\left\|\widetilde{T}\right\|_{2}\left\|\Sigma^{1/2}-\widetilde{\Sigma}^{1/2}\right\|_{2}$
$\displaystyle\leq
2\left\|\Sigma^{1/2}-\widetilde{\Sigma}^{1/2}\right\|_{2}\left\|\widetilde{A}\right\|_{2}^{2}\left\|T\right\|_{2}\left\|\Sigma^{1/2}\right\|_{2}+\left\|\Sigma^{1/2}\right\|_{2}^{2}\left\|\widetilde{A}\right\|_{2}^{2}\left\|T-\widetilde{T}\right\|_{2}$
$\displaystyle\leq
2\xi\left(1+1/\sqrt{\delta}+0.01\right)^{2}\left(\sup\operatorname{supp}({\mathcal{T}}(\overline{Y}))+0.01\right)\left(\operatorname{supp}(\overline{\Sigma})+0.01\right)$
$\displaystyle\phantom{=}~{}+\left(\operatorname{supp}(\overline{\Sigma})+0.01\right)\left(1+1/\sqrt{\delta}+0.01\right)^{2}\xi$
$\displaystyle\leq c_{1}\xi,$ (B.4)

where the bound on the penultimate line holds almost surely for every
sufficiently large $d$, and $c_{1}>0$ in the last line is a constant
independent of $d$. The $+0.01$ terms are to exclude deviations for small $d$.
Furthermore, if $\widetilde{a}^{*}>\widetilde{a}^{\circ}$, Theorem 3.1
guarantees that there exists a constant $c_{2}>0$ such that for every
sufficiently large $d$, with probability $1$,

$\displaystyle\lambda_{1}(\widetilde{D})-\lambda_{2}(\widetilde{D})\geq
c_{2}.$ (B.5)

Using Equations B.4 and B.5 in the Davis–Kahan theorem (Proposition G.6), we
obtain

$\displaystyle\min\left\\{\left\|v_{1}(D)-v_{1}(\widetilde{D})\right\|_{2},\left\|v_{1}(D)+v_{1}(\widetilde{D})\right\|_{2}\right\\}$
$\displaystyle\leq\frac{4\left\|D-\widetilde{D}\right\|_{2}}{\lambda_{1}(D)-\lambda_{2}(D)}\leq
4c_{1}\xi/c_{2},$

which implies

$\displaystyle\left|\left|\left\langle
v_{1}(D),\frac{x^{*}}{\sqrt{d}}\right\rangle\right|-\left|\left\langle
v_{1}(\widetilde{D}),\frac{x^{*}}{\sqrt{d}}\right\rangle\right|\right|$
$\displaystyle=\min_{\sigma\in\\{-1,1\\}}\left|\left\langle v_{1}(D)-\sigma
v_{1}(\widetilde{D}),\frac{x^{*}}{\sqrt{d}}\right\rangle\right|$
$\displaystyle\leq\min_{\sigma\in\\{-1,1\\}}\left\|v_{1}(D)-v_{1}(\widetilde{D})\right\|_{2}\leq
4c_{1}\xi/c_{2}.$ (B.6)

By Theorem 3.1, the condition $\widetilde{a}^{*}>\widetilde{a}^{\circ}$ also
implies that the overlap between $v_{1}(\widetilde{D})$ and $x^{*}$ converges
in probability to $\eta>0$. Since $\varsigma>0$ (and therefore $\xi$) can be
made arbitrarily small, Equation B.6 then allows us to conclude that the
overlap between $v_{1}(D)$ and $x^{*}$ also converges to $\eta$. This proves
Equation 3.12 for $D$.

Using Equation B.4 and Weyl’s inequality, we have for any $i\in[d]$,

$\displaystyle\left|\lambda_{i}(D)-\lambda_{i}(\widetilde{D})\right|$
$\displaystyle\leq\left\|D-\widetilde{D}\right\|_{2}\leq c_{1}\xi,$

which in particular establishes Equation 3.11 for $D$. The whole proof is then
completed.

##  Appendix C Characterization of the right edge of the bulk: proof of Lemma
9.2

Recall from Equation 9.1 the definition of $\widehat{D}\in\mathbb{R}^{d\times
d}$:

$\widehat{D}=\Sigma^{1/2}\widehat{A}^{\top}T\widehat{A}\Sigma^{1/2}.$

We already know that both $\lambda_{1}(\widehat{D})$ and
$\lambda_{3}(\widehat{D})$ converge to the upper edge
$\lambda^{\circ}=\sup\operatorname{supp}\overline{\mu}_{\widehat{D}}$ of the
limiting spectrum (see Lemmas 9.5 and 9.6). The main goal of this section is
to prove the characterization of the upper edge $\lambda^{\circ}$ in Lemma
9.2. We deduce Lemma 9.2 from the following lemma. We present the proofs of
Lemmas 9.2 and C.1 at the end of this section.

######  Lemma C.1.

Let $a\in(\sup\operatorname{supp}\overline{\mu}_{T},\infty)$. Then, the
following holds:

  1. 1.

If $\psi(\widetilde{a})>\lambda^{\circ}$ for all $\widetilde{a}\geq a$, then
$\psi^{\prime}(a)>0$;

  2. 2.

If $\psi^{\prime}(a)>0$, then
$\psi(a)\notin\operatorname{supp}\overline{\mu}_{\widehat{D}}$.

We will shortly see in Lemma C.3 that $a^{\circ}$ is indeed well-defined. More
precisely, $\psi$ is an analytic function with at least one critical point,
and $\psi^{\prime}(a)$ converges to a positive number as $a\to\infty$.

###  C.1 Properties of $\psi$

Recall that the function
$\psi:(\sup\operatorname{supp}\overline{\mu}_{T},\infty)\to\mathbb{R}$ is
defined by $\psi(a)=a\gamma(a)$. With a slight modification to the definition
of $\gamma(a)$, we have the following result.

######  Lemma C.2.

  1. 1.

The sets ${\mathcal{S}},{\mathcal{S}}^{\prime}\subset\mathbb{R}$ defined by

$\displaystyle{\mathcal{S}}$
$\displaystyle\coloneqq\left\\{a>\sup\operatorname{supp}\overline{\mu}_{T}:\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{{\mathcal{T}}(\overline{Y})-a}\right]=0\right\\},$
$\displaystyle{\mathcal{S}}^{\prime}$
$\displaystyle\coloneqq\left\\{a>\sup\operatorname{supp}\overline{\mu}_{T}:\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{{\mathcal{T}}(\overline{Y})-a}\right]=\frac{1}{\delta}\right\\}$

are finite.

  2. 2.

For each
$a\in(\sup\operatorname{supp}\overline{\mu}_{T},\infty)\setminus{\mathcal{S}}$,
there exists a unique
$\omega\equiv\omega(a)\in\mathbb{R}\setminus(\inf\operatorname{supp}\overline{\mu}_{\Sigma},\sup\operatorname{supp}\overline{\mu}_{\Sigma})$
such that

$\delta\int_{\mathbb{R}}\frac{t}{t-a}\mathrm{d}\overline{\mu}_{T}(t)=\int_{\mathbb{R}}\frac{s}{s-\omega}\mathrm{d}\overline{\mu}_{\Sigma}(s).$
(C.1)

  3. 3.

The map
$\omega:(\sup\operatorname{supp}\overline{\mu}_{T},\infty)\setminus{\mathcal{S}}\to\mathbb{R}$
defined in Item 2 extends meromorphically to an open set in $\mathbb{C}$
containing $(\sup\operatorname{supp}\overline{\mu}_{T},\infty)$. The extension
is analytic at each
$a\in(\sup\operatorname{supp}\overline{\mu}_{T},\infty)\setminus{\mathcal{S}}$,
has a pole at each $a\in{\mathcal{S}}$ and a zero at each
$a\in{\mathcal{S}}^{\prime}$.

  4. 4.

The function
$\psi:(\sup\operatorname{supp}\overline{\mu}_{T},\infty)\to\mathbb{R}$ defined
by $\psi(a)=a\gamma(a)$ satisfies

$\psi(a)=-\frac{a}{\delta}\int_{\mathbb{R}}\frac{s\omega(a)}{s-\omega(a)}\mathrm{d}\overline{\mu}_{\Sigma}(s),\qquad\forall
a\in(\sup\operatorname{supp}\overline{\mu}_{T},\infty)\setminus{\mathcal{S}}.$
(C.2)

Furthermore, $\psi$ extends analytically to an open set in $\mathbb{C}$
containing $(\sup\operatorname{supp}\overline{\mu}_{T},\infty)$, and has zeros
precisely at ${\mathcal{S}}^{\prime}$.

###### Proof.

Note that the function
$a\mapsto\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{{\mathcal{T}}(\overline{Y})-a}\right]$
is analytic in $(\sup\operatorname{supp}\overline{\mu}_{T},\infty)$, so both
${\mathcal{S}}$ and ${\mathcal{S}}^{\prime}$ cannot have accumulating points
in $(\sup\operatorname{supp}\overline{\mu}_{T},\infty)$. Thus, in order to
prove Item 1, it suffices to prove that ${\mathcal{S}},{\mathcal{S}}^{\prime}$
are contained in a compact subset of
$(\sup\operatorname{supp}\overline{\mu}_{T},\infty)$. By the assumptions on
${\mathcal{T}}$ (_(d)_ in Equation 2.9) we have

$\lim_{a\searrow\sup\operatorname{supp}\overline{\mu}_{T}}\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{{\mathcal{T}}(\overline{Y})-a}\right]=-\infty,$

hence ${\mathcal{S}}$ and ${\mathcal{S}}^{\prime}$ are contained in
$[x,\infty)$ for some $x>\sup\operatorname{supp}\overline{\mu}_{T}$. Also, we
have the series expansion

$\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{{\mathcal{T}}(\overline{Y})-a}\right]=-\frac{\mathbb{E}\left[{\mathcal{T}}(\overline{Y})\right]}{a}-\frac{\mathbb{E}\left[{\mathcal{T}}(\overline{Y})^{2}\right]}{a^{2}}+{\mathcal{O}}(a^{-3}),\qquad\text{as
}a\to\infty,$

where $\mathbb{E}\left[{\mathcal{T}}(\overline{Y})^{2}\right]>0$ by the
assumption in Equation 2.7. This already proves that ${\mathcal{S}}^{\prime}$
is bounded, as
$\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{{\mathcal{T}}(\overline{Y})-a}\right]$
converges to $0$ as $a\to\infty$. Similarly, the same expansion implies that
for large enough $x>\sup\operatorname{supp}\overline{\mu}_{T}$ we have

$\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{{\mathcal{T}}(\overline{Y})-a}\right]\in\begin{cases}(0,\infty),&\text{if
}\mathbb{E}\left[{\mathcal{T}}(\overline{Y})\right]<0,\\\
(-\infty,0),&\text{if }\mathbb{E}\left[{\mathcal{T}}(\overline{Y})\right]\geq
0,\end{cases}\qquad\forall a>x.$

Thus, ${\mathcal{S}}\cap[x,\infty)=\emptyset$. This concludes Item 1.

For Item 2, we only need to notice that the right-hand side of Equation C.1 is
a bijection between
$\mathbb{R}\setminus(\inf\operatorname{supp}\overline{\mu}_{\Sigma},\sup\operatorname{supp}\overline{\mu}_{\Sigma})$
and $\mathbb{R}\setminus\\{0\\}$. Notice further that the right-hand side is
analytic in $\omega$ with strictly positive derivative whenever $\omega$ is
well-defined;

$\frac{\mathrm{d}}{\mathrm{d}\omega}\int_{\mathbb{R}}\frac{s}{s-\omega}\mathrm{d}\overline{\mu}_{\Sigma}=\int_{\mathbb{R}}\frac{s}{(s-\omega)^{2}}\mathrm{d}\overline{\mu}_{\Sigma}.$

We now turn to Item 3. Since the left-hand side of Equation C.1 is an analytic
function of $a$, it immediately follows from analytic inverse function theorem
that $\omega$ extends analytically to a neighborhood of
$(\sup\operatorname{supp}\overline{\mu}_{T},\infty)\setminus{\mathcal{S}}$.
Similarly, for each $a>\sup\operatorname{supp}{\mathcal{T}}(\overline{Y})$
with $a\notin{\mathcal{S}}\cup{\mathcal{S}}^{\prime}$, we find that
$\widetilde{\omega}(a)\coloneqq 1/\omega(a)$ solves

$\delta\int_{\mathbb{R}}\frac{t}{t-a}\mathrm{d}\overline{\mu}_{T}(t)=-\widetilde{\omega}(a)\int_{\mathbb{R}}\frac{s}{1-s\widetilde{\omega}(a)}\mathrm{d}\overline{\mu}_{\Sigma}.$

Defining $\widetilde{\omega}(a)\equiv 0$ for $a\in{\mathcal{S}}$ and following
the same reasoning as for $\omega$, one easily finds that $\widetilde{\omega}$
extends analytically to a neighborhood of
$(\sup\operatorname{supp}\overline{\mu}_{T},\infty)\setminus{\mathcal{S}}^{\prime}$.
By analytic continuation, $\omega$ extends to a meromorphic function on a
neighborhood of $(\sup\operatorname{supp}\overline{\mu}_{T},\infty)$ with
poles at ${\mathcal{S}}$. From Equation C.1 we immediately find that the zeros
of $\omega$ are exactly at ${\mathcal{S}}^{\prime}$.

Finally, for Item 4, note that by a trivial rescaling we have

$-\omega(a)\int_{\mathbb{R}}\frac{t}{t-a}\mathrm{d}\overline{\mu}_{T}(t)=\gamma(a),$

which implies

$\psi(a)=-a\omega(a)\int_{\mathbb{R}}\frac{t}{t-a}\mathrm{d}\overline{\mu}_{T}(t),\qquad
a\notin{\mathcal{S}}.$ (C.3)

Using the definition of $\omega$, we immediately have Equation C.2 from
Equation C.3. Also, Equation C.3 already shows that $\psi$ is a meromorphic
function on a neighborhood of
$(\sup\operatorname{supp}\overline{\mu}_{T},\infty)$ by Item 2, with possible
poles at ${\mathcal{S}}$. Hence we only need to check that each
$a\in{\mathcal{S}}$ is a removable singularity for $\psi$. Recall that
$\omega(z)\to\infty$ as $z\to a\in{\mathcal{S}}$, so that by dominated
convergence

$\displaystyle\psi(z)$
$\displaystyle=-\frac{z}{\delta}\int_{\mathbb{R}}\frac{s\omega(z)}{s-\omega(z)}\mathrm{d}\overline{\mu}_{\Sigma}(s)=-\frac{z}{\delta}\int_{\mathbb{R}}\frac{s}{s/\omega(z)-1}\mathrm{d}\overline{\mu}_{\Sigma}(s)\to\frac{a}{\delta}\mathbb{E}\left[\overline{\Sigma}\right].\qed$

######  Lemma C.3.

We have

$\lim_{a\to\infty}\psi^{\prime}(a)=\frac{\mathbb{E}\left[\overline{\Sigma}\right]}{\delta}=\lim_{\operatorname{\mathrm{Re}}a\to\infty}\frac{\operatorname{\mathrm{Im}}\psi(a)}{\operatorname{\mathrm{Im}}a},$
(C.4)

where we identified $\psi$ with its analytic extension. We also have

$\lim_{a\to\infty}\psi(a)=\infty=\lim_{a\searrow\sup\operatorname{supp}\overline{\mu}_{T}}\psi(a).$
(C.5)

In particular, the set of critical points of $\psi$ is nonempty and bounded
from above (as a subset of ${\mathbb{R}}$).

###### Proof.

We compute the derivative of $\psi$ as

$\displaystyle\begin{split}\delta\psi^{\prime}(a)&=-\int_{\mathbb{R}}\frac{s\omega(a)}{s-\omega(a)}\mathrm{d}\overline{\mu}_{\Sigma}(s)-a\omega^{\prime}(a)\int_{\mathbb{R}}\frac{s^{2}}{(s-\omega(a))^{2}}\mathrm{d}\overline{\mu}_{\Sigma}(s)\\\
&=-\int_{\mathbb{R}}\frac{s\omega(a)}{s-\omega(a)}\mathrm{d}\overline{\mu}_{\Sigma}(s)\\\
&\phantom{=}~{}-a\delta\left(\int_{\mathbb{R}}\frac{s}{(s-\omega(a))^{2}}\mathrm{d}\overline{\mu}_{\Sigma}(s)\right)^{-1}\int_{\mathbb{R}}\frac{t}{(t-a)^{2}}\mathrm{d}\overline{\mu}_{T}(t)\int_{\mathbb{R}}\frac{s^{2}}{(s-\omega(a))^{2}}\mathrm{d}\overline{\mu}_{\Sigma}(s).\end{split}$
(C.6)

Furthermore, notice from Item 2 of Lemma C.2 that $|\omega(a)|\to\infty$ as
$a\to\infty$, so that the second term in Equation C.6 satisfies

$\displaystyle\lim_{a\to\infty}\left(\int_{\mathbb{R}}\frac{s\omega(a)^{2}}{(s-\omega(a))^{2}}\mathrm{d}\overline{\mu}_{\Sigma}(s)\right)^{-1}\int_{\mathbb{R}}\frac{s^{2}\omega(a)^{2}}{(s-\omega(a))^{2}}\mathrm{d}\overline{\mu}_{\Sigma}(s)\cdot\int_{\mathbb{R}}\frac{ta}{(t-a)^{2}}\mathrm{d}\overline{\mu}_{T}(t)$
$\displaystyle=\frac{\mathbb{E}\left[\overline{\Sigma}^{2}\right]}{\mathbb{E}\left[\overline{\Sigma}\right]}\lim_{a\to\infty}\int_{\mathbb{R}}\frac{ta}{(t-a)^{2}}\mathrm{d}\overline{\mu}_{T}(t)=0.$

Therefore, we conclude that the first equality in Equation C.4 holds as

$\lim_{a\to\infty}\psi^{\prime}(a)=\frac{1}{\delta}\lim_{a\to\infty}\int_{\mathbb{R}}\frac{-s\omega(a)}{s-\omega(a)}\mathrm{d}\overline{\mu}_{\Sigma}(s)=\frac{1}{\delta}\mathbb{E}\left[\overline{\Sigma}\right].$

The second equality can be proved analogously, except that the following
identity replaces Equation C.6:

$\displaystyle\delta\frac{\operatorname{\mathrm{Im}}\psi(a)}{\operatorname{\mathrm{Im}}a}$
$\displaystyle=-\operatorname{\mathrm{Re}}\left[\int_{\mathbb{R}}\frac{s\omega(a)}{s-\omega(a)}\mathrm{d}\overline{\mu}_{\Sigma}(s)\right]$
$\displaystyle\phantom{=}~{}-\delta\operatorname{\mathrm{Re}}[a]\left(\int_{\mathbb{R}}\frac{s}{|s-\omega(a)|^{2}}\mathrm{d}\overline{\mu}_{\Sigma}(s)\right)^{-1}\int_{\mathbb{R}}\frac{t}{|t-a|^{2}}\mathrm{d}\overline{\mu}_{T}(t)\int_{\mathbb{R}}\frac{s^{2}}{|s-\omega(a)|^{2}}\mathrm{d}\overline{\mu}_{\Sigma}(s),$

where we used

$\frac{\operatorname{\mathrm{Im}}\omega(a)}{\operatorname{\mathrm{Im}}a}=\delta\left(\int_{\mathbb{R}}\frac{s}{|s-\omega(a)|^{2}}\mathrm{d}\overline{\mu}_{\Sigma}(s)\right)^{-1}\int_{\mathbb{R}}\frac{t}{|t-a|^{2}}\mathrm{d}\overline{\mu}_{T}(t),$

from Equation C.1.

Notice that the first equality in Equation C.5 follows from the first equality
in Equation C.4. For the second equality in Equation C.5, recall from the
assumption _(d)_ in Equation 2.9 that

$\lim_{a\searrow\sup\operatorname{supp}\overline{\mu}_{T}}\int_{\mathbb{R}}\frac{t}{t-a}\mathrm{d}\overline{\mu}_{T}(t)=-\infty,$

which implies
$\lim_{a\searrow\sup\operatorname{supp}\overline{\mu}_{T}}\omega(a)=\sup\operatorname{supp}\overline{\mu}_{\Sigma}$
via Item 2 of Lemma C.2. Plugging these in the definition of $\psi$ in
Equation C.2 and using $\sup\operatorname{supp}\overline{\mu}_{T}>0$ prove
$\psi(a)\to\infty$. ∎

###  C.2 Complex analytic characterization of $\overline{\mu}_{\widehat{D}}$

######  Lemma C.4 ([Zha07, Theorem 1.2.1]).

Let $m_{\overline{\mu}_{\widehat{D}}}$ denote the Stieltjes transform of the
limiting eigenvalue distribution $\overline{\mu}_{\widehat{D}}$. For each
$z\in{\mathbb{H}}\coloneqq\left\\{z\in{\mathbb{C}}:\operatorname{\mathrm{Im}}(z)>0\right\\}$,
$m=m_{\overline{\mu}_{\widehat{D}}}(z)$ is characterized as the unique
solution $(m,m_{1},m_{2})$ of the following system of equations:

$\begin{cases}\displaystyle-
zm=(1-\delta)+\delta\int_{\mathbb{R}}\frac{1}{1+m_{1}t}\mathrm{d}\overline{\mu}_{T}(t),\\\
\displaystyle-
zm=\int_{\mathbb{R}}\frac{1}{1+m_{2}s}\mathrm{d}\overline{\mu}_{\Sigma}(s),\\\
\displaystyle-zm=1+\delta zm_{1}m_{2},\end{cases}$ (C.7)

subject to the constraint $m,m_{1},zm_{2}\in{\mathbb{H}}$. All of
$m,m_{1},m_{2}$ are analytic in ${\mathbb{H}}$ as a function of $z$.

We adopt the notation $m(\overline{z})=\overline{m}(z)$ and
$m_{i}(\overline{z})=\overline{m_{i}(z)}$ ($i\in\\{1,2\\}$). The major
difference from the case of positive ${\mathcal{T}}$ is that $m_{2}$ might not
be in ${\mathbb{H}}$; still the second equation in Equation C.7 is well-
defined as
$m_{2}(z)\in\\{z^{-1}w:w\in{\mathbb{H}}\\}\subset\mathbb{C}\setminus(-\infty,0]$.
(Cf., when ${\mathcal{T}}$ is positive then $m_{i}\in{\mathbb{H}}$ and
$zm_{i}\in{\mathbb{H}}$ for both $i\in\\{1,2\\}$.) Alternatively, using the
last equation in Equation C.7 to substitute $m$ in the first two equations, we
may write the system of two equations for $m_{1},m_{2}$:

$\begin{cases}\displaystyle-
zm_{1}=\frac{1}{\delta}\int_{\mathbb{R}}\frac{s}{1+m_{2}s}\mathrm{d}\overline{\mu}_{\Sigma}(s),\\\
\displaystyle-
zm_{2}=\int_{\mathbb{R}}\frac{t}{1+m_{1}t}\mathrm{d}\overline{\mu}_{T}(t).\end{cases}$
(C.8)

For later purposes, we define for all $z,w\in{\mathbb{C}}\setminus\mathbb{R}$,

$\displaystyle I_{1}(z,w)$
$\displaystyle\coloneqq\int_{\mathbb{R}}\frac{t^{2}}{(1+m_{1}(z)t)(1+m_{1}(w)t)}\mathrm{d}\overline{\mu}_{T}(t),$
(C.9) $\displaystyle I_{2}(z,w)$
$\displaystyle\coloneqq\int_{\mathbb{R}}\frac{s^{2}}{(1+m_{2}(z)s)(1+m_{2}(w)s)}\mathrm{d}\overline{\mu}_{\Sigma}(s),$

so that $I_{1}(z,\overline{z})$ and $I_{2}(z,\overline{z})$ are positive since
$m_{i}(\overline{z})=\overline{m_{i}(z)}$. Note also that

$\displaystyle|zm_{1}(z)|\leq\delta^{-1}I_{2}(z,\overline{z})^{1/2},\qquad|zm_{2}(z)|\leq
I_{1}(z,\overline{z})^{1/2},$ (C.10)

by Cauchy–Schwarz.

######  Lemma C.5.

For all $z\in{\mathbb{H}}$,

$\frac{1}{\delta|z|^{2}}I_{1}(z,\overline{z})I_{2}(z,\overline{z})<1.$ (C.11)

Consequently,

$\displaystyle|m_{1}(z)|^{2}I_{1}(z,\overline{z})<\frac{1}{\delta},\qquad|m_{2}(z)|^{2}I_{2}(z,\overline{z})<\delta.$
(C.12)

###### Proof.

Dividing the first line of Equation C.8 by $z$ and then taking imaginary
parts, we get

$\operatorname{\mathrm{Im}}m_{1}(z)=\frac{1}{\delta}\operatorname{\mathrm{Im}}\int_{\mathbb{R}}\frac{s}{-z(1+m_{2}(z)s)}\mathrm{d}\overline{\mu}_{\Sigma}(s)=\frac{1}{\delta}\int_{\mathbb{R}}\frac{s\operatorname{\mathrm{Im}}z+s^{2}\operatorname{\mathrm{Im}}zm_{2}(z)}{|z|^{2}|1+m_{2}(z)s|^{2}}\mathrm{d}\overline{\mu}_{\Sigma}(t).$
(C.13)

Similarly taking the imaginary part of the second line of Equation C.8 gives

$\operatorname{\mathrm{Im}}zm_{2}(z)=-\operatorname{\mathrm{Im}}\int_{\mathbb{R}}\frac{t}{1+m_{1}(z)t}\mathrm{d}\overline{\mu}_{T}(t)=\int_{\mathbb{R}}\frac{t^{2}\operatorname{\mathrm{Im}}m_{1}(z)}{|1+m_{1}(z)t|^{2}}\mathrm{d}\overline{\mu}_{T}(t).$
(C.14)

Combining Equations C.13 and C.14, we obtain

$\displaystyle\begin{split}\delta\operatorname{\mathrm{Im}}m_{1}(z)&=\int_{\mathbb{R}}\frac{s\operatorname{\mathrm{Im}}z}{|z|^{2}|1+m_{2}(z)s|^{2}}\mathrm{d}\overline{\mu}_{\Sigma}(s)\\\
&\phantom{=}~{}+\frac{\operatorname{\mathrm{Im}}m_{1}(z)}{|z|^{2}}\left(\int_{\mathbb{R}}\frac{t^{2}}{|1+m_{1}(z)t|^{2}}\mathrm{d}\overline{\mu}_{T}(t)\right)\left(\int_{\mathbb{R}}\frac{s^{2}}{|1+m_{2}(z)s|^{2}}\mathrm{d}\overline{\mu}_{\Sigma}(s)\right).\end{split}$
(C.15)

Since $\operatorname{\mathrm{Im}}m_{1}(z)$ and the first term on the right-
hand side of Equation C.15 are positive for all $z\in{\mathbb{H}}$, we have
proved Equation C.11:

$\frac{1}{\delta|z|^{2}}\left(\int_{\mathbb{R}}\frac{t^{2}}{|1+m_{1}(z)t|^{2}}\mathrm{d}\overline{\mu}_{T}(t)\right)\left(\int_{\mathbb{R}}\frac{s^{2}}{|1+m_{2}(z)s|^{2}}\mathrm{d}\overline{\mu}_{\Sigma}(s)\right)<1,\qquad\forall
z\in{\mathbb{H}}.$

For Equation C.12, we only need to notice from Equations C.11 and C.10 that

$|m_{1}|^{2}I_{1}(z,\overline{z})\leq\frac{1}{\delta^{2}|z|^{2}}I_{1}(z,\overline{z})I_{2}(z,\overline{z})<\frac{1}{\delta},$

and the second line in Equation C.12 follows similarly. ∎

Note also that Equation C.11 implies for all $z\in{\mathbb{H}}$ that

$\displaystyle|zm(z)+1|\leq\frac{\delta}{|z|}|zm_{1}(z)||zm_{2}(z)|$
$\displaystyle\leq\frac{1}{|z|}\sqrt{I_{1}(z,\overline{z})I_{2}(z,\overline{z})}\leq\sqrt{\delta},$
(C.16)

where we used the third line of Equation C.7 in the first, Equation C.10 in
the second, and Equation C.11 in the last inequality.

######  Lemma C.6.

Let ${\mathcal{D}}\subset{\mathbb{H}}$ be bounded. Then, there exists a
constant $K>0$ depending only on ${\mathcal{D}}$, $\overline{\mu}_{\Sigma}$,
and $\overline{\mu}_{T}$ such that

$|zm_{1}(z)|\leq K,\qquad|zm_{2}(z)|\leq K,\qquad\forall z\in{\mathcal{D}}.$

###### Proof.

We only consider $|zm_{1}(z)|$, and the same argument applies to
$|zm_{2}(z)|$. The proof is by contradiction. Suppose that there exists a
sequence $z_{k}$ in ${\mathcal{D}}$ such that $|z_{k}m_{1}(z_{k})|\to\infty$.
Then by combining Equation C.16 with the third equation in Equation C.7, we
have $|m_{2}(z_{k})|\to 0$. Therefore by dominated convergence (together with
$\sup\operatorname{supp}\overline{\mu}_{\Sigma}<\infty)$ we have

$-\delta\lim_{k\to\infty}z_{k}m_{1}(z_{k})=\lim_{k\to\infty}\int_{\mathbb{R}}\frac{s}{1+m_{2}(z_{k})s}\mathrm{d}\overline{\mu}_{\Sigma}(s)=\int_{\mathbb{R}}s\mathrm{d}\overline{\mu}_{\Sigma}(s)\in\mathbb{R},$

which gives a contradiction to $|z_{k}m_{1}(z_{k})|\to\infty$. ∎

######  Lemma C.7.

For all $z\in{\mathbb{H}}$, we have

$0<(\inf\operatorname{supp}\overline{\mu}_{\Sigma})\leq\delta\frac{\operatorname{\mathrm{Im}}m_{1}(z)}{\operatorname{\mathrm{Im}}m(z)}\leq(\sup\operatorname{supp}\overline{\mu}_{\Sigma}).$
(C.17)

For each bounded ${\mathcal{D}}\subset{\mathbb{H}}$, there exists a constant
$K_{1}$ depending only on ${\mathcal{D}},\overline{\mu}_{\Sigma}$, and
$\overline{\mu}_{T}$ such that

$\operatorname{\mathrm{Im}}(zm_{2}(z))\leq
K_{1}\operatorname{\mathrm{Im}}m_{1}(z),\qquad z\in{\mathcal{D}}.$ (C.18)

###### Proof.

To see Equation C.17, note that the second line of Equation C.7 implies

$\operatorname{\mathrm{Im}}m(z)=\int_{\mathbb{R}}\operatorname{\mathrm{Im}}\left[\frac{1}{-z(1+m_{2}(z)s)}\right]\mathrm{d}\overline{\mu}_{\Sigma}(s).$
(C.19)

Comparing Equation C.19 with Equation C.13 proves Equation C.17.

For Equation C.18, we recall from Equations C.14 and C.11 that

$\operatorname{\mathrm{Im}}zm_{2}(z)=\operatorname{\mathrm{Im}}m_{1}(z)\cdot
I_{1}(z,\overline{z})\leq\operatorname{\mathrm{Im}}m_{1}(z)\cdot\frac{\delta|z|^{2}}{I_{2}(z,\overline{z})}.$

By definition of $I_{2}(z,\overline{z})$, we have

$\displaystyle\frac{|z|^{2}}{I_{2}(z,\overline{z})}$
$\displaystyle=\left(\int_{\mathbb{R}}\frac{s^{2}}{|z+zm_{2}(z)s|^{2}}\mathrm{d}\overline{\mu}_{\Sigma}(s)\right)^{-1}$
$\displaystyle\leq
2\left(\left[(\sup\operatorname{supp}\overline{\mu}_{\Sigma})\cdot|zm_{2}(z)|\right]^{2}+|z|^{2}\right)\left(\int_{\mathbb{R}}s^{2}\mathrm{d}\overline{\mu}_{\Sigma}(s)\right)^{-1}.$
(C.20)

Since ${\mathcal{D}}$ is bounded, the right-hand side of Equation C.20 is
bounded by a constant for all $z\in{\mathcal{D}}$. This proves Equation C.18.
∎

######  Proposition C.8.

  1. 1.

There exist two finite measures $\nu_{1},\nu_{2}$ on $\mathbb{R}$ such that
the following holds; for all $z\in{\mathbb{H}}$ we have

$\displaystyle\int_{\mathbb{R}}\frac{1}{x-z}\mathrm{d}\nu_{1}(x)$
$\displaystyle=m_{1}(z),$ $\displaystyle\nu_{1}(\mathbb{R})$
$\displaystyle=\frac{\mathbb{E}\left[\overline{\Sigma}\right]}{\delta},$
(C.21) $\displaystyle\int_{\mathbb{R}}\frac{1}{x-z}\mathrm{d}\nu_{2}(x)$
$\displaystyle=zm_{2}(z)+\int_{\mathbb{R}}t\mathrm{d}\overline{\mu}_{T}(t),$
$\displaystyle\nu_{2}(\mathbb{R})$
$\displaystyle=\frac{\mathbb{E}\left[\overline{\Sigma}\right]}{\delta}\mathbb{E}\left[{\mathcal{T}}(\overline{Y})^{2}\right].$

Consequently we have

$\operatorname{supp}\nu_{1}=\operatorname{supp}\overline{\mu}_{\widehat{D}},\qquad\operatorname{supp}\nu_{2}\subset\operatorname{supp}\overline{\mu}_{\widehat{D}},$
(C.22)

so that $m_{1}$ and $m_{2}$ are respectively analytic and meromorphic
functions on
$\mathbb{R}\setminus\operatorname{supp}\overline{\mu}_{\widehat{D}}$.

  2. 2.

For all $x>\lambda^{\circ}$, we have

$\displaystyle-\frac{1}{m_{1}(x)}\in(\sup\operatorname{supp}\overline{\mu}_{T},\infty),\qquad-\frac{1}{m_{2}(x)}\in(\mathbb{R}\cup\\{\infty\\})\setminus(\inf\operatorname{supp}\overline{\mu}_{\Sigma},\sup\operatorname{supp}\overline{\mu}_{\Sigma}),$
(C.23) $\displaystyle\limsup_{z\to
x,z\in{\mathbb{H}}}\frac{1}{\delta|z|^{2}}I_{1}(z,\overline{z})I_{2}(z,\overline{z})<1,$

where we used the convention $1/0=\infty$ in the second assertion.

###### Proof.

We start with the proof of Item 1. First, notice that once Equation C.21 is
proved, Equation C.22 immediately follows from Lemma C.7 and Stieltjes
inversion. In order to prove the first identity in Equation C.21, since
$m_{1}$ is an analytic self-map of ${\mathbb{H}}$, by Nevanlinna–Pick
representation theorem it suffices to check

$\limsup_{\eta\to\infty}\eta|m_{1}(\mathrm{i}\eta)|<\infty.$ (C.24)

Suppose the contrary, so that there exists a sequence $\eta_{k}\to\infty$ with
$\eta_{k}|m_{1}(\mathrm{i}\eta_{k})|\to\infty$. Then by Equation C.16 we find
that $|m_{2}(\mathrm{i}\eta_{k})|\to 0$. On the other hand by Equation C.8, we
have

$-\mathrm{i}\eta
m_{1}(\mathrm{i}\eta)=\frac{1}{\delta}\int_{\mathbb{R}}\frac{s}{1+m_{2}(\mathrm{i}\eta)s}\mathrm{d}\overline{\mu}_{\Sigma}(s),$
(C.25)

so that the dominated convergence theorem (with
$\left\|\Sigma\right\|_{2}={\mathcal{O}}(1)$) leads to a contradiction as

$\lim_{k\to\infty}\eta_{k}|m_{1}(\mathrm{i}\eta_{k})|=\frac{1}{\delta}\lim_{k\to\infty}\left|\int_{\mathbb{R}}\frac{s}{1+m_{2}(\mathrm{i}\eta_{k})s}\mathrm{d}\overline{\mu}_{\Sigma}(s)\right|=\frac{1}{\delta}\int_{\mathbb{R}}s\mathrm{d}\overline{\mu}_{\Sigma}(s).$

Thus we have proved the first line of Equation C.21.

Next, we prove the corresponding representation for $zm_{2}(z)$, the second
line of Equation C.21. As before, it suffices to prove

$\limsup_{\eta\to\infty}\eta\left|\mathrm{i}\eta
m_{2}(\mathrm{i}\eta)+\int_{\mathbb{R}}t\mathrm{d}\overline{\mu}_{T}(t)\right|<\infty.$
(C.26)

To this end, we use Equation C.8 to write

$z\left(zm_{2}(z)+\int_{\mathbb{R}}t\mathrm{d}\overline{\mu}_{T}(t)\right)=zm_{1}(z)\int_{\mathbb{R}}\frac{t^{2}}{1+m_{1}(z)t}\mathrm{d}\overline{\mu}_{T}(t).$
(C.27)

Taking the limit along $z=\mathrm{i}\eta\to\mathrm{i}\infty$, by Equation C.21
we have $m_{1}(z)\to 0$ and $zm_{1}(z)\to-\nu_{1}(\mathbb{R})$ (note that
$\nu_{1}(\mathbb{R})$ is finite due to Equation C.24), so that

$\lim_{\eta\to\infty}\mathrm{i}\eta\left(\mathrm{i}\eta
m_{2}(\mathrm{i}\eta)+\int_{\mathbb{R}}t\mathrm{d}\overline{\mu}_{T}(t)\right)=-\nu_{1}(\mathbb{R})\int_{\mathbb{R}}t^{2}\mathrm{d}\overline{\mu}_{T}(t).$

Finally, given the two representations in Equation C.21, we have
$m_{1}(\mathrm{i}\eta),m_{2}(\mathrm{i}\eta)\to 0$ as $\eta\to\infty$. Then
$\nu_{1}(\mathbb{R})$ and $\nu_{2}(\mathbb{R})$ can be computed by taking the
limits of Equations C.25 and C.27 as $z=\mathrm{i}\eta\to\mathrm{i}\infty$.
This completes the proof of Item 1.

Now we prove Item 2. Notice that $m_{1}$ is analytic, negative-valued, and
increasing on $(\lambda^{\circ},\infty)$, and that
$\lim_{x\to\infty}m_{1}(x)=0$. Therefore the image of the half line
$(\lambda^{\circ},\infty)$ under $x\mapsto-1/m_{1}(x)$ is again an half-line
$(y_{0},\infty)$ for some $y_{0}>0$. Next, notice from Equation C.12 that for
all $x\in\mathbb{R}$,

$\limsup_{z\to
x,z\in{\mathbb{H}}}|m_{1}(z)|^{2}I_{1}(z,\overline{z})=\limsup_{z\to
x,z\in{\mathbb{H}}}\int_{\mathbb{R}}\frac{t^{2}}{|t-(-1/m_{1}(z))|^{2}}\mathrm{d}\overline{\mu}_{T}(t)<\frac{1}{\delta}.$
(C.28)

On the other hand, by the assumptions on ${\mathcal{T}}$ (see _(d)_ in
Equation 2.9) and Cauchy–Schwarz, there exists an $\varepsilon>0$ so that

$\lim_{w\to
y,w\in{\mathbb{H}}}\int_{\mathbb{R}}\frac{t^{2}}{|t-w|^{2}}\mathrm{d}\overline{\mu}_{T}(t)=\int_{\mathbb{R}}\frac{t^{2}}{|t-y|^{2}}\mathrm{d}\overline{\mu}_{T}(t)>\frac{1}{\delta},\quad\forall
y\in(\sup\operatorname{supp}\overline{\mu}_{T},\sup\operatorname{supp}\overline{\mu}_{T}+\varepsilon).$
(C.29)

Combining Equations C.28 and C.29, we conclude that $(y_{0},\infty)$ does not
intersect with
$(\sup\operatorname{supp}\overline{\mu}_{T},\allowbreak\sup\operatorname{supp}\overline{\mu}_{T}+\varepsilon)$,
so that $y_{0}\geq\sup\operatorname{supp}\overline{\mu}_{T}+\varepsilon$. This
proves the first assertion of Item 2.

The proof of the second assertion in Item 2 follows similar lines, except that
we view $x\mapsto-1/m_{2}(x)$ as an analytic (instead of meromorphic) function
mapping into the Riemann sphere $\mathbb{C}\cup\\{\infty\\}$. Consequently,
the closure of the image of $(\lambda^{\circ},\infty)$ under
$z\mapsto-1/m_{2}(z)$ is a connected real interval in the Riemann sphere; or
equivalently, it is the image of a closed connected arc in the unit circle
under stereographic projection. Next, notice from the assumptions on
$\overline{\Sigma}$ (see _(b)_ in Equation 2.8) that there exists an
$\varepsilon>0$ so that

$\lim_{w\to
y,w\in{\mathbb{H}}}\int_{\mathbb{R}}\frac{s^{2}}{|s-w|^{2}}\mathrm{d}\overline{\mu}_{\Sigma}(s)>\delta,\quad\forall
y\in(\inf\operatorname{supp}\overline{\mu}_{\Sigma}-\varepsilon,\inf\operatorname{supp}\overline{\mu}_{\Sigma})\cup(\sup\operatorname{supp}\overline{\mu}_{\Sigma},\sup\operatorname{supp}\overline{\mu}_{\Sigma}+\varepsilon).$

Therefore Equation C.12 implies that the image of $(\lambda^{\circ},\infty)$
under $x\mapsto-1/m_{2}(x)$ does not intersect with the two segments of length
$\varepsilon$, while containing $\infty$ in its closure since $m_{2}(x)\to 0$
as $x\to\infty$. This proves the second assertion of Item 2.

For the final assertion of Item 2, recall from Equation C.15 that for all
$z\in{\mathbb{H}}$,

$\displaystyle
1-\frac{1}{\delta|z|^{2}}I_{1}(z,\overline{z})I_{2}(z,\overline{z})$
$\displaystyle=\frac{\operatorname{\mathrm{Im}}z}{\delta\operatorname{\mathrm{Im}}m_{1}(z)}\int_{\mathbb{R}}\frac{s}{|z|^{2}|1+m_{2}(z)s|^{2}}\mathrm{d}\overline{\mu}_{\Sigma}(s)$
$\displaystyle=\left(\delta\int_{\mathbb{R}}\frac{1}{|y-z|^{2}}\mathrm{d}\nu_{1}(y)\right)^{-1}\int_{\mathbb{R}}\frac{s}{|z|^{2}|1+m_{2}(z)s|^{2}}\mathrm{d}\overline{\mu}_{\Sigma}(s),$

where we used Equation C.21 in the second equality. Taking the limit $z\to
x>\lambda^{\circ}$, we have

$\displaystyle 1-\limsup_{z\to
x,z\in{\mathbb{H}}}\frac{1}{\delta|z|^{2}}I_{1}(z,\overline{z})I_{2}(z,\overline{z})$
$\displaystyle=\left(\delta\int_{\mathbb{R}}\frac{1}{|y-x|^{2}}\mathrm{d}\nu_{1}(y)\right)^{-1}$
$\displaystyle\phantom{=}~{}\times\int_{\mathbb{R}}s\left(x^{2}+s^{2}\limsup_{z\to
x,z\in{\mathbb{H}}}|zm_{2}(z)|^{2}\right)^{-1}\mathrm{d}\overline{\mu}_{\Sigma}(s)>0,$

where we used Fatou’s lemma in the first equality and Lemma C.6 in the last
inequality. This concludes the proof of Proposition C.8. ∎

###  C.3 Proof of Lemmas 9.2 and C.1

###### Proof of Lemma 9.2 given Lemma C.1.

Notice that since $a^{\circ}$ is the largest critical point of $\psi$ and
$\lim_{a\to\infty}\psi^{\prime}(a)>0$, we find that $\psi^{\prime}(a)>0$ for
all $a\in(a^{\circ},\infty)$, i.e. $\psi$ is strictly increasing on
$[a^{\circ},\infty)$.

Next, we prove $\psi(a^{\circ})\leq\lambda^{\circ}$. Note from the
contrapositive of Item 1 of Lemma C.1 that if
$a>\sup\operatorname{supp}\overline{\mu}_{{\mathcal{T}}}$ and
$\psi^{\prime}(a)\leq 0$, then there exists an $\widetilde{a}\geq a$ such that
$\psi(\widetilde{a})\leq\lambda^{\circ}$. We may apply this to the largest
critical point $a^{\circ}$ since $\psi^{\prime}(a^{\circ})=0$, so that
$\psi(\widetilde{a})\leq\lambda^{\circ}$ for some $\widetilde{a}\geq
a^{\circ}$. As $\psi$ is increasing in $[a^{\circ},\infty)$, we conclude
$\psi(a^{\circ})\leq\psi(\widetilde{a})\leq\lambda^{\circ}$

Conversely, Item 2 of Lemma C.1 implies
$(\psi(a^{\circ}),\infty)\cap\operatorname{supp}\overline{\mu}_{\widehat{D}}=\emptyset$,
so that $\lambda^{\circ}\leq\psi(a^{\circ})$. Therefore we have
$\psi(a^{\circ})=\lambda^{\circ}$. ∎

###### Proof of Item 1 of Lemma C.1.

Let $a\in(\sup\operatorname{supp}\overline{\mu}_{T},\infty)$ satisfy the
assumption of Item 1 of Lemma C.1, that is,
$\psi(\widetilde{a})>\lambda^{\circ}$ for all $\widetilde{a}\geq a$. First of
all, we prove that there exists a complex neighborhood $U$ of $[a,\infty)$
such that

$w=-1/m_{1}(\psi(w)),\qquad\omega(w)=-1/m_{2}(\psi(w)),\qquad\forall w\in U.$
(C.30)

Here we remark that $\psi(a)>\lambda^{\circ}$ by assumption, so that all four
functions of $w$ in Equation C.30 are well-defined by Proposition C.8; those
in the first and second equalities are analytic and meromorphic, respectively.

Recall from Lemma C.3 that for large enough $\widetilde{a}>a$, there exists a
neighborhood $V$ of $\widetilde{a}$ so that
$\operatorname{\mathrm{Im}}\psi(w)/\operatorname{\mathrm{Im}}w>0$ for every
$w\in V$. Then it also follows that for each $w\in V\cap{\mathbb{H}}$,

$\operatorname{\mathrm{Im}}\left[-\frac{\psi(w)}{\omega(w)}\right]=\operatorname{\mathrm{Im}}\left[\int_{\mathbb{R}}\frac{tw}{t-w}\mathrm{d}\overline{\mu}_{T}(t)\right]=\operatorname{\mathrm{Im}}w\int_{\mathbb{R}}\frac{t^{2}}{|t-w|^{2}}\mathrm{d}\overline{\mu}_{T}(t)>0.$
(C.31)

Also notice that the triple $(\psi(w),-1/w,-1/\omega(w))$ satisfies the same
system of equations as in Equation C.8:

$\displaystyle-\frac{\psi(w)}{w}=\frac{1}{\delta}\int_{\mathbb{R}}\frac{s\omega(w)}{s-\omega(w)}\mathrm{d}\overline{\mu}_{\Sigma}(s)=-\frac{1}{\delta}\int_{\mathbb{R}}\frac{s}{1+s\cdot(-\omega(w))^{-1}}\mathrm{d}\overline{\mu}_{\Sigma}(s),$
(C.32)
$\displaystyle\frac{\psi(w)}{\omega(w)}=-\int_{\mathbb{R}}\frac{tw}{t-w}\mathrm{d}\overline{\mu}_{T}(t)=-\int_{\mathbb{R}}\frac{t}{1+t\cdot(-w^{-1})}\mathrm{d}\overline{\mu}_{T}(t).$

Therefore, by the uniqueness of the solution of Equation C.8, we conclude

$(\psi(w),-1/w,-1/\omega(w))=(\psi(w),m_{1}(\psi(w)),m_{2}(\psi(w))),\qquad
w\in V\cap{\mathbb{H}}.$ (C.33)

By Proposition C.8 and the assumption of Item 1, in both sides of Equation
C.33 are meromorphic functions defined on a neighborhood of $[a,\infty)$, so
that the identity holds in the whole (connected) neighborhood.

We now prove $\psi^{\prime}(a)>0$, provided
$a\notin{\mathcal{S}}\cup{\mathcal{S}}^{\prime}$. Recall from Equation C.6
that

$\displaystyle\delta\psi^{\prime}(a)$
$\displaystyle=\left(\int_{\mathbb{R}}\frac{s}{(s-\omega(a))^{2}}\mathrm{d}\overline{\mu}_{\Sigma}(s)\right)^{-1}$
(C.34)
$\displaystyle\phantom{=}~{}\times\left[-\delta\int_{\mathbb{R}}\int_{\mathbb{R}}\frac{t}{t-a}\frac{s\omega(a)}{(s-\omega(a))^{2}}+\frac{ta}{(t-a)^{2}}\frac{s^{2}}{(s-\omega(a))^{2}}\mathrm{d}\overline{\mu}_{\Sigma}(s)\mathrm{d}\overline{\mu}_{T}(t)\right].$

Note that the second line in Equation C.34 can be written as

$\displaystyle\begin{split}&-\delta\int_{\mathbb{R}}\int_{\mathbb{R}}\left[-\frac{t}{t-a}\frac{s}{s-\omega(a)}+\frac{t^{2}}{(t-a)^{2}}\frac{s^{2}}{(s-\omega(a))^{2}}\right]\mathrm{d}\overline{\mu}_{\Sigma}(s)\mathrm{d}\overline{\mu}_{T}(t)\\\
&=\frac{\delta^{2}\psi(a)^{2}}{a^{2}\omega(a)^{2}}-\delta\int_{\mathbb{R}}\int_{\mathbb{R}}\frac{t^{2}}{(t-a)^{2}}\frac{s^{2}}{(s-\omega(a))^{2}}\mathrm{d}\overline{\mu}_{\Sigma}(s)\mathrm{d}\overline{\mu}_{T}(t).\end{split}$
(C.35)

Then, we use Equation C.30 for $w=a$ to substitute $a$ and $\omega(a)$ in
Equation C.34 to obtain

$\displaystyle\psi^{\prime}(a)$
$\displaystyle=\frac{\delta\psi(a)^{2}}{a^{2}\omega(a)^{2}}\left(\int_{\mathbb{R}}\frac{s}{(s-\omega(a))^{2}}\mathrm{d}\overline{\mu}_{\Sigma}(s)\right)^{-1}$
(C.36)
$\displaystyle\phantom{=}~{}\times\left(1-\frac{1}{\delta\psi(a)^{2}}I_{1}(\psi(a),\psi(a))I_{2}(\psi(a),\psi(a))\right)>0,$

where we used $0<|m_{2}(\psi(a))|,|\psi(a)|<\infty$ for
$a\neq{\mathcal{S}}\cup{\mathcal{S}}^{\prime}$ and Equation C.23.

Now it only remains to prove $\psi^{\prime}(a)>0$ for
$a\in{\mathcal{S}}\cup{\mathcal{S}}^{\prime}$. Since ${\mathcal{S}}$ and
${\mathcal{S}}^{\prime}$ are both finite, we may consider a sequence
$\widetilde{a}_{k}>a$ such that
$\widetilde{a}_{k}\notin{\mathcal{S}}\cup{\mathcal{S}}^{\prime}$ and
$\widetilde{a}_{k}\to a$. Since $\psi$ is analytic at $a$ and the second line
of Equation C.36 is strictly positive by Proposition C.8, is suffices to prove

$\lim_{k\to\infty}\frac{\psi(\widetilde{a}_{k})^{2}}{\omega(\widetilde{a}_{k})^{2}}\left(\int_{\mathbb{R}}\frac{s}{(s-\omega(\widetilde{a}_{k}))^{2}}\mathrm{d}\overline{\mu}_{\Sigma}(s)\right)^{-1}>0.$

If $a\in{\mathcal{S}}$ so that $\omega(\widetilde{a}_{k})\to\infty$, we have

$\lim_{k\to\infty}\frac{\psi(\widetilde{a}_{k})^{2}}{\omega(\widetilde{a}_{k})^{2}}\left(\int_{\mathbb{R}}\frac{s}{(s-\omega(\widetilde{a}_{k}))^{2}}\mathrm{d}\overline{\mu}_{\Sigma}(s)\right)^{-1}=\psi(a)^{2}\lim_{k\to\infty}\left(\int_{\mathbb{R}}s\left(\frac{\omega(\widetilde{a}_{k})}{s-\omega(\widetilde{a}_{k})}\right)^{2}\mathrm{d}\overline{\mu}_{\Sigma}(s)\right)^{-1}=\frac{\psi(a)^{2}}{\mathbb{E}\left[\overline{\Sigma}\right]}>0,$

where in the last inequality we used $a\in{\mathcal{S}}$ implies
$a\notin{\mathcal{S}}^{\prime}$, which in turn gives $\psi(a)\neq 0$. Finally
for $a\in{\mathcal{S}}^{\prime}$, we use $\omega(\widetilde{a}_{k})\to 0$ to
write

$\displaystyle\lim_{k\to\infty}\frac{\psi(\widetilde{a}_{k})^{2}}{\omega(\widetilde{a}_{k})^{2}}\left(\int_{\mathbb{R}}\frac{s}{(s-\omega(\widetilde{a}_{k}))^{2}}\mathrm{d}\overline{\mu}_{\Sigma}(s)\right)^{-1}=\frac{1}{\mathbb{E}\left[\overline{\Sigma}^{-1}\right]}\lim_{k\to\infty}\frac{\psi(\widetilde{a}_{k})^{2}}{\omega(\widetilde{a}_{k})^{2}}$
$\displaystyle=\frac{a^{2}}{\delta^{2}\mathbb{E}\left[\overline{\Sigma}^{-1}\right]}\lim_{k\to\infty}\left(\int_{\mathbb{R}}\frac{s}{s-\omega(\widetilde{a}_{k})}\mathrm{d}\overline{\mu}_{\Sigma}(s)\right)^{2}=\frac{a^{2}}{\delta^{2}\mathbb{E}\left[\overline{\Sigma}^{-1}\right]}>0,$

where we used the definition of $\psi$ in the second equality and
$\inf\operatorname{supp}\overline{\mu}_{\Sigma}>0$ in the last inequality.
This concludes the proof of Item 1 of Lemma C.1. ∎

###### Proof Item 2 of Lemma C.1.

Since $\psi^{\prime}(a)>0$, there exist small neighborhoods $U$ and $V$
respectively of $a$ and $\psi(a)$ and an analytic inverse function
$\psi^{-1}:V\to U$ of $\psi$. We first prove that

$(z,-1/\psi^{-1}(z),-1/\omega(\psi^{-1}(z)))=(z,m_{1}(z),m_{2}(z)),$ (C.37)

for all $z\in V\cap{\mathbb{H}}$. Following Equation C.32, we easily find that
$(z,-1/\psi^{-1}(z),-1/\omega(\psi^{-1}(z)))$ satisfies Equation C.8. Also,
there is an open subset $V^{\prime}\subset V\cap{\mathbb{H}}$ so that
$\operatorname{\mathrm{Im}}\psi^{-1}(z)>0$ for all $z\in V^{\prime}$; to see
this, we write

$\operatorname{\mathrm{Im}}\psi^{-1}(z)=\operatorname{\mathrm{Im}}\left[(\psi^{-1})^{\prime}(\psi(a))\cdot(z-\psi(a))\right]+{\mathcal{O}}(|z-\psi(a)|^{2})=\frac{1}{\psi^{\prime}(a)}\operatorname{\mathrm{Im}}z+{\mathcal{O}}(|z-\psi(a)|^{2}).$

Hence, it suffices to take
$V^{\prime}=\\{z:|z-\psi(a)|<2\operatorname{\mathrm{Im}}z<r\\}$ with small
enough $r>0$ in order to have $\psi^{-1}(V^{\prime})\subset{\mathbb{H}}$.
Then, by Equation C.31 it also follows that
$\operatorname{\mathrm{Im}}[-z/\omega(\psi^{-1}(z))]>0$. As in the proof of
Item 1 of Lemma C.1, the uniqueness of the solution of Equation C.8 implies
Equation C.37 for $z\in V^{\prime}$. Finally the conclusion extends to
$V\cap{\mathbb{H}}$ by analytic continuation.

Since $\psi$ maps $(\sup\operatorname{supp}\overline{\mu}_{T},\infty)$ to
$\mathbb{R}$, its inverse function $\psi^{-1}$ is real-valued on
$V\cap\mathbb{R}$. Hence it follows

$\lim_{\eta\to
0}\operatorname{\mathrm{Im}}m_{1}(x+\mathrm{i}\eta)=\lim_{\eta\to
0}\operatorname{\mathrm{Im}}\left[-\frac{1}{\psi^{-1}(x+\mathrm{i}\eta)}\right]=0,\qquad
x\in V\cap\mathbb{R}.$

Then, applying Stieltjes inversion to Equation C.21, we have
$\operatorname{supp}\nu_{1}\cap V=\emptyset$. Finally by Equation C.21 we
conclude $\operatorname{supp}\overline{\mu}_{\widehat{D}}\cap V=\emptyset$, so
that $\psi(a)\notin\operatorname{supp}\overline{\mu}_{\widehat{D}}$. This
completes the proof of Item 2 in Lemma C.1. ∎

##  Appendix D Whitened spectral estimator

To complement Theorem 3.1, let us consider an alternative spectral estimator
that operates in the following situation. Suppose we are given _(i)_ the
observation $y\in{\mathbb{R}}^{n}$ generated according to Equation 1.1, _(ii)_
the design matrix $A\in{\mathbb{R}}^{n\times d}$ with correlated Gaussian
rows, and additionally _(iii)_ the covariance matrix
$\Sigma\in{\mathbb{R}}^{d\times d}$ of the rows of $A$. Now, for a given
preprocessing function ${\mathcal{T}}\colon{\mathbb{R}}\to{\mathbb{R}}$, a
natural spectral estimator could first “whiten” the matrix $A$ by inverting
out the covariance of the rows and then output

$\displaystyle x^{\mathrm{spec}}_{\smalltriangleup}(y,A,\Sigma)$
$\displaystyle\coloneqq\Sigma^{-1/2}v_{1}(D_{\smalltriangleup})\in{\mathbb{R}}^{d},$
(D.1)

where

$\displaystyle D_{\smalltriangleup}$
$\displaystyle\coloneqq\sum_{i=1}^{n}(\Sigma^{-1/2}a_{i})(\Sigma^{-1/2}a_{i})^{\top}{\mathcal{T}}(y_{i})=\Sigma^{-1/2}A^{\top}TA\Sigma^{-1/2}=\widetilde{A}^{\top}T\widetilde{A}=\Sigma^{-1/2}D\Sigma^{-1/2}\in{\mathbb{R}}^{d\times
d}.$

Intuitively, $x^{\mathrm{spec}}_{\smalltriangleup}$ is a meaningful estimate
of $x^{*}$ since one can think of $\Sigma^{1/2}x^{*}$ as an auxiliary
parameter in the model $y=q(\widetilde{A}\Sigma^{1/2}x^{*},\varepsilon)$ with
design matrix $\widetilde{A}$. Therefore, the top eigenvector of
$D_{\smalltriangleup}=\widetilde{A}^{\top}\mathrm{diag}({\mathcal{T}}(q(\widetilde{A}\Sigma^{1/2}x^{*},\varepsilon)))\widetilde{A}$
estimates $\Sigma^{1/2}x^{*}$ and $\Sigma^{-1/2}v_{1}(D_{\smalltriangleup})$
estimates $x^{*}$. We highlight that computing this spectral estimator
requires knowledge of $\Sigma$.

As before, our results concerning $x^{\mathrm{spec}}_{\smalltriangleup}$ are
expressed in terms of a few functions and parameters. Define
$\varphi_{\smalltriangleup},\psi_{\smalltriangleup},\zeta_{\smalltriangleup}\colon(\sup\operatorname{supp}({\mathcal{T}}(\overline{Y})),\infty)\to{\mathbb{R}},a^{\circ}_{\smalltriangleup}\in(\sup\operatorname{supp}({\mathcal{T}}(\overline{Y})),\infty)$
as

$\displaystyle\varphi_{\smalltriangleup}(a)$
$\displaystyle=\frac{a\delta}{\mathbb{E}\left[\overline{\Sigma}\right]}\mathbb{E}\left[\frac{\overline{G}^{2}{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right],\quad\psi_{\smalltriangleup}(a)=a\left(\frac{1}{\delta}+\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\right),$
$\displaystyle a^{\circ}_{\smalltriangleup}$
$\displaystyle=\operatorname*{argmin}_{a\in(\sup\operatorname{supp}({\mathcal{T}}(\overline{Y})),\infty)}\psi_{\smalltriangleup}(a),\quad\zeta_{\smalltriangleup}(a)=\psi_{\smalltriangleup}(\max\\{a,a^{\circ}_{\smalltriangleup}\\}),$

and
$a^{*}_{\smalltriangleup}\in(\sup\operatorname{supp}({\mathcal{T}}(\overline{Y})),\infty)$
as the unique solution to

$\displaystyle\zeta_{\smalltriangleup}(a^{*}_{\smalltriangleup})=\varphi_{\smalltriangleup}(a^{*}_{\smalltriangleup}).$

[LL20, Item 1 of Theorem 2.1] and [MM19, Item 1 of Lemma 2] show that both
$a^{\circ}_{\smalltriangleup}$ and $a^{*}_{\smalltriangleup}$ are uniquely
defined.444Note that
$\sqrt{\frac{\delta}{\mathbb{E}\left[\overline{\Sigma}\right]}}\,\overline{G}\sim{\mathcal{N}}(0,1)$.
Thus, our functions
$\varphi_{\smalltriangleup},\psi_{\smalltriangleup},\zeta_{\smalltriangleup}$
match $\varphi,\psi,\zeta$ in [LL20] upon setting $\kappa$ in the latter paper
to be $\sqrt{\frac{\mathbb{E}\left[\overline{\Sigma}\right]}{\delta}}$.  The
formula of the asymptotic overlap $\eta_{\smalltriangleup}$ is:

$\displaystyle\eta_{\smalltriangleup}$
$\displaystyle\coloneqq\left(\frac{1-\delta\mathbb{E}\left[\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}_{\smalltriangleup}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]}{1+\delta\mathbb{E}\left[\left(\mathbb{E}\left[\frac{\delta}{\overline{\Sigma}}\right]\overline{G}^{2}-1\right)\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}_{\smalltriangleup}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]}\right)^{1/2}.$

######  Theorem D.1 (Whitened spectral estimator).

Consider the above setting and let Items (A1), (A2), (A3), (A4), (A5) and (A6)
hold. Suppose $a^{*}_{\smalltriangleup}>a^{\circ}_{\smalltriangleup}$. Then,
the top two eigenvalues $\lambda_{1}(D),\lambda_{2}(D)$ of $D$ satisfy

$\displaystyle\operatorname*{p-lim}_{d\to\infty}\lambda_{1}(D)$
$\displaystyle=\zeta(a^{*}_{\smalltriangleup}),\qquad\lim_{d\to\infty}\lambda_{2}(D)=\zeta(a^{\circ}_{\smalltriangleup})\quad\text{almost
surely},$

and $\zeta(a^{*}_{\smalltriangleup})>\zeta(a^{\circ}_{\smalltriangleup})$.
Furthermore, the limiting overlap between the spectral estimator
$x^{\mathrm{spec}}_{\smalltriangleup}=\Sigma^{-1/2}v_{1}(D_{\smalltriangleup})$
and $x^{*}$ equals

$\displaystyle\operatorname*{p-lim}_{d\to\infty}\frac{\left|\left\langle
x^{\mathrm{spec}}_{\smalltriangleup},x^{*}\right\rangle\right|}{\left\|x^{\mathrm{spec}}_{\smalltriangleup}\right\|_{2}\left\|x^{*}\right\|_{2}}$
$\displaystyle=\eta_{\smalltriangleup}>0.$

We caution that, even if the spectral estimator is now computed with respect
to $\widetilde{A}$ whose rows have identity covariance, the observation $y$
still depends on $\Sigma$ through
$y=q(\widetilde{A}\Sigma^{1/2}x^{*},\varepsilon)$ and there is no easy way to
further inverse out $\Sigma^{1/2}$ therein. Therefore, the situation here
cannot be exactly reduced to the $\Sigma=I_{d}$ case studied in [LL20, MM19].

Let $x^{\mathrm{spec}}_{\square}$ be the estimator in Equation 2.5 with
$\Sigma=I_{d}$. Interestingly, it turns out that the performance of
$x^{\mathrm{spec}}_{\smalltriangleup}$ given the additional knowledge of
$\Sigma$ is still no better than that of $x^{\mathrm{spec}}_{\square}$. In
fact we precisely quantify their performance gap in Remark D.2 below. We
observe in passing that there is no clear dominance of either
$x^{\mathrm{spec}}_{\smalltriangleup}$ or $x^{\mathrm{spec}}_{\square}$ over
our estimator $x^{\mathrm{spec}}$ in Equation 2.5 (which does not need to know
anything about $\Sigma$), as corroborated by numerical results in Figures 2, 3
and 4.

To properly make the comparison, let us first record below Lemma 2 from
[MM19], which concerns the case of $\Sigma=I_{d}$. This generalizes the
previous result [LL20, Theorem 2.1] by removing the assumption
${\mathcal{T}}\geq 0$. Denote by
$D_{\square},\overline{G}_{\square},\overline{Y}_{\square},\varphi_{\square},\psi_{\square},a^{\circ}_{\square},\zeta_{\square},a^{*}_{\square}$
the matrix/random variables/functions/parameters obtained by setting
$\Sigma=I_{d},\overline{\Sigma}=1$ in
$D,\overline{G},\overline{Y},\varphi_{\smalltriangleup},\psi_{\smalltriangleup},a^{\circ}_{\smalltriangleup},\zeta_{\smalltriangleup},a^{*}_{\smalltriangleup}$.
Correspondingly, the expression of the asymptotic overlap $\eta_{\square}$ in
this case is obtained by replacing the subscript $\smalltriangleup$ with
$\square$ in the various parameters in $\eta_{\smalltriangleup}$:

$\displaystyle\eta_{\square}$
$\displaystyle\coloneqq\left(\frac{1-\delta\mathbb{E}\left[\left(\frac{{\mathcal{T}}(\overline{Y}_{\square})}{a^{*}_{\square}-{\mathcal{T}}(\overline{Y}_{\square})}\right)^{2}\right]}{1+\delta\mathbb{E}\left[(\delta\overline{G}_{\square}^{2}-1)\left(\frac{{\mathcal{T}}(\overline{Y}_{\square})}{a^{*}_{\square}-{\mathcal{T}}(\overline{Y}_{\square})}\right)^{2}\right]}\right)^{1/2}.$
(D.2)

######  Theorem D.2 (Spectral estimator with $\Sigma=I_{d}$, [MM19, Lemma 2]).

Consider the above setting and let Items (A1), (A2), (A4), (A5) and (A6) hold
with $\Sigma=I_{d}$ and $\varepsilon\sim P_{\varepsilon}^{\otimes n}$. Let
$x^{\mathrm{spec}}_{\square}\coloneqq v_{1}(D_{\square})$. Then,

$\displaystyle\lim_{d\to\infty}\frac{\left|\left\langle
x^{\mathrm{spec}}_{\square},x^{*}\right\rangle\right|}{\left\|x^{\mathrm{spec}}_{\square}\right\|_{2}\left\|x^{*}\right\|_{2}}$
$\displaystyle=\begin{cases}\eta_{\square},&a^{*}_{\square}>a^{\circ}_{\square}\\\
0,&a^{*}_{\square}\leq
a^{\circ}_{\square}\end{cases},\quad\lim_{d\to\infty}\lambda_{1}(D_{\square})=\zeta_{\square}(a^{*}_{\square}),\quad\lim_{d\to\infty}\lambda_{2}(D_{\square})=\zeta_{\square}(a^{\circ}_{\square}).$

where the convergence holds almost surely.

######  Remark D.1 (Comparison with Theorem D.2).

The result above (Theorem D.2) is stronger than the specialization of Theorems
3.1 and D.1 to $\Sigma=I_{d}$ in the following two aspects. First, the
convergence in probability of the outlier eigenvalue and the overlap is
strengthened to almost sure convergence. Second, more importantly, a full
phase transition phenomenon is uncovered which also justifies the
ineffectiveness of spectral estimator in the subcritical regime.
Comparatively, both weaknesses are due to the limitation of our proof
techniques. We use AMP with non-separable denoisers to study the outlier
eigenvalue and eigenvector. The state evolution for such AMPs only guarantees
convergence in probability, and the AMP iterate provably converges to the
outlier eigenvector only in the presence of a spectral gap.

######  Remark D.2 (Comparison between spectral estimators: whitened worse
than $\Sigma=I_{d}$).

If $\mathbb{E}\left[\overline{\Sigma}\right]=1$ (for a fair comparison), it is
not hard to see that $\eta_{\smalltriangleup}\leq\eta_{\square}$. In words,
the whitened spectral estimator $x^{\mathrm{spec}}_{\smalltriangleup}$ for
_general_ Gaussian design has asymptotic overlap no larger than that of the
standard spectral estimator $x^{\mathrm{spec}}_{\square}$ for _isotropic_
Gaussian design. To see the claim, note that
$\sqrt{\frac{\delta}{\mathbb{E}\left[\overline{\Sigma}\right]}}\overline{G}\sim{\mathcal{N}}(0,1)$.
Therefore if
$\mathbb{E}\left[\frac{\delta}{\overline{\Sigma}}\right]\overline{G}^{2}$ in
the denominator of $\eta_{\smalltriangleup}$ was replaced with
$\frac{\delta}{\mathbb{E}\left[\overline{\Sigma}\right]}\overline{G}^{2}$,
then $\eta_{\smalltriangleup}$ will equal $\eta_{\square}$. However, Jensen’s
inequality gives that
$\mathbb{E}\left[\frac{1}{\overline{\Sigma}}\right]\geq\frac{1}{\mathbb{E}\left[\overline{\Sigma}\right]}$,
which implies $\eta_{\smalltriangleup}\leq\eta_{\square}$.

######  Remark D.3 (Optimal preprocessing function).

If $\mathbb{E}\left[\overline{\Sigma}\right]=1$, the definitions of
$a^{*}_{\smalltriangleup}$ and $a^{\circ}_{\smalltriangleup}$ are the same as
those of $a^{*}_{\square}$ and $a^{\circ}_{\square}$ in the case of
$\Sigma=I_{d}$. This in particular implies that the spectral threshold in
these two settings coincide and can be achieved by the same preprocessing
function. In the case of $\Sigma=I_{d}$, under the assumption

$\displaystyle\inf_{y\in\operatorname{supp}(\overline{Y})}\frac{\mathbb{E}\left[\delta\overline{G}^{2}p\left(y\,|\,\overline{G}\right)\right]}{\mathbb{E}\left[p\left(y\,|\,\overline{G}\right)\right]}>0,$
(D.3)

[LAL19] shows that

$\displaystyle{\mathcal{T}}^{*}_{\square}(y)$
$\displaystyle=1-\frac{\mathbb{E}\left[p\left(y\,|\,\overline{G}\right)\right]}{\mathbb{E}\left[\delta\overline{G}^{2}p\left(y\,|\,\overline{G}\right)\right]}$
(D.4)

not only minimizes the spectral threshold, but also maximizes the overlap. If
the infimum in Equation D.3 is equal to $0$, ${\mathcal{T}}^{*}_{\square}$ in
Equation D.4 becomes unbounded and a certain perturbation is needed to create
a sequence of functions whose spectral threshold approaches the optimal one.
We refer the readers to [LAL19, Item 3 of Theorem 1] for a specific
construction of such a sequence of functions.

###  D.1 Proof of Theorem D.1

The proof of Theorem D.1 follows similar ideas used in that of Theorem 3.1,
that is, designing a proper AMP algorithm to simulate power iteration for the
whitened spectral matrix $D_{\smalltriangleup}$ and proving that its iterate
converges to the top eigenvector of $D_{\smalltriangleup}$ – when a certain
analytic condition associated to the presence of a spectral gap is fulfilled.

####  D.1.1 Heuristics

Let us consider the generic GAMP iteration in Equation 5.1. Let
${\mathcal{F}}_{\smalltriangleup}\colon{\mathbb{R}}\to{\mathbb{R}}$ be an
auxiliary preprocessing function to be chosen later. Set

$\displaystyle f_{t+1}(v^{t+1})$
$\displaystyle=\frac{v^{t+1}}{\beta_{t+1}},\quad t\geq 0,$ (D.5)

for a sequence $(\beta_{t+1})_{t\geq 0}$ to be specified later via state
evolution. One should think of the normalization $\beta_{t+1}>0$ as

$\displaystyle\beta_{t+1}=\lim_{d\to\infty}\frac{1}{\sqrt{d}}\left\|v^{t+1}\right\|_{2},$

such that

$\displaystyle\lim_{d\to\infty}\frac{1}{\sqrt{d}}\left\|f_{t+1}(v^{t+1})\right\|_{2}$
$\displaystyle=1,$

as in Equation 5.9. Furthermore, we set

$\displaystyle g_{t}(u^{t};y)$ $\displaystyle=F_{\smalltriangleup}u^{t},\quad
t\geq 0,$ (D.6)

where
$F_{\smalltriangleup}=\mathrm{diag}({\mathcal{F}}_{\smalltriangleup}(y))\in{\mathbb{R}}^{n\times
n}$ and ${\mathcal{F}}_{\smalltriangleup}(y)\in{\mathbb{R}}^{n}$ is understood
as the vector obtained by applying ${\mathcal{F}}_{\smalltriangleup}$ to each
entry of $y$. The Onsager coefficients specialize to

$\displaystyle b_{t+1}$ $\displaystyle=\frac{1}{\delta\beta_{t+1}},\quad
c_{t}=\mathbb{E}\left[{\mathcal{F}}_{\smalltriangleup}(\overline{Y})\right]\eqqcolon
c.$

Now, let us examine the following heuristics which will suggest a natural
choice of ${\mathcal{F}}_{\smalltriangleup}$. Heuristically, assume
$u^{t},v^{t+1},\beta_{t+1}$ converge respectively to
$u\in{\mathbb{R}}^{n},v\in{\mathbb{R}}^{d},\beta\in{\mathbb{R}}$ in the
following sense

$\displaystyle\lim_{t\to\infty}\lim_{n\to\infty}\frac{1}{\sqrt{n}}\left\|u^{t}-u\right\|_{2}$
$\displaystyle=0,\quad\lim_{t\to\infty}\lim_{d\to\infty}\frac{1}{\sqrt{d}}\left\|v^{t+1}-v\right\|_{2}=0,\quad\lim_{t\to\infty}\left|\beta_{t+1}-\beta\right|=0.$

Then in the $t\to\infty$ limit, the GAMP iteration becomes

$\displaystyle u$
$\displaystyle=\frac{1}{\beta}\widetilde{A}v-bF_{\smalltriangleup}u,\quad
v=\widetilde{A}^{\top}F_{\smalltriangleup}u-\frac{1}{\beta}cv,$

where $b=\frac{1}{\delta\beta}$ is the limit of $b_{t+1}$ as $t\to\infty$.
Solving $u$ in terms of $v$ from the first equation, we get

$\displaystyle u$
$\displaystyle=\frac{1}{\beta}(I_{n}+bF_{\smalltriangleup})^{-1}\widetilde{A}v.$

We then use this to eliminate $u$ from the equation for $v$ and obtain:

$\displaystyle(\beta+c)v$
$\displaystyle=\widetilde{A}^{\top}F_{\smalltriangleup}(I_{n}+bF_{\smalltriangleup})^{-1}\widetilde{A}v.$
(D.7)

Our aim is to choose ${\mathcal{F}}_{\smalltriangleup}$ judiciously to turn
the above equation into an eigenequation for
$D_{\smalltriangleup}=\widetilde{A}^{\top}T\widetilde{A}$. First, to simplify
the derivation, we require $b=1$ which will be the case if
$\beta=\frac{1}{\delta}$. Next, we choose

$\displaystyle{\mathcal{F}}_{\smalltriangleup}(\cdot)$
$\displaystyle=\frac{{\mathcal{T}}(\cdot)}{a^{*}_{\smalltriangleup}-{\mathcal{T}}(\cdot)},$
(D.8)

where $a^{*}_{\smalltriangleup}$ is to be specified later. With these choices,
Equation D.7 becomes

$\displaystyle\left(\frac{1}{\delta}+c\right)v$
$\displaystyle=\frac{1}{a^{*}_{\smalltriangleup}}\widetilde{A}^{\top}T\widetilde{A}v=\frac{1}{a^{*}_{\smalltriangleup}}D_{\smalltriangleup}v,$

which, upon multiplying by $a^{*}_{\smalltriangleup}$ on both sides, is an
eigenequation of $D_{\smalltriangleup}$ with respect to the eigenvalue

$\displaystyle
a^{*}_{\smalltriangleup}\left(\frac{1}{\delta}+c\right)=a^{*}_{\smalltriangleup}\left(\frac{1}{\delta}+\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a^{*}_{\smalltriangleup}-{\mathcal{T}}(\overline{Y})}\right]\right),$

and the corresponding eigenvector (up to scaling) $v$.

At this point, the only parameter that remains to determine is
$a^{*}_{\smalltriangleup}$. In fact, the value of $a^{*}_{\smalltriangleup}$
is fixed when we enforce $\beta=\frac{1}{\delta}$ which in turn enforces
$b=1$. From the state evolution analysis to be presented in the sequel,
$\beta$ can be derived and therefore $a^{*}_{\smalltriangleup}$ should be
defined as the solution to the following equation

$\displaystyle\beta=\lim_{t\to\infty}\beta_{t+1}=\mathbb{E}\left[\left(\frac{\delta}{\mathbb{E}\left[\overline{\Sigma}\right]}\overline{G}^{2}-1\right)\frac{{\mathcal{T}}(\overline{Y})}{a^{*}_{\smalltriangleup}-{\mathcal{T}}(\overline{Y})}\right]=\frac{1}{\delta}.$
(D.9)

####  D.1.2 State evolution of artificial GAMP and its fixed points

Inspired by the heuristics in Section D.1.1, consider the unique solution
$a^{*}_{\smalltriangleup}$ to Equation D.9 in
$\left(\sup\operatorname{supp}({\mathcal{T}}(\overline{Y})),\infty\right)$ and
let ${\mathcal{F}}_{\smalltriangleup}\colon{\mathbb{R}}\to{\mathbb{R}}$ be
defined in Equation D.8. Set the denoisers $(f_{t+1},g_{t})_{t\geq 0}$ in
Equation 5.1 to those given in Equations D.5 and D.6 and initialize the GAMP
iteration with

$\displaystyle\widetilde{u}^{-1}$
$\displaystyle=0_{n},\quad\widetilde{v}^{0}=\mu\widetilde{x}^{*}+\sqrt{1-\mu^{2}\mathbb{E}\left[\overline{\Sigma}\right]}w\in{\mathbb{R}}^{d},$
(D.10)

where $w\sim{\mathcal{N}}(0_{d},I_{d})$ is independent of everything else and
$\mu$ is given in Equation D.11 below. Given all these configurations, the
state evolution recursion specializes to

$\displaystyle\mu_{t}$
$\displaystyle=\frac{\delta}{\mathbb{E}\left[\overline{\Sigma}\right]}\lim_{n\to\infty}\frac{1}{n}\mathbb{E}\left[(\widetilde{X}^{*})^{\top}V_{t}/\beta_{t}\right]=\frac{\delta}{\mathbb{E}\left[\overline{\Sigma}\right]}\lim_{n\to\infty}\frac{1}{n}\mathbb{E}\left[(\widetilde{X}^{*})^{\top}\widetilde{X}^{*}\right]\chi_{t}/\beta_{t}=\chi_{t}/\beta_{t},$
$\displaystyle\sigma_{U,t}^{2}$
$\displaystyle=\lim_{n\to\infty}\frac{1}{n}\mathbb{E}\left[V_{t}^{\top}V_{t}/\beta_{t}^{2}\right]-\frac{\mathbb{E}\left[\overline{\Sigma}\right]}{\delta}\mu_{t}^{2}$
$\displaystyle=\frac{1}{\beta_{t}^{2}}\lim_{n\to\infty}\frac{1}{n}\mathbb{E}\left[(\widetilde{X}^{*})^{\top}\widetilde{X}^{*}\right]\chi_{t}^{2}+\frac{1}{\beta_{t}^{2}}\lim_{n\to\infty}\frac{1}{n}\mathbb{E}\left[W_{V,t}^{\top}W_{V,t}\right]\sigma_{V,t}^{2}-\frac{\mathbb{E}\left[\overline{\Sigma}\right]}{\delta}\mu_{t}^{2}$
$\displaystyle=\frac{1}{\beta_{t}^{2}}\frac{\mathbb{E}\left[\overline{\Sigma}\right]}{\delta}\chi_{t}^{2}+\frac{1}{\beta_{t}^{2}}\frac{1}{\delta}\sigma_{V,t}^{2}-\frac{\mathbb{E}\left[\overline{\Sigma}\right]}{\delta}\mu_{t}^{2}=\frac{\sigma_{V,t}^{2}}{\delta\beta_{t}^{2}},$
$\displaystyle\chi_{t+1}$
$\displaystyle=\frac{\delta}{\mathbb{E}\left[\overline{\Sigma}\right]}\lim_{n\to\infty}\frac{1}{n}\mathbb{E}\left[G^{\top}F_{\smalltriangleup}U_{t}\right]-\mu_{t}\mathbb{E}\left[{\mathcal{F}}_{\smalltriangleup}(\overline{Y})\right]=\frac{\delta}{\mathbb{E}\left[\overline{\Sigma}\right]}\lim_{n\to\infty}\frac{1}{n}\mathbb{E}\left[G^{\top}F_{\smalltriangleup}G\right]\mu_{t}-\mu_{t}\mathbb{E}\left[{\mathcal{F}}_{\smalltriangleup}(\overline{Y})\right]$
$\displaystyle=\mathbb{E}\left[\left(\frac{\delta}{\mathbb{E}\left[\overline{\Sigma}\right]}\overline{G}^{2}-1\right){\mathcal{F}}_{\smalltriangleup}(\overline{Y})\right]\mu_{t}=\mathbb{E}\left[\left(\frac{\delta}{\mathbb{E}\left[\overline{\Sigma}\right]}\overline{G}^{2}-1\right){\mathcal{F}}_{\smalltriangleup}(\overline{Y})\right]\frac{\chi_{t}}{\beta_{t}},$
$\displaystyle\sigma_{V,t+1}^{2}$
$\displaystyle=\lim_{n\to\infty}\frac{1}{n}\mathbb{E}\left[U_{t}^{\top}F_{\smalltriangleup}^{2}U_{t}\right]=\lim_{n\to\infty}\frac{1}{n}\mathbb{E}\left[G^{\top}F_{\smalltriangleup}^{2}G\right]\mu_{t}^{2}+\lim_{n\to\infty}\frac{1}{n}\mathbb{E}\left[W_{U,t}^{\top}F_{\smalltriangleup}^{2}W_{U,t}\right]\sigma_{U,t}^{2}$
$\displaystyle=\mathbb{E}\left[\overline{G}^{2}{\mathcal{F}}_{\smalltriangleup}(\overline{Y})^{2}\right]\mu_{t}^{2}+\mathbb{E}\left[{\mathcal{F}}_{\smalltriangleup}(\overline{Y})^{2}\right]\sigma_{U,t}^{2}=\mathbb{E}\left[\overline{G}^{2}{\mathcal{F}}_{\smalltriangleup}(\overline{Y})^{2}\right]\frac{\chi_{t}^{2}}{\beta_{t}^{2}}+\mathbb{E}\left[{\mathcal{F}}_{\smalltriangleup}(\overline{Y})^{2}\right]\frac{\sigma_{V,t}^{2}}{\delta\beta_{t}^{2}},$
$\displaystyle\beta_{t+1}^{2}$
$\displaystyle=\lim_{d\to\infty}\frac{1}{d}\mathbb{E}\left[V_{t+1}^{\top}V_{t+1}\right]=\lim_{d\to\infty}\frac{1}{d}\mathbb{E}\left[(\widetilde{X}^{*})^{\top}\widetilde{X}^{*}\right]\chi_{t+1}^{2}+\lim_{d\to\infty}\frac{1}{d}\mathbb{E}\left[W_{V,t+1}^{\top}W_{V,t+1}\right]\sigma_{V,t+1}^{2}$
$\displaystyle=\mathbb{E}\left[\overline{\Sigma}\right]\chi_{t+1}^{2}+\sigma_{V,t+1}^{2}.$

It turns out that there are $3$ fixed points of
$(\mu_{t},\sigma_{U,t},\chi_{t+1},\sigma_{V,t+1},\beta_{t+1})$. They can be
easily solved below:

$\displaystyle\mathsf{FP}_{+}$
$\displaystyle=(\mu,\sigma_{U},\chi,\sigma_{V},\beta),\quad\mathsf{FP}_{-}=(-\mu,\sigma_{U},-\chi,\sigma_{V},\beta),$
$\displaystyle\mathsf{FP}_{0}$
$\displaystyle=\left(0,\frac{1}{\sqrt{\delta}},0,\frac{1}{\sqrt{\delta}}\mathbb{E}\left[\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}_{\smalltriangleup}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]^{1/2},\frac{1}{\sqrt{\delta}}\mathbb{E}\left[\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}_{\smalltriangleup}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]^{1/2}\right),$

where $\mu,\sigma_{U},\chi,\sigma_{V},\beta$ are given by

$\displaystyle\beta$
$\displaystyle=\mathbb{E}\left[\left(\frac{\delta}{\mathbb{E}\left[\overline{\Sigma}\right]}\overline{G}^{2}-1\right)\frac{{\mathcal{T}}(\overline{Y})}{a^{*}_{\smalltriangleup}-{\mathcal{T}}(\overline{Y})}\right]=\frac{1}{\delta},$
$\displaystyle\chi$
$\displaystyle=\left(\frac{\beta^{2}-\frac{1}{\delta}\mathbb{E}\left[{\mathcal{F}}_{\smalltriangleup}(\overline{Y})^{2}\right]}{\mathbb{E}\left[\overline{\Sigma}\right]-\frac{\mathbb{E}\left[\overline{\Sigma}\right]}{\delta\beta^{2}}\mathbb{E}\left[{\mathcal{F}}_{\smalltriangleup}(\overline{Y})^{2}\right]+\frac{1}{\beta^{2}}\mathbb{E}\left[\overline{G}^{2}{\mathcal{F}}_{\smalltriangleup}(\overline{Y})^{2}\right]}\right)^{1/2}$
$\displaystyle=\left(\frac{\frac{1}{\delta^{2}}-\frac{1}{\delta}\mathbb{E}\left[\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}_{\smalltriangleup}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]}{\mathbb{E}\left[\overline{\Sigma}\right]-\delta\mathbb{E}\left[\overline{\Sigma}\right]\mathbb{E}\left[\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}_{\smalltriangleup}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]+\delta^{2}\mathbb{E}\left[\overline{G}^{2}\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}_{\smalltriangleup}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]}\right)^{1/2},$
$\displaystyle\sigma_{V}$
$\displaystyle=\left(\frac{\delta^{2}\mathbb{E}\left[\overline{G}^{2}{\mathcal{F}}_{\smalltriangleup}(\overline{Y})^{2}\right]\chi^{2}}{1-\frac{1}{\delta\beta^{2}}\mathbb{E}\left[{\mathcal{F}}_{\smalltriangleup}(\overline{Y})^{2}\right]}\right)^{1/2}=\left(\frac{\mathbb{E}\left[\overline{G}^{2}\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}_{\smalltriangleup}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]}{\mathbb{E}\left[\overline{\Sigma}\right]-\delta\mathbb{E}\left[\overline{\Sigma}\right]\mathbb{E}\left[\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}_{\smalltriangleup}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]+\delta^{2}\mathbb{E}\left[\overline{G}^{2}\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}_{\smalltriangleup}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]}\right)^{1/2},$
$\displaystyle\mu$
$\displaystyle=\frac{\chi}{\beta}=\left(\frac{1-\delta\mathbb{E}\left[\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}_{\smalltriangleup}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]}{\mathbb{E}\left[\overline{\Sigma}\right]-\delta\mathbb{E}\left[\overline{\Sigma}\right]\mathbb{E}\left[\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}_{\smalltriangleup}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]+\delta^{2}\mathbb{E}\left[\overline{G}^{2}\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}_{\smalltriangleup}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]}\right)^{1/2},$
(D.11) $\displaystyle\sigma_{U}$
$\displaystyle=\frac{\sigma_{V}}{\sqrt{\delta}\beta}=\left(\frac{\delta\mathbb{E}\left[\overline{G}^{2}\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}_{\smalltriangleup}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]}{\mathbb{E}\left[\overline{\Sigma}\right]-\delta\mathbb{E}\left[\overline{\Sigma}\right]\mathbb{E}\left[\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}_{\smalltriangleup}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]+\delta^{2}\mathbb{E}\left[\overline{G}^{2}\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}_{\smalltriangleup}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]}\right)^{1/2}.$

Furthermore, the initialization scheme in Equation D.10 guarantees that
$(\mu_{t},\sigma_{U,t},\chi_{t+1},\sigma_{V,t+1},\beta_{t+1})$ stays at
$\mathsf{FP}_{+}$ for every $t\geq 0$.

Executing similar arguments in the proofs of Lemmas 8.1 and 9.1 allows us to
claim:

$\displaystyle\lim_{t\to\infty}\operatorname*{p-lim}_{d\to\infty}\frac{\left\langle
v^{t+1},v_{1}(D_{\smalltriangleup})\right\rangle^{2}}{\left\|v^{t+1}\right\|_{2}^{2}\left\|v_{1}(D_{\smalltriangleup})\right\|_{2}^{2}}$
$\displaystyle=1,\quad\operatorname*{p-lim}_{d\to\infty}\lambda_{1}(D_{\smalltriangleup})=\zeta(a^{*}_{\smalltriangleup})>\zeta(a^{\circ}_{\smalltriangleup})=\lim_{d\to\infty}\lambda_{2}(D_{\smalltriangleup}).$
(D.12)

Recall from Equation D.1 that the whitened spectral estimator is defined as
$x_{\smalltriangleup}^{\mathrm{spec}}=\Sigma^{-1/2}v_{1}(D_{\smalltriangleup})$.
Given the result in Equation D.12, the overlap between
$x_{\smalltriangleup}^{\mathrm{spec}}$ and $x^{*}$ is asymptotically the same
as that between $\Sigma^{-1/2}v^{t+1}$ and $x^{*}$ which we compute below:

$\displaystyle\lim_{t\to\infty}\operatorname*{p-lim}_{d\to\infty}\frac{\left\langle\Sigma^{-1/2}v^{t+1},x^{*}\right\rangle^{2}}{\left\|\Sigma^{-1/2}v^{t+1}\right\|_{2}^{2}\left\|x^{*}\right\|_{2}^{2}}$
$\displaystyle=\frac{\lim\limits_{t\to\infty}\operatorname*{p-lim}\limits_{d\to\infty}\frac{1}{d^{2}}\left\langle\Sigma^{-1/2}v^{t+1},x^{*}\right\rangle^{2}}{\lim\limits_{t\to\infty}\operatorname*{p-lim}\limits_{d\to\infty}\frac{1}{d}\left\|\Sigma^{-1/2}v^{t+1}\right\|_{2}^{2}},$

the numerator and denominator of which are given respectively as follows:

$\displaystyle\lim_{t\to\infty}\operatorname*{p-lim}_{d\to\infty}\frac{1}{d^{2}}\left\langle\Sigma^{-1/2}v^{t+1},x^{*}\right\rangle^{2}$
$\displaystyle=\lim_{t\to\infty}\lim_{d\to\infty}\frac{1}{d^{2}}\mathbb{E}\left[(\widetilde{X}^{*})^{\top}\Sigma^{-1/2}X^{*}\right]^{2}\chi_{t+1}^{2}=\chi^{2},$
$\displaystyle\lim_{t\to\infty}\operatorname*{p-lim}_{d\to\infty}\frac{1}{d}\left\|\Sigma^{-1/2}v^{t+1}\right\|_{2}^{2}$
$\displaystyle=\lim_{t\to\infty}\lim_{d\to\infty}\frac{1}{d}\mathbb{E}\left[(\widetilde{X}^{*})^{\top}\Sigma^{-1}\widetilde{X}^{*}\right]\chi_{t+1}^{2}+\frac{1}{d}\mathbb{E}\left[W_{V,t+1}^{\top}\Sigma^{-1}W_{V,t+1}\right]\sigma_{V,t+1}^{2}$
$\displaystyle=\chi^{2}+\mathbb{E}\left[\frac{1}{\overline{\Sigma}}\right]\sigma_{V}^{2}.$

Using the expressions of $\chi,\sigma_{V}$, we obtain

$\displaystyle\operatorname*{p-lim}_{d\to\infty}\frac{\left\langle
x^{\mathrm{spec}}_{\smalltriangleup},x^{*}\right\rangle^{2}}{\left\|x^{\mathrm{spec}}_{\smalltriangleup}\right\|_{2}^{2}\left\|x^{*}\right\|_{2}^{2}}$
$\displaystyle=\frac{\chi^{2}}{\chi^{2}+\mathbb{E}\left[\frac{1}{\overline{\Sigma}}\right]\sigma_{V}^{2}}=\frac{\frac{1}{\delta^{2}}-\frac{1}{\delta}\mathbb{E}\left[\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}_{\smalltriangleup}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]}{\frac{1}{\delta^{2}}-\frac{1}{\delta}\mathbb{E}\left[\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}_{\smalltriangleup}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]+\mathbb{E}\left[\frac{1}{\overline{\Sigma}}\right]\mathbb{E}\left[\overline{G}^{2}\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}_{\smalltriangleup}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]}$
$\displaystyle=\frac{1-\delta\mathbb{E}\left[\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}_{\smalltriangleup}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]}{1+\delta\mathbb{E}\left[\left(\mathbb{E}\left[\frac{\delta}{\overline{\Sigma}}\right]\overline{G}^{2}-1\right)\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}_{\smalltriangleup}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]}=\eta_{\smalltriangleup},$

which concludes the proof.

##  Appendix E Examples

###  E.1 Identity covariance

In the case of $\Sigma=I_{d}$, i.e., each covariate vector is an i.i.d.
isotropic Gaussian, the outlier eigenvalue and the right edge of the bulk of
$D$, and the overlap of $v_{1}(D)$ have all been characterized in [LL20,
MM19].

We specialize our results for general $\Sigma$ to the case of $\Sigma=I_{d}$
and recover those in Theorem D.2. Clearly, it suffices to verify
$\varphi=\varphi_{\square},\psi=\psi_{\square},\eta=\eta_{\square}$. Let us
start with the implicit function $\gamma$ in Equation 3.3. Note that
$\overline{\Sigma}=1$ is a constant. Therefore

$\displaystyle\gamma(a)$
$\displaystyle=\frac{1}{\delta}+\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right].$

The functions $\varphi,\psi$ in Equation 3.2 then become

$\displaystyle\varphi(a)$ $\displaystyle=\delta
a\mathbb{E}\left[\frac{\overline{G}^{2}{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right],\quad\psi(a)=a\left(\frac{1}{\delta}+\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a-{\mathcal{T}}(\overline{Y})}\right]\right),$

coinciding with $\varphi_{\square},\psi_{\square}$ on page D. Consequently, we
have
$\zeta=\zeta_{\square},a^{*}=a^{*}_{\square},a^{\circ}=a^{\circ}_{\square}$.

Finally, $\eta$ in Equation 3.8 specializes to

$\displaystyle\eta$ $\displaystyle=\sqrt{\frac{(1-x_{2})}{(1-x_{2})+x_{1}}},$

where

$\displaystyle x_{1}$
$\displaystyle\coloneqq\frac{1}{\delta}\left(\mathbb{E}\left[\left(\delta\overline{G}^{2}-1\right)\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]\frac{1}{\left(\gamma^{*}-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a^{*}-{\mathcal{T}}(\overline{Y})}\right]\right)^{2}}+\mathbb{E}\left[\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]\frac{1}{\left(\gamma^{*}-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a^{*}-{\mathcal{T}}(\overline{Y})}\right]\right)^{2}}\right)$
$\displaystyle=\delta\left(\mathbb{E}\left[\left(\delta\overline{G}^{2}-1\right)\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]+\mathbb{E}\left[\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]\right)$
(E.1)
$\displaystyle=\delta\mathbb{E}\left[\delta\overline{G}^{2}\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right],$
$\displaystyle x_{2}$
$\displaystyle\coloneqq\frac{1}{\delta}\mathbb{E}\left[\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]\frac{1}{\left(\gamma^{*}-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a^{*}-{\mathcal{T}}(\overline{Y})}\right]\right)^{2}}$
$\displaystyle=\delta\mathbb{E}\left[\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right].$
(E.2)

We use the definition of $\gamma^{*}=\gamma(a^{*})$ in Equations E.1 and E.2
above. Using the expressions of $x_{1},x_{2}$, we obtain

$\displaystyle\eta$
$\displaystyle=\left(\frac{1-\delta\mathbb{E}\left[\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]}{1-\delta\mathbb{E}\left[\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]+\delta\mathbb{E}\left[\delta\overline{G}^{2}\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]}\right)^{1/2}=\left(\frac{1-\delta\mathbb{E}\left[\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]}{1+\delta\mathbb{E}\left[\left(\delta\overline{G}^{2}-1\right)\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]}\right)^{1/2},$

which agrees with $\eta_{\square}$ in Equation D.2. Therefore, it is verified
that Theorem 3.1 recovers Theorem D.2 whenever $a^{*}>a^{\circ}$ holds.

###  E.2 Toeplitz covariance

Consider covariance matrices with the following _Toeplitz_ structure. For
$\rho\in(0,1)$, let $\Sigma\in{\mathbb{R}}^{d\times d}$ be defined as
$\Sigma_{i,j}=\rho^{|i-j|}$ ($1\leq i,j\leq d$). Such matrices are known as
_Kac–Murdock–Szegö matrices_ [KMS53]. The entries of $\Sigma$ are the Fourier
coefficients of

$\displaystyle h(\theta;\rho)$
$\displaystyle=\frac{1-\rho^{2}}{1-2\rho\cos(\theta)+\rho^{2}}.$

Indeed,

$\displaystyle h(\theta;\rho)$
$\displaystyle=\sum_{i=-\infty}^{\infty}\rho^{|i|}e^{\mathrm{i}i\theta}.$

The eigenvalues of $\Sigma$ can be well approximated as follows [GS84, Chapter
5]: for any $i\in[d]$,

$\displaystyle\lambda_{i}(\Sigma)$
$\displaystyle=\frac{1-\rho^{2}}{1-2\rho\cos(\theta_{i})+\rho^{2}},$

where

$\displaystyle\frac{(i-1)\pi}{d+1}<\theta_{i}<\frac{i\pi}{d+1}.$

(See [Tre88] for more on this.) This allows us to access the limiting spectral
distribution of $\Sigma$. Indeed, Szegö’s distribution theorem [GS84, Chapter
5] asserts: for any continuous function $H\colon{\mathbb{R}}\to{\mathbb{R}}$,

$\displaystyle\lim_{d\to\infty}\frac{1}{d}\sum_{i=1}^{d}H(\lambda_{i}(\Sigma))$
$\displaystyle=\int_{0}^{1}H\left(\frac{1-\rho^{2}}{1-2\rho\cos(\alpha\pi)+\rho^{2}}\right)\mathrm{d}\alpha.$

In particular, the largest and smallest eigenvalues converge to
$\frac{1+\rho}{1-\rho}$ and $\frac{1-\rho}{1+\rho}$ respectively.

###  E.3 Circulant covariance

Another popular family of covariance structures is given by circulant
matrices. Specifically, consider a symmetric circulant matrix $\Sigma$
specified by
$c_{0},c_{1},c_{2},\cdots,c_{\left\lfloor\frac{d}{2}\right\rfloor}$:

$\displaystyle\Sigma$
$\displaystyle=\begin{bmatrix}c_{0}&c_{1}&\cdots&c_{2}&c_{1}\\\
c_{1}&c_{0}&c_{1}&&c_{2}\\\ \vdots&c_{1}&c_{0}&\ddots&\vdots\\\
c_{2}&&\ddots&\ddots&c_{1}\\\
c_{1}&c_{2}&\cdots&c_{1}&c_{0}\end{bmatrix}\in{\mathbb{R}}^{d\times d}.$

In words, the first row of $\Sigma$ is given by

$\displaystyle\begin{cases}(c_{1},c_{2},\cdots,c_{\frac{d-1}{2}},c_{\frac{d-1}{2}},\cdots,c_{2},c_{1})\in{\mathbb{R}}^{d},&\text{if
}d\text{ is odd}\\\
(c_{1},c_{2},\cdots,c_{\frac{d}{2}-1},c_{\frac{d}{2}},c_{\frac{d}{2}-1},\cdots,c_{2},c_{1})\in{\mathbb{R}}^{d},&\text{if
}d\text{ is even}\end{cases}.$

Then, for any $2\leq i\leq d$, the $i$-th row is obtained by circularly
shifting the $(i-1)$-st row to the right by one position. Let
$\\{\lambda_{0},\lambda_{1},\cdots,\lambda_{d-1}\\}$ denote the set of
eigenvalues of $\Sigma$. Then they admit the following description: for $0\leq
i\leq d-1$,

$\displaystyle\lambda_{i}$
$\displaystyle=\begin{cases}c_{0}+2\sum_{j=1}^{\frac{d-1}{2}}c_{j}\operatorname{\mathrm{Re}}(\omega^{ij}),&\text{if
}d\text{ is odd}\\\
c_{0}+2\sum_{j=1}^{\frac{d}{2}-1}c_{j}\operatorname{\mathrm{Re}}(\omega^{ij})+c_{\frac{d}{2}}\omega^{i\frac{d}{2}},&\text{if
}d\text{ is even}\end{cases},$ (E.3)

where $\omega=e^{2\pi\mathrm{i}/d}$ is a primitive $d$-th root of unity. We
caution the readers that $\\{\lambda_{i}\\}_{i=0}^{d-1}$ are _not_ listed in
descending/ascending order therefore the notation
$\\{\lambda_{i}(\Sigma)\\}_{i=1}^{d}$ is not used. However, we stick with such
parametrization since it is convenient for enumerating all eigenvalues.

In the experiments, we use the following special symmetric circulant
covariance matrix with a band of radius $\ell\leq\frac{d-1}{2}$ around the
diagonal. The first row is specified by $c_{0},c_{1}\in{\mathbb{R}}$:

$\displaystyle(c_{0},\underbracket{c_{1},\cdots,c_{1}}_{\ell},\underbracket{0,\cdots,0}_{d-2\ell-1},\underbracket{c_{1},\cdots,c_{1}}_{\ell})$
$\displaystyle\in{\mathbb{R}}^{d}.$

Using Equation E.3, we can derive the eigenvalues
$\\{\lambda_{0},\lambda_{1},\cdots,\lambda_{d-1}\\}$ of such matrices: for
$0\leq i\leq d-1$,

$\displaystyle\lambda_{i}$
$\displaystyle=c_{0}+2c_{1}\sum_{j=1}^{\ell}\operatorname{\mathrm{Re}}(\omega^{ij})=c_{0}+2c_{1}\sum_{j=1}^{\ell}\cos(2\pi
ij/d)=c_{0}+2c_{1}\frac{\sin(\ell\pi i/d)}{\sin(\pi i/d)}\cos((\ell+1)\pi
i/d).$

The first equality follows from
$e^{\mathrm{i}\theta}=\cos(\theta)+\mathrm{i}\sin(\theta)$ and the second one
follows from the formula

$\displaystyle\sum_{j=1}^{\ell}\cos(j\theta)$
$\displaystyle=\frac{\sin(\ell\theta/2)}{\sin(\theta/2)}\cos((\ell+1)\theta/2).$

##  Appendix F Proof of results in Section 6

###  F.1 Proof of Proposition 6.1

The decomposition of $U_{t}$ in Equation 6.9 and the expressions of
$\mu_{t},\sigma_{U,t}$ in Equations 6.10, 6.11, 6.12 and 6.13 can be easily
obtained from Equations 6.5 and 6.7 using the following elementary fact
regarding Gaussian random variables. If

$\displaystyle(G_{1},G_{2})\sim{\mathcal{N}}\left(0_{2},\begin{bmatrix}\sigma_{1,1}&\sigma_{1,2}\\\
\sigma_{1,2}&\sigma_{2,2}\end{bmatrix}\right),$

then their joint law can be realized as

$\displaystyle(G_{1},G_{2})\overset{\mathrm{d}}{=}\left(G_{1},\frac{\sigma_{1,2}}{\sigma_{1,1}}\,G_{1}+\sqrt{\sigma_{2,2}-\frac{\sigma_{1,2}^{2}}{\sigma_{1,1}}}\,W\right),$
(F.1)

where $W\sim{\mathcal{N}}(0,1)$ is independent of $G_{1}$.

To show Equation 6.14, we use the chain rule and Stein’s lemma (Proposition
G.2). We have:

$\displaystyle\chi_{t+1}$
$\displaystyle=\lim_{n\to\infty}\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\left[\frac{\partial}{\partial
G_{i}}\widetilde{g}_{t}(U_{t},G,\varepsilon)_{i}\right]$
$\displaystyle=\lim_{n\to\infty}\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\left[\frac{\partial}{\partial
G_{i}}g_{t}(U_{t};q(G,\varepsilon))_{i}\right]$
$\displaystyle=\lim_{n\to\infty}\frac{1}{n}\sum_{i=1}^{n}\left(\mathbb{E}\left[\frac{\partial}{\partial
G_{i}}g_{t}(\mu_{t}G+\sigma_{U,t}W_{U,t};q(G,\varepsilon))_{i}\right]-\mu_{t}\mathbb{E}\left[\frac{\partial}{\partial
U_{t,i}}g_{t}(U_{t};Y)_{i}\right]\right)$ (F.2)
$\displaystyle=\lim_{n\to\infty}\frac{1}{n}\sum_{i=1}^{n}\left(\frac{\delta}{\mathbb{E}\left[\overline{\Sigma}\right]}\mathbb{E}\left[G_{i}g_{t}(\mu_{t}G+\sigma_{U,t}W_{U,t};q(G,\varepsilon))_{i}\right]-\mu_{t}\mathbb{E}\left[\frac{\partial}{\partial
U_{t,i}}g_{t}(U_{t};Y)_{i}\right]\right)$ (F.3)
$\displaystyle=\frac{\delta}{\mathbb{E}\left[\overline{\Sigma}\right]}\lim_{n\to\infty}\frac{1}{n}\mathbb{E}\left[\left\langle
G,g_{t}(U_{t};Y)\right\rangle\right]-\mu_{t}\lim_{n\to\infty}\frac{1}{n}\mathbb{E}\left[\operatorname{div}_{U_{t}}g_{t}(U_{t};Y)\right].$

Equation F.2 follows from the chain rule of derivatives:

$\displaystyle\frac{\partial}{\partial
G_{i}}g_{t}(U_{t};q(G,\varepsilon))_{i}=\frac{\partial}{\partial
G_{i}}g_{t}(\mu_{t}G+\sigma_{U,t}W_{U,t};q(G,\varepsilon))_{i}$
$\displaystyle=\mu_{t}\frac{\partial}{\partial
U_{t,i}}g_{t}(U_{t};Y)_{i}+\frac{\partial}{\partial
G_{i}}g_{t}(U_{t};q(G,\varepsilon))_{i}.$

Equation F.3 is by Proposition G.2, noting that
$G\sim{\mathcal{N}}\left(0_{n},\frac{\mathbb{E}\left[\overline{\Sigma}\right]}{\delta}I_{n}\right)$.

###  F.2 Proof of Proposition 6.2

##### Reduction to graph-based AMP.

Define the a rescaled versions of $\widetilde{A}$ as
$\widecheck{A}\coloneqq\sqrt{\frac{n}{n+d}}\,\widetilde{A}\in{\mathbb{R}}^{n\times
d}$. Note that each entry of $\widecheck{A}$ is i.i.d. according to
${\mathcal{N}}(0,1/(n+d))$. Let $g\coloneqq\widetilde{A}\widetilde{x}^{*}$.
Consider a pair of matrix-valued iterates $p^{t}\in{\mathbb{R}}^{n\times 2}$
and $q^{t}\in{\mathbb{R}}^{d\times 2}$ defined as

$\displaystyle p^{t}$
$\displaystyle=\begin{bmatrix}\widecheck{u}^{t}&g\end{bmatrix}\in{\mathbb{R}}^{n\times
2},\quad
q^{t}=\begin{bmatrix}\widecheck{v}^{t}-\widecheck{\chi}_{t-1}\widetilde{x}^{*}&0_{d}\end{bmatrix}\in{\mathbb{R}}^{d\times
2},$ (F.4)

where $(\widecheck{u}^{t},\widecheck{v}^{t},\widecheck{\chi}_{t-1})_{t\geq
0}\subset{\mathbb{R}}^{n+d+1}$ will be specified later. For
$(i,j)\in[n]\times[2]$, we use $p_{j}^{t}\in{\mathbb{R}}^{n}$ and
$p_{i,j}^{t}\in{\mathbb{R}}$ to denote the $j$-th column and the $(i,j)$-th
entry of the matrix $p^{t}$, respectively. Similar notation is used for other
matrix-valued iterates. Consider also a pair of denoising functions
$\pi_{t}\colon{\mathbb{R}}^{d\times 3}\to{\mathbb{R}}^{d\times 2}$ and
$\rho_{t}\colon{\mathbb{R}}^{n\times 3}\to{\mathbb{R}}^{n\times 2}$ defined as

$\displaystyle\begin{split}\pi_{t}(q^{t};\widetilde{x}^{*})&=\sqrt{\frac{n+d}{n}}\begin{bmatrix}\widecheck{f}_{t}(q_{1}^{t}+\widecheck{\chi}_{t-1}\widetilde{x}^{*})&\widetilde{x}^{*}\end{bmatrix}\in{\mathbb{R}}^{d\times
2},\\\
\rho_{t}(p^{t};\varepsilon)&=\begin{bmatrix}\sqrt{\frac{n+d}{n}}\,\widecheck{g}_{t}(p_{1}^{t};q(p_{2}^{t};\varepsilon))&0_{n}\end{bmatrix}\in{\mathbb{R}}^{n\times
2},\end{split}$ (F.5)

where $(\widecheck{f}_{t},\widecheck{g}_{t})_{t\geq 0}$ will be specified
later. We claim that the iteration

$\displaystyle\begin{split}p^{t+1}&=\widecheck{A}\widetilde{q}^{t}-\widetilde{p}^{t-1}\ell_{t}^{\top},\quad\widetilde{p}^{t}=\rho_{t}(p^{t};\varepsilon),\quad\ell_{t}=\frac{1}{n+d}\sum_{i=1}^{d}\begin{bmatrix}\frac{\partial\pi_{t}(q^{t};\widetilde{x}^{*})_{i,1}}{\partial
q^{t}_{i,1}}&\frac{\partial\pi_{t}(q^{t};\widetilde{x}^{*})_{i,1}}{\partial
q^{t}_{i,2}}\\\ \frac{\partial\pi_{t}(q^{t};\widetilde{x}^{*})_{i,2}}{\partial
q^{t}_{i,1}}&\frac{\partial\pi_{t}(q^{t};\widetilde{x}^{*})_{i,2}}{\partial
q^{t}_{i,2}}\end{bmatrix},\\\
q^{t+1}&=\widecheck{A}^{\top}\widetilde{p}^{t}-\widetilde{q}^{t-1}m_{t}^{\top},\quad\widetilde{q}^{t}=\pi_{t}(q^{t};\widetilde{x}^{*}),\quad
m_{t}=\frac{1}{n+d}\sum_{i=1}^{n}\begin{bmatrix}\frac{\partial\rho_{t}(p^{t};\varepsilon)_{i,1}}{\partial
p^{t}_{i,1}}&\frac{\partial\rho_{t}(p^{t};\varepsilon)_{i,1}}{\partial
p^{t}_{i,2}}\\\ \frac{\partial\rho_{t}(p^{t};\varepsilon)_{i,2}}{\partial
p^{t}_{i,1}}&\frac{\partial\rho_{t}(p^{t};\varepsilon)_{i,2}}{\partial
p^{t}_{i,2}}\end{bmatrix},\end{split}$ (F.6)

initialized with $\pi_{-1}=0,\rho_{-1}=0$ and
$p^{0}=\begin{bmatrix}\widecheck{u}^{0}&g\end{bmatrix},q^{0}=\begin{bmatrix}\widecheck{v}^{0}&0_{d}\end{bmatrix}$
(for some
$\widecheck{u}^{0}\in{\mathbb{R}}^{n},\widecheck{v}^{0}\in{\mathbb{R}}^{d}$ to
be specified later), is equivalent to the following iteration:

$\displaystyle\begin{split}\widecheck{u}^{t+1}&=\widetilde{A}\widecheck{f}_{t}(\widecheck{v}^{t})-\widecheck{b}_{t}\widecheck{g}_{t-1}(\widecheck{u}^{t-1};y),\quad\widecheck{b}_{t}=\frac{1}{n}\sum_{i=1}^{d}\frac{\partial\widecheck{f}_{t}(\widecheck{v}^{t})_{i}}{\partial\widecheck{v}_{i}^{t}},\\\
\widecheck{v}^{t+1}&=\widetilde{A}^{\top}\widecheck{g}_{t}(\widecheck{u}^{t};y)-\widecheck{c}_{t}\widecheck{f}_{t-1}(\widecheck{v}^{t-1}),\quad\widecheck{c}_{t}=\frac{1}{n}\sum_{i=1}^{n}\frac{\partial\widecheck{g}_{t}(\widecheck{u}^{t};y)_{i}}{\partial\widecheck{u}_{i}^{t}},\end{split}$
(F.7)

initialized with $\widecheck{f}_{-1}=0,\widecheck{g}_{-1}=0$ and
$\widecheck{u}^{0}\in{\mathbb{R}}^{n},\widecheck{v}^{0}\in{\mathbb{R}}^{d}$.

Let us verify the equivalence. By the design of the matrix-valued iterates in
Equation F.4 and the matrix-valued denoisers in Equation F.5, we have

$\displaystyle\widetilde{p}^{t}$
$\displaystyle=\rho_{t}\left(\begin{bmatrix}\widecheck{u}^{t}&g\end{bmatrix};\varepsilon\right)=\begin{bmatrix}\sqrt{\frac{n+d}{n}}\,\widecheck{g}_{t}(\widecheck{u}^{t};q(g;\varepsilon))&0_{n}\end{bmatrix}=\begin{bmatrix}\sqrt{\frac{n+d}{n}}\,\widecheck{g}_{t}(\widecheck{u}^{t};y)&0_{n}\end{bmatrix},$
$\displaystyle\widetilde{q}^{t}$
$\displaystyle=\pi_{t}\left(\begin{bmatrix}\widecheck{v}^{t}-\widecheck{\chi}_{t-1}\widetilde{x}^{*}&0_{d}\end{bmatrix};\widetilde{x}^{*}\right)=\sqrt{\frac{n+d}{n}}\begin{bmatrix}\widecheck{f}_{t}(\widecheck{v}^{t})&\widetilde{x}^{*}\end{bmatrix}.$

Furthermore, by chain rule of derivatives, the matrices $\ell_{t},m_{t}$
specialize to

$\displaystyle\ell_{t}$
$\displaystyle=\frac{1}{n+d}\sum_{i=1}^{d}\begin{bmatrix}\sqrt{\frac{n+d}{n}}\frac{\partial\widecheck{f}_{t}(\widecheck{v}^{t})_{i}}{\partial\widecheck{v}_{i}^{t}}&0\\\
0&0\end{bmatrix}=\sqrt{\frac{n}{n+d}}\begin{bmatrix}\frac{1}{n}\sum_{i=1}^{d}\frac{\partial\widecheck{f}_{t}(\widecheck{v}^{t})_{i}}{\partial\widecheck{v}_{i}^{t}}&0\\\
0&0\end{bmatrix}=\sqrt{\frac{n}{n+d}}\begin{bmatrix}\widecheck{b}_{t}&0\\\
0&0\end{bmatrix},$ $\displaystyle m_{t}$
$\displaystyle=\frac{1}{n+d}\sum_{i=1}^{n}\begin{bmatrix}\sqrt{\frac{n+d}{n}}\frac{\partial\widecheck{g}_{t}(\widecheck{u}^{t};y)_{i}}{\partial\widecheck{u}_{i}^{t}}&\sqrt{\frac{n+d}{n}}\frac{\partial\widecheck{g}_{t}(\widecheck{u}^{t};q(g;\varepsilon))_{i}}{\partial
g_{i}}\\\
0&0\end{bmatrix}=\sqrt{\frac{n}{n+d}}\begin{bmatrix}\widecheck{c}_{t}&\widecheck{\chi}_{t}\\\
0&0\end{bmatrix}.$

Using these expressions, we write the iteration in Equation F.6 as

$\displaystyle\begin{bmatrix}\widecheck{u}^{t+1}&g\end{bmatrix}$
$\displaystyle=\sqrt{\frac{n+d}{n}}\widecheck{A}\begin{bmatrix}\widecheck{f}_{t}(\widecheck{v}^{t})&\widetilde{x}^{*}\end{bmatrix}-\begin{bmatrix}\sqrt{\frac{n+d}{n}}\,\widecheck{g}_{t-1}(\widecheck{u}^{t-1};y)&0_{n}\end{bmatrix}\sqrt{\frac{n}{n+d}}\begin{bmatrix}\widecheck{b}_{t}&0\\\
0&0\end{bmatrix},$
$\displaystyle\begin{bmatrix}\widecheck{v}^{t+1}-\widecheck{\chi}_{t}\widetilde{x}^{*}&0_{d}\end{bmatrix}$
$\displaystyle=\widecheck{A}^{\top}\begin{bmatrix}\sqrt{\frac{n+d}{n}}\,\widecheck{g}_{t}(\widecheck{u}^{t};y)&0_{n}\end{bmatrix}-\sqrt{\frac{n+d}{n}}\begin{bmatrix}\widecheck{f}_{t-1}(\widecheck{v}^{t-1})&\widetilde{x}^{*}\end{bmatrix}\sqrt{\frac{n}{n+d}}\begin{bmatrix}\widecheck{c}_{t}&0\\\
\widecheck{\chi}_{t}&0\end{bmatrix}.$

Expanding the above equations into vector forms and using the relation between
$\widetilde{A}$ and $\widecheck{A}$, we obtain:

$\displaystyle\widecheck{u}^{t+1}$
$\displaystyle=\widetilde{A}\widecheck{f}_{t}(\widecheck{v}^{t})-\widecheck{b}_{t}\widecheck{g}_{t-1}(\widecheck{u}^{t-1};y),\quad
g=\widetilde{A}\widetilde{x}^{*},$ $\displaystyle\widecheck{v}^{t+1}$
$\displaystyle=\widetilde{A}^{\top}\widecheck{g}_{t}(\widecheck{u}^{t};y)-\widecheck{c}_{t}\widecheck{f}_{t-1}(\widecheck{v}^{t-1}),$

which matches Equation F.7 and the definition of $g$.

##### Proof of state evolution.

The iteration in Equation F.6 is an instance of the abstract graph-based AMP
iteration proposed in [GB21]. To see this, consider a simple graph on two
vertices $v_{1},v_{2}$ with two directed edges $\vec{e}=(v_{1},v_{2})$ to
$\reflectbox{$\vec{\reflectbox{$e$}}$}=(v_{2},v_{1})$ between them. The tuple
$(\widetilde{A},p^{t},\pi_{t})$ is associated with the edge $\vec{e}$ and the
tuple $(\widetilde{A}^{\top},q^{t},\rho_{t})$ is associated with
$\vec{\reflectbox{$e$}}$ . We record below the state evolution results in
[GB21, Section 3.3] for our special case of Equation F.6, and then translate
them to Equation F.7. For each $t\geq 1$, define two sequences of random
matrices

$\displaystyle(P_{0},P_{1},\cdots,P_{t})$
$\displaystyle\sim{\mathcal{N}}(0_{2n(t+1)},\Theta_{t}\otimes
I_{n}),\quad(Q_{0},Q_{1},\cdots,Q_{t})\sim{\mathcal{N}}(0_{2d(t+1)},\Xi_{t}\otimes
I_{d}),$ (F.8)

where $P_{r}\in{\mathbb{R}}^{n\times 2},Q_{r}\in{\mathbb{R}}^{d\times 2}$
($0\leq r\leq t$), and the entries of the covariance matrices
$\Theta_{t},\Xi_{t}\in{\mathbb{R}}^{2(t+1)\times 2(t+1)}$ are specified
recursively as follows: for $0\leq r,s\leq t$,

$\displaystyle(\Theta_{t})_{r+1,s+1}$
$\displaystyle=\lim_{n\to\infty}\frac{1}{n+d}\mathbb{E}\left[\pi_{r}(Q_{r};\widetilde{X}^{*})^{\top}\pi_{s}(Q_{s}\widetilde{X}^{*})\right]\in{\mathbb{R}}^{2\times
2},$ $\displaystyle(\Xi_{t})_{r+1,s+1}$
$\displaystyle=\lim_{n\to\infty}\frac{1}{n+d}\mathbb{E}\left[\rho_{r}(P_{r};\varepsilon)^{\top}\rho_{s}(P_{s};\varepsilon)\right]\in{\mathbb{R}}^{2\times
2}.$

The notation $(P_{0},P_{1},\cdots,P_{t})\in({\mathbb{R}}^{n\times 2})^{t+1}$
should be interpreted as a $2n(t+1)$-dimensional vector given by

$\displaystyle\begin{bmatrix}(P_{0})_{1}\\\ (P_{0})_{2}\\\ \vdots\\\
(P_{t})_{1}\\\ (P_{t})_{2}\end{bmatrix}$

where $(P_{r})_{j}$ ($0\leq r\leq t,j\in\\{1,2\\}$) denotes the $j$-th column
of $P_{r}\in{\mathbb{R}}^{n\times 2}$. The notation
$(Q_{0},Q_{1},\cdots,Q_{t})\in({\mathbb{R}}^{d\times 2})^{t+1}$ should be
interpreted in a similar way. Accordingly,
$\Theta_{t},\Xi_{t}\in{\mathbb{R}}^{2(t+1)\times 2(t+1)}$ are block matrices
whose $(r+1,s+1)$-st ($0\leq r,s\leq t$) block has size $2\times 2$.

The state evolution result in [GB21, Theorem 1 and Section 3.3] asserts that
for any uniformly pseudo-Lipschitz functions
$h_{1}\colon{\mathbb{R}}^{2n(t+1)}\to{\mathbb{R}},h_{2}\colon{\mathbb{R}}^{2d(t+1)}\to{\mathbb{R}}$
of finite order,

$\displaystyle\begin{split}\operatorname*{p-lim}_{n\to\infty}h_{1}(p^{0},p^{1},\cdots,p^{t})-\mathbb{E}\left[h_{1}(P_{0},P_{1},\cdots,P_{t})\right]&=0,\\\
\operatorname*{p-lim}_{d\to\infty}h_{2}(q^{0},q^{1},\cdots,q^{t})-\mathbb{E}\left[h_{2}(Q_{0},Q_{1},\cdots,Q_{t})\right]&=0.\end{split}$
(F.9)

With the reduction in Equations F.4 and F.5, the state evolution iterates
become

$\displaystyle P_{t}$
$\displaystyle=\begin{bmatrix}\widecheck{U}_{t}&G\end{bmatrix},\quad
Q_{t}=\begin{bmatrix}\widecheck{V}_{t}-\widecheck{\chi}_{t-1}\widetilde{X}^{*}&0_{d}\end{bmatrix},$

whose covariance structure specializes to

$\displaystyle(\Theta_{t})_{r+1,s+1}$
$\displaystyle=\lim_{n\to\infty}\frac{1}{n+d}\mathbb{E}\left[\frac{n+d}{n}\begin{bmatrix}\widecheck{f}_{r}(\widecheck{V}_{r})&\widetilde{x}^{*}\end{bmatrix}^{\top}\begin{bmatrix}\widecheck{f}_{s}(\widecheck{V}_{s})&\widetilde{x}^{*}\end{bmatrix}\right]$
$\displaystyle=\begin{bmatrix}\lim\limits_{n\to\infty}\frac{1}{n}\mathbb{E}\left[\widecheck{f}_{r}(\widecheck{V}_{r})^{\top}\widecheck{f}_{s}(\widecheck{V}_{s})\right]&\lim\limits_{n\to\infty}\frac{1}{n}\mathbb{E}\left[\widecheck{f}_{r}(\widecheck{V}_{r})^{\top}\widetilde{X}^{*}\right]\\\
\lim\limits_{n\to\infty}\frac{1}{n}\mathbb{E}\left[\widecheck{f}_{s}(\widecheck{V}_{s})^{\top}\widetilde{X}^{*}\right]&\lim\limits_{n\to\infty}\frac{1}{n}\mathbb{E}\left[(\widetilde{X}^{*})^{\top}\widetilde{X}^{*}\right]\end{bmatrix},$
(F.10) $\displaystyle(\Xi_{t})_{r+1,s+1}$
$\displaystyle=\lim_{n\to\infty}\frac{1}{n+d}\mathbb{E}\left[\begin{bmatrix}\sqrt{\frac{n+d}{n}}\widecheck{g}_{r}(\widecheck{U}_{r};Y)&0_{n}\end{bmatrix}^{\top}\begin{bmatrix}\sqrt{\frac{n+d}{n}}\widecheck{g}_{s}(\widecheck{U}_{s};Y)&0_{n}\end{bmatrix}\right]$
$\displaystyle=\begin{bmatrix}\lim\limits_{n\to\infty}\frac{1}{n}\mathbb{E}\left[\widecheck{g}_{r}(\widecheck{U}_{r};Y)^{\top}\widecheck{g}_{s}(\widecheck{U}_{s};Y)\right]&0\\\
0&0\end{bmatrix}.$ (F.11)

Reorganizing the elements of $P_{t},Q_{t}$ and $\Theta_{t},\Xi_{t}$, we obtain

$\displaystyle(G,\widecheck{U}_{0},\cdots,\widecheck{U}_{t})\sim{\mathcal{N}}(0_{n(t+2)},\widecheck{\Theta}_{t}\otimes
I_{n}),$
$\displaystyle(\widecheck{V}_{0}-\widecheck{\chi}_{-1}\widetilde{X}^{*},\cdots,\widecheck{V}_{t}-\widecheck{\chi}_{t-1}\widetilde{X}^{*})\sim{\mathcal{N}}(0_{d(t+1)},\widecheck{\Xi}_{t}\otimes
I_{d}),$ (F.12)

where the entries of
$\widecheck{\Theta}_{t}\in{\mathbb{R}}^{(t+2)\times(t+2)}$ and
$\widecheck{\Xi}_{t}\in{\mathbb{R}}^{(t+1)\times(t+1)}$ are obtained as
follows from $\Theta_{t}$ and $\Xi_{t}$. Recalling that each entry
$(\Theta_{t})_{r,s},(\Xi_{t})_{r,s}$ of $\Theta_{t},\Xi_{t}$, respectively, is
itself a $2\times 2$ matrix, we use
$((\Theta_{t})_{r,s})_{i,j},((\Xi_{t})_{r,s})_{i,j}$ to denote the $(i,j)$-th
($i,j\in\\{1,2\\}$) entry of $(\Theta_{t})_{r,s},(\Xi_{t})_{r,s}$,
respectively.

$\displaystyle(\widecheck{\Theta}_{t})_{1,1}=((\Theta_{t})_{1,1})_{2,2},\quad(\widecheck{\Theta}_{t})_{1,s}=((\Theta_{t})_{s-1,s-1})_{1,2},\quad
2\leq s\leq t+2,$
$\displaystyle(\widecheck{\Theta}_{t})_{r,s}=(\widecheck{\Theta}_{t})_{s,r}=((\Theta_{t})_{r-1,s-1})_{1,1},\quad
2\leq r\leq s\leq t+2,$
$\displaystyle(\widecheck{\Xi}_{t})_{r,s}=(\widecheck{\Xi}_{t})_{s,r}=((\Xi_{t})_{r,s})_{1,1},\quad
1\leq r\leq s\leq t+1.$

We further transform $\widecheck{\Theta}_{t}$ by introducing
$\widecheck{\Omega}_{t}\in{\mathbb{R}}^{2\times
2},\widecheck{\Phi}_{t}\in{\mathbb{R}}^{(t+1)\times(t+1)}$. First, we have
$(G,\widecheck{U}_{t})\sim{\mathcal{N}}(0_{2},\widecheck{\Omega}_{t})$ where

$\displaystyle\widecheck{\Omega}_{t}$
$\displaystyle=\begin{bmatrix}(\widecheck{\Theta}_{t})_{1,1}&(\widecheck{\Theta}_{t})_{1,t+2}\\\
(\widecheck{\Theta}_{t})_{1,t+2}&(\widecheck{\Theta}_{t})_{t+2,t+2}\end{bmatrix}\in{\mathbb{R}}^{2\times
2}.$ (F.13)

Next, applying the representation in Equation 6.9 to $(G,\widecheck{U}_{t})$,
we write
$\widecheck{U}_{t}=\widecheck{\mu}_{t}G+\widecheck{\sigma}_{U,t}\widecheck{W}_{U,t}$.
Here $\widecheck{\mu}_{t}$ can be derived in a way similar to Proposition 6.1:

$\displaystyle\widecheck{\mu}_{t}$
$\displaystyle=\frac{(\widecheck{\Theta}_{t})_{1,t+2}}{(\widecheck{\Theta}_{t})_{1,1}}=\frac{((\Theta_{t})_{t+1,t+1})_{1,2}}{(\widecheck{\Theta}_{t})_{1,1}}=\frac{\delta}{\mathbb{E}\left[\overline{\Sigma}\right]}\lim\limits_{n\to\infty}\frac{1}{n}\mathbb{E}\left[\widecheck{f}_{t}(\widecheck{V}_{t})^{\top}\widetilde{X}^{*}\right],$
(F.14)

where the last equality is obtained by recalling Equation F.10. Moreover,
$(\widecheck{\sigma}_{U,0}\widecheck{W}_{U,0},\cdots,\widecheck{\sigma}_{U,t}\widecheck{W}_{U,t})\sim{\mathcal{N}}(0_{n(t+1)},\widecheck{\Phi}_{t}\otimes
I_{n})$ are jointly Gaussian whose covariance can be derived from
$\widecheck{\Theta}_{t}$. For any $0\leq r,s\leq t$,

$\displaystyle(\widecheck{\Theta}_{t})_{r+2,s+2}=\frac{1}{n}\mathbb{E}\left[\left\langle\widecheck{U}_{r},\widecheck{U}_{s}\right\rangle\right]$
$\displaystyle=\widecheck{\mu}_{r}\widecheck{\mu}_{s}(\widecheck{\Theta}_{t})_{1,1}+\frac{1}{n}\mathbb{E}\left[\left\langle\widecheck{\sigma}_{U,r}\widecheck{W}_{U,r},\widecheck{\sigma}_{U,s}\widecheck{W}_{U,s}\right\rangle\right],$

from which we obtain

$\displaystyle(\widecheck{\Phi}_{t})_{r+1,s+1}$
$\displaystyle=\frac{1}{n}\mathbb{E}\left[\left\langle\widecheck{\sigma}_{U,r}\widecheck{W}_{U,r},\widecheck{\sigma}_{U,s}\widecheck{W}_{U,s}\right\rangle\right]=(\widecheck{\Theta}_{t})_{r+2,s+2}-\widecheck{\mu}_{r}\widecheck{\mu}_{s}(\widecheck{\Theta}_{t})_{1,1}$
$\displaystyle=((\Theta_{t})_{r+1,s+1})_{1,1}-\frac{((\Theta_{t})_{r+1,r+1})_{1,2}((\Theta_{t})_{s+1,s+1})_{1,2}}{((\Theta_{t})_{1,1})_{2,2}}.$
(F.15)

We claim that the the above expression equals

$\displaystyle\lim_{n\to\infty}\frac{1}{n}\mathbb{E}\left[\left\langle\widecheck{f}_{r}(\widecheck{V}_{r})-\widecheck{\mu}_{r}\widetilde{X}^{*},\widecheck{f}_{s}(\widecheck{V}_{s})-\widecheck{\mu}_{s}\widetilde{X}^{*}\right\rangle\right],$
(F.16)

Indeed,

$\displaystyle\phantom{=}~{}\lim_{n\to\infty}\frac{1}{n}\mathbb{E}\left[\left\langle\widecheck{f}_{r}(\widecheck{V}_{r})-\widecheck{\mu}_{r}\widetilde{X}^{*},\widecheck{f}_{s}(\widecheck{V}_{s})-\widecheck{\mu}_{s}\widetilde{X}^{*}\right\rangle\right]$
$\displaystyle=\lim_{n\to\infty}\frac{1}{n}\left(\mathbb{E}\left[\left\langle\widecheck{f}_{r}(\widecheck{V}_{r}),\widecheck{f}_{s}(\widecheck{V}_{s})\right\rangle\right]-\widecheck{\mu}_{s}\mathbb{E}\left[\left\langle\widecheck{f}_{r}(\widecheck{V}_{r}),\widetilde{X}^{*}\right\rangle\right]-\widecheck{\mu}_{r}\mathbb{E}\left[\left\langle\widecheck{f}_{s}(\widecheck{V}_{s}),\widetilde{X}^{*}\right\rangle\right]+\widecheck{\mu}_{r}\widecheck{\mu}_{s}\mathbb{E}\left[\left\langle\widetilde{X}^{*},\widetilde{X}^{*}\right\rangle\right]\right)$
$\displaystyle=\lim_{n\to\infty}\frac{1}{n}\mathbb{E}\left[\left\langle\widecheck{f}_{r}(\widecheck{V}_{r}),\widecheck{f}_{s}(\widecheck{V}_{s})\right\rangle\right]-\frac{\delta}{\mathbb{E}\left[\overline{\Sigma}\right]}\left(\lim_{n\to\infty}\frac{1}{n}\mathbb{E}\left[\left\langle\widecheck{f}_{r}(\widecheck{V}_{r}),\widetilde{X}^{*}\right\rangle\right]\right)\left(\lim_{n\to\infty}\frac{1}{n}\mathbb{E}\left[\left\langle\widecheck{f}_{s}(\widecheck{V}_{s}),\widetilde{X}^{*}\right\rangle\right]\right),$

which agrees with Equation F.15. In the last equality, we use Equation F.14.

Finally, for $t\geq 0$, let
$\widecheck{\sigma}_{V,t}\widecheck{W}_{V,t}\coloneqq\widecheck{V}_{t}-\widecheck{\chi}_{t-1}\widetilde{X}^{*}$
where $\widecheck{W}_{V,t}\sim{\mathcal{N}}(0,1)$ is independent of
$\widetilde{X}^{*}$. From Equation F.12, we have
$(\widecheck{\sigma}_{V,0}\widecheck{W}_{V,0},\cdots,\widecheck{\sigma}_{V,t}\widecheck{W}_{V,t})\sim{\mathcal{N}}(0_{d(t+1)},\widecheck{\Xi}_{t}\otimes
I_{d})$ where $\widecheck{\Xi}_{t}$ has entries

$\displaystyle(\widecheck{\Xi}_{t})_{r+1,s+1}$
$\displaystyle=((\Xi_{t})_{r+1,s+1})_{1,1}=\lim_{n\to\infty}\frac{1}{n}\mathbb{E}\left[\left\langle\widecheck{g}_{r}(\widecheck{U}_{r};Y),\widecheck{g}_{s}(\widecheck{U}_{s};Y)\right\rangle\right].$
(F.17)

With $(\widecheck{\mu}_{t},\widecheck{\sigma}_{U,t})$ (or equivalently
$\widecheck{\Omega}_{t}$),
$\widecheck{\Phi}_{t},\widecheck{\chi}_{t-1},\widecheck{\Xi}_{t}$ at hand,
Equation F.9 naturally translates to the following state evolution result. For
any uniformly pseudo-Lipschitz functions
$h_{1}\colon{\mathbb{R}}^{n(t+2)}\to{\mathbb{R}},h_{2}\colon{\mathbb{R}}^{d(t+1)}\to{\mathbb{R}}$
of finite order,

$\displaystyle\begin{split}\operatorname*{p-lim}_{n\to\infty}h_{1}(g,\widecheck{u}_{0},\cdots,\widecheck{u}_{t})-\mathbb{E}\left[h_{1}(G,\widecheck{U}_{0},\cdots,\widecheck{U}_{t})\right]&=0,\\\
\operatorname*{p-lim}_{d\to\infty}h_{2}(\widecheck{v}_{0},\cdots,\widecheck{v}_{t})-\mathbb{E}\left[h_{2}(\widecheck{V}_{0},\cdots,\widecheck{V}_{t})\right]&=0.\end{split}$
(F.18)

##### Change of variables.

Note that the AMP iteration in Equation F.7 is almost the same as that in
Equation 5.1 albeit with a difference in time indices. Indeed, the following
relabellling maps Equation F.7 to Equation 5.1 precisely:

$\begin{gathered}\widecheck{u}^{2t-1}=u^{t-1},\quad\widecheck{v}^{2t}=v^{t},\quad
t\geq 1,\\\
\widecheck{u}^{0}=0_{n},\quad\widecheck{f}_{0}(\widecheck{v}^{0})=\widetilde{v}^{0},\\\
\widecheck{g}_{2t-1}=g_{t},\quad\widecheck{g}_{2t}=0,\quad\widecheck{f}_{2t-1}=0,\quad\widecheck{f}_{2t}=f_{t},\quad\widecheck{\chi}_{2t-2}=0,\quad\widecheck{\chi}_{2t-1}=\chi_{t},\quad
t\geq 1,\\\
\widecheck{g}_{0}=0,\quad\widecheck{f}_{0}=0,\quad\widecheck{\chi}_{-1}=0.\end{gathered}$
(F.19)

The change of indices above is similar to that presented in [GB21, Appendix
A].

The change of time index in Equation F.19 also maps respectively
$(\widecheck{\mu}_{2t-1},\widecheck{\sigma}_{U,2t-1})$ (or equivalently
$\widecheck{\Omega}_{2t-1}$),
$\widecheck{\Phi}_{2t-1},\widecheck{\chi}_{2t-1},\widecheck{\Xi}_{2t}$ in
Equations F.13, F.14, F.15 and F.17 to $(\mu_{t},\sigma_{U,t})$ (or
equivalently $\Omega_{t}$), $\Phi_{t},\chi_{t},\Psi_{t}$ in Equations 6.7,
6.12, 6.16, 6.17 and 6.18. Therefore, the convergence result in Equation F.18
translates to Equation 6.19, which completes the whole proof of Proposition
6.2.

##  Appendix G Auxiliary lemmas

######  Proposition G.1 ($x_{1}>0$).

Let $x_{1}$ be defined in Equation 3.9. Then $x_{1}>0$.

###### Proof.

By definition, we have

$\displaystyle x_{1}$
$\displaystyle=\frac{1}{\mathbb{E}\left[\overline{\Sigma}\right]^{2}}\mathbb{E}\left[\overline{G}^{2}\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]\mathbb{E}\left[\frac{\overline{\Sigma}^{2}}{\gamma^{*}-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a^{*}-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}}\right]^{2}$
$\displaystyle\phantom{=}~{}-\frac{1}{\delta\mathbb{E}\left[\overline{\Sigma}\right]}\mathbb{E}\left[\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]\mathbb{E}\left[\frac{\overline{\Sigma}^{2}}{\gamma^{*}-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a^{*}-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}}\right]^{2}$
$\displaystyle\phantom{=}~{}+\frac{1}{\delta}\mathbb{E}\left[\left(\frac{{\mathcal{T}}(\overline{Y})}{a^{*}-{\mathcal{T}}(\overline{Y})}\right)^{2}\right]\mathbb{E}\left[\frac{\overline{\Sigma}^{3}}{\left(\gamma^{*}-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a^{*}-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}\right)^{2}}\right].$

The first term is strictly positive. It suffices to show that the sum of the
last two terms is non-negative. This follows from the Cauchy–Schwarz
inequality:

$\displaystyle\mathbb{E}\left[\frac{\overline{\Sigma}^{2}}{\gamma^{*}-\mathbb{E}\left[\frac{{\mathcal{T}}(\overline{Y})}{a^{*}-{\mathcal{T}}(\overline{Y})}\right]\overline{\Sigma}}\right]^{2}$