# Low-complexity subspace-descent over symmetric positive definite manifold

arXiv: https://arxiv.org/abs/2305.02041 · HTML: https://mlsanity.com/paper/2305.02041/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 63 references that are in the map.
- First posted on arXiv 3 May 2023.

## Builds on (most cited first, 19 of 19)

- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Riemannian Adaptive Optimization Methods](https://mlsanity.com/paper/1810.00760/) (2018)
- [First-order Methods for Geodesically Convex Optimization](https://mlsanity.com/paper/1602.06053/) (2016)
- [Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds](https://mlsanity.com/paper/1605.07147/) (2016)
- [Averaging Stochastic Gradient Descent on Riemannian Manifolds](https://mlsanity.com/paper/1802.09128/) (2018)
- [A Riemannian Block Coordinate Descent Method for Computing the Projection Robust Wasserstein Distance](https://mlsanity.com/paper/2012.05199/) (2020)
- [Accelerated, Parallel and Proximal Coordinate Descent](https://mlsanity.com/paper/1312.5799/) (2013)
- [From Nesterov's Estimate Sequence to Riemannian Acceleration](https://mlsanity.com/paper/2001.08876/) (2020)
- [Riemannian Optimization via Frank-Wolfe Methods](https://mlsanity.com/paper/1710.10770/) (2017)
- [Global Convergence of Non-Convex Gradient Descent for Computing Matrix Squareroot](https://mlsanity.com/paper/1507.05854/) (2015)
- [Coordinate Descent Without Coordinates: Tangent Subspace Descent on Riemannian Manifolds](https://mlsanity.com/paper/1912.10627/) (2019)
- [Multivariate Generalized Gaussian Distribution: Convexity and Graphical Models](https://mlsanity.com/paper/1304.3206/) (2013)
- [Riemannian stochastic variance reduced gradient on Grassmann manifold](https://mlsanity.com/paper/1605.07367/) (2016)
- [R-SPIDER: A Fast Riemannian Stochastic Optimization Algorithm with Curvature Independent Rate](https://mlsanity.com/paper/1811.04194/) (2018)
- [The Cyclic Block Conditional Gradient Method for Convex Optimization Problems](https://mlsanity.com/paper/1502.03716/) (2015)
- [On the matrix square root via geometric optimization](https://mlsanity.com/paper/1507.08366/) (2015)
- [Gradient Method for Optimization on Riemannian Manifolds with Lower Bounded Curvature](https://mlsanity.com/paper/1806.02694/) (2018)
- [Riemannian preconditioned coordinate descent for low multi-linear rank approximation](https://mlsanity.com/paper/2109.01632/) (2021)
- [A Flexible Coordinate Descent Method](https://mlsanity.com/paper/1507.03713/) (2015)

## Built on by (most cited first, 2 of 2)

- [Riemannian coordinate descent algorithms on matrix manifolds](https://mlsanity.com/paper/2406.02225/) (2024)
- [Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Method](https://mlsanity.com/paper/2505.12378/) (2025)

## Abstract (arXiv)

This work puts forth low-complexity Riemannian subspace descent algorithms for the minimization of functions over the symmetric positive definite (SPD) manifold. Different from the existing Riemannian gradient descent variants, the proposed approach utilizes carefully chosen subspaces that allow the update to be written as a product of the Cholesky factor of the iterate and a sparse matrix. The resulting updates avoid the costly matrix operations like matrix exponentiation and dense matrix multiplication, which are generally required in almost all other Riemannian optimization algorithms on SPD manifold. We further identify a broad class of functions, arising in diverse applications, such as kernel matrix learning, covariance estimation of Gaussian distributions, maximum likelihood parameter estimation of elliptically contoured distributions, and parameter estimation in Gaussian mixture model problems, over which the Riemannian gradients can be calculated efficiently. The proposed uni-directional and multi-directional Riemannian subspace descent variants incur per-iteration complexities of O(n) and O(n2) respectively, as compared to the O(n3) or higher complexity incurred by all existing Riemannian gradient descent variants. The superior runtime and low per-iteration complexity of the proposed algorithms is also demonstrated via numerical tests on large-scale covariance estimation and matrix square root problems. MATLAB code implementation is publicly available on GitHub : https://github.com/yogeshd-iitk/subspacedescentoverSPDmanifold