
(Permutation Bandable Model) \({\mathbf {\Sigma }}= (\sigma _{ij})_{1\le i, j\le p}\) , where \(\sigma _{ij} = \max (0, 1 - 0.2\cdot |s(i)-s(j)|)\)  and \(s(i), i=1,\dots , p\)  is a random permutation of \(\lbrace 1, \ldots , p \rbrace \) .

(Randomly Sparse Model) \({\mathbf {\Sigma }}= I_p + ( )/(\Vert  \Vert +0.01) \) , where \( is randomly generated as\)\( (d_{ij})_{1\le i, j\le p}, \quad d_{ij} = \left\lbrace \begin{array}{ll}1 & \text{w.p. } 0.1\\0 & \text{w.p. } 0.8 \\-1 & \text{w.p. } 0.1\\\end{array}\right. \quad \text{for $i\ne j$};\quad d_{ii} = 0. \)\(\) 
Similar to the sparse covariance matrix estimation, for missingness, we consider both MUCR and MCR. The results for the spectral norm, matrix \(\ell _1\)  norm and Frobenius norm losses are summarized in Table REF .
It can be seen from Table REF  that, even under the MUCR setting, the proposed estimator \(\hat{{\mathbf {\Sigma }}}^{\rm at}\)  based on the generalized sample covariance matrix is uniformly better than the one based on \(\hat{{\mathbf {\Sigma }}}^\bullet \) . In the more general MCR setting, the difference in the performance between the two estimators is even more significant.
<TABLE>Comparison with Complete Samples
For covariance matrix estimation with missing data, an interesting question is: what is the “effective sample size"? That is, for samples with missing values, we would like to know the equivalent size of complete samples such that the accuracy for covariance matrix estimation is approximately the same.
We now compare the performance of the proposed estimator based on the incomplete data with the corresponding estimator based on the complete data for various sample sizes. We fix the dimension \(p=100\) . For the incomplete data, we consider \(n = 1000\)  and MUCR with \(\rho = .5\) . The covariance matrix \({\mathbf {\Sigma }}\)  is chosen as

Linear Decaying Bandable Model (in Bandable Covariance Matrix Estimation);

Permutation Bandable Model (in Sparse Covariance Matrix Estimation);

Correspondingly, we consider the similar settings for the complete data with the same \({\mathbf {\Sigma }}\)  and \(p\) , but different sample size \(n_c\) , where \(n_c\)  can be one of the following three values,

\(\overline{n_{\rm pair}^\ast } = \sum _{i,j=1}^n n_{ij}^\ast /p^2\) : the average number of pairs of \((x_i, x_j)\) 's that can be observed within the same sample;

\(\overline{n_{\rm s}^\ast } = \sum _{i=1}^n n_{i}^\ast /p\) : the average number of single \(x_i\) 's can be observed;

\(n\) : the same number of samples with the missing values.

The results for all the settings are summarized in Table REF . It can be seen that the equivalent sample size depends on the loss function and in general it is between \(\overline{n_{\rm pair}^\ast } \)  and \(\overline{n_{\rm s}^\ast }\) .
Overall, the average risk under the missing data setting is most comparable to that under the complete data setting for the sample size of \(n_c=\overline{n_{\rm pair}^\ast }\) , the average number of observed pairs.
<TABLE>
Analysis of Ovarian Cancer Data
In this section, we illustrate the proposed adaptive thresholding procedure with an application to data from four ovarian cancer genomic studies, Cancer Genome Atlas Research Network [1]} (TCGA), Bonome et al. [2]} (BONO), Dressman et al. [3]} (DRES) and Tothill et al. [4]} (TOTH).
The method introduced in Sections  enables us to estimate the covariance matrix by integrating data from all four studies and thus yields a more accurate estimator.
The data structure is illustrated in Figure REF . The gene expression markers (the first 426 rows) are observed in all four studies without any missingness (the top black block in Figure REF ). The miRNA expression markers are observed in 552 samples from the TCGA study (the bottom left block in Figure REF ) and completely missing in the 881 samples from the TOTH, DRES, BONO and part of TCGA studies (the white block in Figure REF ).
<FIGURE>Our goal is to estimate the covariance matrix \({\mathbf {\Sigma }}\)  of the 1225 variables with the particular interest in the cross-covariances between the gene and miRNA expression markers. It is clear that the missingness here is not uniformly at random. On the other hand, it is reasonable to assume the missingness does not depend on the value of the data and thus missing completely at random (Assumption REF ) can be assumed.
We apply the adaptive thresholding procedure with \(\delta = 2\)  to estimate the covariance matrix and recover its support based on all the observations. The support of the estimate is shown in a heatmap in Figure REF . The left panel is for the whole covariance matrix and the right panel zooms into the cross-covariances between the gene and miRNA expression markers.
<FIGURE>It can be seen from Figure REF  that the two diagonal blocks, with 12.24% and 8.39% nonzero off-diagonal entries respectively, are relatively dense, indicating that the relationships among the gene expression markers and those among the miRNA expression markers, as measured by their covariances, are relatively close.
In contrast, the cross-covariances between gene and miRNA expression markers are very sparse with only 0.38% of significant gene-miRNA pairs. The gene and miRNA expression markers affect each other through different mechanisms, the cross-covariances between the gene and miRNA markers are of significant interest (see Ko et al. [5]}). It is worthwhile to take a closer look at the cross-covariance matrix displayed on the right panel in Figure REF . For each given gene, we count the number of miRNAs whose covariances with this gene are significant, and then rank all the genes by the counts. Similarly, we rank all the miRNAs. The top 5 genes and the top 5 miRNA expression markers are shown in Table REF .
<TABLE>Many of these gene and miRNA expression markers have been studied before in the literature. For example, the miRNA expression markers hsa-miR-142-5p and hsa-miR-142-3p have been demonstrated in Andreopoulos and Anastassiou [6]} as standing out among the miRNA markers as having higher correlations with more genes, as well as methylation sites.
Carraro et al. [7]} finds that inhibition of miR-142-3p leads to ectopic expression of the gene marker ACTA2. This indicates strong interaction between miR-142-3p and ACTA2.
To further demonstrate the robustness of our proposed procedure against missingness, we consider a setting with additional missing observations. We first randomly select half of the 552 complete samples (where both gene and miRNA expression markers are observed) and half of the 881 incomplete samples (where only gene expression markers are observed), and then independently mask each entry of the selected samples with probability \(0.05\) . The proposed adaptive thresholding procedure is then applied to the data with these additional missing values. The estimated covariance matrix is shown in heatmaps in Figure REF .
These additional missing observations do not significantly affect the estimation accuracy. Figure REF  is visually very similar to Figure REF . To quantify the similarity between the two estimates, we calculate the Matthews correlation coefficient (MCC) between them.
The value of MCC is equal to 0.9441, which indicates that the estimate based on the data with the additional missingness is very close to the estimate based on the original samples. We also pay close attention to the cross-covariance matrix displayed on the right panel in Figure REF  and rank the gene and miRNA expression markers in the same way as before. The top 5 genes and the top 5 miRNA expression markers, listed in Table REF , are nearly identical to those given in Table REF , which are based on the original samples.
These results indicate that the proposed method is robust against additional missingness.
<FIGURE><TABLE>
Discussions
We considered in the present paper estimation of bandable and sparse covariance matrices in the presence of missing observations. The pivotal quantity is the generalized sample covariance matrix defined in (REF ).
The technical analysis is more challenging due to the missing data. We have mainly focused on the spectral norm loss in the theoretical analysis. Performance under other losses such as the Frobenius norm can also be analyzed.
To illustrate the proposed methods, we integrated four ovarian cancer studies. These methods for high-dimensional covariance matrix estimation with missing data are also useful for other types of data integration. For example, linking multiple data sources such as electronic data records, medicare data, registry data and patient reported outcomes could greatly increase the power of exploratory studies such as phenome-wide association studies (Denny et al. [8]}). However, missing data inevitably arises and may hinder the potential of integrative analysis. In addition to random missingness due to unavailable information on a small fraction of patients, many variables such as the genetic measurements may only exist in one or two data sources and are hence structurally missing for other data sources. Our proposed methods could potentially provide accurate recovery of the covariance matrix in the presence of missingness.
In this paper, we allowed the proportion of missing values to be non-negligible as long as the minimum number of occurrences of any pair of variables \(n_{\min }^\ast \)  is of order \(n\) . An interesting question is what happens when the number of observed values is large but \(n_{\min }^\ast \)  is small (or even zero). We believe that the covariance matrix \({\mathbf {\Sigma }}\)  can still be well estimated under certain global structural assumptions. This is out of the scope of the present paper and is an interesting problem for future research.
The key ideas and techniques developed in this paper can be used for a range of other related problems in high-dimensional statistical inference with missing data. For example, the same techniques can also be applied to estimation of other structured covariance matrices such as Toeplitz matrices, which have been studied in the literature in the case of complete data. When there are missing data, we can construct similar estimators using the generalized sample covariance matrix. The large deviation bounds for a sub-matrix and self-normalized entries of the generalized sample covariance matrix developed in Lemmas REF  and REF  would be helpful for analyzing the properties of the estimators.
The techniques can also be used on two-sample problems such as estimation of differential correlation matrices and hypothesis testing on the covariance structures. The generalized sample covariance matrix can be standardized to form the generalized sample correlation matrix which can then be used to estimate the differential correlation matrix in the two-sample case. It is also of significant interest in some applications to test the covariance structures in both one- and two-sample settings based on incomplete data.
In the one-sample case, it is of interest to test the hypothesis \(\lbrace H_0: {\mathbf {\Sigma }}=I\rbrace \)  or \(\lbrace H_0: \mathbf {R}=I\rbrace \) , where \(\mathbf {R}\)  is the correlation matrix. In the two-sample case, one wishes to test the equality of two covariance matrices \(\lbrace H_0:{\mathbf {\Sigma }}_1 = {\mathbf {\Sigma }}_2\rbrace \) .
These are interesting problems for further exploration in the future.

