Do semidefinite relaxations solve sparse PCA up to the information limit?

Introduction

In contemporary applications where variables are plentiful (large $p$) but samples are relatively scarce (small $n$), PCA suffers from two major limitations: (1) the principal components are typically a linear combination of all variables, which hinders their interpretation and subsequent use, and (2) while PCA is consistent in the classical setting ($p$ is fixed and $n\to\infty$) , it is generally inconsistent in high-dimensions. Indeed, as shown, for example, in , when $p$ is comparable to, or significantly larger than $n$, the sample covariance matrix ${\hat{\Sigma}}$ may be a poor approximation to the population’s covariance matrix $\Sigma$, and its leading eigenvectors may be far from the population’s principal components.

SDP-based algorithm. We study the following concrete SDP relaxation of (1), which was suggested by d’Aspremont et al. :

Single-spike input model. We examine Algorithm 1 under the single-spike multivariate Gaussian model introduced in , where the samples $\mathbf{x}_{i}$ are of the form

and its largest eigenvalue is $1+\beta$, with associated eigenvector $\mathbf{z}$. We consider throughout the scenario $(n,p,k)\to\infty$, and mention additional assumptions (e.g., $\beta$ is fixed or $p/n$ tends to $c>0$) as needed.

Information versus computational limits. Amini and Wainwright studied this single-spike input model, under the additional assumption that the nonzero entries of $\mathbf{z}$ are exactly of the form $\pm 1/\sqrt{k}$, which represents the hardest type of $k$-sparse vectors. They proved that up to sparsity level $k=O(\kappa_{n,p})$ where $\kappa_{n,p}=\sqrt{n/\log p}$, Algorithm 1 outputs a vector $\hat{\mathbf{z}}$ whose support coincides with that of $\mathbf{z}$;For technical reasons, their proof requires the additional condition $k=O(\log p)$, which they conjecture can be removed. they further showed, using a simple second moment calculation, that up to the same order of sparsity level $k=O(\kappa_{n,p})$, the diagonal thresholding algorithm also recovers the support of $\mathbf{z}$ and fails whenever $k/\kappa_{n,p}\to\infty$. In contrast, Amini and Wainwright showed that for $k=\Omega(\kappa_{n,p}^{2})$,We write $f=\Omega(g)$ if $f(n)\geq Cg(n)$ for some absolute positive constant $C$ and all sufficiently large $n$. Similarly, $f=\Theta(g)$ means $C_{1}g(n)\leq f(n)\leq C_{2}g(n)$. every method [including exhaustive search over all $p\choose k$ subsets of size $k$] will err with probability at least $1/2$. In fact, even the simpler task of detecting the presence of a spike is not possible for this range of parameters, as recently proved in . For further results including minimax rates, under more general sparsity models, see .

Our results, formally stated below, prove that unfortunately this is not the case—in fact, when $k$ slightly exceeds $\kappa_{n,p}$, namely $k=\Omega(\kappa_{n,p}\sqrt{\log p)}=\Omega(\sqrt{n})$, the solution $X$ of SDP (2) does not have rank one and is not close to $\mathbf{z}\mathbf{z}^{T}$. Furthermore, if $X$ has a low rank, then the output $\hat{\mathbf{z}}$ of Algorithm 1 is at best weakly correlated with $\mathbf{z}$. In Section 3 we present empirical simulation results showing that indeed Algorithm 1 and DT perform similarly.

Given that the SDP algorithm does not seem to significantly improve over DT under the single spike model, the following question arises: Is there a simple algorithm which outperforms both? Motivated by the work of Bickel and Levina , we suggest a light-weight greedy algorithm called Covariance Thresholding (CT), which can be seen as a generalization of Diagonal Thresholding. We provide experimental results suggesting that CT is consistent for $k=O(\sqrt{n})$; see Section 3 for details. Recently, following our work, Deshpande and Montanari rigorously proved that a variant of our CT algorithm indeed asymptotically recovers the support of $\mathbf{z}$ up to these sparsity levels. Finally, we note that despite our results, there are other settings, such as estimating sparse eigenvectors of correlation matrices, where SDP-based methods are provably better than diagonal thresholding, possibly even achieving the relevant minimax rates .

We consider the single-spike model defined in (3) in high-dimensional settings whereby $(n,p,k)\to\infty$ and $p/n^{\alpha}\to c$ for positive constants $c,\alpha\geq 1$. We further assume that the $k$-sparse vector $\mathbf{z}$ has $k$ nonzero entries of the form $\pm 1/\sqrt{k}$. In what follows, we denote by $\operatorname{supp}(\mathbf{x})$ the set $\{i\dvtx\mathbf{x}_{i}\neq 0\}$. In the analysis, we assume without loss of generality that the nonzero coordinates of the spike $\mathbf{z}$ are exactly its first $k$ coordinates, that is, $\operatorname{supp}(\mathbf{z})=\{1,2,\ldots,k\}$.

