The Geometry of Algorithms with Orthogonality Constraints

By Alan Edelman, T. Arias, Steven Thomas Smith. 1998

In this paper we develop new Newton and conjugate gradient algorithms on the Grassmann and Stiefel manifolds. These manifolds represent the constraints that arise in such areas as the symmetric eigenvalue problem, nonlinear eigenvalue problems, electronic structures computations, and signal processing. In addition to the new algorithms, we show how the geometrical framework gives penetrating new insights allowing us to create, understand, and compare algorithms. The theory proposed here provides a taxonomy for numerical linear algebra algorithms that provide a top level mathematical view of previously unrelated algorithms. It is our hope that developers of new algorithms and perturbation theories will benefit from the theory, methods, and examples in this paper.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Domain Adaptation with Conditional Transferable Components (2016, methodology): “Therefore, we ﬁnd W by the conjugate gradient algorithm on the Grassmann manifold , which is an efﬁcient approach by exploiting the geometric properties of orthogonality and rotation invariance (Edelman et al., 1999).”
Discriminative virtual views for cross-view action recognition (2012, positive): “There are various ways to establish such connections between the two matrices, among which one possibility is to look into the space of all D × d matrices and make use of its geometry [24].”
Global rates of convergence for nonconvex optimization on manifolds (2016, unknown): “where M is a (smooth) Riemannian manifold and f : M→ R is a (sufficiently smooth) cost function (Gabay, 1982; Smith, 1994; Edelman et al., 1998; Absil et al., 2008).”
Intrinsic Statistics on Riemannian Manifolds: Basic Tools for Geometric Measurements (2006, methodology): “On the applied mathematics and computer science side, people get interested in computing and optimizing in specific manifolds, like rotations and rigid body transformations [4, 31–34], Stiefel and Grassmann manifolds [35], etc.”
Riemannian Approaches in Brain-Computer Interfaces: A Review (2017, unknown): “The reader interested by the details about optimization can refer to [24] and to [29] for the special case of Stiefel and Grassman manifolds.”
Adaptive blind signal and image processing (2002, unknown): “The natural Riemannian gradient in the Stiefel manifold was calculated by Amari [34] as (see also Edelman, Arias and Smith [418]) ∇̃ρ(y,W) = ∇ρ(y,W)−W [∇ρ(y,W)] W.”
A feasible method for optimization with orthogonality constraints (2012, methodology): “The basic analysis of this manifold can be found, for example, in [18].”
Adaptive Method of Realizing Natural Gradient Learning for Multilayer Perceptrons (2000, background): “(cid:181) / in the Riemannian space, and it suggests the natural gradient descent algorithm of the form (2.9) (Amari, 1998; Edelman, Arias, & Smith, 1998).”
Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Lojasiewicz Inequality (2008, background): “Matrix theory provides a long list of semialgebraic objects (see [36]): positive semidefinite matrices, Stiefel manifolds (spheres, orthogonal group; see e.g. [29]), constant rank matrices...”
Kernel Methods for Measuring Independence (2005, methodology): “This yields 1max =G−WG*W, where the proof is provided by Edelman et al. (1998); Hyvärinen and Plumbley (2002).”