Proofs
We prove Theorem REF  and the key technical result Lemma REF  for the bandable covariance matrix estimation in this section.
Proof of Lemma  REF
To prove this lemma, we first introduce the following technical tool for the spectral norm of the sub-matrices.
Lemma 6.1 
Suppose \({\mathbf {\Sigma }}\in \mathbb {R}^{p\times p}\)  is any positive semi-definite matrix, \(A, B\in \lbrace 1,\ldots , p\rbrace \) , then
\(\Vert {\mathbf {\Sigma }}_{A\times B}\Vert  \le (\Vert {\mathbf {\Sigma }}_A\Vert  \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}.\) 

The proof of Lemma REF  is provided later and now we move back to the proof of Lemma REF . Without loss of generality, we assume that \(\mu = {\rm E}{\mathbf {X}}= 0\) . We further define
\(\breve{{\mathbf {\Sigma }}}^* = (\breve{\sigma }^*_{ij})_{1\le i, j\le p}, \quad \breve{\sigma }^*_{ij} = \frac{1}{n_{ij}^*} \sum _{k=1}^n X_{ik} X_{jk} S_{ik}S_{jk}.\) 
Also for convenience of presentation, we use \(C, C_1, c, \ldots \)  to denote uniform constants, whose exact values may vary in different senarios. The lemma is now proved in the following steps:

We first consider for fixed unit vectors \({\mathbf {a}}, {\mathbf {b}}\in \mathbb {R}^p\)  with \({\rm supp}({\mathbf {a}})\subseteq A, {\rm supp}({\mathbf {b}})\subseteq B\) , the tail bound of \({\mathbf {a}}^{\top }(\hat{{\mathbf {\Sigma }}}^* - {\mathbf {\Sigma }}){\mathbf {b}}\) . We would like to show that there exist uniform constants \(C_1, c>0\)  such that for all \(x>0\) ,
\(\begin{split}& \Pr \left\lbrace \left|{\mathbf {a}}^{\top }\left(\hat{{\mathbf {\Sigma }}}^\ast - {\mathbf {\Sigma }}\right){\mathbf {b}}\right|\ge x\right\rbrace \\\le & C_1\exp \left\lbrace -cn_{\min }^\ast \min \left(\frac{x^2}{\tau ^4\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert }, \frac{x}{\tau ^2(\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}}\right)\right\rbrace .\end{split}\) 
Specifically, we will bound \({\mathbf {a}}^{\top }(\breve{{\mathbf {\Sigma }}}^\ast - \hat{{\mathbf {\Sigma }}}){\mathbf {b}}\)  and \({\mathbf {a}}^{\top }(\breve{{\mathbf {\Sigma }}}^\ast - {\mathbf {\Sigma }}){\mathbf {b}}\)  separately in the next two steps.

