© Wuhan University 2022

0 Introduction

High dimensional data can be efficiently collected at a low cost in many scientific areas due to the advance of information technology. In analysis of high dimensional data, estimating the positive-definite covariance matrix, denoted $\Sigma$, is perhaps one of the most fundamental problems. It is however not straightforward to estimate $\Sigma$ precisely in high dimensions. To estimate the positive-definite covariance matrix $\Sigma$ accurately, an important concept, sparsity, is introduced which assumes many off-diagonal components of $\Sigma =({\sigma }_{i,j}{)}_{p\times p}$ are identically zero. The sparsity assumption plays an important role to construct $\widehat{\Sigma }=({\sigma }_{i,j}{)}_{p\times p}$, an intuitively feasible estimate of $\Sigma$, and to establish the consistency property of $\widehat{\Sigma }$. If $\Sigma$ is sparse, many interesting approaches, such as banding^[1], tapering^[2] and thresholding^[1，3] are proposed in the literature to produce sparse estimates of $\Sigma$. However, these sparse estimates are not always positive-definite, though the positive-definite property is highly desirable.

The definition of positive-definite was described in Xue et al ^[4]. When the positive-definite property is concerned in estimating the high dimensional covariance matrix, Friedman et al ^[5] and Rothman^[6] considered the following minimization problem:$\widehat{\Sigma }=\left(\tau ,\lambda \right)=\arg \underset{\Sigma \ge 0}{\min }\left\{\frac{1}{2}{\Vert \Sigma -{\widehat{\Sigma }}_n\Vert }_2^2-\tau \log \left\{\det \left(\Sigma \right)\right\}+\lambda {\Vert \Sigma \Vert }_1\right\}$(1)where τ and λ are two distinctive regularization parameters, τ≥0 is introduced here to ensure the positive-definite of $\widehat{\Sigma }=(\tau ,\lambda )$ and $\lambda \ge 0$ controls the trade-off between the penalty and the loss function. The following notations will be used:

${\widehat{\Sigma }}_n=n^{-1}{\displaystyle \sum _{i=1}^n\left(x_i-\overline{x}\right)}{\left(x_i-\overline{x}\right)}^{\text{T}}$ is the sample covariance matrix, $\overline{x}=n^{-1}{\displaystyle \sum _{i=1}^n{x}_i},x_1,\cdots ,x_n$ is a random sample of size $n,X_i={(X_{i,1},\cdots ,X_{i,p})}^{\text{T}}\in R^p,\det (\Sigma )$ stands for the determinant of $\Sigma ,{\Vert \Sigma \Vert }_2$ stands for the Frobenius norm of $\Sigma ,\text{\hspace{0.17em}and\hspace{0.17em}}{\Vert \Sigma \Vert }_1$ stands for the ${\mathcal{l}}_1$ norm of all off-diagonal elements of $\Sigma$. Specifically,$\begin{array}{l}{\Vert \Sigma \Vert }_2={\displaystyle \sum _{i,j=1}^p{\sigma }_{i,j}^2}\text{ and }{\Vert \Sigma \Vert }_1={\displaystyle \sum _{i\ne j}\left|{\sigma }_{i,j}\right|}\\ \end{array}$

An iterative shooting algorithm is proposed by Friedman et al ^[5] and Rothman^[6] to solve (1). However, whether this shooting algorithm converges or not remains unknown in the literature. To yield a positive-definite estimate of $\Sigma$, Xue et al ^[4] considered a different optimization problem:$\widehat{\Sigma }\left(\lambda \right)=\arg \underset{\Sigma \ge \epsilon I}{\min }\left\{\frac{1}{2}{\Vert \Sigma -{\widehat{\Sigma }}_n\Vert }_2^2+\lambda {\Vert \Sigma \Vert }_1\right\}$(2)for a sufficiency small positive constant ε, where I stands for an identity matrix. Solving (2) with the constraint $\Sigma \ge \epsilon {\rm I}$ must yield a positive-definite $\widehat{\Sigma }(\lambda )$. Xue et al ^[4] proposed an Alternating Direction Method of Multiplies (ADMM ) to convert the problem of solving (2) into a sequence of simpler optimization subproblems. This method has been cited and studied in many subsequent researches^[4].

