IEOR PhD student Salar Fattahi has been chosen as one of five finalists for the prestigious American Control Conference Best Student Paper Award for his paper titled “Closed-Form Solution and Sparsity Path for Inverse Covariance Estimation Problem.” The research was developed under the supervision of Dr. Somayeh Sojoudi, assistant professor in residence in the Departments of Electrical Engineering & Computer Sciences and Mechanical Engineering at UC Berkeley.
In this paper, we study the problem of determining a sparsity graph that describes the conditional dependence between different elements of a multivariate random distribution, using a limited number of samples. Graphical Lasso is one of the popular methods for addressing this problem, which imposes a soft penalty in the form of an l1 regularization term in its objective function. The first goal of this work is to study the behavior of the optimal solution of Graphical Lasso as a function of its regularization coefficient. We show that if the number of samples is not too small compared to the number of parameters, the sparsity pattern of the optimal solution of Graphical Lasso changes gradually in terms of the regularization coefficient. More precisely, it is proved that each change in the sparsity pattern corresponds to the addition or removal of a single edge of the graph, under generic conditions. We also prove that Graphical Lasso as a conic optimization problem has a closed-form solution if an acyclic graph is sought. This explicit formula also serves as an approximate solution for non-acyclic sparse graphs. The results are demonstrated on synthetic data and electrical systems.
The 2018 American Control Conference will take place July 27-29 in Milwaukee, WI.