We consider \({\mathbf {a}}^{\top }(\breve{{\mathbf {\Sigma }}}^\ast - \hat{{\mathbf {\Sigma }}}){\mathbf {b}}\)  first. Since
\(\breve{\sigma }^\ast _{ij} - \hat{\sigma }^\ast _{ij} = \frac{1}{n_{ij}^\ast }\sum _{k=1}^n (X_{jk}\bar{X}_i^\ast + X_{ik}\bar{X}_j^\ast )S_{ik}S_{jk} - \bar{X}_i^\ast \bar{X}_j^\ast ,\) 
\({\mathbf {a}}^{\top }(\breve{{\mathbf {\Sigma }}}^\ast - \hat{{\mathbf {\Sigma }}}^\ast ){\mathbf {b}}\)  can be written as
\(\begin{split}& {\mathbf {a}}^{\top }(\breve{{\mathbf {\Sigma }}}^\ast - \hat{{\mathbf {\Sigma }}}^\ast ){\mathbf {b}}= \sum _{i, j=1}^p a_ib_j (\breve{\sigma }_{ij}^\ast - \hat{\sigma }_{ij}^\ast )\\= & \sum _{i, j = 1}^p a_i b_j \Bigg (\frac{\sum _{k=1}^n X_{ik}S_{ik}}{n_i^\ast }\cdot \frac{\sum _{l=1}^n X_{jl}S_{il}S_{jl}}{n_{ij}^\ast }\\& + \frac{\sum _{k=1}^n X_{ik}S_{ik}S_{jk}}{n_{ij}^\ast }\cdot \frac{\sum _{l=1}^n X_{jl}S_{jl}}{n_j^\ast } - \frac{\sum _{k=1}^n X_{ik}S_{ik}}{n_i^\ast }\cdot \frac{\sum _{l=1}^n X_{jl}S_{jl}}{n_j^\ast }\Bigg )\\= & \sum _{i,j = 1}^p\sum _{k, l = 1}^n X_{ik}X_{jl}a_ib_j \left(\frac{S_{ik}S_{il}S_{jl}}{n_i^\ast n_{ij}^\ast } + \frac{S_{ik}S_{jk}S_{jl}}{n_{ij}^\ast n_j^\ast } - \frac{S_{ik}S_{jl}}{n_i^\ast n_j^\ast }\right).\end{split}\) 
We can calculate from (REF ) that
\(\begin{split}& \left|{\rm E}{\mathbf {a}}^{\top }(\breve{{\mathbf {\Sigma }}}^\ast - \hat{{\mathbf {\Sigma }}}^\ast ){\mathbf {b}}\right|\\= & \left|\sum _{i,j = 1}^p\sum _{k = 1}^n \sigma _{ij}a_ib_j \left(\frac{S_{ik}S_{ik}S_{jk}}{n_i^\ast n_{ij}^\ast } + \frac{S_{ik}S_{jk}S_{jk}}{n_{ij}^\ast n_j^\ast } - \frac{S_{ik}S_{jk}}{n_i^\ast n_j^\ast }\right)\right|\\= & \left|\sum _{i, j=1}^p \sigma _{ij}\frac{a_i}{n_i^\ast }b_j + \sum _{i, j = 1}^p a_i\frac{b_j}{n_j^\ast } \sigma _{ij} - \sum _{k=1}^n\sum _{i, j=1}^p\frac{S_{ik}a_i}{n_i^\ast }\frac{S_{jk}b_j}{n_j^\ast }\sigma _{ij}\right|\\\le & \left|\left(\frac{a_1}{n_1^\ast }, \ldots , \frac{a_p}{n_p^\ast }\right){\mathbf {\Sigma }}{\mathbf {b}}\right| + \left|{\mathbf {a}}^{\top }{\mathbf {\Sigma }}\left(\frac{b_1}{n_1^\ast }, \ldots , \frac{b_p}{n_p^\ast }\right)^\top \right|\\& + \sum _{k=1}^n \left|\left(\frac{S_{1k}a_1}{n_1^\ast }, \ldots , \frac{S_{pk}a_p}{n_p^\ast }\right){\mathbf {\Sigma }}\left(\frac{S_{1k}b_1}{n_1^\ast }, \ldots , \frac{S_{pk}b_p}{n_p^\ast }\right)^{\top }\right| \\\le & \Vert {\mathbf {\Sigma }}_{A\times B}\Vert \frac{\Vert {\mathbf {a}}\Vert _2\Vert {\mathbf {b}}\Vert _2}{n_{\min }^\ast } + \Vert {\mathbf {\Sigma }}_{A\times B}\Vert \frac{\Vert {\mathbf {a}}\Vert _2\Vert {\mathbf {b}}\Vert _2}{n_{\min }^\ast }\\& + \sum _{k=1}^n\Vert {\mathbf {\Sigma }}_{A\times B}\Vert \cdot \frac{1}{2}\left\lbrace \left\Vert \left(\frac{S_{1k}a_1}{n_1^\ast }, \ldots , \frac{S_{pk}a_p}{n_p^\ast }\right)\right\Vert _2^2 + \left\Vert \left(\frac{S_{1k}b_1}{n_1^\ast }, \ldots , \frac{S_{pk}b_p}{n_p^\ast }\right) \right\Vert _2^2\right\rbrace .\end{split}\) 
For the last term in (REF ), we have the following bound,
\(\begin{split}& \sum _{k=1}^n\Vert {\mathbf {\Sigma }}_{A\times B}\Vert \cdot \frac{1}{2}\left\lbrace \left\Vert \left(\frac{S_{1k}a_1}{n_1^\ast }, \ldots , \frac{S_{pk}a_p}{n_p^\ast }\right)\right\Vert _2^2 + \left\Vert \left(\frac{S_{1k}b_1}{n_1^\ast }, \ldots , \frac{S_{pk}b_p}{n_p^\ast }\right) \right\Vert _2^2\right\rbrace \\= & \Vert {\mathbf {\Sigma }}_{A\times B}\Vert  \sum _{k=1}^n\sum _{i=1}^p \frac{1}{2} \left(\frac{S_{ik}a_i^2}{n_i^{\ast 2}} + \frac{S_{ik}b_i^2}{n_i^{\ast 2}}\right)\\= & \Vert {\mathbf {\Sigma }}_{A\times B}\Vert  \sum _{i=1}^p \frac{1}{2}\left(\frac{a_i^2 + b_i^2}{n_i^\ast }\right)\\\le & \Vert {\mathbf {\Sigma }}_{A\times B}\Vert  \sum _{i=1}^p \frac{a_i^2+b_i^2}{2n_{\min }^\ast } \le \frac{(\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}}{n_{\min }^\ast }.\end{split}\) 
Thus, by (REF ) and the inequality above, we have
\(\left|{\rm E}a^\top (\breve{{\mathbf {\Sigma }}}^\ast - \hat{{\mathbf {\Sigma }}}^\ast ) b \right| \le \frac{3(\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}}{n_{\min }^\ast }.\) 
The last term of (REF ) can be treated as a quadratic form of the vectorization of \({\mathbf {X}}: \text{vec}({\mathbf {X}})\in \mathbb {R}^{pn}\) . We note the last term as \(\text{vec}({\mathbf {X}})^{\top }{\mathbf {Q}}\text{vec}({\mathbf {X}})\) , where \({\mathbf {Q}}\in \mathbb {R}^{pn\times pn}\)  and
\({\mathbf {Q}}_{(i, k), (j, l)} = a_ib_j \left(\frac{S_{ik}S_{il}S_{jl}}{n_i^\ast n_{ij}^\ast } + \frac{S_{ik}S_{jk}S_{jl}}{n_{ij}^\ast n_j^\ast } - \frac{S_{ik}S_{jl}}{n_i^\ast n_j^\ast }\right),\quad 1\le i, j\le p, 1\le k, l\le n. \) 
\({\mathbf {Q}}\)  has the following properties,
\(\begin{split}\Vert {\mathbf {Q}}\Vert _F^2 = & \sum _{i,j = 1}^p\sum _{k,l=1}^n a_i^2b_j^2 \left(\frac{S_{ik}S_{il}S_{jl}}{n_i^\ast n_{ij}^\ast } + \frac{S_{ik}S_{jk}S_{jl}}{n_{ij}^\ast n_j^\ast } - \frac{S_{ik}S_{jl}}{n_i^\ast n_j^\ast }\right)^2\\\le & \sum _{i, j=1}^p a_i^2b_j^2\sum _{k, l =1}^n \left(2\frac{S_{ik}S_{il}S_{jl}}{n_i^{\ast 2}n_{ij}^{\ast 2}} + 2\frac{S_{ik}S_{jk}S_{jl}}{n_{ij}^{\ast 2}n_j^{\ast 2}} + \frac{S_{ik}S_{jl}}{n_i^{\ast 2}n_j^{\ast 2}}\right),\quad \text{since } S_{ik} \in \lbrace 0, 1\rbrace ;\\\le & \sum _{i,j=1}^p a_i^2b_j^2 \frac{5}{n_{\min }^{\ast 2}} = \frac{5\Vert {\mathbf {a}}\Vert _2^2\Vert {\mathbf {b}}\Vert _2^2}{n_{\min }^{\ast 2}} = \frac{5}{n_{\min }^{\ast 2}};\end{split}\) 
\(\Vert {\mathbf {Q}}\Vert  \le \Vert {\mathbf {Q}}\Vert _F \le \frac{\sqrt{5}\Vert {\mathbf {a}}\Vert _2\Vert {\mathbf {b}}\Vert _2}{n_{\min }^\ast } \le \frac{\sqrt{5}}{n_{\min }^{\ast }}.\) 
For \({\rm vec}({\mathbf {X}}) \in \mathbb {R}^{pn}\) , since its segments \(\lbrace {\mathbf {X}}_{k}, k=1,\ldots , p\rbrace \)  are independent and \({\mathbf {X}}_k = \Gamma {\mathbf {Z}}_k\) , we can further write \(\text{vec}({\mathbf {X}}) = {\Gamma } \text{vec}({\mathbf {Z}})\) , where \({\Gamma }\in \mathbb {R}^{pn\times qn}\)  is with \(n\)  diagonal blocks of \(\Gamma \) , \(\text{vec}({\mathbf {Z}})\)  is a \((qn)\) -dimensional i.i.d. sub-Gaussian random vector. Based on Hanson-Wright's inequality (Theorem 1.1 in Rudelson and Vershynin [9]}),
\(\begin{split}& \Pr \left\lbrace \left|{\mathbf {a}}^{\top }\left(\breve{{\mathbf {\Sigma }}}^\ast - \hat{{\mathbf {\Sigma }}}^\ast \right){\mathbf {b}}- {\rm E}{\mathbf {a}}^{\top }\left(\breve{{\mathbf {\Sigma }}}^\ast - \hat{{\mathbf {\Sigma }}}^\ast \right){\mathbf {b}}\right|\ge x\right\rbrace \\= & \Pr \left\lbrace \left|\text{vec}({\mathbf {X}})^{\top }{\mathbf {Q}}\text{vec}({\mathbf {X}}) - {\rm E}\text{vec}({\mathbf {X}})^{\top }{\mathbf {Q}}\text{vec}({\mathbf {X}})\right|\ge x\right\rbrace \\= & \Pr \left[\left|\text{vec}({\mathbf {Z}})^{\top }{\Gamma }^{\top }{\mathbf {Q}}{\Gamma } \text{vec}({\mathbf {Z}}) - {\rm E}\left\lbrace \text{vec}({\mathbf {Z}})^{\top }{\Gamma }^{\top }{\mathbf {Q}}{\Gamma } \text{vec}({\mathbf {Z}})\right\rbrace \right|\ge x\right]\\\le & 2\exp \left\lbrace -c\min \left(\frac{x^2}{\tau ^4\Vert {\Gamma }^{\top }{\mathbf {Q}}{\Gamma }\Vert _F^2}, \frac{x}{\tau ^2\Vert {\Gamma }{\mathbf {Q}}{\Gamma }\Vert } \right)\right\rbrace .\end{split}\) 
Here \(c>0\)  is a uniform constant. Since \({\mathbf {Q}}\)  is supported on \(\lbrace (i, k), (j, l): i\in A, j\in B\rbrace \) , we have \({\Gamma }^{\top }{\mathbf {Q}}{\Gamma } = {\Gamma _A}^{\top }{\mathbf {Q}}_{A\times B}{\Gamma _B}\) . Here \({\Gamma _A} \in \mathbb {R}^{|A|n\times qn}, {\Gamma _B}\in \mathbb {R}^{|B|n\times qn}\)  are with \(n\)  diagonal block \(\Gamma _{A\times [q]}\)  and \(\Gamma _{B \times [q]}\) , respectively, where \([q] = \lbrace 1, \ldots , q\rbrace \) . Since \(\Gamma _{A\times [q]} \Gamma _{A\times [q]}^{\top }= {\mathbf {\Sigma }}_{A}\) , \(\Gamma _{B\times [q]} \Gamma _{B\times [q]}^{\top }= {\mathbf {\Sigma }}_{B}\) , we know
\(\Vert {\Gamma _A}\Vert  = \Vert \Gamma _{A\times [q]}\Vert  \le \Vert {\mathbf {\Sigma }}_A\Vert ^{1/2}, \quad \Vert \Gamma _{B\times [q]}\Vert  \le \Vert {\Gamma _B}\Vert  \le \Vert {\mathbf {\Sigma }}_B\Vert ^{1/2}. \) 
Then we further have
\(\begin{split}& \Pr \left\lbrace \left|{\mathbf {a}}^{\top }\left(\breve{{\mathbf {\Sigma }}}^\ast - \hat{{\mathbf {\Sigma }}}^\ast \right){\mathbf {b}}- {\rm E}{\mathbf {a}}^{\top }\left(\breve{{\mathbf {\Sigma }}}^\ast - \hat{{\mathbf {\Sigma }}}^\ast \right){\mathbf {b}}\right|\ge x\right\rbrace \\\le & 2\exp \left\lbrace -c\min \left(\frac{x^2}{\tau ^4\Vert {\Gamma _A}^{\top }{\mathbf {Q}}_{A\times B}{\Gamma _B}\Vert _F^2}, \frac{x}{\tau ^2\Vert {\Gamma _A}^{\top }{\mathbf {Q}}_{A\times B}{\Gamma _B}\Vert } \right)\right\rbrace \\\le & 2\exp \left\lbrace -c\min \left(\frac{x^2}{\tau ^4\Vert {\Gamma _B}\Vert ^2\Vert {\Gamma _A}^{\top }\Vert ^2\Vert {\mathbf {Q}}\Vert _F^2}, \frac{x}{\tau ^2\Vert {\Gamma _B}\Vert \Vert {\Gamma _A}^{\top }\Vert \Vert {\mathbf {Q}}\Vert } \right)\right\rbrace \\\le & 2\exp \left[-c\min \left\lbrace \frac{x^2}{\tau ^4\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert \Vert {\mathbf {Q}}\Vert _F^2}, \frac{x}{\tau ^2(\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}\Vert {\mathbf {Q}}\Vert } \right\rbrace \right]\\\le & 2\exp \left[-c \min \left\lbrace \frac{x^2n_{\min }^{\ast 2}}{\tau ^4\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert  }, \frac{xn_{\min }^{\ast }}{\tau ^2(\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}}\right\rbrace \right].\end{split}\) 
We define \(x^{\prime } = \max \left\lbrace x -3(\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}/n_{\min }^\ast , 0\right\rbrace \) , combining the inequality above and (REF ), we have
\(\begin{split}& \Pr \left\lbrace \left|{\mathbf {a}}^\top \left(\breve{{\mathbf {\Sigma }}}^\ast - \hat{{\mathbf {\Sigma }}}^\ast \right){\mathbf {b}}\right| \ge x\right\rbrace  \le \Pr \left\lbrace \left|{\mathbf {a}}^\top \left(\breve{{\mathbf {\Sigma }}}^\ast - \hat{{\mathbf {\Sigma }}}^\ast \right){\mathbf {b}}- {\rm E}{\mathbf {a}}^\top \hat{{\mathbf {\Sigma }}}^\ast {\mathbf {b}}\right| \ge x^{\prime }\right\rbrace \\\le & 2\exp \left[-c \min \left\lbrace \frac{(x^{\prime })^2n_{\min }^{\ast 2}}{\tau ^4\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert  }, \frac{x^{\prime }n_{\min }^{\ast }}{\tau ^2(\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}}\right\rbrace \right]\\\le & 2\exp \left[-c^{\prime } \min \left\lbrace \frac{x^2n_{\min }^{\ast 2}}{\tau ^4\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert  }, \frac{xn_{\min }^{\ast }}{\tau ^2(\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}}\right\rbrace  +C\max \left(\frac{1}{\tau ^4}, \frac{1}{\tau ^2}\right)\right]\\\le & C\exp \left[-c^{\prime } \min \left\lbrace \frac{x^2n_{\min }^{\ast 2}}{\tau ^4\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert  }, \frac{xn_{\min }^{\ast }}{\tau ^2(\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}}\right\rbrace  \right].\end{split}\) 
In the last inequality above, we used a fact that \(\tau \)  is lower bounded by a uniform constant. This is due to Assumption REF  that \({\rm E}(Z) = 0\) , \({\rm var}(Z) = 1\) , \({\rm E}\exp (tZ)\le \exp (t^2\tau ^2/2)\) . Then,
\(\exp (4\tau ^2/2) \ge \frac{1}{2}\left\lbrace {\rm E}\exp (2Z) + {\rm E}\exp (-2Z)\right\rbrace  =\sum _{k=0}^\infty \frac{2^{2k}{\rm E}Z^{2k}}{(2k)!} \ge 2{\rm E}Z^2 = 2, \) 
which implies \(\tau ^2\ge \frac{1}{2}\ln (2)\) .

