Time-Series Analysis on Multiperiodic Conditional Correlation
by Sparse Covariance Selection and Its Computational Method
Tokyo Institute of Technology
Tokyo Institute of Technology
1Introduction

In this research, we consider optimization problems
where the objective is a negative Gaussian log-likelihood
with two penalty terms. This minimization problem estimates the sparse inverse of its input covariance matrix;
sparse covariance selection [Dem72]. The first penaltyof `1 -norm regularization term ensures a sparse solution, i.e., one with few nonzero entries, while the second penalty enhances block partitions in the parameter
space. One of the well-known application of this estimation problem is Markowitz’s portfolio selection [Mar52],
where the inverse of covariance matrix is needed as its
input. We propose to apply (a) Alternating Direction
Method of Multipliers (ADMM) algorithm [Boy+11]and (b) Quadratic Approximation Method [Hsi+11] forsolving the problem of sparse covariance selection.

2Problem Setup

T p rows

Given a set of i.i.d. data of Yt = {y1,t , · · · , yn,t }, t ∈{1, · · · , T } drawn from p-variate Gaussian distributionof N (y; µ, Σ). Let the empirical covariance matrix between Yi and Yj is given by1X
Sij :=(yk,i − µ̂i )(yl,j − µ̂j )> ,nP k,lwhere µ̂i = n1 k yk,i . Consider a stationary-time process such that the multiperiodic inverse covariance matrix X can be expressed as
X
X12
X13· · · X1,T  
11X
X·· · X2,T  
 X>
2223

12

 >
X>
X33
· · · X3,T  X1323X=.
..
..
..   ..
..
 .
.
.
.
. X>
1,T

X>
2,T|

X>
3,T
{z···XT,T}

T p columns

We assume that X is a stationary time-process, suchthat Xi,i+h = Xj,j+h for all i, j. Given some regularization penalty λ1 > 0, λ2 > 0, the `1 and `2 regularized Gaussian MLE for the inverse covariance matrix
can be estimated by solving the following regularized
log-determinant program:XX
argmin − ln det X +trace S>
kXij k1
ij Xij + λ1
X0+ λ2i,jX

X

strictly convex, while the second part h(X) is convex
but non-differentiable.
Then, we can write Equation (2.1) into the following
optimization problem.
minimizeg(X) + h(Z)(3.1)
subject to X̃ = Z̃
whereXX

kZ1 k1 + λ2
kZ2 k2F ,i,jhi>i>X̃ = (X0 )> , (DX0 )> , (HX0 )>, Z̃ = (Z1 )> , (Z2 )> , (0)>h(Z̃) = λ1

for appropriate matrices D and H that represent setof time difference matrices and set of stationary timedifference matrices, respectively. The augmented Lagrangian of Equation (3.1) isLρ (X̃, Z̃, Y) = g(X) + h(Z̃) + (ρ/2) X̃ − Z̃ +Y
ρTherefore, the iteration of ADMM is given as:2.
F2 X̃-update:Y (k)ρX̃ − Z̃(k) +X̃(k) := argmin g(X) +,2ρX̃
FZ̃-update:
2 
Y (k)
ρ,X̃(k+1) − Z̃ +Z̃(k) := argmin h(Z̃) +2
ρFỸ-update: Z̃
Y (k+1) :=Y (k) + ρ X̃(k+1) − Z̃(k+1) .

(b) Quadratic Approximation
The summary of the algorithm is given as follows:
Input: Empirical covariance matrices S, time difference T,scalar values of λ1 , λ2 , inner stopping tolerance Output: Minimizer X of f (X).
1: for k = 0, 1, · · · do−12:Compute W(t) = X(t).
3:Form the second order approximation of f (X(t) +∆).
4:
Partition the variables into free and fixed sets basedon the gradient.
5:
Use coordinate descent to find the Newton direction
D(t) over the free variable set.
6:
Use an Armijo-rule based step-size selection to get α.
7:Update X(t+1) = X(t) + αD(t) .
8: end for

4Conclusion

Both algorithms show consistency on the optimal values and as we can see from the following table that
Quadratic Approximation method runs much fastercompared to the ADMM algorithm.
T=: argminf (X)1
2
3

Xij 0Xi,i+h = Xj,j+h , ∀i, j.

i,jhi,jkXij − Xkl k22i,j k>i,l>j

subject toMichael LieSuzuki Taiji(2.1)

n = 20(a)(b)
179.650.75
418.251.9
876.94
5.71

n = 30(a)
(b)
283
2.11
739.434.22
1725.67
12.84

Table 1: Runtime (in seconds) for both algorithms.

3

Proposed Algorithm

References(a) ADMM algorithm
Firstly, the objective function f comprises of two parts,f (X) ≡ g(X) + h(X), whereg(X) = − ln det X +X
trace S>ij Xij ,i,jh(X) = λ1

Xi,jkXij k1 + λ2

X

X

[Boy+11]

S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein. “Distributed optimization and statistical learning via the alternating direction method of multipliers.” In: Foundations and Trends
in Machine Learning 3.1 (2011), pp. 1–122.

[Dem72]A. P. Dempster. “Covariance selection.” In: Biometrics (1972),
pp. 157–175.

[Hsi+11]

C.-J. Hsieh, I. S. Dhillon, P. K. Ravikumar, and M. A. Sustik.
“Sparse inverse covariance matrix estimation using quadraticapproximation.” In: Advances in Neural Information Processing Systems. 2011, pp. 2330–2338.

[Mar52]H. Markowitz. “Portfolio selection.” In: The Journal of Finance
7.1 (1952), pp. 77–91.

kXij − Xkl k2F .

i,j k>i,l>j

The first component g(X) is twice differentiable and