Simultaneous support recovery in high dimensions: Benefits and perils of block $\ell_1/\ell_\infty$-regularization

Introduction

The area of high-dimensional statistical inference is concerned with the behavior of models and algorithms in which the dimension $p$ is comparable to, or possibly even larger than the sample size $n$. In the absence of additional structure, it is well-known that many standard procedures—among them linear regression and principal component analysis—are not consistent unless the ratio $p/n$ converges to zero. Since this scaling precludes having $p$ comparable to or larger than $n$, an active line of research is based on imposing structural conditions on the data (e.g., sparsity, manifold constraints, or graphical model structure), and studying the high-dimensional consistency (or inconsistency) of various types of estimators.

Consider the problem of image denoising or compression, say using a wavelet transform or some other type of multiresolution basis . It is well known that natural images tend to have sparse representations in such bases . Moreover, similar images—say the same scene taken from multiple cameras—would be expected to share a similar subset of active features in the reconstruction. Consequently, one might expect that using a block-regularizer that enforces such joint sparsity could lead to improved image denoising or compression.

Finally, consider a standard problem in genetic analysis: given a set of gene expression arrays, where each array corresponds to a different patient but the same underlying tissue type (e.g., tumor), the goal is to discover the subset of features relevant for tumorous growths. This problem can be expressed as a joint regression problem, again with a shared sparsity constraint coupling together the different patients. In this context, the recent work of Liu et al. shows that imposing additional structural constraints can be beneficial (e.g., they are able to greatly reduce the number of expressed genes while maintaining the same prediction performance).

Given these structural conditions of shared sparsity in these and other applications, it is reasonable to consider how this common structure can be exploited so as to increase the statistical efficiency of estimation procedures.

Answers to these questions yield useful insight into the tradeoff between computational and statistical efficiency in high-dimensional inference. Indeed, the convex programs that arise from using block-regularization typically require a greater computational cost to solve. Accordingly, it is important to understand under what conditions this increased computational cost guarantees that fewer samples are required for achieving a fixed level of statistical accuracy.

In words, for any $\delta>0$ and for scalings of the quadruple $(n,p,s,\alpha)$ such that $\theta_{1,\infty}\geq 1+\delta$, the probability of successfully recovering both $S(\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{2.84009pt}{0.43057pt}}{\beta}^{\,1})$ and $S(\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{2.84009pt}{0.43057pt}}{\beta}^{\,2})$ converges to one, whereas for scalings such that $\theta_{1,\infty}\leq 1-\delta$, the probability of success converges to zero.

the stacks of curves shift to the right as the overlap parameter $\alpha$ decreases from $1$ towards , showing that problems with less overlap require a larger rescaled sample size. More interesting is the sharpness of agreement in quantitative terms: the vertical lines in the center of each stack show the point at which our theory (1) predicts that the method should transition from failure to success.

The remainder of this paper is organized as follows. In Section 2, we provide a precise description of the problem. Section 3 is devoted to the statement of our main results, some discussion of their consequences, and illustration by comparison to empirical simulations. In Section 4, we provide an outline of the proof, with the technical details of many intermediate lemmas deferred to the appendices.

We use the following standard asymptotic notation: for functions $f,g$, the notation $f(n)=\mathcal{O}(g(n))$ means that there exists a fixed constant $0<C<+\infty$ such that $f(n)\leq Cg(n)$; the notation $f(n)=\Omega(g(n))$ means that $f(n)\geq Cg(n)$, and $f(n)=\Theta(g(n))$ means that $f(n)=\mathcal{O}(g(n))$ and $f(n)=\Omega(g(n))$.

Problem set-up

We begin by setting up the problem to be studied in this paper, including multivariate regression and family of block-regularized programs for estimating sparse vectors.

where $\lambda_{n}>0$ is a user-defined regularization parameter. Note that the data term is separable across the different regression problems $i=1,\ldots,r$, due to our assumption of independence on the noise vectors. Any coupling between the different regression problems is induced by the block-norm regularization.

corresponding to the subset $U\subseteq\{1,\ldots,p\}$ of indices that are active in at least one regression problem. Note that the cardinality of $|U|$ is upper bounded by $rs$, but can be substantially smaller (as small as $s$) if there is overlap among the different supports.

As discussed at more length in Appendix A, given an estimate of the row support of $\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.73494pt}{0.43057pt}}{B}$, it is possible to either use additional structure of the solution $\widehat{B}$ or perform some additional computation to recover individual signed supports of the columns of $\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.73494pt}{0.43057pt}}{B}$. To be precise, define the sign function

As our development will clarify, this procedure (9) corresponds to estimating the signed support on the basis of a dual optimal solution associated with the optimal primal solution. We discuss the primal-based recovery method and its differences with the dual-based method at more length in Appendix A.

Main results and their consequences

In addition to the sample size $n$, problem dimensions $p$ and $r$, sparsity index $s$ and overlap parameter $\alpha$, our results involve certain quantities associated with the design matrices $X^{i}$. To begin, in the deterministic case, we assume that the columns of each design matrix $X^{i},i=1,\ldots,r$ are normalizedThe choice of the factor $2$ in this bound is for later technical convenience. so that

More significantly, we require that the following incoherence condition on the design matrix be satisfied:

In addition, the statement of our results involve certain quantities associated with the $|U|\times|U|$ matrices $\frac{1}{n}\langle X^{i}_{U},\,X^{i}_{U}\rangle$; in particular, we define a lower bound on the minimum eigenvalue

Remembering that our analysis applies to to sequences $\{X_{n,p}\}$ of design matrices, in the simplest scenario, both of the bounding quantities $C_{\min}$ and $D_{\max}$ do not scale with $(n,p,s)$. To keep notation compact, we write $C_{\min}$ and $D_{\max}$ in the analysis to follow.

The block-regularized program has a unique solution $\widehat{B}$ such that $\bigcup_{i=1}^{r}S(\widehat{\beta}^{\,i})\subseteq U$.

Consequently, as long as $\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.73494pt}{0.43057pt}}{B}_{\operatorname{min}}\geq b_{1}(\xi,\lambda_{n},n,s)$, then $\bigcup_{i=1}^{r}S(\widehat{\beta}^{\,i})=U$, so that the solution $\widehat{B}$ correctly specifies the union of supports $U$.

We now state an analogous result for random design matrices; in particular, consider the observation model (3) with design matrices $X^{i}$ chosen with i.i.d. rows from covariance matrices $\Sigma^{i}$. In analogy to definitions (12) and (13) in the deterministic case, we define the lower bound

