Fast and accurate optimization on the orthogonal manifold without retraction

• URL: http://arxiv.org/abs/2102.07432v1
• Date: Mon, 15 Feb 2021 10:12:05 GMT
• Title: Fast and accurate optimization on the orthogonal manifold without retraction
• Abstract summary: We propose a landing algorithm which does not involve retractions. The algorithm is not constrained to stay on the manifold but its evolution is driven by a potential energy. One of the landing algorithm only involves matrix multiplications, which makes it cheap compared to its retraction counterparts.
• Score: 7.887285735878797
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 or matrix 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 involve 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 problems, where it is faster and less prone to numerical errors than retraction-based methods.

Related papers

• The Structural Complexity of Matrix-Vector Multiplication [0.10485739694839669]
  We show that the matrix-vector multiplication problem can be solved with $tildeO(n2)$ preprocessing and $tilde O(n2-1/d)$ query time. Our results yield the first non-trivial upper bounds for many applications.
  arXiv  Detail & Related papers  (2025-02-28T17:11:36Z)
• Riemannian coordinate descent algorithms on matrix manifolds [12.05722932030768]
  We provide a general framework for developing computationally efficient coordinate descent (CD) algorithms on matrix manifold. We propose CD algorithms for various manifold such as Stiefel, Grassmann, (generalized) hyperbolic, symplectic, and symmetric positive (semi)definite. We analyze their convergence and complexity, and empirically illustrate their efficacy in several applications.
  arXiv  Detail & Related papers  (2024-06-04T11:37:11Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• Learning the Positions in CountSketch [49.57951567374372]
  We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem. In this work, we propose the first learning-based algorithms that also optimize the locations of the non-zero entries.
  arXiv  Detail & Related papers  (2023-06-11T07:28:35Z)
• Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms for Optimization under Orthogonality Constraints [9.301728976515255]
  This article provides new practical and theoretical developments for the landing algorithm. First, the method is extended to the Stiefel manifold. We also consider variance reduction algorithms when the cost function is an average of many functions.
  arXiv  Detail & Related papers  (2023-03-29T07:36:54Z)
• Orthogonal Directions Constrained Gradient Method: from non-linear equality constraints to Stiefel manifold [16.099883128428054]
  We propose a novel algorithm, the Orthogonal Directions Constrained Method (ODCGM) ODCGM only requires computing a projection onto a vector space. We show that ODCGM exhibits the near-optimal oracle complexities.
  arXiv  Detail & Related papers  (2023-03-16T12:25:53Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  We introduce a new inference scheme that avoids explicit construction of the covariance matrix. Our approach couples a little-known diagonal estimation result from numerical linear algebra with the conjugate gradient algorithm. On several simulations, our method scales better than existing approaches in computation time and memory.
  arXiv  Detail & Related papers  (2022-02-25T16:35:26Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  We present dimensionality reduction methods for non-PSD and square-roots" matrices. We show how these techniques can be used for multiple downstream tasks.
  arXiv  Detail & Related papers  (2021-06-16T04:07:48Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  In many applications, we need algorithms which can align partially overlapping point sets are invariant to the corresponding corresponding RPM algorithm. We first show that the objective is a cubic bound function. We then utilize the convex envelopes of trilinear and bilinear monomial transformations to derive its lower bound. We next develop a branch-and-bound (BnB) algorithm which only branches over the transformation variables and runs efficiently.
  arXiv  Detail & Related papers  (2021-01-19T04:24:23Z)
• Adaptive and Momentum Methods on Manifolds Through Trivializations [6.85316573653194]
  We introduce a framework to generalize adaptive and momentum methods to arbitrary manifold. For every differentiable manifold, there exists a radially convex open set that covers almost all the manifold. We show how to extend these methods to the context of descent methods with a retraction.
  arXiv  Detail & Related papers  (2020-10-09T14:58:09Z)
• Dynamical perturbation theory for eigenvalue problems [0.0]
  We show that our algorithm outperforms the usual Rayleigh-Schr"odinger expansion on three counts. Our scheme also scales better with the size of the matrix than general-purpose eigenvalue routines.
  arXiv  Detail & Related papers  (2020-02-28T17:13:22Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  We study the performance of iterative sketching for least-squares problems. We show that the convergence rate for Haar and randomized Hadamard matrices are identical, andally improve upon random projections. These techniques may be applied to other algorithms that employ randomized dimension reduction.
  arXiv  Detail & Related papers  (2020-02-03T16:17:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.