the 2014 International Symposium on Nonlinear Theory and its Applications
Line-search methods and rank increase on low-rank matrix varieties
Andre Uschmajew, Bart Vandereycken,
PDF download (229.5KB)
Based on an explicit characterization of tangent cones one can devise line-search methods to minimize functions on the variety of matrices with rank bounded by some fixed value, thereby extending the Riemannian optimization techniques from the smooth manifold of fixed rank to its closure. This allows for a rank-adaptive optimization strategy where locally optimal solutions of some smaller rank are used as a starting point for an improved approximation with a larger rank. Contrary to optimization on the smooth manifold of fixed-rank matrices, no special treatment is needed for rankdeficient matrices when optimizing on the variety. Hence, this gives a sound theoretical framework for the analysis of rank-increasing greedy algorithms, which can be more effcient than starting the calculations with large but fixed rank.