Note that unlike the case of deterministic designs, these quantities are not functions of the design matrix $X$, which is now a random variable. Finally, our results involve an analogous incoherence parameter of the covariance matrices $\Sigma=\{\Sigma^{i},i=1,\ldots,r\}$, defined as

With this notation, the following result provides an analog of Theorem 1 for random design matrices:

Suppose that we are given $n$ i.i.d. observations from the model (3) with

for some $\kappa>1$. If we solve the convex program (6) with regularization parameter satisfying \lambda_{n}\geq\frac{4\xi\sigma^{2}}{\gamma^{2}}\big{[}\frac{r^{2}+r\log(p)}{n}] for some $\xi>1$, then with probability greater than

The block-regularized program (6) has a unique solution $\widehat{B}$ such that $\bigcup_{i=1}^{r}S(\widehat{\beta}^{\,i})\subseteq U$.

Consequently, if $B^{*}_{\operatorname{min}}\geq b_{2}(\xi,\lambda_{n},n,s)$, then $\bigcup_{i=1}^{r}S(\widehat{\beta}^{\,i})=U$, so that the solution $\widehat{B}$ correctly specifies the union of supports $U$.

To clarify the interpretation of Theorems 1 and Theorem 2, part (a) of each claim guarantees that the estimator has no false inclusions, in that the row support of the estimate $\widehat{B}$ is contained within the row support of the true matrix $\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.73494pt}{0.43057pt}}{B}$. One consequence of part (b) is that as long as the minimum signal parameter $B^{*}_{\operatorname{min}}$ decays slowly enough, then the estimators have no false exclusions, so that the true row support is correctly recovered.

In this expression, the extra term $\max\{1,s/(r\log p)\}$ arises in the analysis due to the need to control the norms of the random design matrices. For sufficiently sparse problems (e.g., $s=\mathcal{O}(\log p)$), this factor is constant.

2 A phase transition for standard Gaussian ensembles

Consider sequences of problems, indexed by $(n,p,s,\alpha)$ drawn from the observation model (3) with random design $X$ drawn with i.i.d. standard Gaussian entries and with $C_{\min}=1=D_{\max}$.

Success: Suppose that the problem sequence $(n,p,s,\alpha)$ satisfies

Failure: For problem sequences $(n,p,s,\alpha)$ such that

and for any non-increasing regularization sequence $\lambda_{n}>0$, no solution $\widehat{B}=(\widehat{\beta}^{\,1},\widehat{\beta}^{\,2})$ to the block-regularized program (6) has the correct signed support.

Recall that support overlap $S(\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{2.84009pt}{0.43057pt}}{\beta}^{\,1})\cap S(\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{2.84009pt}{0.43057pt}}{\beta}^{\,2})$ has cardinality $\alpha s$ by assumption. Therefore, $T_{\lambda_{n}}(\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.73494pt}{0.43057pt}}{B})$ has at most $\alpha s$ non-zero entries, and moreover $\|T_{\lambda_{n}}(\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.73494pt}{0.43057pt}}{B})\|_{2}^{2}\leq\lambda_{n}^{2}\alpha s$. We then define the rescaled gap limit

Note that $\Delta(\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.73494pt}{0.43057pt}}{B},\lambda_{n})\in[0,\alpha]$ by construction. With these definitions, we have the following:

If for any $\delta>0$, the sample size $n$ is upper bounded as

then the dual recovery method (9) fails to recover the individual signed supports.

3 Illustrative simulations and some consequences

We now seek to explore the dependence of the sample size on the overlap fraction $\alpha\in$ of the two regression vectors. For this purpose, we plot the probability of successful recovery versus the rescaled sample size

As shown by Figure 2(b), when plotted with this rescaling, there is any longer size $p$. Moreover, if we choose the sparsity index $s$ to grow in a fixed way with $p$ (i.e., $s=f(p)$ for some fixed function $f$), then the only remaining free variable is the overlap parameter $\alpha$. Note that the theory predicts that the required sample size should decrease as $\alpha$ increases towards $1$.

As shown earlier in Section 1, Figure 1 plots the probability of successful recovery of the joint supports versus the rescaled samples size $\theta_{1,\infty}(n,p,s,\alpha)$. Notice that the plot shows four sets of ‘stacked” curves, where each stack corresponds to a different choice of the overlap parameter, ranging from $\alpha=1$ (left-most stack), to $\alpha=0.1$ (right-most stack). Each stack contains three curves, corresponding to the problem sizes $p\in\{128,256,512\}$. In all cases, we fixed the support size $s=0.1p$. As with Figure 2(b), the “stacking” behavior of these curves demonstrates that Theorem 3 isolates the correct dependence on $p$. Moreover, their step-like behavior is consistent with the theoretical prediction of a phase transition. Notice how the curves shift towards the left as the overlap parameter $\alpha$ parameter increases towards one, reflecting that the problems become easier as the amount of shared sparsity increases. To assess this shift in a qualitative manner for each choice of overlap $\alpha\in\{0.1,0.3.0.7.1\}$, we plot a vertical line within each group, which is obtained as the threshold value of $\theta_{1,\infty}$ predicted by our theory. Observe how the theoretical value shows excellent agreement with the empirical behavior.

Figure 3 provides an alternative perspective on the data, where we have plotted how the sample size required by block regression changes as a function of the overlap parameter $\alpha\in$. Each set of data points plots a scaled form of the sample size required to hit $50\%$ success, for a range of overlaps, and the straight line $(4-3\alpha)/2$ that is predicted by Theorem 3 Note the excellent agreement between the experimental results, for all three problem sizes for $p\in\{128,256,512\}$, and the full range of overlaps. The line $(4-3\alpha)/2$ also characterizes the relative efficiency $R$ of block regularization versus the naive Lasso-based method, as described in Corollary 2. For overlaps $\alpha>2/3$, this parameter $R$ drops below $1$. On the other hand, for overlaps $\alpha<1$, we have $R>1$, so that applying the joint optimization problem actually decreases statistical efficiency. Intuitively, although there is still some fraction of overlap, the regularization is misleading, in that it tries to enforce a higher degree of shared sparsity than is actually present in the data.

Proofs

If $\widetilde{\beta}^{i}_{k}\neq 0$ for at least one index $i\in\{1,\ldots,r\}$, then

If $\widetilde{\beta}^{i}_{k}=0$ for all $i=1,\ldots,r$, then we require $\sum_{i=1}^{r}|\widetilde{z}^{\,i}_{k}|\leq 1$.

2 Primal-dual construction

We now describe our method for constructing the matrix pair $(\widetilde{B},\widetilde{Z})$. Recalling that $U=\bigcup_{i=1}^{r}S(\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{2.84009pt}{0.43057pt}}{\beta}^{\,i})$ denotes the union of supports of the true regression vectors, let ${U^{c}}$ denote the complement of $\{1,\ldots,p\}\backslash U$. With this notation, Figure 4 provides the four steps of the primal-dual witness construction.