For the case $\alpha=1$, that is, $p/n\to c$, we focus on weak signal strengths $\beta\leq\sqrt{\frac{p}{n}}$, whereas when $\alpha>1$, the signal strength may grow to infinity provided it still satisfies $\beta\leq\sqrt{\frac{p}{n}}$; see assumption (b) below. The reason is that when $\alpha=1$ and $\beta>\sqrt{\frac{p}{n}}$, as the next theorem shows, recovering the support of $\mathbf{z}$ is computationally easy, almost up to the information limit. As before, we let $\kappa_{n,p}=\sqrt{n/\log p}$.

Fix $c>1$ and $\beta>\sqrt{c}$, and let $(n,p,k)\to\infty$ such that $p/n\to c$ and $k/\kappa_{n,p}^{2}\to 0$. Let $\hat{\mathbf{w}}_{1}$ be the leading eigenvector of ${\hat{\Sigma}}$, and denote by $\operatorname{supp}_{k}(\hat{\mathbf{w}}_{1})$ its $k$ largest entries in absolute value. Then $\operatorname{supp}_{k}(\hat{\mathbf{w}}_{1})=\operatorname{supp}(\mathbf{z})$ with probability tending to one as $(n,p,k)\to\infty$.

Our next results, stated in the three theorems below, refer to the following assumptions: {longlist}[(a)]

Fix positive $c,\alpha\geq 1$, and let $(n,p,k)\to\infty$ such that $p/n^{\alpha}\to c$.

The signal strength, either fixed or growing with $n,p$, satisfies $\beta\leq\sqrt{\frac{p}{n}}$.

The sparsity level $k$ satisfies $k\geq 2p/\sqrt{n}$, and $k/p\to 0$.

We next analyze the quality of the output $\hat{\mathbf{z}}$ of Algorithm 1, as measured by its cosine-similarity to the planted spike $\mathbf{z}$.

Assume (a)–(c). Then there exists ${\varepsilon}={\varepsilon}(n)\to 0$, such that if $X$ is a solution of SDP (2), and $\lambda_{1}$ is its largest eigenvalue, then with probability tending to one as $(n,p,k)\to\infty$, the output $\hat{\mathbf{z}}$ of Algorithm 1 satisfies

The following corollary of Theorem 1.2 shows that the SDP solution is far from $\mathbf{z}\mathbf{z}^{T}$. For a matrix $A$ we denote its spectral norm by $\|A\|=\sqrt{\lambda_{\max}(AA^{T})}$.

Assume (a)–(c), and further that $p\geq 150^{4}n$. Let $X$ be a solution of SDP (2). Then $\|X-\mathbf{z}\mathbf{z}^{T}\|\geq\frac{1}{3}$ with probability tending to one as $(n,p,k)\to\infty$.

Assume for contradiction that the matrix $Y=X-\mathbf{z}\mathbf{z}^{T}$ has a small spectral norm $\eta_{1}=\|Y\|<1/3$. Using Weyl’s inequality , $\|X\|\geq\|\mathbf{z}\mathbf{z}^{T}\|-\|Y\|$. Since $\|\mathbf{z}\|_{2}=1$, the largest eigenvalue of $X$ is thus lower bounded by $\lambda_{1}\geq 1-1/3=2/3$. Let $\hat{\mathbf{z}}$ be a (unit-length) eigenvector of $X$ corresponding to this largest eigenvalue $\lambda_{1}$. Recalling the variational definition of the largest eigenvector of a matrix, we obtain

Using our assumption, $\hat{\mathbf{z}}^{T}Y\hat{\mathbf{z}}\leq\|Y\|=\eta_{1}\leq 1/3$. By Theorem 1.2

Plugging $p/n=150^{4}$, $\beta\leq\sqrt{p/n}=150^{2}$ and $\lambda_{1}\geq 2/3$ into equation (7) gives that its right-hand side is at most $0.2315+\frac{3}{2}{\varepsilon}$. Since by Theorem 1.2, ${\varepsilon}={\varepsilon}(n)\to 0$ as $n\to\infty$, (7) is strictly smaller than $1/3$ for a sufficiently large $n$. Combining (6) and (7) we arrive at the following contradictory set of inequalities:

Note that the constant 23 appearing in equation (5), and consequently the factor $150^{4}$ in the corollary, are not necessarily optimal. Both may be further reduced at the expense of more involved proofs.

