View Abstract
Abstract: Positive semi-definite fixed rank constraint arises in certain machine learning and data science applications, e.g., it is also used for approximating the PSD constraint. For optimization under such constraints, we study and compare three methodologies for minimizing f(X) with X being a Hermitian PSD fixed rank matrix. The first approach is the simplest factor-based Burer-Monteiro method, in which a PSD fixed rank matrix X is replaced by its low-rank decomposition YY^* thus an unconstrained minimization of f(YY^*) can be solved instead. The second approach is to regard the set of Hermitian PSD fixed rank matrices as an embedded manifold in the Euclidean space and consider the Riemannian optimization over the embedded manifold. The third approach is to regard it as a quotient manifold and consider the Riemannian optimization over the quotient manifold. For simplicity, we only consider the nonlinear conjugate gradient (CG) algorithm, which is an efficient algorithm in these methods. We show that CG in the first two methodologies is equivalent to CG on the quotient manifold with suitably chosen metrics, retractions, and vector transports. In particular, the simple Bure-Monteiro approach corresponds to the Bures-Wasserstein metric. We also analyze the condition number of the Riemannian Hessian under these different metrics. The difference in the condition number of the Riemannian Hessian under different metrics is consistent with the difference in the numerical performance of three methodologies for problems including matrix completion, phase retrieval, and interferometry recovery. This part is based on joint work with Shixin Zheng at Purdue, Wen Huang at Xiamen University and Bart Vandereycken at University of Geneva.Â
It is also natural to consider sampling schemes under the same constraints. For the manifold of positive semi-definite matrices of fixed rank, we construct two sampling schemes on the manifold, which can generate samples from the Gibbs distribution. The two sampling schemes correspond to the Euler-Maruyama scheme for the Stochastic Differential Equation on the manifold under the embedded geometry and the Bures-Wasserstein metric. This can be regarded as Monte Carlo sampling on the manifold. There are many potential applications. For integrating a nice function on the manifold, one can simply take the Arithmetic mean of the samples, thus it would be a very simple quadrature rule on the manifold since all geometric information are encoded in the samples. The sampling schemes are constructed by adding white noise and a proper geometric correction term to the gradient descent algorithms on the manifold, thus the computational complexity of each iteration is comparable to the Riemannian gradient decent methods. Preliminary numerical results will be shown. This is based on an ongoing joint work with Tianmin Yu and Govind Menon at Brown University, Jianfeng Lu at Duke University, and Shixin Zheng at Purdue University.Â