The following lemma summarizes the utility of the primal-dual witness method:

Suppose that for each $i=1,\ldots,r$, the $|U|\times|U|$ sub-matrix $\langle X^{i}_{U},\,X^{i}_{U}\rangle$ is invertible. Then for any $\lambda_{n}>0$, we have the following correspondences:

We provide the proof of Lemma 2 in Appendix D.2. It is convex-analytic in nature, based on exploiting the subgradient optimality conditions associated with both the restricted convex program (29) and the original program (6), and performing some algebra to characterize when the convex program recovers the correct signed support. Lemma 2 lies at the heart of all three of our theorems. In particular, the positive results of Theorem 1, Theorem 2 and Theorem 3(a) are based on claims (i) and (iii), which show that it is sufficient to verify that the primal-dual witness construction succeeds with high probability. The negative result of Theorem 3(b), in contrast, is based on part (ii), which can be restated as asserting that if the primal-dual witness construction fails, then no solution has support contained with $U$.

Before proceeding to the proofs themselves, we introduce some additional notation and develop some auxiliary results concerning the primal-dual witness procedure, to be used in subsequent development. With reference to steps (A) and (B), we show in Appendix D.2 that unique solution $\widetilde{B}_{U}$ has the form

and $\widetilde{z}^{\,i}_{U}$ is the $i^{th}$ column of the sub-gradient matrix $\widetilde{Z}_{U}$.

See the end of Appendix D.2 for derivation of this condition.

Finally, in order to further simplify notation in our proofs, for each $k\in{U^{c}}$, we define the random variable

With this notation, the strict dual feasibility condition (30) is equivalent to the event $\{\max\limits_{k\in{U^{c}}}V_{k}<1\}$.

Proof of Theorem 1

We begin by establishing a set of sufficient conditions for deterministic design matrices, as stated in Theorem 1.

We begin by obtaining control on the probability of the event $\mathcal{E}(V)$, so as to show that step (C) of the primal-dual witness construction succeeds. Recall that $\Pi_{X^{i}_{U}}$ denotes the orthogonal projection onto the range space of $X^{i}_{U}$, and the definition (11) of the incoherence parameter $\gamma\in(0,1]$. By the mutual incoherence condition (11), we have

where we have used the fact that $\sum_{i=1}^{r}|\widetilde{z}^{\,i}_{j}|=1$ for each $j\in U$. Recalling that $V_{k}=\sum_{i=1}^{r}|\widetilde{z}^{\,i}_{k}|$ and using the definition (33), we have by triangle inequality

To analyze this remaining probability, for each index $i=1,\ldots,r$ and $k\in{U^{c}}$, define the random variable

Since the elements of the $n$-vector $w^{i}$ follow a $N(0,\sigma^{2})$ distribution, the variable $W^{i}_{k}$ is zero-mean Gaussian with variance \frac{\sigma^{2}}{\lambda_{n}^{2}\,n^{2}}\big{\langle}X^{i}_{k},\,(I-\Pi_{X^{i}_{U}})X^{i}_{k}\big{\rangle}. Since $\|X^{i}_{k}\|_{2}^{2}\leq 2n$ by assumption and $(I-\Pi_{X^{i}_{U}})$ is an orthogonal projection matrix, the variance of each $W^{i}_{k}$ is upper bounded by $\frac{2\sigma^{2}}{\lambda_{n}^{2}n}$. Consequently, for any choice of sign vector $b\in\{-1,+1\}^{r}$, the variance of the zero-mean Gaussian $\sum_{i=1}^{r}b_{i}W^{i}_{k}$ is upper bounded by $\frac{2r\sigma^{2}}{\lambda_{n}^{2}n}$.

Consequently, by taking the union bound over all sign vectors and over indices $k\in{U^{c}}$, we have

With the choice $\lambda_{n}^{2}\geq\frac{4\xi\sigma^{2}}{\gamma^{2}}\frac{r^{2}+r\log(p)}{n}$ for some $\xi>1$, we conclude that

By Lemma 2(i), this event implies the uniqueness of the solution $\widehat{B}$, and moreover the inclusion of the supports $S(\widehat{B})\subseteq S(\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.73494pt}{0.43057pt}}{B})$, as claimed.

We split the analysis of the random variable $\max_{k\in U}|\Delta^{i}_{k}|$ into two terms, based on the form of $\Delta$ from equation (32), one involving the dual variables $\widetilde{z}^{\,i}_{U}$, and the other involving the observation noise $w^{i}$, as follows:

The second term is easy to control: from the characterization of the subdifferential (Lemma 1), we have $\|\widetilde{z}^{\,i}_{U}\|_{\infty}\leq 1$, so that $T_{b}^{i}\leq\lambda_{n}|\!|\!|(\langle\frac{1}{n}X^{i}_{U},\,X^{i}_{U}\rangle)^{-1}|\!|\!|_{{\infty}}\;\leq\;D_{\max}\lambda_{n}$.

Turning to the first term $T_{a}^{i}$, we note that since $X^{i}_{U}$ is fixed, the $|U|$-dimensional random vector Y:\,=\big{(}\big{\langle}\frac{1}{n}X^{i}_{U},\,X^{i}_{U}\big{\rangle}\big{)}^{-1}\frac{1}{n}\langle X^{i}_{U},\,w^{i}\rangle is zero-mean Gaussian, with covariance \frac{1}{n}\big{(}\big{\langle}\frac{1}{n}X^{i}_{U},\,X^{i}_{U}\big{\rangle}\big{)}^{-1}. Therefore, we have $\operatorname{var}(Y_{k})\leq\frac{1}{C_{\min}n}$, and can use this in standard Gaussian tail bounds. By applying the union bound twice, first over $k\in U$, and then over $i\in\{1,2,\ldots,r\}$, we obtain

where we have used the fact that $|U|\leq rs$. Setting $t=\xi\;\sqrt{\frac{4\log(rs)}{C_{\min}n}}$ yields that

with probability greater than $1-2\exp(-(\xi^{2}-1)\log(rs))$, as claimed.

Finally, to establish support recovery, recall that we proved above that $\Delta^{i}$ is bounded by $b_{1}(\xi,\lambda_{n},n,s)$. Hence, as long as $B^{*}_{\operatorname{min}}>b_{1}(\xi,\lambda_{n},n,s)$, then we are guaranteed that if $\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.73494pt}{0.43057pt}}{B}^{i}_{k}\neq 0$, then $\widehat{B}^{i}_{k}\neq 0$.

