Colloquium Mathematics - Prof. M. Bollhoefer

Title: Large-Scale Sparse Inverse Covariance Matrix Estimation

Abstract:
The estimation of large sparse inverse covariance matrices is an

ubiquitous statistical problem in many application areas such as

mathematical finance or geology or many others. Numerical approaches

typically rely on the maximum likelihood estimation or its negative

log-likelihood function. When the Gaussian mean random field is

expected to be sparse, regularization techniques which add a sparsity

prior have become popular to address this issue. Recently a quadratic

approximate inverse covariance method (QUIC) [1] has been proposed.

The hallmark of this method is its superlinear to quadratic convergence

which makes this algorithm to be among the most competitive methods.

In this talk we present a sparse version (SQUIC) [2] of this method

and we will demonstrate that using advanced sparse matrix technology

the sparse version of QUIC is easily able to deal with problems of

size one million within a few minutes on modern multicore computers.

[1] C.J. Hsieh, M.A. Sustik, I.S. Dhillon, and P.K. Ravikumar.

  Sparse inverse covariance matrix estimation using quadratic approximation,

  in Advances in Neural Information Processing Systems, J. Shawe-Taylor,

  R. Zemel, P. Bartlett, F. Pereira, and K. Weinberger, eds., vol. 24, Neural

  Information Processing Systems Foundation, 2011, pp. 2330-2338.

[2] M. Bollhoefer, A. Eftekhari, S. Scheidegger, and O. Schenk. Large-Scale

  Sparse Inverse Covariance Matrix Estimation. SIAM J. Sci. Comput., to appear

This is joined work with O.Schenk, A. Eftekhari (USI Lugano) and S. Scheidegger (EPFL Lausanne).