It is easy to see that \({\rm E}\breve{{\mathbf {\Sigma }}}^\ast = {\mathbf {\Sigma }}\) , so \({\rm E}{\mathbf {a}}^{\top }(\breve{{\mathbf {\Sigma }}}^\ast - {\mathbf {\Sigma }}){\mathbf {b}}= 0\) . Then
\(\begin{split}& a^{\top }(\breve{{\mathbf {\Sigma }}}^\ast - {\mathbf {\Sigma }})b\\= & \sum _{i,j= 1}^p a_i b_j \left(\frac{1}{n_{ij}^\ast }\sum _{k=1}^n X_{ik}X_{jk}S_{ik}S_{jk}\right) - {\rm E}\sum _{i,j= 1}^p a_i b_j \left(\frac{1}{n_{ij}^\ast }\sum _{k=1}^n X_{ik}X_{jk}S_{ik}S_{jk}\right)\\= & \sum _{k=1}^n \sum _{i, j=1}^p \left(\frac{a_ib_jS_{ik}S_{jk}}{n_{ij}^\ast } X_{ik}X_{jk} - {\rm E}\frac{a_ib_jS_{ik}S_{jk}}{n_{ij}^\ast } X_{ik}X_{jk} \right)\\\triangleq & \sum _{k=1}^n \left({\mathbf {X}}_k^{\top }k {\mathbf {X}}_k - {\rm E}{\mathbf {X}}_k ^{\top }k {\mathbf {X}}_k\right)\\= & \sum _{k=1}^n \left({\mathbf {Z}}_k^{\top }\Gamma ^{\top }k\Gamma {\mathbf {Z}}_k - {\rm E}{\mathbf {Z}}_k^{\top }\Gamma ^{\top }k\Gamma {\mathbf {Z}}_k\right).\end{split}\) 
Here \(k\in \mathbb {R}^{p\times p}\)  is a matrix such that \(C^k_{ij} = a_ib_jS_{ik}S_{jk}/n_{ij}^\ast \) . Note that \(k\)  is supported on \(A\times B\) , we can prove the following properties of \(k\) .
\(\begin{split}\Vert \Gamma ^{\top }k\Gamma \Vert _F = & \sqrt{{\rm tr}\left(k\Gamma \Gamma ^{\top }{k\top }\Gamma \Gamma ^{\top }\right)}\\= & \sqrt{{\rm tr}\left(k_{A\times B} \Gamma _{B\times [q]}\Gamma _{B\times [q]}^{\top }{k\top }_{A\times B}\Gamma _{A\times [q]}\Gamma _{A\times [q]}^{\top }\right)} \\\le & \Vert \Gamma _{B\times [q]}\Vert  \Vert \Gamma _{A\times [q]}\Vert  \sqrt{{\rm tr}(k{k\top })}\\\le & (\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2} \sqrt{{\rm tr}(k{k\top })};\end{split}\) 
\(\begin{split}& \sum _{k=1}^n \Vert \Gamma ^\top k \Gamma \Vert _F^2 \le \Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert  \Vert k\Vert _F^2 = \Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert  \sum _{k=1}^n \sum _{i,j=1}^p \left(\frac{a_ib_jS_{ik}S_{jk}}{n_{ij}^\ast }\right)^2\\= & \Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert  \sum _{k=1}^n \sum _{i, j=1}^p \frac{S_{ik}S_{jk}a_i^2b_j^2}{n_{ij}^{\ast 2}} = \Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert  \sum _{i,j=1}^p \frac{a_i^2b_j^2}{n_{ij}^\ast } \\\le & \Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert  \frac{\Vert {\mathbf {a}}\Vert _2^2\Vert {\mathbf {b}}\Vert _2^2}{n_{\min }^\ast } = \frac{\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert }{n_{\min }^\ast };\end{split}\) 
\(\begin{split}\Vert \Gamma ^\top k\Gamma \Vert  \le & \Vert \Gamma ^\top k\Gamma \Vert _F \le (\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2} \sqrt{{\rm tr}(k{k\top })}\\\le & (\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2} \sqrt{\sum _{i, j=1}^p \left(\frac{a_ib_j S_{ik}S_{jk}}{n_{ij}^\ast }\right)^2}\\\le & (\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}\sqrt{\sum _{i,j=1}^p \frac{a_i^2b_j^2}{n_{\min }^{\ast 2}}}\le \frac{\sqrt{\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert }}{n_{\min }^\ast }.\end{split}\) 
Now, note that the last line of (REF ) can be also equivalently written as
\(\text{vec}({\mathbf {Z}})^\top {con}\text{vec}({\mathbf {Z}})^\top - {\rm E}\text{vec}({\mathbf {Z}})^\top {con}\text{vec}({\mathbf {Z}})^\top , \) 
\({con} = \begin{bmatrix}\Gamma ^\top 1 \Gamma & & \\& \ddots & \\& & \Gamma ^\top n \Gamma \end{bmatrix} \in \mathbb {R}^{(qn)\times (qn)}, \) 
where \(\text{vec}({\mathbf {Z}})\)  is the vectorization of \({\mathbf {Z}}\) , which is an \(qn\) -dimensional i.i.d. sub-Gaussian vector. Based on the properties of \(k\)  above, we have
\(\Vert {con} \Vert _F^2 = \sum _{k=1}^n \Vert \Gamma ^\top k \Gamma \Vert _F^2 \overset{(\ref {ineq:GammaCGamma_fro_sum})}{\le } \frac{\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert }{n_{\min }^\ast },\) 
\(\Vert {con}\Vert  \le \max _{1\le k\le n} \Vert \Gamma ^\top k \Gamma \Vert  \overset{(\ref {ineq:GammaCGamma_spe})}{\le } \frac{(\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}}{n_{\min }^\ast }. \) 
Now applying Hanson-Wright's inequality (Theorem 1.1 in Rudelson and Vershynin [9]}), we have
\(\begin{split}& \Pr \left\lbrace \left|\text{vec}({\mathbf {Z}}_k)^{\top }{con}\text{vec}({\mathbf {Z}}_k) - {\rm E}\text{vec}({\mathbf {Z}}_k)^{\top }{con}\text{vec}({\mathbf {Z}}_k)\right|\ge x\right\rbrace \\\le & 2\exp \left\lbrace -c \min \left(\frac{x^2}{\tau ^4\Vert {con}\Vert _F^2}, \frac{x}{\tau ^2\Vert {con}\Vert }\right)\right\rbrace  \\\le & 2\exp \left\lbrace -cn_{\min }^\ast \min \left(\frac{x^2}{\tau ^4\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert }, \frac{x}{\tau ^2 (\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}}\right)\right\rbrace .\end{split}\) 
Thus,
\(\begin{split}& \Pr \left\lbrace \left|{\mathbf {a}}^\top (\breve{{\mathbf {\Sigma }}}^\ast - {\mathbf {\Sigma }}){\mathbf {b}}\right|\ge x\right\rbrace \\\le & 2\exp \left\lbrace -cn_{\min }^\ast \min \left(\frac{x^2}{\tau ^4\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert }, \frac{x}{\tau ^2 (\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}}\right)\right\rbrace .\end{split}\) 
Here \(c\)  is a uniform constant. Combining (REF ) and (REF ), we have (REF ).

