Fundamental Limits of Weak Recovery with Applications to Phase Retrieval

In phase retrieval, we want to recover an unknown signal \({{\varvec{x}}}\in {{\mathbb {C}}}^d\) from n quadratic measurements of the form \(y_i = |\langle {{\varvec{a}}}_i,{{\varvec{x}}}\rangle |^2+w_i\), where \({{\varvec{a}}}_i\in {{\mathbb {C}}}^d\) are known sensing vectors and \(w_i\) is measurement noise. We ask the following weak recovery question: What is the minimum number of measurements n needed to produce an estimator \({\hat{{{\varvec{x}}}}}({{\varvec{y}}})\) that is positively correlated with the signal \({{\varvec{x}}}\)? We consider the case of Gaussian vectors \({{\varvec{a}}}_i\). We prove that—in the high-dimensional limit—a sharp phase transition takes place, and we locate the threshold in the regime of vanishingly small noise. For \(n\le d-o(d)\), no estimator can do significantly better than random and achieve a strictly positive correlation. For \(n\ge d+o(d)\), a simple spectral estimator achieves a positive correlation. Surprisingly, numerical simulations with the same spectral estimator demonstrate promising performance with realistic sensing matrices. Spectral methods are used to initialize non-convex optimization algorithms in phase retrieval, and our approach can boost the performance in this setting as well. Our impossibility result is based on classical information-theoretic arguments. The spectral algorithm computes the leading eigenvector of a weighted empirical covariance matrix. We obtain a sharp characterization of the spectral properties of this random matrix using tools from free probability and generalizing a recent result by Lu and Li. Both the upper bound and lower bound generalize beyond phase retrieval to measurements \(y_i\) produced according to a generalized linear model. As a by-product of our analysis, we compare the threshold of the proposed spectral method with that of a message passing algorithm.

1. This gap is not due to the looseness of our lower bound. Indeed, by using the result of [6], one can show that the actual information-theoretic threshold is finite.

We would like to thank the anonymous reviewers for their helpful comments.

Authors and Affiliations

1. Department of Electrical Engineering, Stanford University, Packard Building 239, 350 Serra Mall, Stanford, CA, 94305, USA

   Marco Mondelli

2. Department of Electrical Engineering, Stanford University, Packard Building 272, 350 Serra Mall, Stanford, CA, 94305, USA

   Andrea Montanari

3. Department of Statistics, Stanford University, 390 Serra Mall, Stanford, CA, 94305, USA

   Andrea Montanari

Corresponding author

Correspondence to Marco Mondelli.

Emmanuel Candes.

M. Mondelli was supported by an Early Postdoc.Mobility fellowship from the Swiss National Science Foundation. A. Montanari was partially supported by Grants NSF DMS-1613091 and NSF CCF-1714305.

A Proof of Corollary 1

We start by providing in Lemma 6 a less compact, but more explicit form of expression (10). This more explicit expression is employed to prove Lemma 7, which yields the value of \(\delta _{\ell }\) for the case of phase retrieval. Finally, we provide the proof of Corollary 1.

Lemma 6

(Explicit formula for f(m)—complex case) Consider the function \(f:[0, 1]\rightarrow {\mathbb {R}}\) defined in (10). Then, f(m) is given by the following expression:

(144)

where \(I_0\) denotes the modified Bessel function of the first kind, given by

Proof

Let us rewrite G as

i.e., \(G^{(\mathrm R)}\) and \(G^{(\mathrm I)}\) are i.i.d. Gaussian random variables with mean 0 and variance 1 / 2. Set

Then, R follows a Rayleigh distribution with scale parameter \(1/\sqrt{2}\), and hence

Let us rewrite \((G_{1}, G_{2})\) as

with

and consider the following change in variables:

Then, after some algebra, we have that

By writing \((\mathfrak {R}{(c)}, \mathfrak {I}{(c)})=(|c|\cos \theta _c, |c|\sin \theta _c)\) and by using definition (145), we can further simplify the RHS of (147) as

From (146) and (148), the claim easily follows. \(\square \)

Lemma 7

(Computation of \(\delta _{\ell }\) for phase retrieval) Computation of \(\delta _{\ell }\) for Phase Retrieval Let \(\delta _{\ell }(\sigma ^2)\) be defined as in (13) and assume that the distribution \(p(\cdot \mid |G|)\) appearing in (10) is given by (9). Then,

Proof

For the special case of phase retrieval, it is possible to compute explicitly the function f(m) defined in (10) and simplified in Lemma 6. Indeed,

(150)

where in (a) we do the change in variables \(z= r^2\); in (b) we use definition (9) and we define \(H(x)=1\) if \(x\ge 0\) and \(H(x)=0\) otherwise; and in (c) we define \(Z\sim {\textsf {N}}(y, \sigma ^2)\). In the limit \(\sigma ^2\rightarrow 0\), we have that

by Lebesgue’s dominated convergence theorem. Similarly,

where in (a) we do the change in variables \(z_1= r_1^2\) and \(z_2= r_2^2\); in (b) we use definition (9) and we define \(H(x)=1\) if \(x\ge 0\) and \(H(x)=0\) otherwise; and in (c) we define \((Z_1, Z_2)\sim _{i.i.d.} {\textsf {N}}(y, \sigma ^2)\). In the limit \(\sigma ^2\rightarrow 0\), we have that

by Lebesgue’s dominated convergence theorem. As a result, by using (145), we obtain that

Consequently,

which implies the desired result. \(\square \)

Proof (Proof of Corollary 1)

We follow the proof of Theorem 1 presented in Sect. 4. The first step is exactly the same, i.e., by applying Lemma 1, we show that (68) holds. On the contrary, the second step requires some modifications, since the definition of the error metric is different. In particular, we will prove that

Furthermore, we have that

(153)

where in (a) we use the triangle inequality; in (b) we use that \({\mathbb {E}} \left\{ {{\varvec{X}}}{{\varvec{X}}}^*\right\} ={{\varvec{I}}}_d\) by Lemma 12; in (c) we use that, for any matrix \({{\varvec{A}}}\), \(\left| \left| {{\varvec{A}}}\right| \right| _F=\sqrt{\mathrm{trace}({{\varvec{A}}}{{\varvec{A}}}^*)}\); and in (d) we use that \({{\mathbb {E}}}\left\{ \mathrm{trace}\left( {{\varvec{X}}}{{\varvec{X}}}^*{{\varvec{X}}}{{\varvec{X}}}^*\right) \right\} ={{\mathbb {E}}}\left\{ \left| \left| {{\varvec{X}}}\right| \right| ^4\right\} =d^2\). By applying (152) and (153), the proof of Corollary 1 is complete.