Proof of Theorem 2

Recalling that $V_{k}=\sum_{i=1}^{r}|\widetilde{z}^{\,i}_{k}|$ and using the definition (33), we have the decomposition

In order to show that $\max_{k\in{U^{c}}}|V_{k}|<1$ with high probability, we deal with each of these two terms in turn, showing that $M_{1}<\gamma/2$, and $M_{2}<1-\gamma/2$, both with high probability.

In order to bound $M_{1}$, we require the following condition on the columns of the design matrices:

This claim follows immediately by union bound and concentration results for $\chi^{2}$-variates; in particular, the bound (66a) in Appendix E.

Under the condition of Lemma 3, each variable W^{i}_{k}:\,=\frac{1}{\lambda_{n}n}\big{\langle}X^{i}_{k},\,(I-\Pi_{X^{i}_{U}})w^{i}\big{\rangle} is zero-Gaussian, with variance at most $\frac{2\sigma^{2}}{\lambda_{n}^{2}n}$. Consequently, for any choice of signs $b\in\{-1,+1\}^{r}$, the vector $\sum_{i=1}^{r}b_{i}W^{i}_{k}$ is zero-mean Gaussian, with variance at most $\frac{2\sigma^{2}r}{\lambda_{n}^{2}n}$. Therefore, for any $t>0$, we have

Suppose that the design covariance matrices $\Sigma^{i},i=1,\ldots,r$ satisfy the mutual incoherence condition (11). Then we have

See Appendix B for the proof of this claim.

It remains to show that the random variable $M^{\prime}_{2}$ defined in equation (4) is upper bounded by $\gamma/2$ with high probability. Conditioning on $X^{i}_{U}$ and $w^{i}$, the scalar random variable \frac{1}{n}\big{\langle}Y^{i}_{k},\,X^{i}_{U}(\langle\frac{1}{n}X^{i}_{U},\,X^{i}_{U}\rangle)^{-1}\widetilde{z}^{\,i}_{U}\big{\rangle} is zero-mean Gaussian, with variance upper bounded as

Recalling that $\sum_{i=1}^{r}|\widetilde{z}^{\,i}_{j}|=1$, for any choice of signs $b\in\{-1,+1\}^{r}$, the variable

is zero-mean Gaussian, with variance at most $\frac{rs}{C_{\min}\;n}$. Therefore, we have

This probability vanishes faster than 2\exp\big{\{}-\kappa(r+\log p)\big{\}}\rightarrow 0, as long as

In the setting of random design matrices, a bit more work is required to control these terms.

Beginning with the second term, by triangle inequality, we have

Now consider the first term $T_{a}^{i}$: if we condition on $X^{i}_{U}$, then the $|U|$-dimensional random vector Y:\,=\big{(}\big{\langle}\frac{1}{n}X^{i}_{U},\,X^{i}_{U}\big{\rangle}\big{)}^{-1}\frac{1}{n}\langle X^{i}_{U},\,w^{i}\rangle is zero-mean Gaussian, with covariance \frac{1}{n}\big{(}\big{\langle}\frac{1}{n}X^{i}_{U},\,X^{i}_{U}\big{\rangle}\big{)}^{-1}. By concentration bounds for eigenvalues of Gaussian random matrices (see equation (69b) in Appendix E), we have

since $rs/n\leq 1$. Therefore, we have shown that the variance of each element of $Y$ is upper bounded by $5/(C_{\min}n)$, so that we can apply standard Gaussian tail bounds. By applying the union bound twice, first over $k\in U$, and then over $i\in\{1,2,\ldots,r\}$, we obtain

Setting $t=\xi\;\sqrt{\frac{100\log(rs)}{C_{\min}n}}$ yields that

where we have used the fact that $|U|\leq rs$. Combining the pieces, we conclude that

Proof of Theorem 3

We now turn to the proof of the phase transition predicted by Theorem 3, which applies to random design matrices $X^{1}$ and $X^{2}$ drawn from the standard Gaussian ensemble. This proof requires significantly more technical work than the preceding two proofs, since we need to control all the constants exactly, and to establish both necessary and sufficient conditions on the sample size.

Recalling that $V_{k}=\sum_{i=1}^{2}|\widetilde{z}^{\,i}_{k}|$, we have

where the random variables $M_{1}$ and $M_{2}$ were defined at the start of Section 6.1. In order to prove that $\max_{k\in{U^{c}}}|V_{k}|<1$ with high probability for the values of $n$, $s$, and $p$, we will first establish that $M_{1}<\epsilon/2$ and $M_{2}<1-\epsilon$ for an appropriately chosen value of $\epsilon$.

By the results from the previous section, we have $M_{1}<\epsilon/2$ with probability

and that $X^{i}_{{U^{c}}}$ is independent of $X^{i}_{U}$ and $w^{i}$. We will show that $M_{2}<1-\epsilon$ with high probability by using results on Gaussian extrema. Conditioning on $(X_{U},w,\widetilde{z}^{\,1}_{U})$, the random variable Y^{i}_{k}=\frac{1}{n}\big{\langle}X^{i}_{k},\,X^{i}_{U}(\frac{1}{n}\langle X^{i}_{U},\,X^{i}_{U}\rangle)^{-1}\widetilde{z}^{\,i}_{U}\big{\rangle} is zero-mean with variance upper-bounded as

Under the given conditioning, the random variables $Y^{1}_{k}$ and $Y^{2}_{k}$ are independent and for any sign vector $b\in\{-1,+1\}^{2}$, the random variable $\sum_{i=1}^{2}b_{i}Y^{i}_{k}$ is Gaussian, zero-mean with variance upper bounded as

By Lemma 13, $|\!|\!|(\langle\frac{1}{n}X^{i}_{U},\,X^{i}_{U}\rangle)^{-1}|\!|\!|_{{2}}^{2}\leq(1+\delta)$ with probability at least $1-c_{1}\exp{-c_{2}n}$ for sufficiently large $s$ and $n$ under the given scaling for each $i$. Hence, $\sum_{i=1}^{2}b_{i}Y^{i}_{k}$ is normal, zero-mean, with variance upper bounded as

Recall that $\widetilde{Z}_{U}$ was obtained from Step (B) of the Prima-dual witness construction. The next lemma provides control over $\sum_{i=1}^{2}\|\widetilde{z}^{\,i}_{U}\|^{2}_{2}$.

Under the assumptions of Theorem 3 and Corollary 1, if $\lambda_{n}^{2}n\rightarrow+\infty$ and $s/n\rightarrow 0$, then $\|\widetilde{z}^{\,1}_{U}\|^{2}_{2}$ is concentrated: for all $\delta>0$, we have that for sufficiently large $s$ and $n$