Next, we use the \(\varepsilon \) -net technique to give the bound on \(\Vert \hat{{\mathbf {\Sigma }}}^\ast _{A\times B} - {\mathbf {\Sigma }}_{A\times B}\Vert \) . Denote \(\ast = \hat{{\mathbf {\Sigma }}}^\ast _{A\times B} - {\mathbf {\Sigma }}_{A\times B}\) . Suppose \(S_{1/3}^{A}\)  is the \((1/3)\) -net for all unit vectors in \(\mathbb {R}^{|A|}\) ; similarly \(S_{1/3}^B\)  is the \((1/3)\) -net for all unit vectors in \(\mathbb {R}^{|B|}\) . Based on the proof of Lemma 3 in Cai et al. [11]}, we can let \(\text{Card}(S_{1/3}^A) \le 7^k\) , \(\text{Card}(S_{1/3}^B) \le 7^k\) . Since for all \({\mathbf {a}}, {\mathbf {a}}_0\in \mathbb {R}^{|A|}, {\mathbf {b}}, {\mathbf {b}}_0\in \mathbb {R}^{|B|}\) ,
\(\begin{split}\left|{\mathbf {a}}^{\top }\ast {\mathbf {b}}\right| - \left|{\mathbf {a}}_0^{\top }\ast {\mathbf {b}}_0\right| \le & \left|{\mathbf {a}}^{\top }\ast {\mathbf {b}}- {\mathbf {a}}_0^{\top }\ast {\mathbf {b}}_0\right| \le \left|({\mathbf {a}}- {\mathbf {a}}_0)^{\top }\ast {\mathbf {b}}\right| + \left|{\mathbf {a}}_0^{\top }\ast ({\mathbf {b}}- {\mathbf {b}}_0) \right|\\\le & \left(\Vert {\mathbf {a}}- {\mathbf {a}}_0\Vert _2 + \Vert {\mathbf {b}}- {\mathbf {b}}_0\Vert _2\right)\Vert \ast \Vert ,\end{split}\) 
we have for all \({\mathbf {a}}\in \mathbb {R}^{|A|}, {\mathbf {b}}\in \mathbb {R}^{|B|}, \Vert {\mathbf {a}}\Vert _2 = \Vert {\mathbf {b}}\Vert _2 = 1\) , we can find \({\mathbf {a}}_0 \in S_{1/3}^A, {\mathbf {b}}_0\in S_{1/3}^B\)  such that \(\Vert {\mathbf {a}}_0 - {\mathbf {a}}\Vert _2\le 1/3, \Vert {\mathbf {b}}_0 - {\mathbf {b}}\Vert _2\le 1/3\) , then
\(|{\mathbf {a}}^\top \ast {\mathbf {b}}| \le |{\mathbf {a}}_0^\top \ast {\mathbf {b}}_0| + \frac{2}{3}\Vert \ast \Vert  \le \sup _{{\mathbf {a}}_0\in S_{1/3}^A, {\mathbf {b}}_0\in S_{1/3}^B}|{\mathbf {a}}_0^\top \ast {\mathbf {b}}_0| + \frac{2}{3}\Vert \ast \Vert , \) 
\(\Vert \ast \Vert  = \sup _{\begin{array}{c}{\mathbf {a}}\in \mathbb {R}^{|A|}, {\mathbf {b}}\in \mathbb {R}^{|B|},\\ \Vert {\mathbf {a}}\Vert _2 = \Vert {\mathbf {b}}\Vert _2 = 1\end{array}} |{\mathbf {a}}^\top \ast {\mathbf {b}}| \le \sup _{{\mathbf {a}}_0\in S_{1/3}^A, {\mathbf {b}}_0\in S_{1/3}^B}|{\mathbf {a}}_0^\top \ast {\mathbf {b}}_0| + \frac{2}{3}\Vert \ast \Vert , \) 
which yields
\(\Vert \hat{{\mathbf {\Sigma }}}^\ast _{A\times B} - {\mathbf {\Sigma }}_{A\times B}\Vert  = \Vert \ast \Vert  \le 3\sup _{{\mathbf {a}}_0\in S_{1/3}^A, {\mathbf {b}}_0\in S_{1/3}^B}|{\mathbf {a}}_0^{\top }\ast {\mathbf {b}}_0|.\) 
Finally, by combining (REF ) and the inequality above, we know there exist uniform constants \(C_1, c>0\)  such that for all \(t>0\) ,
\(\begin{split}& \Pr \left(\Vert \hat{{\mathbf {\Sigma }}}^\ast _{A\times B} - {\mathbf {\Sigma }}_{A\times B}\Vert  \ge x\right) \le \Pr \left(\sup _{{\mathbf {a}}_0\in S_{1/3}^A, {\mathbf {b}}_0 \in S_{1/3}^B}|{\mathbf {a}}_0^{\top }\ast {\mathbf {b}}_0| \ge \frac{x}{3} \right)\\\le & C_1(7)^{|A| + |B|}\exp \left[-cn_{\min }^\ast \min \left\lbrace \frac{x^2}{\tau ^4\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert }, \frac{x}{\tau ^2(\Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert )^{1/2}}\right\rbrace \right].\end{split}\) 
Since \(|A|+|B|\le 2|A\cup B|\) , we have finished the proof of Lemma REF .    \(\square \)

Proof of Lemma REF . Since \({\mathbf {\Sigma }}\)  is positive semi-definite, we can find the Cholesky decomposition such that \({\mathbf {\Sigma }}= ^\top \) . Then \({\mathbf {\Sigma }}_{A\times B} = {A\times [p]}{B\times [p]}^\top \)  and
\(\begin{split}\Vert {\mathbf {\Sigma }}_{A\times B}\Vert  = & \max _{\begin{array}{c}{\mathbf {x}}\in \mathbb {R}^{|A|}, {\mathbf {y}}\in \mathbb {R}^{|B|}\\ \Vert {\mathbf {x}}\Vert _2 = \Vert {\mathbf {y}}\Vert _2 = 1\end{array}} {\mathbf {x}}^\top {A\times [p]} {B\times [p]}^\top {\mathbf {y}}\\\le & \max _{\begin{array}{c}{\mathbf {x}}\in \mathbb {R}^{|A|}, {\mathbf {y}}\in \mathbb {R}^{|B|}\\\Vert {\mathbf {x}}\Vert _2 = \Vert {\mathbf {y}}\Vert _2 = 1\end{array}} \left({\mathbf {x}}^\top {A\times [p]} {A\times [p]}^\top {\mathbf {x}}\right)^{1/2} \left({\mathbf {y}}^\top {B\times [p]}{B\times [p]}^\top {\mathbf {y}}\right)^{1/2}\\= & \max _{\begin{array}{c}{\mathbf {x}}\in \mathbb {R}^{|A|}, {\mathbf {y}}\in \mathbb {R}^{|B|}\\\Vert {\mathbf {x}}\Vert _2 = \Vert {\mathbf {y}}\Vert _2 = 1\end{array}} \left({\mathbf {x}}^\top {\mathbf {\Sigma }}_{A}{\mathbf {x}}\right)^{1/2} \left({\mathbf {y}}^\top {\mathbf {\Sigma }}_B {\mathbf {y}}\right)^{1/2} = \Vert {\mathbf {\Sigma }}_A\Vert \Vert {\mathbf {\Sigma }}_B\Vert .\end{split}\) 
Here we have used the Cauchy-Schwarz inequality.    \(\square \)

Proof of Theorem  REF
Define \({\mathbf {B}}= (b_{ij})_{1\le i,j\le p}\)  such that \(b_{ij} = \sigma _{ij}\)  if \(i \in I_s\) , \(j\in I_{s^{\prime }}\)  and \(|s - s^{\prime }| \le 1\) , and 0 otherwise. Let \(\Delta = {\mathbf {\Sigma }}- {\mathbf {B}}\) . Then
\(\Vert \hat{{\mathbf {\Sigma }}}^{\rm bt} - {\mathbf {\Sigma }}\Vert  \le \Vert \hat{{\mathbf {\Sigma }}}^{\rm bt} - {\mathbf {B}}\Vert  + \Vert \Delta \Vert . \) 
It is easy to see that
\(\Vert \Delta \Vert  \le \Vert \Delta \Vert _{\ell _1} \le \max _{i} \sum _{j: |i-j| \ge k}|\sigma _{ij}| \le Mk^{-\alpha }. \) 
To bound \(\Vert \hat{{\mathbf {\Sigma }}}^{\rm bt} - {\mathbf {B}}\Vert \) , note that
\(\Vert \hat{{\mathbf {\Sigma }}}^{\rm bt} - {\mathbf {B}}\Vert  = \sup _{u\in \mathbb {R}^p: \Vert u\Vert _2 = 1} \left|\langle u, (\hat{{\mathbf {\Sigma }}}^{\rm bt} - {\mathbf {B}})u\rangle \right|. \) 
For any \(u\in \mathbb {R}^p\) , \(\Vert u\Vert _2 =1\) , we have
\(\begin{split}\left|\langle u, (\hat{{\mathbf {\Sigma }}}^{\rm bt} - {\mathbf {B}})u \rangle \right| \le & \sum _{s, s^{\prime }: |s - s^{\prime }|\le 1}\left|\left\langle u_{I_s}, (\hat{{\mathbf {\Sigma }}}^\ast _{I_s\times I_{s^{\prime }}} - {\mathbf {\Sigma }}_{I_s\times I_{s^{\prime }}})u_{I_{s^{\prime }}} \right\rangle \right|\\\le & \sum _{s, s^{\prime }: |s - s^{\prime }|\le 1} \Vert u_{I_s}\Vert _2\Vert u_{I_{s^{\prime }}}\Vert _2 \Vert \hat{{\mathbf {\Sigma }}}^\ast _{I_s\times I_{s^{\prime }}} - {\mathbf {\Sigma }}_{I_s\times I_{s^{\prime }}}\Vert \\\le & \left(\sum _{s, s^{\prime }: |s - s^{\prime }|\le 1} \Vert u_{I_s}\Vert _2\Vert u_{I_{s^{\prime }}}\Vert _2\right) \left(\max _{|s - s^{\prime }|\le 1} \Vert \hat{{\mathbf {\Sigma }}}^\ast _{I_s\times I_{s^{\prime }}} - {\mathbf {\Sigma }}_{I_s\times I_{s^{\prime }}}\Vert \right).\end{split}\) 
The Cauchy-Schwarz inequality yields
\(\sum _{s, s^{\prime }: |s - s^{\prime }|\le 1} \Vert u_{I_s}\Vert _2\Vert u_{I_{s^{\prime }}}\Vert _2 \le \frac{1}{2} \sum _{s, s^{\prime }: |s- s^{\prime }| \le 1} \left(\Vert u_{I_s}\Vert _2^2 + \Vert u_{I_{s^{\prime }}}\Vert _2^2\right) \le 3\sum _{s=1}^N \Vert u_{I_s}\Vert _2^2 = 3.\) 
Therefore,
\(\begin{split}\Vert \hat{{\mathbf {\Sigma }}}^{\rm bt} - {\mathbf {\Sigma }}\Vert  \le & \Vert \hat{{\mathbf {\Sigma }}}^\ast - {\mathbf {B}}\Vert  + \Vert \Delta \Vert \le 3 \max _{|s - s^{\prime }|\le 1} \left\Vert \hat{{\mathbf {\Sigma }}}^\ast _{I_s\times I_{s^{\prime }}} - {\mathbf {\Sigma }}_{I_s\times I_{s^{\prime }}}\right\Vert  + Mk^{-\alpha },\end{split}\) 
which yields
\({\rm E}\Vert \hat{{\mathbf {\Sigma }}}^{\rm bt} - {\mathbf {\Sigma }}\Vert ^2 \le 18 {\rm E}\left(\max _{|s - s^{\prime }|\le 1} \left\Vert \hat{{\mathbf {\Sigma }}}^\ast _{I_s\times I_{s^{\prime }}} - {\mathbf {\Sigma }}_{I_s\times I_{s^{\prime }}}\right\Vert \right)^2 + 2M^2k^{-2\alpha }. \) 
According to lemma REF , there exists constant \(C, c>0\)  which only depend on \(\tau \)  such that for all \(x>0\) ,
\(\begin{split}\Pr \left(\max _{|s - s^{\prime }|\le 1}\Vert \hat{{\mathbf {\Sigma }}}_{I_s \times I_{s^{\prime }}} - {\mathbf {\Sigma }}_{I_s \times I_{s^{\prime }}} \Vert  \ge x\right)\le & C\lceil \frac{p}{k}\rceil (49)^k \exp \left\lbrace -c n_{\min }^\ast \min \left(\frac{x^2}{\Vert {\mathbf {\Sigma }}\Vert ^2}, \frac{x}{\Vert {\mathbf {\Sigma }}\Vert }\right)\right\rbrace .\end{split}\) 
Now we set \(t = C^{\prime }(k + \ln p)/n_{\min }^\ast \)  for \(C^{\prime }\)  large enough. The spectral norm risk satisfies
\(\begin{split}{\rm E}\Vert \hat{{\mathbf {\Sigma }}}^{\rm bt} - {\mathbf {\Sigma }}\Vert ^2 \le & 18{\rm E}\max _{|s - s^{\prime }| \le 1} \left\Vert \hat{{\mathbf {\Sigma }}}^\ast _{I_s\times I_{s^{\prime }}}\right\Vert  + 2M^2k^{-2\alpha }\\\le & 18\int _{0}^\infty \Pr \left(\max _{|s - s^{\prime }|\le 1}\Vert \hat{{\mathbf {\Sigma }}}_{I_s\times I_{s^{\prime }}} - {\mathbf {\Sigma }}_{I_s\times I_{s^{\prime }}} \Vert ^2 \ge x\right)dx + 2M^2k^{-2\alpha }\\\le & 18t + 18\int _t^\infty \Pr \left(\max _{|s - s^{\prime }|\le 1}\Vert \hat{{\mathbf {\Sigma }}}_{I_s\times I_{s^{\prime }}} - {\mathbf {\Sigma }}_{I_s\times I_{s^{\prime }}} \Vert ^2 \ge x\right)dx + 2M^2k^{-2\alpha }\\\le & 18t + C\lceil \frac{p}{k}\rceil (49)^k\int _{t}^\infty \exp \left\lbrace -c^{\prime }n_{\min }^\ast \min \left(x, x^{\frac{1}{2}}\right)\right\rbrace  dx + 2M^2k^{-2\alpha }\\\le & 18t + C\lceil \frac{p}{k}\rceil (49)^k \frac{1}{n_{\min }^\ast }\exp \left(-c^{\prime }n_{\min }^\ast t\right) + 2M^2k^{-2\alpha },\end{split}\) 
then (REF ) yields
\({\rm E}\Vert \hat{{\mathbf {\Sigma }}}^{\rm bt} - {\mathbf {\Sigma }}\Vert ^2 \le C\left(\frac{k+\ln p}{n_{\min }^\ast } + k^{-2\alpha }\right),\) 
where \(C\)  only depends on \(\tau , M, M_0\) . We can finally finish the proof of Theorem REF  by taking \(k = (n_{\min }^\ast )^{1/(2\alpha +1)}\) .   \(\square \)

