The Geometry of Algorithms with Orthogonality Constraints

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.

• Publication year

  1998

• Venue

  SIAM Journal on Matrix Analysis and Applications

• Publication date

  1998-06-19

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1137/S0895479895290954arXiv physics/9806030
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Practical optimization

  2019cited by this paper
• Subspace tracking with full rank updates

  1997cited by this paper
• On conjugate gradient-like methods for eigen-like problems

  1996cited by this paper
• A Jacobi-Davidson Iteration Method for Linear Eigenvalue Problems

  1996cited by this paper
• Linear and nonlinear conjugate gradient methods for adaptive processing

  1996cited by this paper
• Lectures on finite precision computations

  1996cited by this paper
• Conjugate gradient eigenstructure tracking for adaptive spectral estimation

  1995influential reference
• Space-time clutter covariance matrix computation and interference subspace tracking

  1995cited by this paper
• Sequential Quadratic Programming

  1995cited by this paper
• Second Derivatives for Optimizing Eigenvalues of Symmetric Matrices

  1995cited by this paper
• Adaptive estimation of eigensubspace

  1995influential reference
• Numerical Linear Algebra and Applications

  1995influential reference
• The riemannian singular value decomposition

  1995cited by this paper
• University Utrecht a Generalized Jacobi-davidson Iteration Method for Linear Eigenvalue Problems a Generalized Jacobi-davidson Iteration Method for Linear Eigenvalue Problems

  1994cited by this paper
• Riemannian Geometry: A Modern Introduction

  1994cited by this paper
• Differential Geometry I

  1994cited by this paper
• Fast Estimation of Principal Eigenspace Using Lanczos Algorithm

  1994influential reference
• The Davidson Method

  1994cited by this paper
• Efficient linear scaling algorithm for tight-binding molecular dynamics.

  1994cited by this paper
• Space-time adaptive processing for airborne radar

  1994influential reference
• The biographical dictionary of scientists

  1994cited by this paper
• Ab initio theory of dislocation interactions: From close-range spontaneous annihilation to the long-range continuum limit.

  1994cited by this paper
• Adaptive eigendecomposition of data covariance matrices based on first-order perturbations

  1994cited by this paper
• Fast subspace decomposition

  1994cited by this paper
• Large Dense Numerical Linear Algebra in 1993: the Parallel Computing Influence

  1993cited by this paper
• Ab initio molecular dynamics: Analytically continued energy functionals and insights into iterative solutions.

  1992cited by this paper
• A Singular Value Decomposition Updating Algorithm for Subspace Tracking

  1992cited by this paper
• Iterative minimization techniques for ab initio total energy calculations: molecular dynamics and co

  1992cited by this paper
• Ab initio theory of the Si(111)-(7 x 7) surface reconstruction: A challenge for massively parallel computation.

  1992cited by this paper
• An updating algorithm for subspace tracking

  1992cited by this paper
• Recursive updating the eigenvalue decomposition of a covariance matrix

  1991cited by this paper
• Dynamical Systems that Learn Subspaces

  1991influential reference
• Oxygen complexes in silicon.

  1991cited by this paper
• Tracking a few extreme singular values and vectors in signal processing

  1990influential reference
• Ab initio molecular-dynamics study of defects on the reconstructed Si(001) surface.

  1990cited by this paper
• Thermal expansion of c-Si via ab initio molecular dynamics.

  1990cited by this paper
• Solution of Schrödinger's equation for large systems.

  1989cited by this paper
• Calculation of the vacancy formation energy in aluminium

  1989cited by this paper
• A survey of conjugate gradient algorithms for solution of extreme eigen-problems of a symmetric matrix

  1989influential reference
• An adaptive nulling system for a narrow-band signal with a look-direction constraint utilizing the conjugate gradient method

  1989cited by this paper
• ESPRIT-estimation of signal parameters via rotational invariance techniques

  1989cited by this paper
• Adaptive eigensubspace algorithms for direction or frequency estimation and tracking

  1988influential reference
• An algorithm for subspace computation, with applications in signal processing

  1988cited by this paper
• Theory of hydrogen diffusion and reactions in crystalline silicon.

  1988cited by this paper
• High-order reconstructions of the Ge(100) surface.

  1988cited by this paper
• Gradient-Type Algorithms for Partial Singular Value Decomposition

  1987influential reference
• Trace Minimization Algorithm for the Generalized Eigenvalue Problem

  1987influential reference
• Adaptive spectral estimation by the conjugate gradient method

  1986influential reference
• The Biographical dictionary of scientists, Mathematicians

  1986cited by this paper
• Multiple emitter location and signal Parameter estimation

  1986cited by this paper