Although solving a sequence of subproblems may end up taking more iterations than directly solving (2), it runs in less total time because the subproblems are relatively easy to solve in general. In the present context, all the subproblems have explicit analytic forms. These two optimization problems, described in (1) and (2) can be efficiently solved for a single regularization parameter, referring to Kang and Deng^[7], Choi et al ^[8], Zhang et al ^[9], etc. However, when these optimization problems are solved over the full range of regularization parameters, the computational complexity will be dramatically increased.

Efficient estimation of positive-definite covariance matrix can be implemented by these two optimization problems, described in (1) and (2). But Log structure of (1) is not stable in estimation process. In this paper we suggest to compute the regularization paths of $\widehat{\Sigma }(\lambda )$ through a slight modification of Xue et al’s ADMM algorithm^[4]. To choose an optimal λ which yields the “best” estimate $\widehat{\Sigma }(\lambda )$ in a certain sense, Xue et al ^[4] suggested to inspect a sequence of sparse solutions over the full range of regularization parameters:$\{\widehat{\Sigma }=(\lambda ):0\le {\lambda }_1\le \cdots \le {\lambda }_M\}$, where M is usually set to 100 heuristically, ${\lambda }_M={\lambda }_{\max }$ and λ_max is the maximal value of λ such that $\widehat{\Sigma }(\lambda )=0$, the sparsest solution. Conceptually, estimating $\widehat{\Sigma }(\lambda )$ at a fixed λ consists of two ingredients. The first is to seek for the support of $\widehat{\Sigma }(\lambda )={\{{\widehat{\sigma }}_{i,j}(\lambda )\}}_{p\times p}$, which is defined as the (i,j) pairs such that ${\widehat{\sigma }}_{i,j}(\lambda )\ne 0$. The second step is to solve (2) over the support of $\widehat{\Sigma }(\lambda )$. In general, the first step is much more important than the second step for large scale problems because one can always refit $\Sigma$ to obtain an optimal estimate of the parameter values with a sufficiently correct estimate of the support of $\Sigma$. To handle large scale problems, we need algorithms not only to recover the support of $\widehat{\Sigma }(\lambda )$ but also to estimate the entire sequence of $\widehat{\Sigma }(\lambda )$ quickly. Following Friedman et al ^[10], Wu and Lange^[11], Hu et al ^[12], we first introduce a procedure to estimate the regularization paths through an ADMM algorithm with warm starts over a range of regularization parameters to yield a path-like sequence of solutions, then perform a one-step approximation along each point on this path to yield an ADMM algorithmic regularization path. This procedure quickly outlines a sequence of $\widehat{\Sigma }(\lambda )$ at a fine resolution and, at the same time, reduces computational time dramatically.

The rest of this paper is organized as follows. In Section 1, we first review the ADMM algorithm with warm-starts over a grid of regularization parameters to yield a path-like sequence of solutions, then use the one-step approximation of this path-like sequence of solutions to obtain an algorithmic regularization path. In Section 2, we demonstrate the effectiveness and computational savings of our proposals through simulated examples. We conclude this paper with some brief remarks in Section 3.

1 The Algorithmic Regularization Path