Acknowledgments
We thank Tianxi Cai for the ovarian cancer data set and for helpful discussions. We also thank the Editor, the Associate editor, one referee and Zoe Russek for useful comments which have helped to improve the presentation of the paper.

Appendix: Proofs
In this appendix we collect the proofs for the main results of the sparse covariance matrix estimation and Propositions REF  and REF .

Proof of Lemma  REF
The main strategy for the proof of this lemma is similar to that for Lemma 2 in Cai and Liu [12]}. Without loss of generality, we can translate \(X\)  and assume that \({\rm E}{\mathbf {X}}= \mu  = 0\) .
First, we show the following property on \(\theta _{ij}\)
\(c\sigma _{ii}\sigma _{jj} \le \theta _{ij} \le C\sigma _{ii}\sigma _{jj}.\) 
Here \(c, C>0\)  only depend on the distribution of \({\mathbf {Z}}\) . Denote \({\mathbf {a}}, {\mathbf {b}}\)  as the \(i\) -th and \(j\) -th row vector of \(\Gamma \) , then \(\Vert {\mathbf {a}}\Vert _2^2 = {\rm var}(X_i) = \sigma _{ii}\) , \(\Vert b\Vert _2^2 = \sigma _{jj}\) . Recall that
\(\theta _{ij} = {\rm var}(X_iX_j - \sigma _{ij}) = {\rm var}({\mathbf {a}}^{\top }{\mathbf {Z}}{\mathbf {b}}^{\top }{\mathbf {Z}}- {\rm E}{\mathbf {a}}^{\top }{\mathbf {Z}}{\mathbf {b}}^{\top }{\mathbf {Z}}),\) 
thus
\(\begin{split}\theta _{ij} = {\rm var}\left({\mathbf {Z}}^{\top }{\mathbf {a}}{\mathbf {b}}^{\top }{\mathbf {Z}}\right) \le {\rm E}\left({\mathbf {Z}}^{\top }{\mathbf {a}}{\mathbf {b}}^{\top }{\mathbf {Z}}\right)^2 \le \sqrt{{\rm E}({\mathbf {Z}}^{\top }{\mathbf {a}})^4 {\rm E}({\mathbf {Z}}^{\top }{\mathbf {b}})^4}.\end{split}\) 
Since
\({\rm E}\left({\mathbf {Z}}^{\top }{\mathbf {a}}\right)^4 \le \left(\sum _{s = 1}^q a_s^4{\rm E}Z_s^4 + 6\sum _{1\le s< t\le q} a_s^2a_t^2 {\rm E}Z_s^2 {\rm E}Z_t^2\right) \le 3\Vert {\mathbf {a}}\Vert _2^4{\rm E}Z^4 \le C_\tau \sigma _{ii}^2,\) 
similarly \({\rm E}\left({\mathbf {Z}}^{\top }{\mathbf {b}}\right)^4 \le C_\tau \sigma _{jj}^2\) , we know \(\theta _{ij} \le C_\tau \sigma _{ii}\sigma _{jj}\)  for some constant \(C_\tau \)  only depending on \(\tau \) .
On the other hand, since the entries of \({\mathbf {Z}}\)  are i.i.d. with mean 0 and variance 1 and \({\rm var}(Z^2) > 0\) , we know \({\rm E}Z^4 > ({\rm E}Z^2)^2 = 1\) . We can calculate that
\(\begin{split}\theta _{ij} = & {\rm var}(X_iX_j) = {\rm E}(X_iX_j)^2 - \left({\rm E}X_iX_j\right)^2\\= & {\rm E}\left\lbrace \sum _{s=1}^q a_sb_s Z_s^2 + \sum _{1\le s<t\le q}(a_sb_t + a_tb_s)Z_sZ_t\right\rbrace ^2 - \left(\sum _{s=1}^q a_sb_s\right)^2\\= & \sum _{s=1}^q a_s^2b_s^2 {\rm E}Z_s^4 + \sum _{1\le s <t \le q} \left(a_s^2b_t^2 + a_t^2 b_s^2 + 4a_sb_sa_tb_t\right){\rm E}Z_s^2Z_t^2 - \left(\sum _{s=1}^q a_sb_s\right)^2\\= & \sum _{s=1}^q a_s^2b_s^2({\rm E}Z^4 - 3) + \left(\sum _{s=1}^q a_s^2\right)\left(\sum _{t=1}^q b_t^2\right) + \left(\sum _{s=1}^q a_sb_s\right)^2.\end{split}\) 
When \({\rm E}Z^4\ge 3\) , it is clear that
\(\theta _{ij} \ge \left(\sum _{s=1}^q a_s^2\right)\left(\sum _{s=1}^q b_s^2\right) = \Vert {\mathbf {a}}\Vert _2^2\Vert {\mathbf {b}}\Vert _2^2 = \sigma _{ii}\sigma _{jj};\) 
when \({\rm E}Z^4 < 3\) , note \(\xi = {\rm E}Z^4\) , \(x = \sum _{s: a_sb_s\ge 0} a_sb_s\) , \(y = -\sum _{s: a_sb_s<0}a_sb_s\) , then \(x, y\ge 0\)  and
\(\begin{split}\theta _{ij} \ge & -(3 - \xi )(x^2 + y^2) + (x-y)^2 + \frac{3 - \xi }{2} \left(\sum _{s=1}^q a_s^2\right)\left(\sum _{s=1}^q b_s^2\right) + \frac{\xi - 1}{2}\left(\sum _{s=1}^q a_s^2\right)\left(\sum _{s=1}^q b_s^2\right)\\\ge & -(3-\xi )(x^2 + y^2) + (x-y)^2 + \frac{3-\xi }{2}\left(\sum _{s=1}^q |a_sb_s|\right)^2 + \frac{\xi - 1}{2}\Vert {\mathbf {a}}\Vert _2^2\Vert {\mathbf {b}}\Vert _2^2\\= & -(3-\xi )(x^2 + y^2) + (x-y)^2 + \frac{3-\xi }{2}\left(x+y\right)^2 + \frac{\xi - 1}{2}\Vert {\mathbf {a}}\Vert _2^2\Vert {\mathbf {b}}\Vert _2^2\\\ge & \frac{\xi -1}{2}(x-y)^2 + \frac{\xi -1}{2}\sigma _{ii}\sigma _{jj}\ge c\sigma _{ii}\sigma _{jj}.\end{split}\) 
Here \(c = (\xi -1)/2\)  only depends on the distribution of \(Z\) .
Now we further normalize each row of \(\Gamma \)  such that \(\Vert \Gamma _{i\cdot }\Vert _2= 1\)  \({\rm var}(X_i) = {\rm var}(\Gamma _i{\mathbf {Z}}) = 1\)  for \(1\le i\le p\) . The rest of the proof is essentially the same as Lemma 2 in Cai and Liu [12]} thus we will not go into details. Let
\(\tilde{\theta }_{ij}^\ast = \frac{1}{n_{ij}^\ast } \sum _{k = 1}^n\left(X_{ik}X_{jk} - \tilde{\sigma }_{ij}^\ast \right)^2S_{ik}S_{jk}, \quad \tilde{\sigma }^\ast _{ij} = \frac{1}{n_{ij}^\ast }\sum _{k = 1}^n X_{ik}X_{jk}S_{ik}S_{jk}.\) 
We would like to show
\(\Pr \left(\max _{ij} |\hat{\theta }_{ij}^\ast - \tilde{\theta }_{ij}^\ast | \ge C_1\sqrt{\ln p/n_{ij}^\ast }\right) = O(p^{-M}).\) 
Denote \(X_i^{(j)\ast }\)  as the average of \(X_i\) 's for those samples \(X_i, X_k\)  are both observed, i.e. \(X_i^{(j)\ast } = \sum _{k=1}^n S_{ik}S_{jk} X_{ik}/n_{ij}^\ast \) . Then,
\(\begin{split}\hat{\theta }_{ij}^\ast = & \frac{1}{n_{ij}^\ast }\sum _{k = 1}^nS_{ik}S_{jk}\left(X_{ik}X_{jk} - \bar{X}_i^\ast X_{jk} - \bar{X}_j^\ast X_{ki} - \tilde{\sigma }_{ij}^\ast + \bar{X}_i^{(j)\ast } \bar{X}_j + \bar{X}_j^{(i)\ast } \bar{X}_i\right)^2\\= & \tilde{\theta }_{ij}^\ast + \frac{2}{n_{ij}^\ast }\sum _{k=1}^n S_{ik}S_{jk} \left(X_{ik}X_{jk} - \tilde{\sigma }_{ij}^\ast \right)\left(\bar{X}_i^{(j)\ast }\bar{X}_j^\ast + \bar{X}_j^{(i)\ast }\bar{X}_i^\ast - \bar{X}_i^\ast X_{jk} - \bar{X}_j^\ast X_{ik}\right)\\& + \frac{1}{n_{ij}^\ast }\sum _{k=1}^n S_{ik}S_{jk} \left(\bar{X}_i^{(j)\ast }\bar{X}_i^\ast + \bar{X}_j^{(i)\ast }\bar{X}_i^\ast - \bar{X}_i^\ast X_{jk} - \bar{X}_j^\ast X_{ik}\right)^2.\end{split}\) 
Similarly to Lemma 2 in Cai and Liu [12]}, we could have
\(\Pr \left(\max _{i,j} | \bar{X}_i^{(j)\ast }| \ge C_2\sqrt{\frac{\ln p}{n_{ij}^\ast }}\right) = O\left(p^{-M}\right),\) 
\(\Pr \left(\max _{ij} \left|\frac{1}{n_{ij}^\ast }\sum _{k=1}^nS_{ik}S_{jk} X_{ik}^2 X_{jk}\bar{X}_j^\ast \right| \ge C_5\sqrt{\frac{\ln p}{n_{ij}^\ast }}\right).\) 
and similar bounds for the other terms in the right hand side of (REF ). Hence we have proved (REF ). By (REF ), we can directly get
\(\Pr \left(\left|\tilde{\theta }_{ij}^\ast - \theta _{ij}\right|\ge \varepsilon \right) = O(p^{-M}),\) 
by applying the result in Lemma 2 in Cai and Liu [12]} on the samples \({\mathbf {X}}_{k}, k\in \lbrace k: S_{ik} = S_{jk} = 1\rbrace \) . Combining (REF ) and (REF ), we can proved (REF ).
The proof of (REF ) is omitted here because it is essentially the same as that of Lemma 2 in [12]}.
   \(\square \)