Further note that if $\lambda_{1}(X)$ is bounded away from zero as $p,n\to\infty$, then for $\alpha>1$, equation (5) implies that $\langle{\hat{\mathbf{z}},\mathbf{z}}\rangle\to 0$. Namely, in this case the output of Algorithm 1 is nearly orthogonal to $\mathbf{z}$. Such an empirical behavior of $\lambda_{1}$ was observed in our experimental results; see Figure 4.

We prove Theorem 1.2 using the next result, which itself may be of interest as it bounds the value of SDP (2). Recall that the SDP solution is highly nonlinear in its inputs, and therefore no closed-form explicit expression is known for the solution $X$ or the SDP value $\langle{\hat{\Sigma}},X\rangle$.

Assume (a)–(c). Then there exists $\zeta=\zeta(n)\to 0$ such that with probability tending to one as $(n,p,k)\to\infty$, every solution $X$ of SDP (2) satisfies

For $\alpha>1$, the ratio between the upper and lower bounds in (8) is at most $1+O(\zeta+\sqrt{\frac{n}{p}}(1+\sqrt{\beta}))$ and tends to one as $p,n\to\infty$.

For the important regime $\alpha=1$, we can use Theorem 1.4 to sharpen our conclusion from Theorem 1.2 and show that with probability tending to one, not only $X\neq\mathbf{z}\mathbf{z}^{T}$, but $X$ is not even rank one. We arrive at this conclusion by combining Theorem 1.4 with the next theorem.

Assume (a)–(c), and in addition $\alpha=1$, $c>20$ and $k/(p/\log^{2}p)\to 0$. Then with probability tending to one as $(n,p,k)\to\infty$, every rank-one matrix $Y=\mathbf{y}\mathbf{y}^{T}$ that is feasible for SDP (2) satisfies

To see that the solution $X$ of SDP (2) is indeed not rank one, we compare the upper bound in (9) with the (larger) lower bound in (8), namely, $\langle{\hat{\Sigma}},Y\rangle\leq\frac{8}{9}\cdot\frac{p}{n}<(1-\zeta)(1+\frac{p}{n})\leq\langle{\hat{\Sigma}},X\rangle$.We remark that another lower bound $\langle{\hat{\Sigma}},X\rangle\geq 1+\beta$ was proved in , Proposition 6.1, in a setting similar to Theorem 1.4, but we cannot use it to derive $\langle{\hat{\Sigma}},Y\rangle<\langle{\hat{\Sigma}},X\rangle$ because $\frac{8}{9}\frac{p}{n}$ could be larger than $1+\beta$.

Our result differs from in several respects. First, our results are unconditional; that is, Theorems 1.2–1.5 are not based on any computational hardness assumptions, and thus remain valid even if future developments will yield a polynomial-time algorithm for finding a hidden clique of size $n^{0.49}$. Second, our focus is on estimation and not on detection, which in general are different problems.

We summarize in Figure 1 the picture emerging from the results of Amini and Wainwright , Berthet and Rigollet , Deshpande and Montanari and our work. Based on these results and the fact that even a sophisticated SDP-based algorithm fails to estimate $\mathbf{z}$ for $k\geq\sqrt{n}$, we conclude with the following conjecture.

Organization. In Section 2 we describe our covariance thresholding algorithm, followed by experimental results in Section 3. In Section 4 we give a short proof of Theorem 1.1. In Section 5 we assert preliminary facts that will be later used in the proofs of Theorem 1.2 in Section 6, Theorem 1.4 in Section 7 and Theorem 1.5 in Section 8.

Covariance thresholding algorithm

We present some intuition as to why we expect this algorithm to work. From the definition of ${\hat{\Sigma}}$ in (3), it follows easily that the off-diagonal noise entries have expected value zero and standard deviation $1/\sqrt{n}$, while for signal entries the expected value is $\pm\beta/k$ with s.d. $C(\beta)/\sqrt{n}$. Consider, for example, a signal strength $\beta=1$, sparsity $k\leq\sqrt{n}/10$ (where 10 is rather arbitrary), and choose $t=5/\sqrt{n}$. Then for a noise entry to survive thresholding, it must deviate from its mean by $5$ s.d. and an analogous deviation for a signal entry to be zeroed out. Both events happen with small constant probability; hence most noise entries are zeroed and a constant fraction of signal entries survive. In fact, when $k=O(\sqrt{n/\log p})$ one can easily show that CT, similar to DT, recovers the support of $\mathbf{z}$. Recently, Deshpande and Montanari proved that a variant of our algorithm is consistent up to sparsity levels $k=O(\sqrt{n})$. Their proof method is not directly applicable to our algorithm, but simulation results, detailed below, suggest that our algorithm is also able to recover the correct support up to $k=O(\sqrt{n})$. Hence, covariance thresholding is thus far the only algorithm, with polynomial run-time, that can provably recover the support up to sparsity levels $k=O(\sqrt{n})$.