See Appendix C for the proof of this claim.

which goes to as $n\to\infty$ under the condition

2 Proof of Theorem 3(b)

By orthogonality, we have $\operatorname{var}(\widetilde{z}^{\,1}_{k})=\|\frac{1}{\lambda_{n}n}\Pi_{U^{\perp}}w\|_{2}^{2}+\|\frac{1}{n}X_{U}(\frac{1}{n}X_{U}^{T}X_{U})^{-1}\widetilde{z}^{\,1}_{U}\|_{2}^{2}$, so that (using the idempotency of projection operators), we have

Note that $\sigma^{2}=\sigma^{2}(X_{U},w,\widetilde{z}^{\,1}_{U})$ is a scalar random variable, but fixed under the conditioning. Turning to the variables $\{\widetilde{z}^{\,2}_{k},k\in{U^{c}}\}$, a similar argument shows that have $\operatorname{var}(\widetilde{z}^{\,2}_{k})\geq\widetilde{\sigma}^{2}$, where $\widetilde{\sigma}^{2}=\widetilde{\sigma}^{2}(\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{6.66843pt}{0.43057pt}}{X}_{U},\makebox[0.0pt][l]{\hskip 1.29167pt\rule[5.59721pt]{5.82973pt}{0.43057pt}}{w},\widetilde{z}^{\,2}_{U})$ is the analogous random variable.

For $k\in{U^{c}}$, let $\widetilde{z}^{\,1}_{k}\sim N(0,\sigma^{2})$ and $\widetilde{z}^{\,2}_{k}\sim N(0,\widetilde{\sigma}^{2})$. We then have

where $Z_{j}\sim N(0,\sigma^{2}+\widetilde{\sigma}^{2})$. Here inequality (a) follows because $\sigma^{2}$ and $\widetilde{\sigma}^{2}$ are lower bounds on the variances of $\{\widetilde{z}^{\,1}_{k},k\in{U^{c}}\}$ and $\{\widetilde{z}^{\,2}_{k},k\in{U^{c}}\}$ respectively, and equality (b) follows since $\widetilde{z}^{\,1}_{j}$ and $\widetilde{z}^{\,2}_{j}$ are independent zero-mean Gaussians with variances $\sigma^{2}$ and $\widetilde{\sigma}^{2}$, respectively.

To simplify notation, let $N=|{U^{c}}|=p-(2-\alpha)s$. By standard results for Gaussian maxima , for any $\delta>0$, there exists an integer $N(\delta)$ such that for all $N\geq N(\delta)$,

Moreover, the maximum function is Lipschitz, so that by Gaussian concentration for Lipschitz functions , for any $\eta>0$, we have

Combining these two statements yields that for all $N\geq N(\delta)$, we have

Case 1: First suppose that $\lambda_{n}^{2}n=\mathcal{O}(1)$. In this case, we have \sigma^{2}=\Omega\big{(}\frac{\|\Pi_{U^{\perp}}w\|_{2}^{2}}{n}\big{)}. With probability greater than $1-c_{1}\exp(-c_{2}n)$, this quantity is lower bounded by a constant, using concentration for $\chi^{2}$-variates. In this case, $\sqrt{2(\sigma^{2}+\widetilde{\sigma}^{2})\log N}-\eta\rightarrow+\infty$ w.h.p., so that the result follows trivially.

Case 2: Otherwise, we must have $\lambda_{n}^{2}n\rightarrow+\infty$. Under this condition, we now establish a lower bound on $\sigma^{2}$ that holds with high probability; it will be seen that a similar lower bound holds for $\widetilde{\sigma}^{2}$. We begin by noting the lower bound $\sigma^{2}\geq\frac{\|\widetilde{z}^{\,1}_{U}\|_{2}^{2}}{n}\lambda_{\operatorname{min}}((\frac{1}{n}X_{U}^{T}X_{U})^{-1})$. To control the minimum eigenvalue, define the event

From Lemma 5, we note that if $s/n=o(1)$, then for any $\delta>0$, we have the lower bound

The following result is the final step in the proof of Theorem 3(b).

Suppose that $\lambda_{n}^{2}n\rightarrow+\infty$. Under this condition:

(a) If $\frac{s}{n}$ is bounded below by some constant $c>0$, then we have

which implies that $(\sigma^{2}+\widetilde{\sigma}^{2})\log N\rightarrow+\infty$. Thus, setting $\delta=1/4$ and $\eta=\frac{1}{2}\sqrt{2(\sigma^{2}+\widetilde{\sigma}^{2})\log N}$ in equation (42) yields that (for $N$ sufficiently large):

Since $\frac{1}{4}\sqrt{2(\sigma^{2}+\widetilde{\sigma}^{2})\log N}\geq 2$ for $N$ large enough, the claim follows.

(b) In this case, we may apply the lower bound (45), so that, for any $\delta>0$, we have

with high probability. Since $n<(1-\nu)[(4-3\alpha)+(\Delta(\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.73494pt}{0.43057pt}}{B},\lambda_{n}))]s\log N$ by assumption, we have

Consequently, from equation (42), for any $\eta>0$ and $\delta>0$, we have for all $N\geq N(\delta)$,

Since $\nu>0$, we may choose $\eta,\delta>0$ sufficiently small so that for sufficiently large choices of $(s,n)$, we have

for some $\epsilon>0$. Since from Lemma 5, the condition $s/n=o(1)$ implies that $\sigma^{2}+\widetilde{\sigma}^{2}=o(1)$ w.h.p, we thus conclude that, using these choices of $\eta$ and $\delta$, we have

Discussion

Appendix A Recovering individual signed supports

In this appendix, we discuss some issues associated with recovering individual signed supports. We begin by observing that once the support union $U$ has been recovered, one can restrict the regression problem to this subset $U$, and then apply Lasso to each problem separately (with substantially lower cost, since each problem is now low-dimensional) in order to recover the individual signed supports. If one is not willing to perform some extra computation in this way, then the the interpretation of Theorems 1 and 2—in terms of recovering the individual signed supports—requires a more delicate treatment, which we discuss in this appendix.

The procedure (48) corresponds to estimating the signed support on the basis of a dual optimal solution associated with the optimal primal solution.

To provide a concrete illustration of this distinction, suppose that $p=4$ and $r=3$, and that the true matrix $\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.73494pt}{0.43057pt}}{B}$ and estimate take the following form:

Consistent with the claims of Theorem 1, the estimate $\widehat{B}$ correctly recovers the support union—viz. $S(\widehat{B})=\widehat{U}=\{1,2\}=S(\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.73494pt}{0.43057pt}}{B})$. The primal (47) and dual (48) methods return the following estimates of the individual signed supports:

