Media.Player

A Method for Computing the Sparse Inverse of the Covariance Matrix (Technion)

Summary

The Sparse Inverse Covariance Estimation problem arises in many statistical applications in Machine Learning and Signal Processing. In this problem, the inverse of the covariance matrix of a multivariate normal distribution is estimated, assuming that it is sparse. An I-1 regularized log-determinant optimization problem is solved to compute such matrices. There are several existing solution methods for this problem, however, due to some technical requirements of the optimization algorithms, most of these methods are unable to handle large-scale instances of this problem, leading to memory limitations. Only one known method is able to handle problems in such scales. In this work, we develop a new block-coordinate descent approach for solving the problem for large-scale data sets. Our method treats the matrix block-by-block using quadratic approximations (Newton’s method), and we show that this approach has advantages: our initial results show that our methods requires less iterations to converge, comparing to BIGQUIC (the cost of the iterations for both methods is comparable). Because we treat the problem block-by-block, we introduce less fill-in to the sparse matrix at the initial stages (have less non-zeros), and our block structure enables us to apply a linesearch procedure very cheaply. This procedure is very costly for BIGQUIC.

Technology Benefits

· Applicable to large data sets (millions of variables).

· Converges faster than the existing method and can be parallelized more efficiently

· Cost-efficient

· Requires less memory

· Size of small sets are chosen to optimize CPU performance

Technology Application

· Determining correlations between signals/images or their representation

· Finding which stocks are correlated in time

· Understanding which areas of the brain are correlated to or influenced by states of mind

· Analysis of Gene expressions

· Automatically recommending items to web-users

· Finding groups of people that have similar behavior on social networks

ID No.

COM-1589

Country/Region

Israel