Simulation results

We compare a few algorithms under the following setup. We generate $n$ i.i.d. samples $\mathbf{x}_{i}$ from the single-spike model (3) with a spike $\mathbf{z}$ of the form $\mathbf{z}=(\frac{1}{\sqrt{k}},\frac{1}{\sqrt{k}},\ldots,\break\frac{1}{\sqrt{k}},0,0,\ldots,0)$. We assume the sparsity level $k$ is a priori known, and say that an execution of an algorithm is successful if it returns the support of $\mathbf{z}$ exactly, that is, if the output is the set $\{1,\ldots,k\}$. The success rate of an algorithm in $M$ independent executions is the number of times it is successful divided by $M$. In each experiment we fix $n=p$ and for various values of $k$ we measure the success rate averaged over $M=500$ independent executions. Figure 2 compares the performance of our CT algorithm to DT. It is evident from this figure that in our setting, CT outperforms DT. Figure 3 shows the success rate of CT as a function of the sparsity level $k$ scaled by $\sqrt{n}$, plotted for five different values of $n$. These results reinforce our prediction that CT works up to sparsity levels proportional to $\sqrt{n}$ (perhaps even slightly more).

2 SDP (Algorithm \texorpdfstring11) versus diagonal thresholding

We run Algorithm 1 with parameters $n=p=50$ and $\beta=0.8$, averaging over $M=100$ runs. We solve the SDP in line 2 of Algorithm 1 using SeDuMi 1.2.1 . Figure 4 plots the dot-product (in absolute value) between $\hat{\mathbf{z}}$, the output of Algorithm 1 and the planted spike $\mathbf{z}$. As expected, the dot-product gets smaller as the sparsity $k$ increases. For comparison, the figure plots also the recovery rate of DT, which also deteriorates as $k$ increases. The figure also shows the largest eigenvalue of the SDP solution $X$; we remark that this value is rather close to one, even when the output of Algorithm 1 is far from $\mathbf{z}$, and is certainly bounded away from , as assumed in the discussion following Theorem 1.2.

Proof of Theorem \texorpdfstring1.11.1 (Strong signal)

Let $\hat{\mathbf{w}}_{1}$ be the leading eigenvector of ${\hat{\Sigma}}$, and write it as a linear combination of the spike $\mathbf{z}$ and some unit vector $\mathbf{a}\perp\mathbf{z}$, namely, $\hat{\mathbf{w}}_{1}=g\mathbf{z}+\sqrt{1-g^{2}}\mathbf{a}$. We may assume $g\in$ by negating $\hat{\mathbf{w}}_{1}$, if necessary. According to , Theorem 4, for our setting of $\beta>\sqrt{c}$,

With probability tending to one, all entries of $\mathbf{a}$ are bounded in absolute value by $h\sqrt{\frac{\log p}{p}}$ for a suitable constant $h>0$.

Lemma 4.1 implies that with probability tending to one, for all $i\in[1,k]$ we have $|(\hat{\mathbf{w}}_{1})_{i}|\geq\frac{g}{\sqrt{k}}-\sqrt{1-g^{2}}\cdot h\sqrt{\frac{\log p}{p}}$, and for all $i\in[k+1,p]$ we have $|(\hat{\mathbf{w}}_{1})_{i}|\leq\sqrt{1-g^{2}}\cdot h\sqrt{\frac{\log p}{p}}$. To correctly identify the support of $\mathbf{z}$, it suffices to require a gap between signal and nonsignal coordinates, namely,

Solving for $k$ and using (10), this inequality holds whenever $k<h^{\prime}p/\log p$ for suitable $h^{\prime}=h^{\prime}(\beta)>0$, which in turn holds with probability tending to one, because our assumption $k/\kappa_{n,p}^{2}=k/(n/\log p)\to 0$ implies $k/(p/\log p)\to 0$. This completes the proof of Theorem 1.1.

Preliminaries

In this section we record a few standard results that will be used later in the proofs. The first is a large deviation result for a Chi-square random variable.

Let $X\sim\chi^{2}_{n}$. For all $x\geq 0$,

The second lemma records a well-known argument about the inner-product of two high-dimensional Gaussians.

For every fixed realization of $\mathbf{x}$, we have $x_{i}y_{i}\sim{{N}}(0,x_{i}^{2})$ and by the independence of the $y_{i}$’s,

The lemma follows by observing that $\|\mathbf{x}\|^{2}\sim\chi^{2}_{n}$.

