Abstract
In fields ranging from computer vision to signal processing and statistics, increasing computational power allows a move from classical linear models to models that incorporate non-linear phenomena. This shift has created interest in computational aspects of differential geometry, and solving optimization problems that incorporate non-linear geometry constitutes an important computational task. In this paper, we develop methods for numerically solving optimization problems over spaces of geodesics using numerical integration of Jacobi fields and second order derivatives of geodesic families. As an important application of this optimization strategy, we compute exact Principal Geodesic Analysis (PGA), a non-linear version of the PCA dimensionality reduction procedure. By applying the exact PGA algorithm to synthetic data, we exemplify the differences between the linearized and exact algorithms caused by the non-linear geometry. In addition, we use the numerically integrated Jacobi fields to determine sectional curvatures and provide upper bounds for injectivity radii.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Blum, H., Wathen-Dunn, W.: A transformation for extracting new descriptors of shape, models for the perception of speech and visual form, 362–380 (1967)
Caselles, V., Kimmel, R., Sapiro, G.: Geodesic active contours. Int. J. Comput. Vis. 22, 61–79 (1995)
Decell, H.P.: On the derivative of the generalized inverse of a matrix. Linear and Multilinear Algebra 1(4), 357 (1974)
Dedieu, J.-P., Nowicki, D.: Symplectic methods for the approximation of the exponential map and the Newton iteration on Riemannian submanifolds. J. Complex. 21(4), 487–501 (2005)
do Carmo, M.P.: Riemannian geometry. In: Mathematics: Theory & Applications. Birkhauser Boston Inc., Boston (1992)
Ferreira, R., Xavier, J., Costeria, J., Barroso, V.: Newton algorithms for riemannian distance related problems on connected locally symmetric manifolds, Technical Report, Institute for Systems and Robotics (ISR) (2008)
Fletcher, P.T., Joshi, S.: Principal geodesic analysis on symmetric spaces: Statistics of diffusion tensors. ECCV Workshops CVAMIA and MMBIA. 3117, 87–98 (2004)
Fletcher, P.T.: Riemannian geometry for the statistical analysis of diffusion tensor data. Signal Process. 87(2), 250–262 (2007)
Fletcher, P.T., Venkatasubramanian, S., Joshi, S.: Robust statistics on Riemannian manifolds via the geometric median, 2008 IEEE Conference on Computer Vision and Pattern Recognition (Anchorage, AK, USA), pp. 1–8 (2008)
Fletcher, P.T.: Geodesic regression on riemannian manifolds, Workshop on Mathematical Foundations of Computational Anatomy (MFCA) at MICCAI (2011)
Fletcher, P.T., Lu, C., Joshi, S.: Statistics of shape via principal geodesic analysis on Lie groups, CVPR 2003, vol. 1, 2003, pp. I–95–I–101 vol.1.
Fletcher, P.T., Lu, C., Pizer, S.M., Joshi, S.: Principal geodesic analysis for the study of nonlinear statistics of shape. IEEE Trans. Med. Imaging (2004)
Fréchet, M.: Les éléments aléatoires de nature quelconque dans un espace distancie. Ann. Inst. H. Poincaré 10, 215–310 (1948)
Golub, G.H., Pereyra, V.: The differentiation of pseudo-inverses and nonlinear least squares problems whose variables separate. SIAM J. Numer. Anal. 10(2), 413–432 (1973)
Hairer, E., Lubich, C., Wanner, G.: Geometric numerical integration. Springer (2002)
Hairer, E., Nørsett, S.P., Wanner, G.: Solving ordinary differential equations I: nonstiff problems (Springer Series in Computational Mathematics), 2nd edn., Springer (2008)
Hanson, R.J., Lawson, C.L.: Extensions and applications of the householder algorithm for solving linear least squares problems. Math. Comput. 23(108), 787–812 (1969)
Hauberg, S., Sommer, S., Pedersen, K.S.: Natural metrics and least-committed priors for articulated tracking. Image Vis. Comput. 30(6–7) (2012)
Huckemann, S., Hotz, T., Munk, A.: Intrinsic shape analysis: geodesic PCA for Riemannian manifolds modulo isometric Lie group actions. Stat. Sin. 20(1), 1–100 (2010)
Joshi, S., Pizer, S., Fletcher, P.T., Yushkevich, P., Thall, A., Marron, J.S.: Multiscale deformable model segmentation and statistical shape analysis using medial descriptions. IEEE Trans. Med. Imaging 21(5), 538–550 (2002). PMID: 12071624
Karcher, H.: Riemannian center of mass and mollifier smoothing. Commun. Pur. Appl. Math. 30(5), 509–541 (1977)
Keller, H.B.: Numerical methods for two-point boundary-value problems, Blaisdell, (Waltham, Mass) (1968)
Kendall, D.G., Manifolds, S.: Procrustean metrics and complex projective spaces. Bull. London Math. Soc. 16(2), 81–121 (1984)
Klassen, E., Srivastava, A.: Geodesics between 3d closed curves using path-straightening, ECCV 2006, vol. 3951, pp. 95–106. Springer (2006)
Klassen, E., Srivastava, A., Mio, W., Joshi, S.: Analysis of planar shapes using geodesic paths on shape spaces. IEEE Trans. Pattern. Anal. Mach. Intell. 26, 372–383 (2004)
Lee, J.M.: Riemannian manifolds, Graduate Texts in Mathematics, vol. 176, Springer-Verlag, New York (1997)
Luenberger, D.G.: The gradient projection method along geodesics. Manag. Sci. 18(11), 620–631 (1972)
Noakes, L.: A global algorithm for geodesics. J. Aust. Math. Soc. 64, 37–50 (1998)
Pennec, X.: Intrinsic statistics on Riemannian manifolds: basic tools for geometric measurements. J. Math. Imaging Vis. 25(1), 127–154 (2006)
Pennec, X., Fillard, P., Ayache, N.: A Riemannian framework for tensor computing. Int. J. Comput. Vis. 66(1), 41–66 (2006)
Pennec, X., Guttmann, C., Thirion, J.-P.: Feature-based registration of medical images: Estimation and validation of the pose accuracy, MICCAI 1998, pp. 1107–1114. Springer, Berlin (1998)
Rabier, P.J., Rheinboldt, W.C.: On a computational method for the second fundamental tensor and its application to bifurcation problems. Numer. Math. 57(1), 681–694 (1990)
Rheinboldt, W.C.: MANPAK: A set of algorithms for computations on implicitly defined manifolds. Comput. Math. Appl. 32(12), 15–28 (1996)
Said, S., Courty, N., Le Bihan, N., Sangwine, S.: Exact principal geodesic analysis for data on SO(3), EUSIPCO 2007 (2007)
Schmidt, F., Clausen, M., Cremers, D.: Shape matching by variational computation of geodesics on a manifold, Pattern Recognition, pp. 142–151. Springer, Berlin (2006)
Sminchisescu, C., Jepson, A.: Generative modeling for continuous non-linearly embedded visual inference, In ICML, 759–766 (2004)
Sommer, S.: Horizontal dimensionality reduction and iterated frame bundle development, Geometric Science of Information (GSI) (2013)
Sommer, S., Lauze, F., Hauberg, S., Nielsen, M.: Manifold valued statistics, exact principal geodesic analysis and the effect of linear approximations, ECCV 2010, vol. 6316, Springer (2010)
Sommer, S., Tatu, A., Chen, C., Jørgensen, D., de Bruijne, M., Loog, M., Nielsen, M., Lauze, F.: Bicycle chain shape models, MMBIA workshop at CVPR. IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops, Miami (2009)
Urtasun, R., Fleet, D.J., Hertzmann, A., Fua, P.: Priors for people tracking from small training sets, 2005 IEEE International Conference on Computer Vision (ICCV), IEEE Computer Society, pp. 403–410 (2005)
Wu, J., Smith, W., Hancock, E.: Weighted principal geodesic analysis for facial gender classification, progress in pattern recognition, Image Analysis and Applications, pp. 331–339. Springer, Berlin (2008)
Yang, L.: Means of probability measures in Riemannian manifolds and applications to radar target detection, Ph.D. thesis, Poitiers University (2011)
Yang, Y.: Globally convergent optimization algorithms on riemannian manifolds: uniform framework for unconstrained and constrained optimization. J. Optim. Theory Appl. 132(2), 245–265 (2007)
Younes, L., Arrate, F., Miller, M.I.: Evolutions equations in computational anatomy. NeuroImage 45(1) (2009). Supplement 1, S40–S50
Zhang, Q., Xu, G.: Curvature computations for n-manifolds in and solution to an open problem proposed by R. Goldman. Comput. Aided Geom. Des. 24(2), 117–123 (2007)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by: J. M. Peña
Rights and permissions
About this article
Cite this article
Sommer, S., Lauze, F. & Nielsen, M. Optimization over geodesics for exact principal geodesic analysis. Adv Comput Math 40, 283–313 (2014). https://doi.org/10.1007/s10444-013-9308-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10444-013-9308-1
Keywords
- Geometric optimization
- Principal geodesic analysis
- Manifold statistics
- Differential geometry
- Riemannian metrics