In this section we use Xue et al ’s^[4] ADMM splitting method as the foundation to develop a new approximation to the sequence of sparse solutions $\widehat{\Sigma }(\lambda )$, which allows us to quickly explore the space of sparse solutions at a fine resolution. And, sacrifice of estimation precision can be ignored as long as the step size, defined as $\underset{j}{\max }({\lambda }_{j+1}-{\lambda }_j)$, is sufficiently small. The objective function formulated in (2) by Xue et al ^[4] consists of a differentiable loss function, ${\Vert \Sigma -{\widehat{\Sigma }}_n\Vert }_2^2$, a non-differentiable penalty, $\lambda {\Vert \Sigma \Vert }_1$, and a constraint $(\Sigma \ge \epsilon I)$ which ensures that $\widehat{\Sigma }(\lambda )$ is positive-definite. In the constraint, $\epsilon$ is a user-specified parametric which is sufficiently small, say, $\epsilon ={10}^{-6}$. The loss function is also convex in $\Sigma$. The regularization parameter $\lambda \ge 0$ controls the trade-off between of the loss function and the penalty. Following Xue et al ^[4], we split the smooth loss function from the nonsmooth penalty through a copy para matrix $\Theta$, and add an equality constraint forcing $\Sigma =\Theta$, which converts (2) into$({\widehat{\Theta }}^{+},{\widehat{\Sigma }}^{+})=\arg \underset{\Sigma ,\Theta }{\min }\left\{\frac{1}{2}{\Vert \Sigma -{\widehat{\Sigma }}_n\Vert }_2^2+\lambda {\Vert \Theta \Vert }_1:\Sigma =\Theta ,\Theta \ge \epsilon I\right\}$(3)

Similar operator splitting strategies are also used in many other learning problems such as total variation^[13], jointly graphical model selection^[14,15], a convex formulation of clustering^[16], etc. With scaled dual variable $\Lambda$ of the same dimension as $\Sigma$ and $\Theta$ and an algorithm tuning parameter $\mu$ the associated augmented Lagrangian of (3) is$\varphi (\Sigma ,\Theta ,\Lambda )=\frac{1}{2}{\Vert \Sigma -{\widehat{\Sigma }}_n\Vert }_2^2+\lambda {\Vert \Theta \Vert }_1+\frac{\mu }{2}{\Vert \Sigma -\Theta +\Lambda \Vert }_2^2$

Then the ADMM algorithm for (2) is partitioned into three subproblems:

1) $\Sigma$-subproblem：${\Sigma }^k=\underset{\Sigma }{\arg \min }\{\varphi (\Sigma ,{\Theta }^{k-1},{\Lambda }^{k-1})\}$(4)

2) $\Theta$-subproblem：${\Theta }^k=\underset{\Theta }{\arg \min }\{\varphi ({\Sigma }^k,\Theta ,{\Lambda }^{k-1})\}，\text{subject to }\Theta \ge \epsilon I$(5)

3) Dual update${\Lambda }^k={\Lambda }^{k-1}+{\Sigma }^k-{\Theta }^k$

We solve these subproblems, together with the dual update, iteratively until convergence. The benefit of solving these subproblems is that there are closed-form solutions to both (4) and (5). The $\Sigma$-subproblem solves a linear regression with an additional quadratic ridge penalty. Specifically,$\begin{array}{l}{\Sigma }^k=\underset{\Sigma }{\arg \min }\\ \{\frac{1}{2}{\Vert \Sigma -{\widehat{\Sigma }}_n\Vert }_2^2+\lambda {\Vert {\Theta }^{k-1}\Vert }_1+\frac{\mu }{2}{\Vert \Sigma -{\Theta }^{k-1}+{\Lambda }^{k-1}\Vert }_2^2\}\\ =\underset{\Sigma }{\arg \min }\{\frac{1}{2}{\Vert \Sigma -{\widehat{\Sigma }}_n\Vert }_2^2+\frac{\mu }{2}{\Vert \Sigma -{\Theta }^{k-1}+{\Lambda }^{k-1}\Vert }_2^2\}\\ =(1+\mu {)}^{-1}\{\mu ({\Theta }^{k-1}-{\Lambda }^{k-1})+{\widehat{\Sigma }}_n\}\end{array}$

The $\Theta$-subproblem also has an analytical solution. For notational clarity, we define ${(B)}_{+}$ as the projection of $(B)={(B_{j,l})}_{1\le j,l\le p}$ onto the convex cone $\{\Theta \ge \epsilon I\}$. Specifically, suppose λ_j is the j-th eigenvalue of B and μ_j is the associated eigenvector, namely,$B={\displaystyle \sum _{j=1}^p{\lambda }_j}{\mu }_j^{\text{T}}{\mu }_j\text{, then }{(B)}_{+}={\displaystyle \sum _{j=1}^p{\lambda }_j}\max ({\lambda }_j,\epsilon ){\mu }_j^{\text{T}}{\mu }_j$