Consequently, the primal estimate includes false non-zeros in positions $(1,2)$ and $(2,3)$, whereas the dual estimate includes false zeros in positions $(1,1)$ and $(2,1)$.

We note that it is possible to ensure that under some conditions that the dual support method (48) will correctly recover each of the individual signed supports, without any incorrect exclusions. However, as illustrated by Theorem 3 and Corollary 1, doing so requires additional assumptions on the size of the gap $|\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{2.84009pt}{0.43057pt}}{\beta}^{\,i}_{k}|-|\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{2.84009pt}{0.43057pt}}{\beta}^{\,j}_{k}|$ for indices $k\in B:\,=S(\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{2.84009pt}{0.43057pt}}{\beta}^{\,i})\cap S(\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{2.84009pt}{0.43057pt}}{\beta}^{\,j})$.

Appendix B Proof of Lemma 4

Note that conditioned $X_{U}$, the rows of the random matrix $X^{i}_{{U^{c}}}$ are i.i.d. Gaussian random vectors with mean \big{\langle}\Sigma^{i}_{{U^{c}}U}(\Sigma^{i}_{UU})^{-1},\,X^{i}_{U}\big{\rangle} and covariance

where $Y^{i}_{{U^{c}}}\sim N(0,\Sigma^{i}_{{U^{c}}\mid U})$.

Using these expressions and triangle inequality, we obtain that $M$ is upper bounded by

Applying the mutual incoherence assumption (19), we obtain

Appendix C Proof of Lemma 5

Recall that $\widetilde{z}^{\,1}_{U}=(\widetilde{z}^{\,1}_{{B^{c}}},\widetilde{z}^{\,1}_{B})$, $\|\widetilde{z}^{\,1}_{{B^{c}}}\|_{2}^{2}=(1-\alpha)s$, and that $B$ is the set where $|\widehat{\beta}^{\,1}_{B}|=|\widehat{\beta}^{\,2}_{B}|$. Thus, the claim is equivalent to showing that $\|\widetilde{z}^{\,1}_{B}\|_{2}^{2}$ is concentrated. If $\alpha=0$, then the claim is trivial, so that we may assume that $\alpha>0$.

Using $|\!|\!|\cdot|\!|\!|_{{2}}$ to denote the spectral norm, we first claim that as long as $s/n\rightarrow 0$, then the following events hold with probability greater than $1-c_{1}\exp(-c_{2}n)$:

as well as the analogous events with $M^{1}$ and $M^{2}$ interchanged.

To verify the bound (50a), we first diagonalize the projection matrix. All of its eigenvalues are or $1$, and it has rank $(n-s)$ w.p. one, so that we may write $\Pi_{{B^{c}}^{\perp}}=U^{T}DU$ for some orthogonal matrix $U$, and the diagonal matrix $D=\operatorname{diag}\{1_{n-s},0_{s}\}$,

since $|\!|\!|W^{T}W/(n-s)|\!|\!|_{{2}}=\mathcal{O}(1)$, and

using concentration arguments for random matrices (see Lemma 13 in Appendix E).

For (50b) we may use the triangle inequality and the submultiplicativity of the norm so that

Finally, since $|\!|\!|[M^{-1}+\widetilde{M}^{-1}]^{-1}|\!|\!|_{{2}}=\mathcal{O}(1)$, equation (50b) is valid.

In order to establish the bound (50c), we have

Since $|\!|\!|[M+\widetilde{M}]-2I|\!|\!|_{{2}}=\mathcal{O}(\sqrt{s/n})\rightarrow 0$, we have $|\!|\!|[M+\widetilde{M}]^{-1}|\!|\!|_{{2}}=\mathcal{O}(1)$, which establishes the claim (50c).

We are now ready to establish the claims of the lemma. From the representation (49), we apply triangle inequality and our bounds on spectral norms, thereby obtaining

with probability greater than $1-c_{1}\exp(-c_{2}n)$, where $r=\widetilde{z}^{\,1}_{B}-\frac{1}{2}(\vec{1}-\frac{1}{\lambda_{n}}(|\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{2.84009pt}{0.43057pt}}{\beta}^{2}_{B}|-|\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{2.84009pt}{0.43057pt}}{\beta}^{1}_{B}|))$. By the decomposition of $\widetilde{z}^{\,1}_{B}$ in equation (49) and applying bounds (50)

Since $s/n=o(1)$, in order to establish the upper bound (40b) it suffices to show that $\|f\|_{2}+\|\widetilde{f}\|_{2}=o(\sqrt{s}\lambda_{n})$ w.h.p. Similarly, in the other direction, we have

Following the same line of reasoning, in order to prove the lower bound (40a), it suffices to show that $\|f\|_{2}+\|\widetilde{f}\|_{2}=o(\sqrt{s}\lambda_{n})$ w.h.p.

Since $\|f\|_{2}$ and $\|\widetilde{f}\|_{2}$ behave similarly, it suffices to show that $\|f\|_{2}=o(\lambda_{n}\sqrt{s})$. From the definition (55a), we see that conditioned on $(X_{B^{c}},w,\widetilde{z}^{\,1}_{B^{c}})$, the random vector $f$ is zero-mean Gaussian, with i.i.d. elements with variance

Recalling that $\|\widetilde{z}^{\,1}_{B^{c}}\|_{2}^{2}=(1-\alpha)s$, we have

By random matrix concentration (see the discussion following Lemma 13 in Appendix E), we have $\lambda_{\operatorname{max}}((X_{B^{c}}^{T}X_{B^{c}}/n)^{-1})\leq 1+\mathcal{O}(\sqrt{s/n})$ w.h.p., and by $\chi^{2}$ tail bounds (see Lemma 12 in Appendix E), we have $\frac{\|\Pi_{{B^{c}}^{\perp}}(w)\|_{2}^{2}}{n}=\mathcal{O}(1)$ w.h.p. Consequently, with high probability, we have $\sigma^{2}=\mathcal{O}(\frac{\lambda_{n}^{2}s}{n}+\frac{1}{n})$. Since the Gaussian random vector $f$ has length $|B|=\Theta(s)$, again by concentration for $\chi^{2}$ random variables, we have (with probability greater than $1-c_{1}\exp(-c_{2}s)$), $\|f\|_{2}^{2}=\mathcal{O}(\sigma^{2}s)$. Combining the pieces, we conclude that w.h.p.

where the final equality follows since $s/n=o(1)$ and $1/(\lambda_{n}^{2}n)=o(1)$.

Appendix D Convex-analytic characterization of optimal solutions