The next proposition establishes an upper bound on $\lambda_{\max}({\hat{\Sigma}})$, the maximal eigenvalue of the sample covariance matrix ${\hat{\Sigma}}$, in the single-spike model, in two regimes: (i) $p/n^{\alpha}\to c$ for positive $c,\alpha\geq 1$ and (ii) $p/n\to 0$. The spectrum of the covariance matrix has been studied extensively in the literature. Specifically, both Baik and Silverstein , Theorem 1.2 and Johnstone , Theorem 1.1, provide the limiting behavior of $\lambda_{\max}({\hat{\Sigma}})$ for $p/n\to c\geq 1$ (i.e., $\alpha=1$). The regime of a fixed $p$ with $n\to\infty$ which implies $p/n\to 0$ was analyzed in , Chapter 3, for example. Since we could not locate a reference for the case $p/n^{\alpha}\to c$ and $\alpha>1$, or for $p/n\to 0$ and $p$ not necessarily fixed, we provide the following proposition. The proof uses standard arguments and is given in Section 9.

Let ${\hat{\Sigma}}$ be a $p\times p$ sample covariance matrix of $n$ samples in the $k$-sparse single-spike model with signal strength $\beta>0$, arbitrary $k$ and either: (i) $p/n\to 0$ or (ii) $p/n^{\alpha}\to c$ for positive constants $c,\alpha\geq 1$. Then there exists an ${\varepsilon}={\varepsilon}(n)\to 0$ such that with probability tending to one as $n\to\infty$,

Let ${\hat{\Sigma}}$ be a $p\times p$ sample covariance matrix of $n$ samples and a $k$-sparse spike $\mathbf{z}$ with signal strength $\beta>0$. Further assume that $k/n\to 0$. Then there exists an ${\varepsilon}={\varepsilon}(n)\to 0$ such that with probability tending to one as $n\to\infty$, for every rank-one trace-one $p\times p$ matrix $Y=\mathbf{y}\mathbf{y}^{T}$ with $\operatorname{supp}(\mathbf{y})\subseteq\operatorname{supp}(\mathbf{z})$,

hence $\sup_{Y}\langle{\hat{\Sigma}},Y\rangle\leq\lambda_{\max}({\hat{\Sigma}}_{\mathbf{z}})$. Now the desired upper bound on $\lambda_{\max}({\hat{\Sigma}}_{\mathbf{z}})$ follows using the fact $k/n\to 0$ from Proposition 5.3, that is, plugging $p=k$ into (11).

Our next proposition estimates $\operatorname{tr}({\hat{\Sigma}})$ and $\operatorname{tr}({\hat{\Sigma}}^{2})$ for the case $\beta=0$ (no signal). These estimates were derived in , Proposition 1, for example, but again only for $\alpha=1$. For lack of reference we reprove it for $\alpha\geq 1$ in Section 9.

Let ${\hat{\Sigma}}$ be a $p\times p$ sample covariance matrix of $n$ multivariate Gaussian observations whose population covariance matrix is the identity. Assume that $(\log p)/n\to 0$ as $n,p\to\infty$. Then there exists an ${\varepsilon}={\varepsilon}(n)\to 0$ such that with probability tending to one as $n\to\infty$,

Proof of Theorem \texorpdfstring1.21.2 (Cosine similarity)

Let us first provide a high-level description of the proof idea. We can bound $\langle{\hat{\Sigma}},X\rangle$ from below (using Theorem 1.4, which we prove in Section 7, and as mentioned earlier is used here) and $\lambda_{\max}({\hat{\Sigma}})$ from above (using Proposition 5.3) both by roughly $\frac{p}{n}$. Now suppose $\lambda_{1}$ is not too small; then on the right-hand side of (12), a large contribution must come from the first term $\lambda_{1}\hat{\mathbf{z}}^{T}{\hat{\Sigma}}\hat{\mathbf{z}}$. But the quadratic form $\hat{\mathbf{z}}^{T}{\hat{\Sigma}}\hat{\mathbf{z}}$ has small value in the direction $\hat{\mathbf{z}}=\mathbf{z}$ (using Corollary 5.4), and thus $\hat{\mathbf{z}}$ and $\mathbf{z}$ cannot be too close to each other.

We now proceed to the detailed proof, starting with a lower bound on $\lambda_{1}\hat{\mathbf{z}}^{T}{\hat{\Sigma}}\hat{\mathbf{z}}$. Assume henceforth that the high-probability event asserted by Theorem 1.4 indeed occurs; namely, inequality (8) holds. Similarly Corollary 5.4 implies that inequality (11) holds. Plugging these two bounds into (12) and using $\lambda_{1}>0$, we get