We further define an entry wise soft thresholding rule, denoted $S(B,\tau )={\left\{s{(B_{j,l},\tau )}_{1\le j,l\le p}\right\}}_{1\le j,l\le p}$, for all the off-diagonal elements of B .$\begin{array}{l}s(B_{j,l},\tau )=\text{sign}(B_{j,l})\max (\left|B_{j,l}\right|-\tau ,0)I\\ (j\ne l)+B_{j,l}I(j=l)\end{array}$The analytical solution of the $\Theta$-subproblem is as follows:$\begin{array}{l}{\Theta }^k=\underset{\Theta \ge \epsilon I}{\arg \min }\\ \{\frac{1}{2}{\Vert {\Sigma }^k-{\widehat{\Sigma }}_n\Vert }_2^2+\lambda {\Vert \Theta \Vert }_1+\frac{\mu }{2}{\Vert {\Sigma }^k-\Theta +{\Lambda }^{k-1}\Vert }_2^2\}\\ =\underset{\Theta \ge \epsilon I}{\arg \min }\{\lambda {\Vert \Theta \Vert }_1+\frac{\mu }{2}{\Vert \Theta -({\Sigma }^k+{\Lambda }^{k-1})\Vert }_2^2\}\\ =\{S({\Sigma }^k+{\Lambda }^{k-1},\lambda /\mu ){\}}_{+}\end{array}$Solving the $\Theta$-subproblem introduces sparsity. Finally, the dual update guarantees that ${\Sigma }^k$ is squeezed towards ${\Theta }^k$. As the iterations proceed, ${\Theta }^k$ becomes increasingly sparse. We shall illustrate this phenomenon with simulations in Section 2. One can refer to Fig. 1 (a) and (c) for details. Because the $\Theta$-subproblem controls the sparsity level of ${\Theta }^k$, a natural question arises: How to use or modify the iterates of the ADMM algorithm to quickly generate regularization paths for estimating a sparse positive-definite covariance matrix in high or even ultrahigh dimensions?

Following the idea of Hu et al ^[12], we provide two options to quickly generate a regularization path. The first is to use warm starts in the ADMM algorithm along a grid of regularization parameters, say, $0\le {\lambda }_1\le \cdots \le {\lambda }_M$. To be precise, the warm starts use the solution from the previous value of ${\lambda }_j$, $\widehat{\Sigma }({\lambda }_j)$, as the initial value for the ADMM algorithm to solve the optimization problem at ${\lambda }_{j+1}$. If ${\lambda }_{j+1}$ is sufficiently close to ${\lambda }_j$, it is reasonable to expect that$\widehat{\Sigma }({\lambda }_{j+1})$ is also very close to $\widehat{\Sigma }({\lambda }_j)$. Using warm starts usually reduces the number of iterations dramatically.

The ADMM algorithm with warm starts, which is referred to as Algorithm 1 in our context, is described below:

In the above algorithm, the convergence is measured by the primal and dual residuals^[17]. The resulting solution goes from dense to sparse, or equivalently, the regularization parameter λ goes from small to large. The ADMM algorithm with warm starts can certainly go in the reverse direction from sparse to dense. However, going from sparse to dense may introduce additional yet unnecessary discontinuities in the $\Theta$-subproblem, consequently would require more iterations for convergence. Therefore, we advocate using the ADMM algorithm with warm starts going from dense to sparse, as described in Algorithm 1 at present.