By standard conditions for optimality in convex programs , the zero-vector must belong to the subdifferential of the objective function in the convex program (6), or equivalently, we must have for each $p=1,2,\ldots,r$

D.2 Proof of Lemma 2

It remains to establish uniqueness of this solution. Define the ball

and observe that we have the variational representation

where $\langle\cdot,\,\cdot\rangle$ denotes the Euclidean inner product. With this notation, the block-regularized program (6) is equivalent to the saddle-point problem

Since this saddle-point problem is strictly feasible and convex-concave, it has a value. Moreover, given any dual optimal solution—in particular, $\widetilde{Z}$ from the primal-dual construction—any optimal primal solution $\widehat{B}$ must satisfy the saddle point condition

But this condition can only hold if $\forall i\in\{1,2,\ldots,r\}$, $\beta^{i}_{k}=0$ for any index $k\in\{1,\ldots,p\}$ such that $\sum_{i=1}^{r}|\widetilde{z}^{\,i}_{k}|<1$. Therefore, any optimal primal solution must satisfy $\widehat{B}_{U^{c}}=0$, so that solving the original program (6) is equivalent to solving the restricted program (29). Lastly, if the matrices \big{\langle}X^{i}_{U},\,X^{i}_{U}\big{\rangle} are invertible for each $i\in\{1,2,\ldots,r\}$, then the restricted problem (29) is strictly convex, and so has a unique solution, thereby completing the proof of Lemma 2(i).

We now prove part (ii) of Lemma 2. Suppose that we are given an estimate $\widehat{B}$ of the true parameters $\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.73494pt}{0.43057pt}}{B}$ by solving the convex program (6) such that $\widehat{B}_{U^{c}}=0$.

Since $\widehat{B}$ is an optimal solution to the convex program (6), the the optimality conditions of equation (52), must be satified. We may rewrite those conditions as

where $\Delta^{i}=\widehat{\beta}^{\,i}-\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{2.84009pt}{0.43057pt}}{\beta}^{i}$. Recalling that $\widehat{B}_{U^{c}}=\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.73494pt}{0.43057pt}}{B}_{U^{c}}=0$, we obtain

Again, by standard conditions for optimality in convex programs , the first of these two equations is exactly the condition that must be satisfied by an optimal solution of the restricted program (29). However, we have already shown that the candidate solution $\widehat{B}_{U}$ satisfies this condition, so that it must also be an optimal solution of the convex program (29). Additionally, the value of $\widetilde{Z}_{U}$ that satisfies equation (53a) for each $i\in\{1,2,\ldots,r\}$ is an element of $\partial\|\widehat{B}\|_{\infty,1}$. We have thus shown that steps (B) and (C) of the primal-witness construction succeed. It remains to establish uniqueness in part (A). However, we note that \big{\langle}X^{i}_{U},\,X^{i}_{U}\big{\rangle} is invertible for each $i$. Hence, for any solution $\widehat{B}$ such that $\widehat{B}_{U^{c}}=0$,

is well-defined and unique, noting that $\Delta^{i}_{U^{c}}=0$. Thus, we have established the equality (32) and that $\widehat{B}_{U}$ is unique. Therefore, $\widehat{B}$ gives solutions to steps (A) and (B) when solving the restricted convex program over the set $U$.

The claimed form of the dual solution follows by substituting equation (32) into equation (53b).

D.3 Subgradients on the support

Given these definitions, we have the following lemma:

Assume that $r=2$, and that $|\widehat{\beta}^{\,1}_{B}|=|\widehat{\beta}^{\,2}_{B}|$. If $\widehat{B}_{U^{c}}=\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.73494pt}{0.43057pt}}{B}_{U^{c}}=0$, then the dual variable $\widetilde{z}^{\,1}$ satisfies the relation

Given these forms for $S^{1}\widetilde{z}^{\,1}_{B}$ and $S^{2}\widetilde{z}^{\,2}_{B}$, it remains to show that the relation $S^{1}\widetilde{z}^{\,1}_{B}+S^{2}\widetilde{z}^{\,2}_{B}=1$ holds under the conditions of Theorem 3(a). Intuitively, this condition should hold since under the conditions of theorem 3(a), the matrix $M^{i}$ is approximately the identity, and the vector $f^{i}$ is approaching . Finally, we expect that $\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.73494pt}{0.43057pt}}{B}_{\operatorname{diff}}:\,=|\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{2.84009pt}{0.43057pt}}{\beta}^{\,2}_{B}|-|\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{2.84009pt}{0.43057pt}}{\beta}^{\,1}_{B}|$ is very small, hence the final term is also very small. Therefore, on the set $B$, both $S^{1}\widetilde{z}^{\,1}_{B}$ and $S^{2}\widetilde{z}^{\,2}_{B}$ are approximately equal to $\frac{1}{2}$. We formalize this rough intuition in the following lemma:

Under the assumptions of Theorem 3(a) each of the following conditions hold for sufficiently large $n$, $s$, and $p$ with probability greater than $1-c_{1}\exp(-c_{2}n)$:

Given Lemmas 7 and 8, we can conclude that the definition for the dual variables on the support is valid. The remaining subsections in this appendix are dedicated to verifying the above results: in particular, we prove Lemma 7 in Appendix D.4 and Lemma 8 in Appendix D.5.

D.4 Proof of Lemma 7

We now proceed to establish the validity of the closed form expressions for $\widetilde{z}^{\,1}_{U}$ and $\widetilde{z}^{\,2}_{U}$. From equation (53a) we have that

Recall that by assumption that $S^{1}\widehat{\beta}^{\,1}_{B}=|\widehat{\beta}^{\,1}_{B}|=|\widehat{\beta}^{\,2}_{B}|=S^{2}\widehat{\beta}^{\,2}_{B}$, and $S\widetilde{z}^{\,1}_{B}+\widetilde{S}\widetilde{z}^{\,2}_{B}=1$.

Subtracting $M^{1}S^{1}\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{2.84009pt}{0.43057pt}}{\beta}^{1}_{B}$ and $M^{2}S^{2}\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{2.84009pt}{0.43057pt}}{\beta}^{2}_{B}$ from equations (58a) and (58b)

Applying the fact that $S^{1}(\Delta^{1}_{B}-\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{2.84009pt}{0.43057pt}}{\beta}^{1}_{B})=S^{2}(\Delta^{2}_{B}-\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{2.84009pt}{0.43057pt}}{\beta}^{2}_{B})$.

D.5 Proof of Lemma 8

The first term $\frac{1}{\lambda_{n}}[(M^{1})^{-1}+(M^{2})^{-1}]^{-1}\,\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.73494pt}{0.43057pt}}{B}_{\operatorname{diff}}$ can be decomposed as