Observe that $\sqrt{\frac{p}{n}}\geq\frac{1}{1+{\varepsilon}_{1}}$ for suitable ${\varepsilon}_{1}\to 0$ and sufficiently large $n,p$. In addition, assumption (b) yields that $\beta\leq\sqrt{\frac{p}{n}}\leq(1+{\varepsilon}_{1})\frac{p}{n}$. For suitable ${\varepsilon}_{2}=O(\zeta+{\varepsilon}+{\varepsilon}_{1})$, we get

Next, we analyze the quadratic form $\hat{\mathbf{z}}^{T}{\hat{\Sigma}}\hat{\mathbf{z}}$ in terms of $\gamma=\langle{\hat{\mathbf{z}},\mathbf{z}}\rangle\in$. Write $\hat{\mathbf{z}}=\gamma\mathbf{z}+\sqrt{1-\gamma^{2}}\mathbf{s}$, where $\mathbf{s}$ is a unit vector orthogonal to $\mathbf{z}$, and recall that our goal is to upper bound $\gamma^{2}$. Using Cauchy–Schwarz and the triangle inequality,

Since ${\hat{\Sigma}}$ is PSD, it can be written as ${\hat{\Sigma}}=B^{T}B$ for some matrix $B$ whose spectral norm is $\|B\|=\|B^{T}\|=\sqrt{\lambda_{\max}({\hat{\Sigma}})}$. Assume henceforth that the high-probability event asserted by Corollary 5.4 indeed occurs, and we have $\|B\mathbf{z}\|^{2}=\mathbf{z}^{T}{\hat{\Sigma}}\mathbf{z}=\langle{\hat{\Sigma}},\mathbf{z}\mathbf{z}^{T}\rangle\leq(1+{\varepsilon}_{3})(1+\sqrt{\beta})^{2}$ for suitable ${\varepsilon}_{3}\to 0$. Using Proposition 5.3 similarly yields $\|B\|^{2}=\lambda_{\max}({\hat{\Sigma}})\leq(1+{\varepsilon}_{4})(1+\sqrt{\frac{p}{n}}+\sqrt{\beta})^{2}$ for suitable ${\varepsilon}_{4}\to 0$. Together, for suitable ${\varepsilon}_{5}=O({\varepsilon}_{3}+{\varepsilon}_{4}+{\varepsilon}_{1})$,

Plugging these into (6) and using $|\gamma|\leq 1$ and $\sqrt{1-\gamma^{2}}\leq 1-\frac{\gamma^{2}}{2}\leq 1$, we have

Now combining this upper bound (15) with our lower bound 13 (after dividing by $\lambda_{1}$), gives

For sufficiently large $n,p$, this yields the bound on $\gamma^{2}=|\langle{\hat{\mathbf{z}},\mathbf{z}}\rangle|^{2}$ asserted in (5), and completes the proof of Theorem 1.2.

Proof of Theorem \texorpdfstring1.41.4 (SDP value)

We start with the upper bound on $\langle{\hat{\Sigma}},X\rangle$. The idea is to drop the constraint $\|X\|_{S}\leq k$ from SDP (2), and show that the value of the resulting SDP, which can only be bigger, is actually $\lambda_{\max}({\hat{\Sigma}})$, and is thus bounded by Proposition 5.3.

Formally, let $X$ be a solution to SDP (2), and let us argue that (with probability $1$)

Indeed, the inequality holds because we have just relaxed SDP (2). The equality holds by the following standard argument. Writing $Y=\sum_{i}\mu_{i}\mathbf{y}_{i}\mathbf{y}_{i}^{T}$, where $\{\mu_{i}\}_{i}$ are the eigenvectors of $Y$ and $\{\mathbf{y}_{i}\}_{i}$ is a corresponding orthonormal eigenbasis, we have

and equality is achieved when maximizing over all relevant $Y$, by taking $Y=\mathbf{y}_{1}\mathbf{y}_{1}^{T}$ to be a rank-one matrix where $\mathbf{y}_{1}$ is a leading eigenvector of ${\hat{\Sigma}}$.

To conclude the upper bound asserted in the theorem, we combine the above with Proposition 5.3, and get that for a suitable ${\varepsilon}={\varepsilon}(n)\to 0$ with probability tending to one as $n\to\infty$,

We turn to proving the lower bound on $\langle{\hat{\Sigma}},X\rangle$. The idea is to consider a specific $X^{*}$ which is feasible (but not necessarily optimal) for SDP (2), and compute its objective value $\langle{\hat{\Sigma}},X^{*}\rangle$. Our $X^{*}$ is based on taking the nonsignal part of ${\hat{\Sigma}}$ [which is a $(p-k)\times(p-k)$ submatrix], padded with zeros elsewhere, and “forcing” it to satisfy the constraints of SDP (2) by scaling it to be trace-one.