• Extreme eigenvalues of large sparse matrices by Rayleigh quotient and modified conjugate gradients

  1986cited by this paper
• Implementation of adaptive array algorithms

  1986cited by this paper
• Unified approach for molecular dynamics and density-functional theory.

  1985cited by this paper
• Real Symmetric Matrices

  1985cited by this paper
• Lanczos algorithms for large symmetric eigenvalue computations

  1985cited by this paper
• Simultaneous Newton’s Iteration for the Eigenproblem

  1984cited by this paper
• An iterative algorithm for locating the minimal eigenvector of a symmetric matrix

  1984influential reference
• Adaptive algorithms for estimating eigenvectors of correlation type matrices

  1984cited by this paper
• Semi-Riemannian Geometry With Applications to Relativity

  1983cited by this paper
• IMPROVING THE ACCURACY OF COMPUTED EIGENVALUES AND EIGENVECTORS

  1983cited by this paper
• Optimality of high resolution array processing using the eigensystem approach

  1983cited by this paper
• The Symmetric Eigenvalue Problem

  1981cited by this paper
• A comprehensive introduction to differential geometry

  1979cited by this paper
• The computation of Lagrange-multiplier estimates for constrained minimization

  1979cited by this paper
• Differential Geometry, Lie Groups, and Symmetric Spaces

  1978cited by this paper
• The simultaneous computation of a few of the algebraically largest and smallest eigenvalues of a large, sparse, symmetric matrix

  1978cited by this paper
• Adaptive data orthogonalization

  1978cited by this paper
• Algorithms for the regularization of ill-conditioned least squares problems

  1977cited by this paper
• Eigensystem Computation for Skew-Symmetric and a Class of Symmetric Matrices

  1976cited by this paper
• The iterative calculation of a few of the lowest eigenvalues and corresponding eigenvectors of large real-symmetric matrices

  1975cited by this paper
• An introduction to differentiable manifolds and Riemannian geometry

  1975cited by this paper
• Iterative Eigenvalue Algorithms for Large Symmetric Matrices

  1974cited by this paper
• Inhomogeneous Electron Gas

  1973cited by this paper
• Error and Perturbation Bounds for Subspaces Associated with Certain Eigenvalue Problems

  1973cited by this paper
• Optimal gradient minimization scheme for finite element eigenproblems

  1972cited by this paper
• Foundations of Differentiable Manifolds and Lie Groups

  1971cited by this paper
• The computational efficiency of a new minimization algorithm for eigenvalue analysis

  1971cited by this paper
• A Biographical Dictionary of Scientists

  1970cited by this paper
• Gradient methods for finite-element eigenproblems.

  1969cited by this paper
• LIE GROUPS AND SYMMETRIC SPACES.

  1968cited by this paper
• A Minimization Method for the Solution of the Eigenproblem Arising in Structural Dynamics

  1968cited by this paper
• Differential geometry of grassmann manifolds.

  1967cited by this paper
• New iterative methods for solution of the eigenproblem

  1966cited by this paper
• The algebraic eigenvalue problem

  1966cited by this paper
• Self-Consistent Equations Including Exchange and Correlation Effects

  1965influential reference
• Foundations of Differential Geometry

  1963influential reference
• Methods of conjugate gradients for solving linear systems

  1952cited by this paper
• Richtungsfelder und Fernparallelismus in n-dimensionalen Mannigfaltigkeiten

  1935cited by this paper

• Behavior-Controllable Stable Dynamics Models on Riemannian Configuration Manifolds

  2026cites this paper
• When model-form and parametric uncertainties matter: A unified stochastic representation for propagation and sensitivity analysis

  2026cites this paper
• An new polar factor retraction on the Stiefel manifold with closed-form inverse

  2026cites this paper
• Fundamental Tradeoff of Bistatic ISAC Under Gaussian Fading Channels at Finite Blocklength

  2026cites this paper
• Riemannian Momentum Tracking: Distributed Optimization with Momentum on Compact Submanifolds

  2026cites this paper
• Rate-Distortion Analysis of Compressed Query Delegation with Low-Rank Riemannian Updates

  2026cites this paper
• An Invitation to Higher-Order Riemannian Optimization: Optimal and Implementable Methods

  2026cites this paper
• Quantum circuit design from a retraction-based Riemannian optimization framework

  2026cites this paper
• Preconditioning Benefits of Spectral Orthogonalization in Muon

  2026cites this paper
• An orthogonal non-negative matrix factorization approach for respiratory rate estimation using a wireless stethoscope

  2026cites this paper
• TTD-Based Hybrid Beamforming for Multi-User Near-Field Communications: A Riemannian Optimization Approach

  2026cites this paper
• Scalable Preparation of Matrix Product States with Sequential and Brick Wall Quantum Circuits

  2026cites this paper