Let us now give the proof of (152). Similarly to (71), we have that

where we define \(\varphi _{\mathrm{PR}}(x)=x\) for \(|x|\le M\), and \(\varphi _{\mathrm{PR}}(x)=M\cdot \mathrm{sign}(x)\) otherwise. Then,

(155)

where in (a) we set

in (b) we use definition (9), and in (c) we use that \(|\langle {{\varvec{A}}}_{n+1}, {{\varvec{x}}}\rangle |^2=\langle {{\varvec{A}}}_{n+1}, {{\varvec{x}}}{{\varvec{x}}}^* {{\varvec{A}}}_{n+1}\rangle \). Similarly, we have that

with

By applying (155) and (156), we can rewrite the RHS of (154) as

where we define \({{\varvec{M}}}= {{\mathbb {E}}}\left\{ {{\varvec{X}}}{{\varvec{X}}}^*\mid {{\varvec{Y}}}_{1:n}, {{\varvec{A}}}_{1:n}\right\} -{{\mathbb {E}}}\left\{ {{\varvec{X}}}{{\varvec{X}}}^*\right\} \). As K goes large, \({{\mathbb {E}}}_{{{\varvec{A}}}_{n+1}}\left\{ |E_i|^2\right\} \) tends to 0, for \(i\in \{1, 2\}\). Furthermore, we have that

(158)

where in (a) we use the following definition of the Kronecker delta:

and in (b) we use that

As a result, we conclude that (152) holds. \(\square \)

B Proof of Corollary 2

First, we evaluate the RHS of (20), as well as the scaling between \(\delta _{\mathrm{u}}\) and \(\sigma ^2\) when \(\sigma ^2\rightarrow 0\). Then, we give the proof of Corollary 2.

Lemma 8

(Computation of \(\delta _{\mathrm{u}}\) for phase retrieval) Let \(\delta _{\mathrm{u}}(\sigma ^2)\) be defined as in (20) and assume that the distribution \(p(\cdot \mid |g|)\) is given by (9). Then,

Proof

The proof boils down to computing expected values and integrals. By using (146) and (150), we immediately obtain that

where \(X\sim {\textsf {N}}(0, 1)\). By computing explicitly the expectation, we deduce that

where \(\mathrm erfc(\cdot )\) is the complimentary error function. Similarly, we have that

Thus, by using (162) and (163), after some manipulations, we obtain that

(164)

By performing the change in variables \(t=-y/\sigma +\sigma \), we simplify the first integral in the RHS of (164) as

where in the last equality we use that the integral

is finite. The other two integrals in the RHS of (164) can be expressed in closed form as

By combining (164), (165), (166), and (167), the result follows. \(\square \)

Proof (Proof of Corollary 2)

Pick \(\sigma \) sufficiently small. Let \(G\sim {\textsf {CN}}(0, 1)\), \(Y\sim p_{\mathrm{PR}}(\cdot \mid |G|)\) and \(Z= {\mathcal {T}}(Y)\), where \(p_{\mathrm{PR}}\) is defined in (9) and \({\mathcal {T}}\) is a pre-processing function (possibly dependent on \(\sigma \)) that we will choose later on. Assume that

1. (1)

   \({\mathcal {T}}(y)\) is upper and lower bounded by constants independent of \(\sigma \);

2. (2)

   \({\mathbb {P}} (Z=0)\le c_1 <1\) and \(c_1\) is independent of \(\sigma \);

3. (3)

   condition (82) holds.

Then, by Lemma 2, we have that, as \(n\rightarrow \infty \),

(168)

where \(\lambda _{\delta }^*\) is the unique solution of the equation \(\zeta _\delta (\lambda )=\phi (\lambda )\), and \(\phi \), \(\psi _\delta \), and \(\zeta _\delta \) are defined in (78), (79), and (81), respectively.

Let \(\tau \) be the supremum of the support of Z. Assume also that, for \(\bar{\lambda }_\delta < \lambda _{\delta }^*\),

1. (4)

   \(\tau \ge c_2 > 0\) and \(c_2\) is independent of \(\sigma \);