We prove below that with probability tending to one, the following inequalities hold for a suitable $\zeta=\zeta(n)\to 0$:

Combining this with $X^{*}\in\mathcal{S}^{p}_{+}$ and $\operatorname{tr}(X^{*})=1$, which hold by construction, will prove that with probability tending to one, $X^{*}$ is feasible and has a high-objective value.

Let us now prove inequality (17). First, using Cauchy–Schwarz,

By the above bounds from Proposition 5.5, with probability tending to one,

which together imply that $\|X^{*}\|_{S}\leq(p-k)\frac{1+{\varepsilon}}{1-{\varepsilon}}\sqrt{\frac{3}{n}}\leq\frac{2p}{\sqrt{n}}\leq k$.

We next prove inequality (18). First, we expand

By the above bounds from Proposition 5.5, with probability tending to one,

for a suitable $\zeta=\zeta(n)\to 0$, where we used here that $k/p\to 0$ by assumption (c). Altogether, we conclude that $\langle{\hat{\Sigma}},X^{*}\rangle\geq(1-\zeta)(1+\frac{p}{n})$.

Having proved inequalities (18) and (17), we conclude that with probability tending to one, $X^{*}$ is feasible and has a high objective value, which establishes a lower bound on the optimal SDP value $\langle{\hat{\Sigma}},X\rangle$, and completes the proof of Theorem 1.4.

Proof of Theorem \texorpdfstring1.51.5 (SDP value)

Let $F$ be the set of all vectors $\mathbf{y}$ whose corresponding rank-one matrix $Y=\mathbf{y}\mathbf{y}^{T}$ is feasible for SDP (2), formally,

The sets $\hat{F},F$ defined above satisfy $F\subseteq\hat{F}_{1/40}$.

Recall that $\beta\leq\sqrt{\frac{p}{n}}$ and that for sufficiently large $n,p$ we have $\frac{p}{n}\geq 20$. Hence by straightforward manipulations, we conclude that as $(n,p,k)\to\infty$, with probability tending to one $\langle{\hat{\Sigma}},Y\rangle\leq\frac{8}{9}\frac{p}{n}$, which proves Theorem 1.5.

Recall from (3) that ${\mathbf{x}}_{i}=\sqrt{\beta}u_{i}{\mathbf{z}}+\bolds\xi_{i}$, where $\bolds\xi_{i}$ is a vector of independent standard Gaussian random variables, and $u_{i}$ is also a standard Gaussian. Therefore,

The first term $\langle{\bolds\xi_{i},\mathbf{y}}\rangle$ has distribution $N(0,\|\mathbf{y}\|^{2})$. Since $u_{i}$ is independent of $\bolds\xi_{i}$, the distribution of $\langle{\mathbf{x}_{i},\mathbf{y}}\rangle$ is just $N(0,\|\mathbf{y}\|^{2}+\beta\langle\mathbf{y},\mathbf{z}\rangle^{2})$. Furthermore, since $\mathbf{y}$ is fixed and the $\bolds\xi_{i}$’s and $u_{i}$’s are all independent, the random variables $\langle{\mathbf{x}_{i},\mathbf{y}}\rangle$ for $i=1,\ldots,n$ are i.i.d., and thus

Lemma 5.1 with $x=n/9$ implies that $\operatorname{Pr}[\chi^{2}_{n}\geq 2n]\leq e^{-n/9}$. We conclude that with probability at least $1-e^{-n/9}$,

where the second inequality uses the Cauchy–Schwarz inequality.

Finally, observe that (19) indeed follows from Lemmas 8.2 and 8.3 by a union bound,

where the last inequality follows from the assumption in Theorem 1.5 that $k/(p/\log^{2}p)\to 0$ and that $p/n\to c$. This completes the proof of (19) and of Theorem 1.5.

Deferred proofs from Section \texorpdfstring55 (preliminaries)

where $U$ is a $p\times n$ matrix whose first row is $(u_{1},\ldots,u_{n})$ and the remaining rows are zero (recall $\mathbf{z}=\mathbf{e}_{1}$), and $\Xi$ is an $p\times n$ matrix whose $i$th column is $\bolds\xi_{i}$. Let $\|A\|=\sqrt{\lambda_{\max}(A^{T}A)}$ be the spectral norm of a matrix $A$. Using also $\|A\|=\|A^{T}\|$ and the triangle inequality,