The second option to speed the computation of regularization paths is to seek for a single path approximating algorithm instead of solving several optimization problems separately over a grid of regularization parameter values. In general, the sparsity levels of ${\Theta }^k(\lambda )$ typically stabilize to that of the solution within a small number of iterations as λ is increased from λ₁ to λ_M; and the remaining iterations and a large proportion of the computation time are spent on squeezing $\Sigma$ towards $\Theta$ to satisfy the primal feasibility. This motivates us to surmise that, if λ_j+1 is sufficiently close to λ_j, then the sparsity patterns given by the $\Theta$-subproblem may correctly approximate the regularization paths within a few or even one iteration when implementing the ADMM algorithm with warm starts. This further motivates us to suggest the following ADMM Algorithmic Regularization Paths to quickly approximate the regularization paths for estimating large scale positive-defi- nite covariance matrices.

This algorithm is described as follows:

In Algorithm 2, the sequence of λ_j can be linearly spaced. As long as the step size, defined as $\underset{j}{\max }({\lambda }_{j+1}-{\lambda }_j)$, is sufficiently small, the sparsity patterns of Algorithm 2 can well approximate the regularization paths of $\widehat{\Sigma }(\lambda )$. This algorithm makes full use of three key ingredients to quickly generate a regularization path: the sparsity patterns of the solution to the $\Theta$-subproblem, the ADMM with warm-starts generating a dense to sparse solution and the one-step approximation at each regularization level. We begin with the fully dense ridge solution, employing these key ingredients, to implement the ADMM algorithm which gradually increases the amount of regularization level until we obtain a fully sparse solution. If we iterate the three subproblems until convergence, Algorithm 2 would be approximatively equivalent to Algorithm 1. Therefore, the one-step approximation is the key difference between these two algorithms.

In both of the above algorithms, there is an ADMM tuning parameter μ. We fix μ=1 in our algorithms. Updating μ dynamically may speed up convergence (Boyd et al ^[17], He et al ^[18]), however, it is not conducive to achieve a path-like algorithm using warm-starts. In particular, the sparsity levels of $\Theta$ dramatically change when μ is changed because the $\Theta$-subproblem was solved by soft-thresholding at the level $\lambda /\mu$, which eliminates the benefit of using warm-starts to achieve relatively smooth transitions in sparsity levels.

There are at least three advantages of working with Algorithm 2: it is easy to implement with a few lines of code; it fleetly gives a sequence of sparse solutions as it requires M iterations to fully explore the regularization paths $\widehat{\Sigma }(\lambda )$; and it also allows us to explore the space of sparse models at a very fine resolution.

Algorithm 1: ADMM with warm starts to estimate sparse and large scale positive-definite covariance
1. Initialize ${\Sigma }^0=0,{\Lambda }^0=0,$and M log-spaced values${\lambda }_1\prec {\lambda }_2\prec \cdots \prec {\lambda }_M$ for${\lambda }_1=0$ and${\lambda }_M={\lambda }_{\text{max}}$
2. for$j=1,\cdots ,M$ do
	Initialize ${\Sigma }^0({\lambda }_j)=\widehat{\Sigma }({\lambda }_{j-1})$ and ${\Lambda }^0({\lambda }_j)=\widehat{\Lambda }({\lambda }_{j-1})$;
	while$\Vert r^k\Vert \wedge \Vert s^k\Vert >{\epsilon }^{\text{tolerance}}$ do
			${\Theta }^k({\lambda }_j)={\left[S\{{\Sigma }^{k-1}({\lambda }_j)+{\Lambda }^{k-1}({\lambda }_j),{\lambda }_j/\mu \}\right]}_{+}$
			${\Sigma }^k({\lambda }_j)={(1+\mu )}^{-1}\left[\mu \{{\Theta }^k({\lambda }_j)-{\Lambda }^{k-1}({\lambda }_j)\}+{\widehat{\Sigma }}_n\right]$
			${\Lambda }^k({\lambda }_j)={\Lambda }^{k-1}({\lambda }_j)+{\Sigma }^k({\lambda }_j)-{\Theta }^k({\lambda }_j)$
			$r^k={\Sigma }^k({\lambda }_j)-{\Theta }^k({\lambda }_j)$ and $S^k={\Theta }^k({\lambda }_j)-{\Theta }^{k-1}({\lambda }_j)$
			$k=k+1$
		end while
	end for
