Covariance Matrix Estimation via
Convex Optimization: Theory, Methods, Algorithms and Applications

In this talk, I will
focus on estimating covariance and inverse covariance matrices in the high
dimensional (large p, small n) setting.

Relational data have
gained much attention recently.
Social network, gene network, computer network and voting blocks are
among many motivating examples. We
take a graphical model approach, and we aim to estimate an s-sparse inverse
covariance matrix based on a sample of n iid p-variate random variables. We propose a constrained L1
minimization method, and the resulting estimator enjoys a number of desirable
properties. It is shown that the convergence
rate is s(log p/n)^{1/2} under the spectral norm, for either
exponential-type or polynomial-type distributions. In addition, graphical model selection is presented. The procedure can be easily implemented
by linear programming. The numerical merits are illustrated using simulated
data and a breast cancer data set.
In particular, it is applied to classification of cancer patients.

In the second part of
the talk, I will consider the problem of estimating the covariance matrix. Factor models and random effect models
have been shown to provide good approximations in modeling multivariate
observations in many settings.
These models motivate us to consider a general framework of covariance
structures, which contains sparse and low rank components. We propose a convex optimization
criterion, and the resulting estimator is shown to recover exactly the rank and
support of the low rank and sparse components respectively. The convergence rates are also
presented. To solve the
optimization problem, we propose an iterative algorithm with low memory cost,
and it converges to the optimal with order K^{-2} for any finite K
iterations. Numerical performance
is demonstrated using simulated data and stock portfolio selection on S&P
100.