• OLion: Approaching the Hadamard Ideal by Intersecting Spectral and $\ell_{\infty}$ Implicit Biases

  2026cites this paper
• Distilling Lightweight Domain Experts from Large ML Models by Identifying Relevant Subspaces

  2026cites this paper
• Constrained dynamics for searching saddle points on general Riemannian manifolds

  2026cites this paper
• Manifold constrained steepest descent

  2026cites this paper
• High Rank Matrix Completion via Grassmannian Proxy Fusion

  2026influential citation
• Low-Complexity and Power-Efficient Precoding Codebook Design on Sparse Grassmannian

  2026cites this paper
• PolySAE: Modeling Feature Interactions in Sparse Autoencoders via Polynomial Decoding

  2026cites this paper
• Neural Wasserstein Two-Sample Tests

  2026cites this paper
• Learning Sparsifying Transforms for mmWave Communication via ℓ4-Norm Maximization

  2026cites this paper
• Physics-informed online low-rank separation for weak target enhancement in rough seabed waveguides

  2026cites this paper
• Three-stage neural network modal parameter identification method incorporating physical constraints and its application in concrete dams

  2026cites this paper
• S⊤S\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$S^{\top \!}S$$\end{document}-SVD via sketching and the nearest S⊤S\

  2026cites this paper
• Generative Modeling of Discrete Data Using Geometric Latent Subspaces

  2026cites this paper
• Spectral Imbalance Causes Forgetting in Low-Rank Continual Adaptation

  2026cites this paper
• Summer-22B: A Systematic Approach to Dataset Engineering and Training at Scale for Video Foundation Model

  2026cites this paper
• An Embarrassingly Simple Way to Optimize Orthogonal Matrices at Scale

  2026cites this paper
• Grassmannian Geometry and Global Convergence of Variable Projection for Neural Networks

  2026cites this paper
• Riemannian optimization on the manifold of unitary and symmetric matrices with application to BD-RIS-assisted systems

  2026cites this paper
• Rethinking PCA Through Duality

  2025cites this paper
• Parametric model order reduction for dynamic non-linear thermoelastic problems in functionally graded materials

  2025cites this paper
• Bounds in the Projective Unitary Group with Respect to Global Phase Invariant Metric

  2025cites this paper
• Graph Generation with Spectral Geodesic Flow Matching

  2025cites this paper
• On Spectral Learning for Odeco Tensors: Perturbation, Initialization, and Algorithms

  2025cites this paper
• Curvature-Aware Deep Learning for Vector Boson Fusion: Differential Geometry, Physics-Inspired Features, and Quantum Method Limitations

  2025cites this paper
• Contribution of task-irrelevant stimuli to drift of neural representations

  2025cites this paper
• A generalized canonical metric for optimization on the indefinite Stiefel manifold

  2025influential citation
• An infeasible projection-type algorithm for finding nonnegative ground state solutions of nonlinear Schrödinger equations

  2025cites this paper
• An explicit formula for the Laplace-Beltrami operator on the Stiefel manifold

  2025cites this paper
• Toroidal area-preserving parameterizations of genus-one closed surfaces

  2025cites this paper
• On learning Gaussian multi‐index models with gradient flow part I: General properties and two‐timescale learning

  2025cites this paper
• Deciding Whether a C-Q Channel Preserves a Bit is QCMA-Complete

  2025cites this paper
• Addressing Multipolarization Interference in GNSS: A Quantitative Measurement and Suppression Solution

  2025cites this paper
• A Geometric Analysis of PCA

  2025cites this paper
• A Parametric, Data-Driven, Non-Intrusive Reduced-Order Model Framework for Crystal Plasticity Simulations of Voids

  2025cites this paper
• Riemannian Inexact Gradient Descent for Quadratic Discrimination

  2025cites this paper
• Spin-orbital magnetism in moir\'e Wigner molecules

  2025cites this paper
• Some notes on higher order concentration of measure

  2025cites this paper
• Geometric Direct Minimization for Low-Spin Restricted Open-Shell Hartree–Fock Theory

  2025cites this paper
• Riemannian Optimization for LoRA on the Stiefel Manifold

  2025cites this paper
• The Geometry of Constrained Optimization: Constrained Gradient Flows via Reparameterization: A-Stable Implicit Schemes, KKT from Stationarity, and Geometry-Respecting Algorithms

  2025cites this paper
• Model Reduction for Discrete-Time Systems via Optimization over Grassmann Manifold

  2025cites this paper
• Online Optimization on Hadamard Manifolds: Curvature-Independent Regret Bounds on Horospherically Convex Objectives

  2025cites this paper
• Autoregressive Processes on Stiefel and Grassmann Manifolds

  2025cites this paper
