On the convergence of gradient descent for finding the Riemannian center of mass
From MaRDI portal
Publication:2848583
DOI10.1137/12086282XzbMATH Open1285.90031arXiv1201.0925OpenAlexW2962777248WikidataQ115247001 ScholiaQ115247001MaRDI QIDQ2848583FDOQ2848583
Authors: Bijan Afsari, Roberto Tron, René Vidal 
Publication date: 26 September 2013
Published in: SIAM Journal on Control and Optimization (Search for Journal in Brave)
Abstract: We study the problem of finding the global Riemannian center of mass of a set of data points on a Riemannian manifold. Specifically, we investigate the convergence of constant step-size gradient descent algorithms for solving this problem. The challenge is that often the underlying cost function is neither globally differentiable nor convex, and despite this one would like to have guaranteed convergence to the global minimizer. After some necessary preparations we state a conjecture which we argue is the best (in a sense described) convergence condition one can hope for. The conjecture specifies conditions on the spread of the data points, step-size range, and the location of the initial condition (i.e., the region of convergence) of the algorithm. These conditions depend on the topology and the curvature of the manifold and can be conveniently described in terms of the injectivity radius and the sectional curvatures of the manifold. For manifolds of constant nonnegative curvature (e.g., the sphere and the rotation group in ) we show that the conjecture holds true (we do this by proving and using a comparison theorem which seems to be of a different nature from the standard comparison theorems in Riemannian geometry). For manifolds of arbitrary curvature we prove convergence results which are weaker than the conjectured one (but still superior over the available results). We also briefly study the effect of the configuration of the data points on the speed of convergence.
Full work available at URL: https://arxiv.org/abs/1201.0925
Recommendations
- Convergence Analysis of Gradient Algorithms on Riemannian Manifolds without Curvature Constraints and Application to Riemannian Mass
- Computing Riemannian center of mass on Hadamard manifolds
- Riemannian \(L^{p}\) center of mass: existence, uniqueness, and convexity
- Sufficient descent Riemannian conjugate gradient methods
- Riemannian conjugate gradient methods: general framework and specific algorithms with convergence analyses
- Publication:4897031
- Computing the Riemannian center of mass on meshes
- Gradient method for optimization on Riemannian manifolds with lower bounded curvature
- scientific article; zbMATH DE number 4031421
- Stochastic Gradient Descent on Riemannian Manifolds
Cited In (59)
- Synchronization of diffusively coupled systems on compact Riemannian manifolds in the presence of drift
- Intrinsic representation of tangent vectors and vector transports on matrix manifolds
- Endpoint geodesics on the Stiefel manifold embedded in Euclidean space
- A kernel regression procedure in the 3D shape space with an application to online sales of children's wear
- Mini-workshop: Computational optimization on manifolds. Abstracts from the mini-workshop held November 15--21, 2020 (online meeting)
- Characterization of lower semicontinuous convex functions on Riemannian manifolds
- Manifold interpolation
- Fréchet means and Procrustes analysis in Wasserstein space
- Quotient geometry with simple geodesics for the manifold of fixed-rank positive-semidefinite matrices
- \(\varepsilon\)-subgradient algorithms for locally Lipschitz functions on Riemannian manifolds
- Distributed methods for synchronization of orthogonal matrices over graphs
- Highly resistant gradient descent algorithm for computing intrinsic mean shape on similarity shape spaces
- A Riemannian stochastic representation for quantifying model uncertainties in molecular dynamics simulations
- Concepts and techniques of optimization on the sphere
- Parameter estimation and model-based clustering with spherical normal distribution on the unit hypersphere
- Intrinsic formulation of KKT conditions and constraint qualifications on smooth manifolds
- Linear convergence of subgradient algorithm for convex feasibility on Riemannian manifolds
- Mumford-Shah and Potts regularization for manifold-valued data
- A Graph Framework for Manifold-Valued Data
- Numerical algorithms on the affine Grassmannian
- Averaging symmetric positive-definite matrices
- An inexact semismooth Newton method on Riemannian manifolds with application to duality-based total variation denoising
- Incremental quasi-subgradient method for minimizing sum of geodesic quasi-convex functions on Riemannian manifolds with applications
- Recursive Computation of the Fréchet Mean on Non-positively Curved Riemannian Manifolds with Applications
- Riemannian \(L^p\) averaging on Lie group of nonzero quaternions
- On some basic results related to affine functions on Riemannian manifolds
- A Broyden class of quasi-Newton methods for Riemannian optimization
- Gradient method for optimization on Riemannian manifolds with lower bounded curvature
- Convergence Analysis of Gradient Algorithms on Riemannian Manifolds without Curvature Constraints and Application to Riemannian Mass
- Wavelet Sparse Regularization for Manifold-Valued Data
- An algorithm for computing Fréchet means on the sphere
- Well-posedness of Hersch-Szegő's center of mass by hyperbolic energy minimization
- An intrinsic aggregation model on the special orthogonal group \(SO(3)\): well-posedness and collective behaviours
- Tree-oriented analysis of brain artery structure
- Non-smooth variational regularization for processing manifold-valued data
- Newton's method, zeroes of vector fields, and the Riemannian center of mass
- Rate-invariant analysis of covariance trajectories
- Characterization of convex and generalized convex vector fields on Riemannian manifolds
- A parallel Douglas-Rachford algorithm for minimizing ROF-like functionals on images with values in symmetric Hadamard manifolds
- Incremental gradient method for Karcher mean on symmetric cones
- The Space of Essential Matrices as a Riemannian Quotient Manifold
- A second order nonsmooth variational model for restoring manifold-valued images
- Subgradient algorithms on Riemannian manifolds of lower bounded curvatures
- Computing Riemannian center of mass on Hadamard manifolds
- On the measure of the cut locus of a Fréchet mean
- A nonlocal denoising algorithm for manifold-valued images using second order statistics
- A majorization-minimization algorithm for computing the Karcher mean of positive definite matrices
- First order methods for optimization on Riemannian manifolds
- Combinatorial convexity in Hadamard manifolds: existence for equilibrium problems
- Path-based incremental target level algorithm on Riemannian manifolds
- Nonsmooth nonconvex optimization on Riemannian manifolds via bundle trust region algorithm
- Convergence of hyperbolic neural networks under Riemannian stochastic gradient descent
- Pseudo-differential and characterization of generalized convex functions on Riemannian manifolds
- Fenchel conjugate via Busemann function on Hadamard manifolds
- Discretized gradient flow for manifold learning
- Stochastic symplectic reduced-order modeling for model-form uncertainty quantification in molecular dynamics simulations in various statistical ensembles
- Karush-Kuhn-Tucker optimality conditions for non-smooth geodesic quasi-convex optimization on Riemannian manifolds
- A Grassmann manifold handbook: basic geometry and computational aspects
- SLERP-TVDRK (STVDRK) methods for ordinary differential equations on spheres
This page was built for publication: On the convergence of gradient descent for finding the Riemannian center of mass
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2848583)
