DocumentCode :
48741
Title :
Newton Algorithms for Riemannian Distance Related Problems on Connected Locally Symmetric Manifolds
Author :
Ferreira, Ricardo ; Xavier, Joao ; Costeira, Joao P. ; Barroso, Victor
Author_Institution :
Inst. for Syst. & Robot., Lisbon, Portugal
Volume :
7
Issue :
4
fYear :
2013
fDate :
Aug. 2013
Firstpage :
634
Lastpage :
645
Abstract :
The squared distance function is one of the standard functions on which an optimization algorithm is commonly run, whether it is used directly or chained with other functions. Illustrative examples include center of mass computation, implementation of k-means algorithm and robot positioning. This function can have a simple expression (as in the Euclidean case), or it might not even have a closed form expression. Nonetheless, when used in an optimization problem formulated on non-Euclidean manifolds, the appropriate (intrinsic) version must be used and depending on the algorithm, its gradient and/or Hessian must be computed. For many commonly used manifolds a way to compute the intrinsic distance is available as well as its gradient, the Hessian however is usually a much more involved process, rendering Newton methods unusable on many standard manifolds. This article presents a way of computing the Hessian on connected locally-symmetric spaces on which standard Riemannian operations are known (exponential map, logarithm map and curvature). Although not a requirement for the result, describing the manifold as naturally reductive homogeneous spaces, a special class of manifolds, provides a way of computing these functions. The main example focused in this article is centroid computation of a finite constellation of points on connected locally symmetric manifolds since it is directly formulated as an intrinsic squared distance optimization problem. Simulation results shown here confirm the quadratic convergence rate of a Newton algorithm on commonly used manifolds such as the sphere, special orthogonal group, special Euclidean group, symmetric positive definite matrices, Grassmann manifold and projective space.
Keywords :
Hessian matrices; Newton method; convergence; gradient methods; quadratic programming; Euclidean group; Grassmann manifold; Hessian process; Newton algorithm; Riemannian distance; Riemannian symmetric positive definite matrix; centroid computation; connected locally symmetric manifold; finite constellation; gradient method; intrinsic squared distance optimization problem; naturally reductive homogeneous space; quadratic convergence rate; standard Riemannian operation; Convergence; Cost function; Manifolds; Newton method; Signal processing algorithms; Vectors; Hessian computation; Riemannian distance; optimization;
fLanguage :
English
Journal_Title :
Selected Topics in Signal Processing, IEEE Journal of
Publisher :
ieee
ISSN :
1932-4553
Type :
jour
DOI :
10.1109/JSTSP.2013.2261799
Filename :
6514064
Link To Document :
بازگشت