Under the assumptions of Theorem 3(a), we have \big{|}\frac{\makebox[0.0pt][l]{\hskip 1.435pt\rule[5.6875pt]{4.01445pt}{0.3014pt}}{B}_{\operatorname{diff}}}{2\,\lambda_{n}}\big{|}\to 0, hence, for $s$ large enough, $T_{2}\leq\epsilon/4$.

In order to bound $T_{1}$, we note that with probability greater than $1-c_{1}\exp(-c_{2}n)$, the spectral norm of $([(M^{1})^{-1}+(M^{2})^{-1}]^{-1}-I/2)$ is $\mathcal{O}(\sqrt{s/n})$ (see the bound (50b) from Appendix C). Consequently, we may decompose $([(M^{1})^{-1}+(M^{2})^{-1}]^{-1}-I/2)$ as $QDQ^{T}$ where $Q$ and $D$ are independent and $Q$ is distributed uniformly over all orthogonal matrices, and $|\!|\!|D|\!|\!|_{{2}}=\mathcal{O}(\sqrt{s/n})$. Using this decomposition, the following lemma, proved in Appendix D.6, allows us to obtain the necessary control on the quantity $\|T_{1}\|_{\infty}$:

If $|\!|\!|A|\!|\!|_{{2}}\leq\sqrt{\frac{s}{n}}$, then

If $|\!|\!|A|\!|\!|_{{2}}\leq\frac{s}{n}$, then

With reference to the problem of bounding $\|T_{1}\|_{\infty}$, we may apply part (a) of this lemma with $A=D$ and $x=\frac{\makebox[0.0pt][l]{\hskip 1.435pt\rule[5.6875pt]{4.01445pt}{0.3014pt}}{B}_{\operatorname{diff}}}{2\lambda_{n}}$ to conclude that $\|T_{1}\|_{\infty}\leq\epsilon/2$ with high probability, thereby establishing the bound (57a).

We now turn the proving the bound (57b). We begin by decomposing the terms involved in this equation as

However, by Lemmas 12 and 13 (see Appendix E), as well as the fact that $\|\widetilde{z}^{\,i}_{s}\|_{2}^{2}=(1-\alpha)s$, for $n$ and $s$ large enough, the variance term is bounded by

with probability greater than $1-c_{1}\exp(-c_{2}n)$. Hence, by standard Gaussian tail bounds, the inequalities $\|f^{1}/(2\lambda_{n})\|_{\infty}<\epsilon/4$ and $\|f^{2}/(2\lambda_{n})\|_{\infty}<\epsilon/4$ both hold with probability greater than $1-c_{1}\exp(-\delta^{\prime}\log(p-2s))$.

Now to bound the first term in the decomposition we begin by diagonalizing $M^{2}=Q^{T}DQ$. Note that $Q$ is independent of $X^{1}$ and $D$ and by symmetry $X^{1}_{B}\stackrel{{\scriptstyle d}}{{=}}QX^{1}_{B}$. Following some algebra, we find that

The random vector $f^{1}$ is independent of $Q$ and $Qf^{1}$ is independent of $Q$ by symmetry. Hence, the vector $v:\,=\frac{1}{2}[2D(D+QM^{1}Q^{T})^{-1}-I]Q\frac{1}{\lambda_{n}}f^{1}$ is independent of $Q$. For a given constant $c_{3}$, let us define the event

Note that we may consider the event that $|\!|\!|D|\!|\!|_{{2}}=\mathcal{O}(1)$ and $[2D(D+QM^{1}Q^{T})^{-1}-I]=\mathcal{O}(\sqrt{s/n})$. We claim that each of these events happens with high probability. Note that the former event occurs with high probability by Lemma 13. The latter event holds with high probability since,

and, both $|\!|\!|D-I|\!|\!|_{{2}}=\mathcal{O}(\sqrt{s/n})$ and $((D+QM^{1}Q^{T})^{-1}-I/2)=\mathcal{O}(\sqrt{s/n})$ by equation (68a). Thus, the sum of the two random matrices is also $\mathcal{O}(\sqrt{s/n})$.

Recall the bound on the variance of each component of $f^{1}$ from equation (61) and note that each component is independent. Applying the concentration results from Lemma 12 for $\chi$-squared random variables yields that $\|f^{1}\|_{2}^{2}\leq\frac{1}{4}(1+\delta)\frac{s^{2}}{n}+\frac{1}{2}\frac{s}{n\lambda_{n}^{2}}$ with high probability. Hence, under the above conditions

It remains to control the first term. We do so using the following lemma, which is proved in Appendix D.7:

We now apply this lemma to the random vector $v$ with $m=s$, and $v^{*}=c_{3}\;\frac{s}{\sqrt{n}}\;\sqrt{\frac{s}{n}+\frac{1}{\lambda_{n}^{2}n}}$. Note that

from which the second claim (57b) in Lemma 8 follows.

Finally, we turn to proving the third claim (57c) in Lemma 8. Following some algebra, we obtain

We diagonalize the matrix $M^{1}=Q^{T}DQ$, where $D$ is diagonal. Since the random matrix $M^{1}$ has a spherically symmetric distribution, the matrix $Q$ has a uniform distribution over the space of orthogonal matrices and is independent of $D$. Using this decomposition, we can rewrite the second term in equation (62) as

where $R\mathrel{\mathop{:}}=\frac{1}{4}(D-QM^{2}Q^{T})(I-2(D+QM^{2}Q^{T})^{-1})$. We note that $R$ is independent of $Q$, because $D$ and $M^{2}$ are independent of $Q$. This independence follows from the spherical symmetry of $M^{2}$ and the fact that $M^{2}\stackrel{{\scriptstyle d}}{{=}}QM^{2}Q^{T}$.

Defining the event \mathcal{T}\mathrel{\mathop{:}}=\big{\{}|\!|\!|R|\!|\!|_{{2}}\leq 4s/n\big{\}}, we claim that

In order to establish this claim, we note that sub-multiplicativity and triangle inequality imply that

since $|\!|\!|2(Q^{T}DQ+QM^{2}Q^{T})^{-1}|\!|\!|_{{2}}\leq 2$ with probability greater than $1-c_{1}\exp(-c_{2}n)$, from the discussion following Lemma 13. Similarly, from this same result, we have $\mathcal{O}(|\!|\!|D-I|\!|\!|_{{2}})=\mathcal{O}(|\!|\!|I-QM^{2}Q^{T}|\!|\!|_{{2}})=\mathcal{O}(|\!|\!|(D+QM^{2}Q^{T})/2-I|\!|\!|_{{2}})\;\leq\;2\sqrt{\frac{s}{n}}$, so that the claim (64) follows.