Proof of Theorem  REF
First without loss of generality, we can assume that \(\mu  = {\rm E}{\mathbf {X}}_k = 0\) . Based on Assumption REF , we have for each \(k\) , \({\mathbf {X}}_k = \Gamma {\mathbf {Z}}_k\) , where \({\mathbf {Z}}_k\)  is an i.i.d. sub-Gaussian random vector. Based on the proof of Lemma REF , we know \(c\sigma _{ii}\sigma _{jj}\le \theta _{ij} \le C\sigma _{ii}\sigma _{jj}\) , where \(c, C\)  are constants which only depend on the distribution of \({\mathbf {Z}}\) . We will prove Theorem REF  in several steps.

For \(\varepsilon >0\) , we first consider the loss under the event that
\(Q = \left\lbrace |\hat{\sigma }_{ij}^\ast - \sigma |/\hat{\theta }_{ij}^\ast \le \delta \sqrt{\ln p/n_{ij}^\ast }, \forall 1\le i, j\le p, \quad \text{and}\quad \max _{ij}|\hat{\theta }_{ij}^\ast - \theta _{ij}|/(\sigma _{ii}\sigma _{jj}) \le \varepsilon .\right\rbrace .\) 
Since \(|\hat{\sigma }_{ij}^\ast - \sigma _{ij}|\le \delta \sqrt{\hat{\theta }_{ij}^\ast \ln p/n_{ij}^\ast } = \lambda _{ij}\) , by Condition (1) of \(T_{\lambda _{ij}}\) , we have
\(|T_{\lambda _{ij}}(\hat{\sigma }_{ij}^\ast ) - \sigma _{ij}| \le c_T|\sigma _{ij}|.\) 
Besides, by condition (3) of \(T_{\lambda _{ij}}\) ,
\(\begin{split}& |T_{\lambda _{ij}}(\hat{\sigma }_{ij}^\ast ) - \sigma _{ij}| \le |T_{\lambda _{ij}}(\hat{\sigma }_{ij}^\ast ) - \hat{\sigma }_{ij}^\ast | + |\hat{\sigma }_{ij}^\ast - \sigma _{ij}| \overset{(\ref {ineq:situ_sparse_cov})}{\le } \lambda _{ij} + \delta \sqrt{\frac{\hat{\theta }_{ij}^\ast \ln p}{n_{ij}^\ast }}\\\le & 2\delta \sqrt{\frac{\hat{\theta }_{ij}^\ast \ln p}{n_{ij}^\ast }}\le 2\delta \sqrt{\frac{(\theta _{ij}+\varepsilon \sigma _{ii}\sigma _{jj})\ln p}{n_{ij}^\ast }}\le C\sqrt{\frac{\sigma _{ii}\sigma _{jj} \ln p}{n_{ij}^\ast }}.\end{split}\) 
Since \(n_{\min }^\ast \le n_{ij}^\ast \le n\) , thus
\(\begin{split}\Vert \hat{{\mathbf {\Sigma }}}^{\rm at} - {\mathbf {\Sigma }}\Vert _{\ell _1} \le & \max _i \sum _{j=1}^p \left|T_{\lambda _{ij}}(\hat{{\mathbf {\Sigma }}}_{ij}^\ast ) - \sigma _{ij}\right|\le \max _i \sum _{j=1}^p C\min \left\lbrace |\sigma _{ij}|, \sqrt{\frac{\sigma _{ii}\sigma _{jj}\ln p}{n_{ij}^\ast }}\right\rbrace \\\overset{(\ref {eq:Hc_np})}{\le } & C c_{n, p} \sqrt{\frac{\ln p}{n_{\min }^\ast }} .\end{split}\) 
Since \(\hat{{\mathbf {\Sigma }}}^{\rm at} - {\mathbf {\Sigma }}\)  is a symmetric matrix, we have
\(\Vert \hat{{\mathbf {\Sigma }}}^{\rm at} - {\mathbf {\Sigma }}\Vert _{\ell _q} \le \Vert \hat{{\mathbf {\Sigma }}}^{\rm at} - {\mathbf {\Sigma }}\Vert _{\ell _1} \le Cc_{n, p}\sqrt{\frac{\ln p}{n_{\min }^\ast }}\) 
for all \(1\le q\le \infty \) .
By Lemma REF , we know (REF ) happens with probability at least \(1 - O\left\lbrace (\ln p)^{-1/2}p^{-\delta +2}\right\rbrace \) , which implies (REF ).

