ORIGINAL

Abstract

Many optimization problems over matrices arising in applications are believed to have low-rank solutions. We may be able to efficiently solve such problems by optimizing only over low-rank matrices. If the rank of the solution is known, we can optimize over the set of matrices having precisely that rank, which is a smooth manifold. If we only have an upper bound on the rank, we can optimize over the set of matrices whose rank is appropriately bounded, which is an algebraic variety. While there exist several algorithms for optimization over smooth manifolds possessing good theoretical guarantees, no such theory exists for optimization over (singular) varieties.

We consider the problem of optimizing over varieties in general, and over bounded-rank matrices in particular. We show that in general optimization over varieties is poorly behaved near singularities. Therefore, we consider parametrizing the variety in such a way that the parameter space, which we call a "lift" because it typically lies in a higher dimensional space, is a smooth manifold. Unfortunately, we show that such lifts can also be poorly behaved --- a point that appears to be a stationary point or even a local minimum on the lifted space may not be stationary on the variety. We show that the existence of these 'false stationary points' on lifts is unavoidable for a large class of algebraic varieties.

Specializing to the variety of bounded-rank matrices, we study three lifts and show that the above pathologies are observed in all three of them. Nevertheless, we show that second order critical points on these lifts are guaranteed to correspond to first order critical points on the variety. Moreover, if we add a natural regularization term to the cost function, we can guarantee that any stationary point of the regularized cost is a local minimum on the lift if and only if it corresponds to a local minimum on the variety. Using this lift and associated regularization scheme, we give an algorithm that converges to a stationary point on the variety of bounded-rank, which is a local minimum on the lift if and only if it corresponds to a local minimum on the variety.

We also discuss difficulties encountered when directly optimizing over the variety of bounded-rank matrices. We show that a natural extension of gradient descent to the variety may fail to converge to a stationary point. We then discuss a potential fix involving projection to the singular locus. To analyze this modified algorithm, we also explicitly bound the difference between the metric projection retraction to the bounded-rank matrix variety and its first-order Taylor expansion. Also, we show that the algorithm does converge to a stationary point for varieties which have finitely many singularities. Unfortunately, for general varieties our analysis is unsatisfactory.

Finally, we state some of the open questions and future directions suggested by this work.