Fast and accurate optimization on the orthogonal manifold without retraction
This addresses computational bottlenecks in optimization on orthogonal manifolds, particularly for high-dimensional matrices, offering a more efficient alternative to existing methods.
The paper tackles the problem of minimizing functions over orthogonal matrices by introducing the landing algorithm, which avoids expensive retraction operations like matrix inversion or exponentiation, resulting in faster and more numerically stable performance on large-scale and deep learning tasks.
We consider the problem of minimizing a function over the manifold of orthogonal matrices. The majority of algorithms for this problem compute a direction in the tangent space, and then use a retraction to move in that direction while staying on the manifold. Unfortunately, the numerical computation of retractions on the orthogonal manifold always involves some expensive linear algebra operation, such as matrix inversion, exponential or square-root. These operations quickly become expensive as the dimension of the matrices grows. To bypass this limitation, we propose the landing algorithm which does not use retractions. The algorithm is not constrained to stay on the manifold but its evolution is driven by a potential energy which progressively attracts it towards the manifold. One iteration of the landing algorithm only involves matrix multiplications, which makes it cheap compared to its retraction counterparts. We provide an analysis of the convergence of the algorithm, and demonstrate its promises on large-scale and deep learning problems, where it is faster and less prone to numerical errors than retraction-based methods.