• High Luminosity LHC data collected by CMS experiment -- an excellent ground for the search of Rare Radiative $B_s^0$ meson decays: A Review

  2025cites this paper
• Panorama: Fast-Track Nearest Neighbors

  2025cites this paper
• StelLA: Subspace Learning in Low-rank Adaptation using Stiefel Manifold

  2025cites this paper
• Leveraging Low-Rank Factorizations of Conditional Correlation Matrices in Graph Learning

  2025cites this paper
• Interpolation-based parametric reduced-order models with dynamic mode decomposition

  2025cites this paper
• Optimization on the Quaternion Stiefel Manifold with Applications—Part I: Basic Geometry

  2025cites this paper
• Mode Collapse of Mean-Field Variational Inference

  2025cites this paper
• A quasi-Grassmannian gradient flow model for eigenvalue problems

  2025cites this paper
• PoLAR: Polar-Decomposed Low-Rank Adapter Representation

  2025cites this paper
• Efficient parametric model order reduction in contact mechanics

  2025cites this paper
• Distributed Retraction-Free and Communication-Efficient Optimization on the Stiefel Manifold

  2025cites this paper
• Optimizing mixed quantum channels via projected gradient dynamics

  2025cites this paper
• Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Method

  2025influential citation
• TensorRL-QAS: Reinforcement learning with tensor networks for improved quantum architecture search

  2025cites this paper
• Quantum information geometry meets DMRG: Uhlmann gauge improvements in computational methods

  2025cites this paper
• Maximizing generalized mean of trace ratios for discriminative feature learning

  2025cites this paper
• A genetic algorithm to generate maximally orthogonal frames in complex space

  2025cites this paper
• Decentralized Optimization on Compact Submanifolds by Quantized Riemannian Gradient Tracking

  2025cites this paper
• Invariant Feature Extraction Functions for UME-Based Point Cloud Detection and Registration

  2025cites this paper
• An Iterative Methodology for Unitary Quantum Channel Search

  2025cites this paper
• Image-set classification using Discriminant Neighborhood Preserving Embedding on Grassmann manifold

  2025cites this paper
• Optimal mode decomposition for control

  2025cites this paper
• RANSAC Revisited: An Improved Algorithm for Robust Subspace Recovery under Adversarial and Noisy Corruptions

  2025cites this paper
• A generalized complex power iteration-based algorithm for quartic-quadratic optimization problems over a spherical constraint and its applications

  2025cites this paper
• A Unified Variational Framework for Quantum Excited States

  2025cites this paper
• Heterogeneous Riemannian Few-Shot Learning Network

  2025cites this paper
• Subspace-Distance-Enabled Active Learning for Efficient Data-Driven Model Reduction of Parametric Dynamical Systems

  2025cites this paper
• Metric degeneracies and gradient flows on symplectic leaves

  2025cites this paper
• Robust Representation and Estimation of Barycenters and Modes of Probability Measures on Metric Spaces

  2025influential citation
• Riemannian Diffusion Adaptation for Distributed Optimization on Manifolds

  2025cites this paper
• Parallel implementations of Riemannian conjugate gradient methods for joint approximate diagonalization

  2025influential citation
• A randomized feasible algorithm for optimization with orthogonal constraints

  2025cites this paper
• Modeling and computing many-body electronic properties of twisted bilayer graphene with mechanical relaxation

  2025cites this paper
• Noncoherent MIMO Communications: Theoretical Foundation, Design Approaches, and Future Challenges

  2025cites this paper
• $S^{\top\!}S$-SVD via Sketching and the Nearest $S^{\top\!}S$-orthogonal Matrix

  2025cites this paper
• Robust Moment Identification for Nonlinear PDEs via a Neural ODE Approach

  2025cites this paper
• A thorough study of Riemannian Newton's Method

  2025cites this paper
• GrFormer: A Novel Transformer on Grassmann Manifold for Infrared and Visible Image Fusion

  2025cites this paper
• Critical point search and linear response theory for computing electronic excitation energies of molecular systems. I. General framework, application to Hartree-Fock and DFT.

  2025cites this paper
• Denoising Multi-Color QR Codes and Stiefel-Valued Data by Relaxed Regularizations

  2025cites this paper
• Stiefel optimization is NP-hard

  2025cites this paper
• Graph Learning With Riemannian Optimization for Multi-View Integrative Clustering

  2025cites this paper
• High-Performance Contraction of Quantum Circuits for Riemannian Optimization

  2025cites this paper
• Smooth tensor decomposition with application to ambulatory blood pressure monitoring data

  2025cites this paper
• Grassmannian Kernels for Efficient and Effective Detection of Group Differences in fMRI Data

  2025cites this paper