Low Complexity Riemannian Coordinate-Descent over Symmetric Positive Definite Matrices

Abstract

Many signal processing and machine learning applications are framed as constrained optimization problems with positive definite constraints. Important examples include kernel matrix learning, covariance estimation of Gaussian distributions, maximum likelihood parameter estimation of elliptically contoured distributions, parameter estimation in Gaussian mixture models and matrix square root. In this work, utilizing Riemannian geometric principles, we propose coordinate-descent algorithms on the Riemannian manifold of symmetric positive definite (SPD) matrices. We further identify a broad class of functions encompassing all the aforementioned applications. Finally, we demonstrate that for this class of functions, the proposed algorithm achieves per-iteration complexities of O(n)—an order of magnitude lower than the O(n3) or higher complexities of full update algorithms like Riemannian gradient-descent and interior-point methods. Interestingly, the proposed algorithm is significantly faster than the Burer-Monteiro factorization based coordinate descent algorithm, which has a per-iteration complexity of O(n2), as confirmed through simulations on the log-det minimization problem.