3. Output $\{\Sigma ({\lambda }_j),j=1,\cdots ,M\}$ as the regularization path.

Algorithm 2: Algorithmic regularization paths to estimate sparse and large scale positive-definite covariance matrices
1. Initialize ${\Theta }^0=0,{\Lambda }^0=0,$ set λ to be ${\lambda }_1<{\lambda }_2<\cdots <{\lambda }_M$ for ${\lambda }_1=0$ and ${\lambda }_M={\lambda }_{\text{max}}$
2. while${\Vert {\Theta }^j\Vert }_{1,\text{off}}\ne 0$ do
		${\Sigma }^j({\lambda }_j)={(1+\mu )}^{-1}\left[\mu \{{\Theta }^{j-1}({\lambda }_{j-1})-{\Lambda }^{j-1}({\lambda }_{j-1})\}+{\widehat{\Sigma }}_n\right]$
		${\Theta }^j({\lambda }_j)={\left[S\{{\Sigma }^j({\lambda }_j)+{\Lambda }^{j-1}({\lambda }_{j-1}),{\lambda }_j/\mu \}\right]}_{+}$
		${\Lambda }^j({\lambda }_j)={\Lambda }^{j-1}({\lambda }_{j-1})+{\Sigma }^j({\lambda }_j)-{\Theta }^j({\lambda }_j)$
		j=j+1
	end while
3. Output $\{{\Theta }^j({\lambda }_j),j=1,\cdots ,M\}$ as the regularization path.

2 Numerical Studies

We illustrate the performance of our proposals through simulations. Write $\Sigma ={({\sigma }_{i,j})}_{p\times p}$. We set the sample size n=50 and vary the dimension p=100, 200, 500 and 1 000. We consider the following two models which were once used in existing literature:

1) Model (I): ${\sigma }_{i,j}={(1-\left|i-j\right|/10)}_{+}$.

2) Model (II): We partition the index set, $\{1,\cdots ,p\}$, into $K=p/20$ non-overlapping subsets of equal size, and denote $I_k$ the index set, $k=1,\cdots ,K$. Let$\begin{array}{l}{\sigma }_{i,j}=0.6I(i=j)+0.4{\displaystyle \sum _{k=1}^{k}I(i\in I_k,j\in I_k)}\\ +0.4{\displaystyle \sum _{k=1}^{K-1}\{I(i=I_k,j\in I_{k+1})+I(i\in I_{k+1},j=I_k)\}}\end{array}$Specifically, Model (I) was used by Cai et al ^[2] and Model (II) was used by Rothman et al ^[5].

Figure 1 shows the sparsity levels. In Fig. 1 (a) and (c) we report the sparsity levels, measured by the number of nonzero components of $\widehat{\Theta }$ of the ADMM algorithm with warm starts (Algorithm 1) for a fixed $\lambda$ when p=1 000. The ADMM algorithm with warm starts spends a large proportion of the computational time on squeezing $\Sigma$ towards $\Theta$ to satisfy the primal feasibility, which does not converge until 500 iterations in Model (I) and 280 iterations in Model (II). In Fig. 1 (b) and (d), we present the ADMM algorithmic regularity paths obtained by Algorithm 2. In both models, the sparsity levels of the ADMM algorithmic regularity paths increase sharply within only a few iterations as the regularity parameter λ increases, and achieve a relatively smooth transition that explores the range of possible sparse estimates at a fine resolution, and requires substantially less computer time for Algorithm 2 to converge. We also remark here that there are some fluctuations in all four plots of Fig. 1, main because we apply the ${(B)}_{+}$ operator to ensure the solution to the $\Theta$-subpr- oblem, denoted $\Theta$, to be positive-definite.

