Rank-Constrained Optimization

This dissertation considers optimization problems on a Riemannian matrix manifold ℳ⊆ℝ[superscript m x n] with an additional rank inequality constraint. A novel technique for building new rank-related geometric objects from known Riemannian objects is developed and used as the basis for new approach to adjusting matrix rank during the optimization process. The new algorithms combine the dynamic update of matrix rank with state-of-the-art rapidly converging and well-understood Riemannian optimization algorithms. A rigorous convergence analysis for the new methods addresses the tradeoffs involved in achieving computationally efficient and effective optimization. Conditions that ensure the ranks of all iterates become fixed eventually are given. This guarantees the desirable consequence that the new dynamic-rank algorithms maintain the convergence behavior of the fixed rank Riemannian optimization algorithm used as the main computational primitive. The weighted low-rank matrix approximation problem and the low-rank approximation approach to the problem of quantifying the similarity of two graphs are used to empirically evaluate and compare the performance of the new algorithms with that of existing methods. The experimental results demonstrate the significant advantages of the new algorithms and, in particular, the importance of the new rank-related geometric objects in efficiently determining a suitable rank for the minimizer.