The matrix $\Xi^{T}\Xi$ follows a Wishart distribution (note that the roles of $p$ and $n$ are reversed). Therefore by , Theorem 2, which applies to the regime $p/n\to 0$ and $p/n\to\infty$, and by , Theorem 1.1, which applies to $p/n\to c\in(0,\infty)$, we know that with probability tending to one,

for some ${\varepsilon}_{1}={\varepsilon}_{1}(n)\to 0$. Since $U^{T}U$ has rank one, $\|U\|^{2}=\lambda_{\max}(U^{T}U)=\operatorname{tr}(U^{T}U)=\sum_{i=1}^{n}u_{i}^{2}\sim\chi^{2}_{n}$. Lemma 5.1 with $x=3\log n$ implies that with probability at least $1-1/n^{3}$,

and thus with probability tending to one, $\|U\|\leq(1+{\varepsilon}_{2})\sqrt{n}$ for some ${\varepsilon}_{2}={\varepsilon}_{2}(n)\to 0$.

Plugging these bounds into (23), we conclude that with probability tending to one as $n\to\infty$,

which completes the proof of Proposition 5.3.

Proof of Proposition 5.5 Starting with $\operatorname{tr}({\hat{\Sigma}})$, observe that ${\hat{\Sigma}}_{ii}\sim\frac{1}{n}\chi^{2}_{n}$. Lemma 5.1 with $x=5\ln p$ implies that with probability at least $1-1/p^{5}$, $\chi^{2}_{n}\leq(1+{\varepsilon}_{1})n$ for ${\varepsilon}_{1}=O(\sqrt{(\log p)/n})\to 0$. Taking a union bound over $i=1,\ldots,p$, we obtain that with probability at least $1-1/p^{4}$, all entries ${\hat{\Sigma}}_{ii}\in[1-{\varepsilon}_{1},1+{\varepsilon}_{1}]$, which implies

By the preceding paragraph, with probability at least $1-1/p^{4}$, $\sum_{i=1}^{p}{\hat{\Sigma}}_{ii}^{2}\in[(1-{\varepsilon}_{1})^{2}p,(1+{\varepsilon}_{1})^{2}p]$. Using the notation of (3), we write off-diagonal entries in ${\hat{\Sigma}}$ as ${\hat{\Sigma}}_{ij}=\frac{1}{n}\sum_{s=1}^{n}\bolds\xi_{si}\bolds\xi_{sj}:=\frac{1}{n}\bolds\rho_{i}^{T}\bolds\rho_{j}$, where $\bolds\rho_{i}=(\bolds\xi_{si})_{s=1}^{n}$, and notice that $\bolds\rho_{1},\ldots,\bolds\rho_{p}$ are independent.

Now fix $i$ and condition on $\bolds\rho_{i}$. Then Lemma 5.2 implies that each off-diagonal entry along row $i$ is distributed ${\hat{\Sigma}}_{ij}\sim\frac{1}{n}\|\bolds\rho_{i}\|\cdot\hat{y}_{j}$, $\hat{y}_{j}\sim N(0,1$). Moreover the $\hat{y}_{j}$’s (for different $j\neq i$) are independent, hence, $\sum_{j\neq i}{\hat{\Sigma}}_{ij}^{2}\sim\frac{1}{n^{2}}\|\bolds\rho_{i}\|^{2}\chi_{p-1}^{2}$. Using Lemma 5.1 with $x=4\log p$, with probability at least $1-1/p^{4}$,

for ${\varepsilon}_{2}=O(\sqrt{(\log p)/p})$.

Next, remove the conditioning on $\bolds\rho_{i}$ (still for a fixed $i$), observing that $\|\bolds\rho_{i}\|^{2}\sim\chi^{2}_{n}$. Lemma 5.1 with $x=4\log p$ then implies that with probability at least $1-1/p^{4}$, we have $\|\bolds\rho_{i}\|^{2}\in[(1-{\varepsilon}_{3})n,(1+{\varepsilon}_{3})n]$ for ${\varepsilon}_{3}=O(\sqrt{(\log p)/n})$.

Finally, taking the union bound over rows $i=1,\ldots,p$ and also the sum along the diagonal, with probability at least $1-3/p^{3}$,

for a suitably chosen ${\varepsilon}_{4}={\varepsilon}_{4}(n)\to 0$. Similarly, $\operatorname{tr}({\hat{\Sigma}}^{2})\geq(1-{\varepsilon}_{5})p(1+\frac{p}{n})$ for ${\varepsilon}_{5}={\varepsilon}_{5}(n)\to 0$. To complete the proof of Proposition 5.5, set ${\varepsilon}=\max\{{\varepsilon}_{1},{\varepsilon}_{4},{\varepsilon}_{5}\}$.

References