Fig.1 Sparsity levels measured by the number of nonzero entries of $\widehat{\Theta }$ (a) and (c) describe the sparsity levels of the $\Theta$-subproblem iterates of the ADMM algorithm, fit for a fixed $\lambda$; (b) and (d) describe the sparsity levels of the $\Theta$-subproblem over the iterates of our proposed ADMM algorithmic regularization paths. (a) and (b) are for Model (I), and (c) and (d) are for Model (II)

In Figs. 2 and 3, we plot the ADMM regularization paths with cool starts in (a), the ADMM regularization paths with warm starts in (b), the ADMM algorithmic regularization paths with a relatively large step size in (c) and a tiny step size in (d), for Models (I) and (II), respectively. In both figures, the ADMM algorithm with warm starts is almost equivalent to the ADMM algorithm with cool starts because the regularization paths exhibit almost identical patterns. The ADMM algorithmic regularization paths with a tiny step size also well approximate the ADMM regularization paths, however, those with a relatively large step-size yields a sequence of sparse models that distinguishes obviously from the sparsity patterns of ADMM algorithm with warm starts. This is mainly because a large change in regularization levels of each step makes that the sparsity levels of the $\Theta$-subproblem after the one-step approximation are not equivalent to that of the solution to (2).

Fig.2 Simulation results for Model (I) (a) The ADMM regularization paths with cool starts; (b) The ADMM regularization paths with warm starts; (c) The ADMM algorithmic regularization paths with a relatively large step size; and (d) The ADMM algorithmic regularization paths with a tiny step size. The blue lines denote the false positive variables and the red lines denote true positive variables

Fig.3 Simulation results for Model (II) (a) The ADMM regularization paths with cool starts; (b) The ADMM regularization paths with warm starts; (c) The ADMM algorithmic regularization paths with a relatively large step size; and (d) The ADMM algorithmic regularization paths with a tiny step size. The blue lines denote the false positive variables and the red lines denote true positive variables

We further compare our algorithms for computing the regularization paths in terms of computational time based on 100 repetitions and each of size n=50. The simulations are entirely coded in Matlab and carried out on an AMD 3.30 GHz processor. The results are summarized in Table 1. Notice that, our proposed ADMM algorithmic regularization paths are at least two times faster than the ADMM with warm starts, while the latter is far superior to the state-of-art ADMM with cool starts.

3 Conclusion

In this paper, we propose two efficient algorithms to quickly derive the regularization paths for estimating the sparse and large scale positive-definite covariance matrices. Instead of solving the optimization problems over a grid of regularization parameters, which is required by the conventional regularization methods, we propose a one-step approximation to the ADMM algorithm with warm starts to quickly approximate the regularization paths. These new algorithms are easy to implement because no iteration is required. These algorithms both estimate the covariance matrices over a lot of regularization parameters, but ADMM algorithmic regularization paths (Algorithm 2) can quickly outline a sequence of sparse solutions at a fine resolution, and ADMM algorithmic regularization paths are at least two times fast than the ADMM with warm starts.

References

All Tables

All Figures

Fig.1 Sparsity levels measured by the number of nonzero entries of $\widehat{\Theta }$ (a) and (c) describe the sparsity levels of the $\Theta$-subproblem iterates of the ADMM algorithm, fit for a fixed $\lambda$; (b) and (d) describe the sparsity levels of the $\Theta$-subproblem over the iterates of our proposed ADMM algorithmic regularization paths. (a) and (b) are for Model (I), and (c) and (d) are for Model (II)

In the text

	Fig.2 Simulation results for Model (I) (a) The ADMM regularization paths with cool starts; (b) The ADMM regularization paths with warm starts; (c) The ADMM algorithmic regularization paths with a relatively large step size; and (d) The ADMM algorithmic regularization paths with a tiny step size. The blue lines denote the false positive variables and the red lines denote true positive variables
In the text

	Fig.3 Simulation results for Model (II) (a) The ADMM regularization paths with cool starts; (b) The ADMM regularization paths with warm starts; (c) The ADMM algorithmic regularization paths with a relatively large step size; and (d) The ADMM algorithmic regularization paths with a tiny step size. The blue lines denote the false positive variables and the red lines denote true positive variables
In the text