Next we consider (REF ). We apply Lemma REF  by restricting \({\mathbf {\Sigma }}\)  on \(\lbrace i, j\rbrace \times \lbrace i, j\rbrace \)  and set \(A = \lbrace i\rbrace \) , \(B = \lbrace j\rbrace \) , then there exists \(C_1, c_1>0\)  such that
\(\Pr \left(|\hat{\sigma }_{ij}^\ast - \sigma _{ij}| \le x\right) \ge 1 - C_1\exp \left[-c_1 n_{ij}^\ast \min \left\lbrace \frac{x^2}{\sigma _{ii}\sigma _{jj}} , \frac{x}{(\sigma _{ii}\sigma _{jj})^{1/2}}\right\rbrace \right]\) 
holds for all \(x>0\) . Therefore,
\(\Pr \left\lbrace |\hat{\sigma }_{ij}^\ast - \sigma _{ij}| \le x(\sigma _{ii}\sigma _{jj})^{1/2}, \forall 1\le i, j\le p \right\rbrace  \ge 1 - C_1p^2\exp \left\lbrace -c_1n_{\min }^\ast \min (x, x^2)\right\rbrace .\) 
We also have
\(|T_{\lambda _{ij}}(\hat{\sigma }^\ast _{ij}) - \sigma _{ij}| \le c_T|\hat{\sigma }^\ast _{ij}| + |\sigma _{ij}| \le (1+c_T)|\sigma _{ij}| + c_T|\hat{\sigma }^\ast _{ij} - \sigma _{ij}|. \) 
Thus,
\(\begin{split}& {\rm E}\Vert \hat{{\mathbf {\Sigma }}}^{\rm at} - {\mathbf {\Sigma }}\Vert ^2_{\ell _1} = \int _Q \Vert \hat{{\mathbf {\Sigma }}}^{\rm at} - {\mathbf {\Sigma }}\Vert _{\ell _1}^2dP + \int _{Q^c} \Vert \hat{{\mathbf {\Sigma }}}^{\rm at} - {\mathbf {\Sigma }}\Vert _{\ell _1}^2dP\\\le & Cc_{n, p}^2\frac{\ln p}{n_{\min }^\ast } + \int _{Q^c}\left(\max _{i} \sum _{j=1}^p |T_{\lambda _{ij}}(\hat{\sigma }_{ij}) - \sigma _{ij}|\right)^2dP\\\le & Cc_{n, p}^2\frac{\ln p}{n_{\min }^\ast } + C\int _{Q^c} \left(\max _i \sum _{j=1}^p |\sigma _{ij}|\right)^2dP + C\int _{Q^c}\left(\max _i \sum _{j=1}^p |\hat{\sigma }_{ij}^\ast - \sigma _{ij}| \right)^2dP.\\\end{split}\) 
For the second term above, we have
\(\begin{split}C\int _{Q^c} \left(\max _i \sum _{j=1}^p |\sigma _{ij}| \right)^2dP \le & C\int _{Q^c} \left[\max _i \sum _{j=1}^p \min \left\lbrace (\sigma _{ii}\sigma _{jj})^{1/2}, \frac{|\sigma _{ij}|}{\sqrt{\ln p/n_{\min }^\ast }}\right\rbrace \right]^2dP\\\le & C \Pr (Q^c)c_{n, p}^2 \le C c_{n, p}^2 p^{-\delta +2} (\ln p)^{-1/2}.\end{split}\) 
Based on the assumption that \(p \ge (n_{\min }^\ast )^\xi \) , \(\delta \ge 4 + 1/\xi \) , we have
\(C\int _{Q^c} \left(\max _i \sum _{j=1}^p |\sigma _{ij}| \right)^2 \le Cc_{n, p}^2\frac{\ln p}{n_{\min }^\ast }.\) 
We denote \(K = \max _i \sigma _{ii}\) , then \(K \le c_{n, p}\) . For the third term above in (REF ), we have
\(\begin{split}& C\int _{Q^c}\left(\max _i \sum _{j=1}^p |\hat{\sigma }_{ij}^\ast - \sigma _{ij}| \right)^2dP \le C p^2\int _{Q^c} \left(\max _{ij} |\hat{\sigma }_{ij}^\ast - \sigma _{ij}| \right)^2dP\\\le & Cp^2 \int _{0}^\infty x \Pr \left(\lbrace \max _{ij} |\hat{\sigma }_{ij}^\ast - \sigma _{ij}| \ge x\rbrace  \cap Q^c\right)dx\\= & Cp^2\int _0^{K} x \Pr \left(\lbrace \max _{ij} |\hat{\sigma }_{ij}^\ast - \sigma _{ij}| \ge x\rbrace  \cap Q^c\right)dx\\& + Cp^2\int _K^{\infty } x \Pr \left(\lbrace \max _{ij} |\hat{\sigma }_{ij}^\ast - \sigma _{ij}| \ge x\rbrace  \cap Q^c\right)dx\\\le & Cp^2K^2\Pr (Q^c) + Cp^2 \int _{K}^\infty x\exp \left\lbrace -c_1 n_{\min }^\ast \min \left(\frac{x^2}{\max _{i}\sigma _{ii}^2}, \frac{x}{\max _i \sigma _{ii}}\right) \right\rbrace dx\\\le & Cp^2c_{n, p}^2p^{-\delta +2}(\ln p)^{-1/2} + Cp^2 \int _K^\infty x\exp (-c_1 n_{\min }^\ast x/K)dx\\\le & Cp^{-\delta +4}(\ln p)^{-1/2} c_{n, p}^2 + Cp^2c_{n, p}^2\exp (-c n_{\min }^\ast ).\end{split}\) 
Based on the assumption \(\ln p = o((n_{\min }^\ast )^{1/3})\)  and \(p \ge (n_{\min }^\ast )^\xi \) , \(\delta \ge 4 + 1/\xi \) , we have
\(C\int _{Q^c}\left(\max _i \sum _{j=1}^p |\hat{\sigma }_{ij}^\ast - \sigma _{ij}| \right)^2dP \le Cc_{n, p}^2 \frac{\ln p}{n_{\min }^\ast }.\) 
Combining (REF ), (REF ) and (REF ), we have finished the proof of (REF ) under the additional assumption that \(p\ge (n_{\min }^\ast )^\xi \) , \(\delta \ge 4 + 1/\xi \) .
   \(\square \)


Proof of Theorem REF .
By Lemma REF , we know
\(\Pr \left(|\hat{\sigma }_{ij}^\ast - \sigma _{ij}| \ge 2\sqrt{\frac{\ln p \hat{\theta }_{ij}^\ast }{n_{ij}^\ast }}, \exists 1\le i, j\le p\right) = O\left\lbrace (\ln p)^{-1/2}\right\rbrace ;\) 
for all \(\varepsilon >0\) ,
\(\Pr \left(|\hat{\theta }_{ij}^\ast - \theta _{ij}|/\sqrt{\sigma _{ii}\sigma _{jj}} \ge \varepsilon , \exists 1\le i, j\le p\right) = O(p^{-M}).\) 
Also by the proof of Lemma REF , there exists \(c>0\)  such that
\(\theta _{ij}/\sqrt{\sigma _{ij}\sigma _{ij}} > c.\) 
When \(\delta =2\) , the thresholding level is
\(\lambda _{ij} = 2\sqrt{\frac{\hat{\theta }_{ij}^\ast \ln p}{n_{ij}^\ast }}.\) 
Therefore,
\(\begin{split}& \Pr \left\lbrace {\rm supp}(\hat{{\mathbf {\Sigma }}}^{\rm at}) \ne {\rm supp}({\mathbf {\Sigma }})\right\rbrace \\=& \Pr \left\lbrace T_{\lambda _{ij}}(\hat{\sigma }^\ast _{ij}) = 0, \exists (i,j)\in {\rm supp}({\mathbf {\Sigma }})\right\rbrace  + \Pr \left\lbrace T_{\lambda _{ij}}(\hat{\sigma }^\ast _{ij}) \ne 0, \exists (i,j)\notin {\rm supp}({\mathbf {\Sigma }})\right\rbrace  \\\le & \Pr \left\lbrace |\hat{\sigma }_{ij}^\ast | \le \lambda _{ij}, \exists (i, j)\in {\rm supp}({\mathbf {\Sigma }}) \right\rbrace  + \Pr \left\lbrace |\hat{\sigma }_{ij}^\ast | > \lambda _{ij}, \exists (i, j)\notin {\rm supp}({\mathbf {\Sigma }}) \right\rbrace \\\overset{(\ref {eq:support_lambda})}{\le } & \Pr \left(|\hat{\sigma }_{ij}^\ast - \sigma _{ij}| \ge 2\sqrt{\frac{\hat{\theta }_{ij}^\ast \ln p}{n_{ij}^\ast }}, \exists 1\le i, j \le p\right)\\& + \Pr \left\lbrace |\sigma _{ij}| \le 4\sqrt{\frac{\hat{\theta }_{ij}^\ast \ln p}{n_{ij}^\ast }}, \exists (i, j)\in {\rm supp}({\mathbf {\Sigma }})\right\rbrace \\\overset{(\ref {ineq:support_sigma})}{\le } & O\left\lbrace (\ln p)^{-1/2}\right\rbrace  + \Pr \left\lbrace (4+\gamma )\sqrt{\frac{\theta _{ij}\ln p}{n_{ij}^\ast }} \le 4\sqrt{\frac{\hat{\theta }_{ij}^\ast }{n_{ij}^\ast }}, \exists (i,j)\in {\rm supp}({\mathbf {\Sigma }})\right\rbrace \\\le & O\left\lbrace (\ln p)^{-1/2}\right\rbrace  + \Pr \left\lbrace \left(\frac{4+\gamma }{4}\right)^2-1 \le \frac{\hat{\theta }_{ij}^\ast - \theta _{ij}}{\theta _{ij}},\exists (i,j)\in {\rm supp}({\mathbf {\Sigma }})\right\rbrace \\\overset{(\ref {ineq:support_1})(\ref {ineq:support_2})}{=} & o(1),\end{split}\) 
which means \(\Pr \left\lbrace {\rm supp}(\hat{{\mathbf {\Sigma }}}^{\rm at}) \ne {\rm supp}({\mathbf {\Sigma }})\right\rbrace  = o(1)\) .
   \(\square \)

Proof of Propositions REF  and REF .
For given \(n_0\ge 1\) , we again consider a special pattern of missingness \({\mathbf {S}}_0\) :
\(({\mathbf {S}}_0)_{ij} = \left\lbrace \begin{array}{ll}1, & 1\le i\le n_0, 1\le j\le p\\0, & n_0 +1\le i\le n, 1\le j\le p.\end{array}\right.\) 
Under this missingness pattern, \(n_{\min }^\ast = n_0\) , and the problem essentially becomes complete data problem with \(n_0\)  samples. Now, Propositions REF , REF  directly follow Theorem 3 of Cai et al. [11]} and Theorem 2 of Cai and Zhou [18]}, respectively.