2. (5)

   \(\phi '(\lambda _{\delta }^*)\) is lower bounded by a constant independent of \(\sigma \);

3. (6)

   \(\displaystyle \min _{\lambda \in (\min (\bar{\lambda }_\delta , \lambda _{\delta }^*))}\psi _{\delta }''(\lambda )\) is lower bounded by a strictly positive constant independent of \(\sigma \).

Let \(\bar{\lambda }_\delta \) be the point at which \(\psi _{\delta }\) attains its minimum. Then,

(169)

where in (a) we use that \(\zeta _\delta (\lambda _{\delta }^*)=\phi (\lambda _{\delta }^*)\); in (b) we use that \(\zeta _\delta (\bar{\lambda }_\delta )=\psi _\delta (\bar{\lambda }_\delta )\); (c) holds for some \(x_1 \in (\bar{\lambda }_\delta , \lambda _{\delta }^*)\) by the mean value theorem; (d) holds for some \(x_2 \in (\bar{\lambda }_\delta , \lambda _{\delta }^*)\) by the mean value theorem; and in (e) we use that \(\psi _{\delta }'(\bar{\lambda }_\delta )=0\). Note that (f) holds for some constant \(c_3\) independent of \(\sigma \), as \(\zeta _\delta '(x_1)\ge 0\), \(\psi _{\delta }''(x_2)\) is bounded, and \(\phi '(x_2)<0\) since \({\mathbb {P}} (Z=0) <1\).

As \(\phi '(\lambda _{\delta }^*)\) is bounded, from (168) and (169) we deduce that

for some constant \(c_4\) independent of \(\sigma \). Notice that, if \(\lambda _{\delta }^*\le \bar{\lambda }_{\delta }\), then the right-hand side is non-positive and hence the lower bound still holds.

As \(\tau >0\), we also have that \(\bar{\lambda }_\delta >0\). Consider now the matrix \({{\varvec{D}}}_n'={{\varvec{D}}}_n/\alpha \) for some \(\alpha >0\). Then, the principal eigenvector of \({{\varvec{D}}}_n'\) is equal to the principal eigenvector of \({{\varvec{D}}}_n\). Hence, we can assume without loss of generality that \(\bar{\lambda }_\delta =1\). This condition can be rewritten as

and (170) can be rewritten as

We set

where \(y_+=\max (y,0)\) and \(c(\sigma )\) is a function of \(\sigma \) to be set as to satisfy Eq. (171). By substituting (173) into (171), we get

Hence, Eq. (171) is satisfied by

where \(W\sim {\textsf {N}}(0,1)\) is independent of G. Therefore, \(c(\sigma )\) is always well defined and, by dominated convergence, \(c(\sigma )\rightarrow c(0) = 1\), as \(\sigma \rightarrow 0\). Furthermore,

By applying again dominated convergence, we get

Hence, by using (170), we get that, for \(\delta >1\) and \(\sigma \le \sigma _1(\delta )\),

where \(\hat{{{\varvec{x}}}}_{\sigma }\) denotes the spectral estimator corresponding to the pre-processing function (173). Let us now verify that, by setting \({\mathcal {T}}={\mathcal {T}}_\delta ^*\), the requirements stated above are fulfilled. As \(\delta >1\), the function \({\mathcal {T}}\) is bounded by constants independent of \(\sigma \). It is also clear that conditions (2) and (4) hold. Furthermore, conditions (5) and (6) follow by showing that \(\phi (\lambda )\), \(\psi _{\delta }(\lambda )\) have well-defined uniform limits as \(\sigma \rightarrow 0\) that satisfy those conditions: This can be proved by one more application of dominated convergence.

In order to show that condition (3) holds, we follow the argument presented at the end of the proof of Lemma 2. First, we add a point mass with associated probability at most \(\epsilon _1\), which immediately implies that (82) is satisfied. Then, by applying the Davis–Kahan theorem [23], we show that we can take \(\epsilon _1 = 0\).

This proves the claim of the corollary for the pre-processing function \({{\mathcal {T}}}_\delta ^*(y, \sigma )\), defined in (173). Let us now prove that the same conclusion holds for \({{\mathcal {T}}}^*_{\delta }(y)\) defined in (25). Let

Then, for any \(x, a \in {{\mathbb {R}}}_{\ge 0}\),

Therefore, since \({{\mathcal {T}}}_\delta ^*(y,\sigma ) = 1-f_{y_+}(\sqrt{\delta c(\sigma )}-1)\), we have that

Denote by \({{\varvec{D}}}_n(\sigma )\) and \({{\varvec{D}}}_n\) the matrices constructed with the pre-processing functions \({{\mathcal {T}}}_\delta ^*(y, \sigma )\) and \({{\mathcal {T}}}^*_\delta (y)\), respectively. It follows that, for any \(\delta >1\), there exists a function \({\varDelta }(\sigma )\) with \({\varDelta }(\sigma )\rightarrow 0\) as \(\sigma \rightarrow 0\) such that

Hence, by applying again the Davis–Kahan theorem, we conclude that, for all \(\delta >1\) and \(\sigma \le \sigma _2(\delta )\),

where \(\hat{{{\varvec{x}}}}\) is the estimator corresponding to the pre-processing function \({{\mathcal {T}}}^*_{\delta }(y)\). \(\square \)

C Auxiliary Lemmas

Lemma 9

(Distribution of scalar product of two unit complex vectors) Let \({{\varvec{x}}}_1, {{\varvec{x}}}_2 \sim _{i.i.d.} {\mathrm{Unif}}({\textsf {S}} _{{\mathbb {C}}}^{d-1})\) and define \(M = |\langle {{\varvec{x}}}_1, {{\varvec{x}}}_2 \rangle |^2\). Then,

Proof

Without loss of generality, we can pick \({{\varvec{x}}}_2\) to be the first element of the canonical base of \({\mathbb {C}}^d\). Thus, M is equal to the squared modulus of the first component of \({{\varvec{x}}}_1\). Furthermore, we can think to \({{\varvec{x}}}_1\) as being chosen uniformly at random on the 2d-dimensional real sphere with radius 1. Note that, by taking a vector of i.i.d. standard Gaussian random variables and dividing it by its norm, we obtain a vector uniformly random on the sphere of radius 1. Hence,

Set \(A = U_1^2+U_2^2\) and \(B = \sum _{i=3}^{2d} U_i^2\). Then, A and B are independent, A follows a gamma distribution with shape 1 and scale 2, i.e., \(A\sim {\varGamma }(1, 2)\), and B follows a Gamma distribution with shape \(d-1\) and scale 2, i.e., \(B\sim {\varGamma }(d-1, 2)\). Thus, we conclude that

which proves the claim. \(\square \)

Lemma 10

(Distribution of scalar product of two unit real vectors) Let \({{\varvec{x}}}_1, {{\varvec{x}}}_2 \sim _{i.i.d.} {\mathrm{Unif}}({\textsf {S}} _{{\mathbb {R}}}^{d-1})\) and define \(M = \langle {{\varvec{x}}}_1, {{\varvec{x}}}_2 \rangle \). Then, the distribution of M is given by

Proof

Without loss of generality, we can pick \({{\varvec{x}}}_2\) to be the first element of the canonical base of \({\mathbb {R}}^d\). Thus, M is equal to the first component of \({{\varvec{x}}}_1\). Note that, by taking a vector of i.i.d. standard Gaussian random variables and dividing it by its norm, we obtain a vector uniformly random on the sphere of radius 1. Hence,

Set \(A = U_1^2\) and \(B = \sum _{i=2}^{d} U_i^2\). Then, A and B are independent, A follows a gamma distribution with shape 1 / 2 and scale 2, i.e., \(A\sim {\varGamma }(1/2, 2)\), and B follows a Gamma distribution with shape \((d-1)/2\) and scale 2, i.e., \(B\sim {\varGamma }((d-1)/2, 2)\). Thus, we obtain that

A change in variable and the observation that the distribution of M is symmetric around 0 immediately let us conclude that, for \(m\in [-1, 1]\),

where the normalization constant c is given by

\(\square \)

Lemma 11

(Laplace’s method) Let \(F:[0, 1]\rightarrow {\mathbb {R}}\) be such that

• F is continuous;

• \(F(x)<0\) for \(x\in (0, 1]\);

• \(F(0)=0\).

Then,

Proof

Pick \(\epsilon >0\) and separate the integral into two parts:

Now, the first integral is at most \(\epsilon \) since \(F(x)\le 0\) for any \(x\in [0, 1]\), and the second integral tends to 0 as \(n\rightarrow +\infty \) since \(F(x)<0\) for \(x\in (0, 1]\). Thus, the claim immediately follows. \(\square \)

Lemma 12

(Second moment of uniform vector on complex sphere) Let \({{\varvec{x}}}\sim {\mathrm{Unif}}(\sqrt{d}{} {\textsf {S}} _{{\mathbb {C}}}^{d-1})\). Then,

Proof

Let \({{\varvec{z}}}\sim {\textsf {CN}}({\varvec{0}}_d, {{\varvec{I}}}_d)\) and note that, by taking a vector of i.i.d. standard complex normal random variables and dividing it by its norm, we obtain a vector uniformly random on the complex sphere of radius 1. Then, \({{\varvec{x}}}= \sqrt{d}{{\varvec{z}}}/\left| \left| {{\varvec{z}}}\right| \right| \).

For \(i\in [d]\), denote by \(x_i\) and by \(z_i\) the ith component of \({{\varvec{x}}}\) and \({{\varvec{z}}}\), respectively. Then, for \(i\ne j\),

where the last equality holds by symmetry. Furthermore,

as \(|Z_i|^2/\left| \left| Z\right| \right| ^2 \sim \mathrm{Beta}(1, d-1)\) by the argument of Lemma 9. As a result, the thesis is readily proved. \(\square \)

D Proof of Lemma 3

Before presenting the proof of the lemma, let us introduce some basic definitions and well-known results. Let H be a probability measure on \([0, +\infty )\). Denote by \({\varGamma }_H\) the support of H and by \(\tau \) the supremum of \({\varGamma }_H\). Let \(s_H(g)\) denote the Stieltjes transform of H, which is defined as

and let \(g_H(s)\) denote its inverse.

Consider a matrix

and assume that

1. (1)

   \({{\varvec{M}}}_n\) is PSD for all \(n\in {\mathbb {N}}\);

2. (2)

   \({{\varvec{U}}}\in {\mathbb {C}}^{d\times n}\) is a random matrix whose entries \(\{u_{i, j}\}_{1\le i \le d, 1\le j \le n}\) are i.i.d. such that \({{\mathbb {E}}}\left\{ U_{i, j}\right\} =0\), \({{\mathbb {E}}}\left\{ |U_{i, j}|^2\right\} =1\), and \({{\mathbb {E}}}\left\{ |U_{i, j}|^4\right\} <\infty \) (this includes the cases in which the entries are \(\sim _{i.i.d.}{\textsf {CN}}(0, 1)\) or are \(\sim _{i.i.d.}{\textsf {N}}(0, 1)\));

3. (3)

   The sequence of empirical spectral distributions of \({{\varvec{M}}}_n\in {\mathbb {C}}^{n\times n}\) converges weakly to a probability distribution H, as \(n\rightarrow +\infty \);

4. (4)

   \(n/d\rightarrow \delta \in (0, +\infty )\), as \(n\rightarrow \infty \);

5. (5)

   The sequence of spectral norms of \({{\varvec{M}}}_n\) is bounded.

Note that the normalization of (190) differs from the normalization of (86) by a factor of \(\delta \). However, since the form (190) is more common in the literature, we will stick to it for the rest of this section. In order to obtain the desired result for the matrix (86), it suffices to incorporate a factor \(1/\delta \) in the definition of the function \(\psi _{\delta }\).

Let \(F_{\delta , H}\) be the probability measure on \([0, +\infty )\) such that the inverse \(g_{F_{\delta , H}}\) of its Stieltjes transform \(s_{F_{\delta , H}}\) is given by

Then, the sequence of empirical spectral distributions of \({{\varvec{S}}}_n\) converges weakly to \(F_{\delta , H}\) [50], [66, Chapter 4].

For \(\alpha \not \in {\varGamma }_H\) and \(\alpha \ne 0\), let us also define

The function \(\psi _{F_{\delta , H}}\) links the support of \(F_{\delta , H}\) with the support of the generating measure H (see [67, Section 4] and [3, Lemma 3.1]). In particular, if \(\lambda \not \in {\varGamma }_{F_{\delta , H}}\), then \(s_{F_{\delta , H}}(\lambda )\ne 0\) and \(\alpha = -1/s_{F_{\delta , H}}(\lambda )\) satisfies

1. (1)

   \(\alpha \not \in {\varGamma }_H\) and \(\alpha \ne 0\) (so that \(\psi _{F_{\delta , H}}(\alpha )\) is well defined);

2. (2)

   \(\psi _{F_{\delta , H}}'(\alpha )>0\).

Conversely, if \(\alpha \) satisfies (1) and (2), then \(\lambda = \psi _{F_{\delta , H}}(\alpha )\not \in {\varGamma }_{F_{\delta , H}}\).

Let \(\lambda _1^{{{\varvec{M}}}_n}\) denote the largest eigenvalue of \({{\varvec{M}}}_n\) and assume that, as \(n\rightarrow \infty \),

(193)

Denote by \(\lambda _1^{{{\varvec{S}}}_n}\) the largest eigenvalue of \({{\varvec{S}}}_n\). Then, the results in [3] prove that

(194)

Informally, the eigenvalue \(\lambda _1^{{{\varvec{M}}}_n}\) is mapped into the point \(\psi _{F_{\delta , H}}(\alpha _*)\), where \(\alpha _* = -1/s_{F_{\delta , H}}(\lambda _*)\). This point emerges from the support of \(F_{\delta , H}\) if and only if \(\psi '_{F_{\delta , H}}(\alpha _*)>0\).

In what follows, we relax the first hypothesis, i.e., we consider the case in which the matrix \({{\varvec{M}}}_n\) is not PSD. We will show that (194) still holds, which implies the claim of Lemma 3.

Proof (Proof of Lemma 3)

As \({{\varvec{U}}}\) is drawn from a rotationally invariant distribution, we can assume without loss of generality that \({{\varvec{M}}}_n\) is diagonal. Then, we have that

where \({{\varvec{M}}}_n^+\in {\mathbb {R}}^{k \times k}\) is the diagonal matrix containing the positive eigenvalues of \({{\varvec{M}}}_n\), \({{\varvec{M}}}_n^-\in {\mathbb {R}}^{(n-k) \times (n-k)}\) is the diagonal matrix containing the negative eigenvalues of \({{\varvec{M}}}_n\) with the sign changed, \({{\varvec{U}}}_+\) contains the first k columns of \({{\varvec{U}}}\), and \({{\varvec{U}}}_-\) contains the remaining \(n-k\) columns of \({{\varvec{U}}}\).

Note that \({{\varvec{U}}}_+\) and \({{\varvec{U}}}_-\) are independent. Furthermore, if \({{\varvec{H}}}\) is a unitary matrix, then \({{\varvec{U}}}_-\) and \({{\varvec{H}}}{{\varvec{U}}}_-\) have the same distribution. Hence, we can rewrite the matrix \({{\varvec{S}}}_n\) as

where \({{\varvec{U}}}_1\) and \({{\varvec{U}}}_2\) are independent with entries \(\sim _{i.i.d.}{\textsf {CN}}(0, 1)\), and \({{\varvec{H}}}\) is a random unitary matrix distributed according to the Haar measure.

Recall that, by hypothesis, the sequence of empirical spectral distributions of \({{\varvec{M}}}_n\) converges weakly to the probability distribution H, where H is the law of the random variable Z. Then, the sequence of empirical spectral distributions of \({{\varvec{M}}}_n^+\) converges weakly to the probability distribution \(H^+\), where \(H^+\) is the law of \(Z^+ = \max (Z, 0)\). Let \(F_{\delta , H^+}\) be the probability measure on \([0, +\infty )\) such that the inverse \(g_{F_{\delta , H^+}}\) of its Stieltjes transform \(s_{F_{\delta , H^+}}\) is given by

Define \({{\varvec{S}}}_n^+=\frac{1}{d}{{\varvec{U}}}_1 {{\varvec{M}}}_n^+ {{\varvec{U}}}_1^*\). Then, as \({{\varvec{M}}}_n^+\) is PSD, the sequence of empirical spectral distributions of \({{\varvec{S}}}_n^+\) converges weakly to \(F_{\delta , H^+}\) [50], [66, Chapter 4].

Similarly, the sequence of empirical spectral distributions of \({{\varvec{M}}}_n^-\) converges weakly to the probability distribution \(H^-\), where \(H^-\) is the law of \(Z^- = -\min (Z, 0)\). Let \(F_{\delta , H^-}\) be the probability measure on \([0, +\infty )\) such that the inverse \(g_{F_{\delta , H^-}}\) of its Stieltjes transform \(s_{F_{\delta , H^-}}\) is given by

Define \({{\varvec{S}}}_n^-=\frac{1}{d}{{\varvec{U}}}_2 {{\varvec{M}}}_n^- {{\varvec{U}}}_2^*\). Then, as \({{\varvec{M}}}_n^-\) is PSD, the sequence of empirical spectral distributions of \({{\varvec{S}}}_n^-\) converges weakly to \(F_{\delta , H^-}\) [50], [66, Chapter 4]. Furthermore, the sequence of empirical spectral distributions of \(-{{\varvec{S}}}_n^-\) converges weakly to the probability measure \(F_{\delta , H^-_{\mathrm{inv}}}\) such that

where \(g_{F_{\delta , H^-_{\mathrm{inv}}}}\) denotes the inverse of the Stieltjes transform \(s_{F_{\delta , H^-_{\mathrm{inv}}}}\) of \(F_{\delta , H^-_{\mathrm{inv}}}\).

Define

where \(\boxplus \) denotes the free additive convolution. Recall the decomposition (196). Then, the sequence of empirical spectral distributions of \({{\varvec{S}}}_n\) converges weakly to \(F_{\delta , H}\) [69, 74]. Consequently, the inverse \(g_{F_{\delta , H}}\) of the Stieltjes transform \(s_{F_{\delta , H}}\) of \(F_{\delta , H}\) can be computed as

(201)

where in (a) we use (200); in (b) we use that the \({\mathcal {R}}\)-transform of the free convolution is the sum of the \({\mathcal {R}}\)-transforms of the addends; in (c) we use (197), (198), and (199); in (d) we perform the change in variable \(t\rightarrow -t\) in the second integral; and in (e) we use the fact that \(H^+(t)\) is the law of \(\max (Z, 0)\), \(H^-(-t)\) is the law of \(\min (Z, 0)\), and that \(t/(1+ts)=0\) for \(t=0\).

By hypothesis, . First, we establish under what condition the largest eigenvalue of \({{\varvec{S}}}_n^+\), call it \(\lambda _1^{{{\varvec{S}}}_n^+}\), converges to a point outside the support of \(F_{\delta , H^+}\). To do so, define \(\psi _{F_{\delta , H^+}}(\alpha ) = g_{F_{\delta , H^+}}(-1/\alpha )\). Then, , if \(\psi '_{F_{\delta , H^+}}(\alpha _*)>0\); and \(\lambda _1^{{{\varvec{S}}}_n^+}\) converges almost surely to a point inside the support of \(F_{\delta , H^+}\), otherwise [3].

For the moment, assume that \(\psi '_{F_{\delta , H^+}}(\alpha _*)>0\). We now establish under what condition the largest eigenvalue of \({{\varvec{S}}}_n\), call it \(\lambda _1^{{{\varvec{S}}}_n}\), converges to a point outside the support of \(F_{\delta , H}\). To do so, let \(\omega _1\) and \(\omega _2\) denote the subordination functions corresponding to the free convolution \(F_{\delta , H^+} \boxplus F_{\delta , H^-_{\mathrm{inv}}}\). These functions satisfy the following analytic subordination property:

Then, by Theorem 2.1 of [11], we have that the spike \(\psi _{F_{\delta , H^+}}(\alpha _*)\) is mapped into \(\omega _1^{-1}(\psi _{F_{\delta , H^+}}(\alpha _*))\). The Stieltjes transform at this point is given by

where in (a) we use (202); in (b) we use the definition of \(\psi _{F_{\delta , H^+}}\); and in (c) we use that \(g_{F_{\delta , H^+}}\) is the functional inverse of the Stieltjes transform \(s_{F_{\delta , H^+}}\). As a result, by [67, Section 4], we conclude that \(\omega _1^{-1}(\psi _{F_{\delta , H^+}}(\alpha _*))\not \in {\varGamma }_{F_{\delta , H}}\) if and only if \(\psi '_{F_{\delta , H}}(\alpha _*)>0\). Furthermore, the condition \(\psi '_{F_{\delta , H}}(\alpha _*)>0\) is more restrictive than the condition \(\psi '_{F_{\delta , H^+}}(\alpha _*)>0\) since

Hence, \(\lambda _1^{{{\varvec{S}}}_n}\) converges to a point outside the support of \(F_{\delta , H}\) if and only if \(\psi '_{F_{\delta , H}}(\alpha _*)>0\) and the proof is complete. \(\square \)

Remark 8

(Lemma 3 for the real case) Consider the random matrix \(\frac{1}{n}{{\varvec{U}}}{{\varvec{M}}}_n{{\varvec{U}}}^{{{\textsf {T}}}}\), where \({{\varvec{U}}}\in {\mathbb {R}}^{(d-1)\times n}\) is a random matrix whose entries are \(\sim _{i.i.d.}{\textsf {N}}(0, 1)\) and \({{\varvec{M}}}_n \in {\mathbb {R}}^{n\times n}\). Then, the claim of Lemma 3 still holds. Let us briefly explain why this is the case.

If \({{\varvec{M}}}_n\) is PSD, then the results of [3] allow us to conclude. If \({{\varvec{M}}}_n\) is not PSD, we can write an expression analogous to (196):

where \({{\varvec{M}}}_n^+\) is the diagonal matrix containing the positive eigenvalues of \({{\varvec{M}}}_n\), \({{\varvec{M}}}_n^-\) is the diagonal matrix containing the negative eigenvalues of \({{\varvec{M}}}_n\) with the sign changed, \({{\varvec{U}}}_1\) and \({{\varvec{U}}}_2\) are independent with entries \(\sim _{i.i.d.}{\textsf {N}}(0, 1)\), \({{\varvec{H}}}\) is a random unitary matrix distributed according to the Haar measure, and we have used the fact that the eigenvalues of \({{\varvec{U}}}_2 {{\varvec{M}}}_n^- {{\varvec{U}}}_2^{{{\textsf {T}}}}\) are the same as the eigenvalues of \({{\varvec{H}}}{{\varvec{U}}}_2 {{\varvec{M}}}_n^- {{\varvec{U}}}_2^{{{\textsf {T}}}}{{\varvec{H}}}^*\) since \({{\varvec{H}}}\) is unitary. Hence, the proof follows from the same argument of Lemma 3.

E Proof of Lemma 4 and Theorem 5

We start by proving a result similar to Lemma 4 for a general AMP iteration, where the function \(f_t({\hat{z}}; y)\) is generic.

Lemma 13

(State evolution for general AMP iteration) Let \({{\varvec{x}}}\in {\mathbb {R}}^d\) denote the unknown signal such that \(\left| \left| {{\varvec{x}}}\right| \right| _2 = \sqrt{d}\), \({{\varvec{A}}}= ({{\varvec{a}}}_1, \ldots , {{\varvec{a}}}_n)^{{{\textsf {T}}} }\)\(\in {\mathbb {R}}^{n\times d}\) with \(\{{{\varvec{a}}}_i\}_{1\le i\le n}\sim _{i.i.d.}{} {\textsf {N}} ({{\varvec{0}}}_d,{{\varvec{I}}}_d/d)\), and \({{\varvec{y}}}= (y_1, \ldots , y_n)\) with \(y_i\sim p(\cdot \mid \langle {{\varvec{x}}}, {{\varvec{a}}}_i \rangle )\). Consider the AMP iterates \({{\varvec{z}}}^t, \hat{{\varvec{z}}}^t\) defined in (126) for some function \(f_t({\hat{z}}; y)\), with \(\textsf {b} _t\) given by

where the expectation is with respect to \(G_0,G_1\sim _{i.i.d.}{} {\textsf {N}} (0,1)\) and \(Y\sim p(\,\cdot \,\mid G_0)\). Assume that the initialization \({{\varvec{z}}}^0\) is independent of \({{\varvec{A}}}\) and that, almost surely,

Let the state evolution recursion \(\tau _t,\mu _t\) be defined as

with initialization \(\mu _0\) and \(\tau _0\), where the expectation is taken with respect to \(X_0,G\sim _{i.i.d.}{} {\textsf {N}} (0,1)\). Then, for any t, and for any function \(\psi :{{\mathbb {R}}}^2\rightarrow {{\mathbb {R}}}\) such that \(|\psi ({{\varvec{u}}})-\psi ({{\varvec{v}}})|\le L(1+\Vert {{\varvec{u}}}\Vert _2+\Vert {{\varvec{v}}}\Vert _2)\Vert {{\varvec{u}}}-{{\varvec{v}}}\Vert _2\) for some \(L\in {\mathbb {R}}\), we have that, almost surely,

Proof

For \(g\in {{\mathbb {R}}}\), let \({{\mathcal {H}}}(\,\cdot \, ;g):[0,1]\rightarrow {{\mathbb {R}}}\cup \{+\infty ,-\infty \}\) be the generalized inverse of

namely,

With this definition, the model \(y_i\sim p(\,\cdot \,\mid \langle {{\varvec{a}}}_i,{{\varvec{x}}}\rangle )\) is equivalent to \(y_i= {{\mathcal {H}}}(w_i;\langle {{\varvec{a}}}_i,{{\varvec{x}}}\rangle )\) for \(\{w_i\}_{1\le i\le n}\sim _{i.i.d.} {\mathrm{Unif}}([0,1])\) independent of \({{\varvec{A}}}\) and \({{\varvec{x}}}\). Let \({{\varvec{w}}}= (w_1, \ldots ,w_n)\in {{\mathbb {R}}}^n\) and denote by \([{{\varvec{v}}}_1\mid \cdots \mid {{\varvec{v}}}_k]\in {{\mathbb {R}}}^{m\times k}\) the matrix obtained by stacking column vectors \({{\varvec{v}}}_1, \ldots ,{{\varvec{v}}}_k\in {{\mathbb {R}}}^m\).

For \(t\ge 0\), define \({{\varvec{r}}}^t = {{\varvec{0}}}_d\), \(\hat{{\varvec{r}}}^t = {{\varvec{A}}}{{\varvec{x}}}\), and introduce the extended state variables \({{\varvec{s}}}^t \in {{\mathbb {R}}}^{d\times 2}\) and \(\hat{{\varvec{s}}}^t \in {{\mathbb {R}}}^{n\times 2}\), defined as

We further define the functions \(h_t =[h_{t, 1}\mid h_{t, 2}]:{{\mathbb {R}}}^{2}\times {{\mathbb {R}}}\rightarrow {{\mathbb {R}}}^{2}\) and \({\hat{h}}_t =[{\hat{h}}_{t, 1}\mid {\hat{h}}_{t, 2}]:{{\mathbb {R}}}^{2}\times {{\mathbb {R}}}\rightarrow {{\mathbb {R}}}^{2}\) by setting

With these notations, the iteration (126) is equivalent to

where the functions \(h_t({{\varvec{s}}}^t;{{\varvec{x}}})\) and \({\hat{h}}_t(\hat{{\varvec{s}}}^t;{{\varvec{w}}})\) are understood to be applied component-wise to their arguments and \({\textsf {B}}_t,\hat{\textsf {B}}_t\in {{\mathbb {R}}}^{2\times 2}\) are defined by

The iteration (211) satisfies the assumptions of [41][Proposition 5]. By applying that result, the claim follows. \(\square \)

At this point, first we present the proof of Lemma 4 and then of Theorem 5.

Proof (Proof of Lemma 4)

Consider the state evolution recursion defined in (124) with initialization \(\mu _0\). Let \(f_t\) be defined as in (127) with \(\textsf {F}\) given by (123). Suppose that, for any t, (206) holds with \(\mu _t = \tau _t^2\). Then, by Lemma 13, the claim immediately follows.

The remaining part of the proof is devoted to show that (206) holds with \(\mu _t = \tau _t^2\), for \(t\ge 0\). First, we prove by induction that \(\mu _t = \tau _t^2\), for \(t\ge 0\). The basis of the induction, i.e., \(\mu _0 =\tau _0^2\), is true by the hypothesis of the Lemma. Now, we assume that \(\mu _t = \tau _t^2\) and we show that \(\mu _{t+1} = \tau _{t+1}^2\). Set

and note that \(Z\sim {\textsf {N}}(0, \mu _t^2+\tau _t^2)\). Then, we can rewrite \(X_0\) as

for some \(a, b\in {\mathbb {R}}\), where \({\widetilde{G}}\sim {\textsf {N}}(0, 1)\) and independent from Z. In order to compute the coefficients a and b, we evaluate \({\mathbb {E}}\{X_0^2\}\) and \({\mathbb {E}}\{X_0\cdot Z\}\), thus obtaining the equations

which can be simplified as

Furthermore, by using the inductive hypothesis \(\mu _{t}=\tau _t^2\) and that \(q_t = \mu _t/(1+\mu _t)\), we obtain that

Hence, the following chain of equalities holds:

(215)

where in (a) we use that \(Y\sim p(\cdot \mid X_0)\); in (b) we use (213) and (214); in (c) we condition with respect to Z; in (d) we use definition (127) of \(f_t\); in (e) we use again definition (127) of \(f_t\); and in (f) we use again (213) and (214).

Finally, we prove that \(\mu _{t+1}\) satisfies (206). Indeed, the following chain of equalities holds:

(216)

where in (a) we use (215); in (b) we set \(G_1 = {\widetilde{G}}\) and \(G_0=Z/\sqrt{\mu _t^2+\tau _t^2}\); and in (c) we use that \(\mu _{t}=\tau _t^2\) and that \(q_t = \mu _t/(1+\mu _t)\). \(\square \)

Proof (Proof of Theorem 5)

In view of Lemma 4, it is sufficient to show that \((q, \mu ) = (0, 0)\) is an attractive fixed point of the recursion (124).

First of all, let us check that \((q, \mu ) = (0, 0)\) is a fixed point. This happens if and only if

which holds because of condition (131).

Let us now prove that this fixed point is stable. We start by rewriting the function h(q) defined in (125) as

where

Note that \(h_{\mathrm{num}}(0, y)=0\) by assumption (131). Then,

for some \(x_1, x_2 \in [0, \sqrt{q}]\). Furthermore, by applying Stein’s lemma, we have that

By using (221), we can rewrite (220) as

where

By applying again Stein’s lemma and by using that the conditional density \(p(y\mid g)\) is bounded, we note that \({\mathbb {E}}_{G_1}\left\{ f_{\mathrm{num}}(G_0, G_1, x_1)\right\} \) and \({\mathbb {E}}_{G_1} \left\{ f_{\mathrm{den}}(G_0, G_1, x_2)\right\} \) are bounded. Hence, by dominated convergence, we obtain that

Therefore, in a neighborhood of the fixed point we have

Furthermore, by applying twice Stein’s lemma, we also have that

By using (223), (224) and by recalling definition (42) of \(\delta _{\mathrm{u}}\), we conclude that

As \(\delta < \delta _{\mathrm{u}}\), the fixed point is stable. \(\square \)

F Proof of Lemma 5 and Theorem 6

For the proofs in this section, it is convenient to introduce the function

First, we present the proof of Lemma 5 and then of Theorem 6.

Proof (Proof of Lemma 5)

Condition (131) implies that

Furthermore, we have that

(228)

where in (a) we use (227) and definition (226) of \(\textsf {G}(0, y;1)\) and in (b) we use the fact that y has density \({\mathbb {E}}_G\{ p(y\mid G)\}\).

Denote by \(\textsf {F}'(x,y;{\bar{q}})\) the derivative of \(\textsf {F}\) with respect to its first argument. Then, we have

Hence,

By using (229) and (230), we linearize the recursion (126) around the fixed point \({{\varvec{z}}}^t={{\varvec{0}}}_d\) and \(\hat{{\varvec{z}}}^{t-1}={{\varvec{0}}}_n\) as

where \({{\varvec{J}}}\in {\mathbb {R}}^{n\times n}\) is a diagonal matrix with entries \(j_{i} =\textsf {F}'(0,y_i;1)\) for \(i\in [n]\). By substituting expression (232) for \(\hat{{\varvec{z}}}^t\) into the RHS of (231), the result follows. \(\square \)

Proof (Proof of Theorem 6)

By definition, \(\alpha \) is an eigenvalue of \({{\varvec{L}}}_n\) if and only if

Recall that, when \({{\varvec{D}}}\) is invertible,

Then, after some calculations, we obtain that (233) is equivalent to

From (235), we immediately deduce that the eigenvalues of \({{\varvec{L}}}_n\) are real if and only if all the solutions to

are real. We will prove that in fact this equation does not have any solution for \(\alpha \in {{\mathbb {C}}}{\setminus } {{\mathbb {R}}}\).

Let \({{\varvec{U}}}{\varvec{\varSigma }}{{\varvec{V}}}^{{{\textsf {T}}}}\) be the SVD of \({{\varvec{A}}}\). Then, (236) is equivalent to

Using the fact that \(\mathrm{det}({\varvec{\varSigma }})\ne 0\), and \(\mathrm{det}( {{\varvec{I}}}_n +\alpha {{\varvec{J}}}^{-1})\ne 0\) for \(\alpha \in {{\mathbb {C}}}{\setminus } {{\mathbb {R}}}\), Eq. (236) is equivalent to

or equivalently

Given that the solutions of this equations are generalized eigenvalues for the pairs of symmetric matrices \({{\varvec{A}}}{{\varvec{A}}}^{{{\textsf {T}}}}-{{\varvec{I}}}_n\) and \({{\varvec{J}}}^{-1}\), they must be real. We conclude that the eigenvalues of \({{\varvec{L}}}_n\) are real.

Note that

(237)

where in (a) we use that \(\textsf {F}(0, 1; y)=0\) as (131) holds; in (b) we apply twice Stein’s lemma; and in (c) we use definition (45) of \({\mathcal {T}}^*\). Then, (236) can be rewritten as

Let \(\lambda _1^{{{\varvec{D}}}^*_n}(\alpha )\) be the largest eigenvalue of the matrix \({{\varvec{D}}}^*_n(\alpha )\) defined as

Note that, as \(\alpha \rightarrow +\infty \), the entries of \({{\varvec{D}}}^*_n(\alpha )\) tend to 0 with high probability. Since the eigenvalues of a matrix are continuous functions of the elements of the matrix, we also obtain that

Hence, if there exists \(\bar{\alpha }>1\) such that \(\lambda _1^{{{\varvec{D}}}^*_n}(\bar{\alpha })>1\), then there exists also \(\bar{\alpha }_0> \bar{\alpha } > 1\) such that \(\lambda _1^{{{\varvec{D}}}^*_n}(\bar{\alpha }_0)=1\). Consequently, there exists \(\alpha > 1\) that satisfies (238), which implies the result of the theorem.

The rest of the proof consists in showing that \(\bar{\alpha }= \sqrt{\delta /\delta _{\mathrm{u}}}\) satisfies the desired requirements. First of all, note that \(\sqrt{\delta /\delta _{\mathrm{u}}}>1\), as \(\delta >\delta _{\mathrm{u}}\). Furthermore, we have that

where \({\mathcal {T}}_{\delta }^*\) is defined in (44). Recall that, by hypothesis, \({{\varvec{x}}}\) is such that \(\left| \left| {{\varvec{x}}}\right| \right| _2 = \sqrt{d}\) and \(\{{{\varvec{a}}}_i\}_{1\le i\le n}\sim _{i.i.d.}{\textsf {N}}({\varvec{0}}_d,{{\varvec{I}}}_d/d)\). Let \({\tilde{{{\varvec{x}}}}} = {{\varvec{x}}}/\sqrt{d}\) and \(\tilde{{{\varvec{a}}}_i} =\sqrt{d}\cdot {{\varvec{a}}}_i\). Then, \(\langle {{\varvec{x}}}, {{\varvec{a}}}_i \rangle = \langle {\tilde{{{\varvec{x}}}}}, {\tilde{{{\varvec{a}}}}}_i \rangle \). Let \(\lambda _1^{{\widetilde{{{\varvec{D}}}}}_n}\) be the largest eigenvalue of the matrix \({\widetilde{{{\varvec{D}}}}}_n\) defined as

Since \({\widetilde{{{\varvec{D}}}}}_n = {{\varvec{D}}}^*_n(\bar{\alpha })/\delta \), it remains to prove that

(242)

To do so, we apply a result analogous to that of Lemma 2 for the real case with \({\mathcal {T}}={\mathcal {T}}_\delta ^*\). For the moment, assume that \({\mathcal {T}}_\delta ^*\) fulfills the hypotheses of Lemma 2 (we will prove later that this is the case). Then, \(\lambda _1^{{\widetilde{{{\varvec{D}}}}}_n}\) converges almost surely to \(\zeta _{\delta }(\lambda _{\delta }^*)\).

Recall that

where \(\bar{\lambda }_\delta \) is the point of minimum of the convex function \(\psi _{\delta }(\lambda )\) defined as

Notice also that this minimum is the unique local minimizer since \(\psi _{\delta }\) is convex and analytic.

Furthermore, \(\lambda _{\delta }^*\) is the unique solution to the equation \(\zeta _{\delta }(\lambda _{\delta }^*) = \phi (\lambda _{\delta }^*)\), where \(\phi (\lambda )\) is defined as

By setting the derivative of \(\psi _{\delta }(\lambda )\) to 0, we have that

By using definition (44) of \({\mathcal {T}}^*_\delta \) and definition (45) of \({\mathcal {T}}^*\), we verify that

Hence, by using definition (42) of \(\delta _{\mathrm{u}}\), we obtain that

which immediately implies that

By using (243), one also obtains that

which implies that

Furthermore, we have that

which implies that

as \(\delta > \delta _{\mathrm{u}}\). By putting (244), (245), and (246) together, we obtain that

Recall that \(\zeta _\delta (\lambda )\) is monotone non-decreasing and \(\phi (\lambda )\) is monotone non-increasing. Consequently, (247) implies that \(\lambda _{\delta }^* > \bar{\lambda }_\delta \). Thus, we conclude that

Now, we show that \({\mathcal {T}}_\delta ^*\) fulfills the hypotheses of Lemma 2 by using arguments similar to those at the end of the proof of Theorem 2. First of all, since \({\mathcal {T}}^*(y)\le 1\), we have that \({\mathcal {T}}_\delta ^*(y)\) is bounded. Furthermore, if \({\mathcal {T}}_\delta ^*(y)\) is equal to the constant value 0, then \(\delta _{\mathrm{u}}=\infty \) and the claim of Theorem 6 trivially holds. Hence, we can assume that \({\mathbb {P}}({\mathcal {T}}_\delta ^*(Y)=0)<1\). Let \(\tau \) be the supremum of the support of \({\mathcal {T}}_\delta ^*(Y)\). If \({\mathbb {P}}({\mathcal {T}}_\delta ^*(Y)=\tau )>0\), then the condition (82) is satisfied and the proof is complete. Otherwise, for any \(\epsilon _1 >0\), there exists \({\varDelta }_1(\epsilon _1)\) such that Eq. (115) holds. Define \({\mathcal {T}}_{\delta }^*(y, \epsilon _1)\) as in (116). Clearly, the random variable \({\mathcal {T}}_{\delta }^*(Y, \epsilon _1)\) has a point mass at \(\delta \); hence, condition (82) is satisfied. As a final step, we show that we can take \(\epsilon _1 \downarrow 0\). Define

Then,

where the constant \(C_1\) depends only on n / d. Consequently, by using (249) and Weyl’s inequality, we conclude that

Hence, for any n, as \(\epsilon _1\) tends to 0, the largest eigenvalue of \({\widetilde{{{\varvec{D}}}}}_n(\epsilon _1)\) tends to the largest eigenvalue of \({\widetilde{{{\varvec{D}}}}}_n\), which concludes the proof. \(\square \)

Reprints and permissions