The Bigraphical Lasso


Alfredo Kalaitzis, John Lafferty, Neil Lawrence, Shuheng Zhou ;
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(3):1229-1237, 2013.


The i.i.d. assumption in machine learning is endemic, but often flawed. Complex data sets exhibit partial correlations between both instances and features. A model specifying both types of correlation can have a number of parameters that scales quadratically with the number of features and data points. We introduce the bigraphical lasso, an estimator for precision matrices of matrix-normals based on the Cartesian product of graphs. A prominent product in spectral graph theory, this structure has appealing properties for regression, enhanced sparsity and interpretability. To deal with the parameter explosion we introduce L1 penalties and fit the model through a flip-flop algorithm that results in a linear number of lasso regressions.

Related Material