Bart Vandereycken

The leapfrog algorithm as nonlinear Gauss–Seidel

by ,

Abstract:

Several applications in optimization, image and signal processing deal with data that belong to the Stiefel manifold St(n, p), that is, the set of n x p matrices with orthonormal columns. Some applications, like the Karcher mean, require evaluating the geodesic distance between two arbitrary points on St(n, p). This can be done by explicitly constructing the geodesic connecting these two points. An existing method for finding geodesics is the leapfrog algorithm of J. L. Noakes. This algorithm is related to the Gauss–Seidel method, a classical iterative method for solving a linear system of equations that can be extended to nonlinear systems. We propose a convergence proof of leapfrog as a nonlinear Gauss–Seidel method. Our discussion is limited to the case of the Stiefel manifold, however it may be generalized to other embedded submanifolds. We discuss other aspects of leapfrog and present some numerical experiments.

Download links:

[pdf]

Reference:

M. Sutti, B. Vandereycken, "The leapfrog algorithm as nonlinear Gauss–Seidel", 2020.

Bibtex Entry:

@misc{Sutti_V:2020b,
    Abstract = {Several applications in optimization, image and signal processing deal with data that belong to the Stiefel manifold St(n, p), that is, the set of n x p matrices with orthonormal columns. Some applications, like the Karcher mean, require evaluating the geodesic distance between two arbitrary points on St(n, p). This can be done by explicitly constructing the geodesic connecting these two points. An existing method for finding geodesics is the leapfrog algorithm of J. L. Noakes. This algorithm is related to the Gauss–Seidel method, a classical iterative method for solving a linear system of equations that can be extended to nonlinear systems. We propose a convergence proof of leapfrog as a nonlinear Gauss–Seidel method. Our discussion is limited to the case of the Stiefel manifold, however it may be generalized to other embedded submanifolds. We discuss other aspects of leapfrog and present some numerical experiments.},
    Author = {Sutti, M. and Vandereycken, B.},
    Howpublished = {Tech. report (submitted)},
    Title = {The leapfrog algorithm as nonlinear Gauss–Seidel},
    Year = {2020},
    Pdf = {http://www.unige.ch/math/vandereycken/papers/preprint_Sutti_V_b.pdf}
    }