A Grassmann manifold handbook: basic geometry and computational aspects. (English) Zbl 1532.53001
Adv. Comput. Math. 50, No. 1, Paper No. 6, 51 p. (2024); correction ibid. 50, No. 2, Paper No. 20, 2 p. (2024).
Summary: The Grassmann manifold of linear subspaces is important for the mathematical modelling of a multitude of applications, ranging from problems in machine learning, computer vision and image processing to low-rank matrix optimization problems, dynamic low-rank decompositions and model reduction. With this mostly expository work, we aim to provide a collection of the essential facts and formulae on the geometry of the Grassmann manifold in a fashion that is fit for tackling the aforementioned problems with matrix-based algorithms. Moreover, we expose the Grassmann geometry both from the approach of representing subspaces with orthogonal projectors and when viewed as a quotient space of the orthogonal group, where subspaces are identified as equivalence classes of (orthogonal) bases. This bridges the associated research tracks and allows for an easy transition between these two approaches. Original contributions include a modified algorithm for computing the Riemannian logarithm map on the Grassmannian that is advantageous numerically but also allows for a more elementary, yet more complete description of the cut locus and the conjugate points. We also derive a formula for parallel transport along geodesics in the orthogonal projector perspective, formulae for the derivative of the exponential map, as well as a formula for Jacobi fields vanishing at one point.
MSC:
| 53-02 | Research exposition (monographs, survey articles) pertaining to differential geometry |
| 51-02 | Research exposition (monographs, survey articles) pertaining to geometry |
| 53A15 | Affine differential geometry |
| 14M15 | Grassmannians, Schubert varieties, flag manifolds |
| 15B10 | Orthogonal matrices |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
| 51A50 | Polar geometry, symplectic spaces, orthogonal spaces |
| 51N05 | Descriptive geometry |
| 51N10 | Affine analytic geometry |
Keywords:
Grassmann manifold; Stiefel manifold; orthogonal group; Riemannian exponential; geodesic; Riemannian logarithm; cut locus; conjugate locus; curvature; parallel transport; quotient manifold; singular value decompositionReferences:
| [1] | Absil, P-A; Edelman, A.; Koev, P., On the largest principal angle between random subspaces, Linear Algebra Appl., 414, 1, 288-294 (2006) · Zbl 1090.15017 · doi:10.1016/j.laa.2005.10.004 |
| [2] | Absil, P-A; Mahony, R.; Sepulchre, R., Riemannian geometry of Grassmann manifolds with a view on algorithmic computation, Acta Applicandae Mathematica, 80, 2, 199-220 (2004) · Zbl 1052.65048 · doi:10.1023/B:ACAP.0000013855.14971.91 |
| [3] | Absil, P.-A., Mahony, R., Sepulchre, R.: Optimization algorithms on matrix manifolds. Princeton University Press, Princeton, New Jersey (2008). http://press.princeton.edu/titles/8586.html · Zbl 1147.65043 |
| [4] | Afsari, B.; Tron, R.; Vidal, R., On the convergence of gradient descent for finding the Riemannian center of mass, SIAM J. Control. Optim., 51, 3, 2230-2260 (2013) · Zbl 1285.90031 · doi:10.1137/12086282X |
| [5] | Alexandrino, M.M., Bettiol, R.G.: Lie groups and geometric aspects of isometric actions. Springer International Publishing, Cham (2015). doi:10.1007/978-3-319-16613-1_2 · Zbl 1322.22001 |
| [6] | Alimisis, F., Orvieto, A., Becigneul, G., Lucchi, A.: Momentum improves optimization on Riemannian manifolds. In: Banerjee, A., Fukumizu, K., (eds.) Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, of Proceedings of Machine Learning Research, vol. 130, pp. 1351-1359. PMLR. Accessed 13-15 Apr 2021 |
| [7] | Alimisis, F., Vandereycken, B.: Geodesic convexity of the symmetric eigenvalue problem and convergence of Riemannian steepest descent (2023). arXiv:2209.03480 |
| [8] | Amsallem, D.; Farhat, C., Interpolation method for adapting reduced-order models and application to aeroelasticity, AIAA J., 46, 7, 1803-1813 (2008) · doi:10.2514/1.35374 |
| [9] | Balzano, L.; Wright, SJ, Local convergence of an algorithm for subspace identification from partial data, Found. Comput. Math., 15, 5, 1279-1314 (2015) · Zbl 1327.90392 · doi:10.1007/s10208-014-9227-7 |
| [10] | Batzies, E.; Hüper, K.; Machado, L.; Silva Leite, F., Geometric mean and geodesic regression on Grassmannians, Linear Algebra Appl., 466, 83-101 (2015) · Zbl 1315.53037 · doi:10.1016/j.laa.2014.10.003 |
| [11] | Berceanu, S., On the geometry of complex Grassmann manifold, its noncompact dual and coherent states, Bull. Belg. Math. Soc. Simon Stevin, 4, 2, 205-243 (1997) · Zbl 0947.53021 · doi:10.36045/bbms/1105731655 |
| [12] | Bergmann, R.; Gousenbourger, P-Y, A variational model for data fitting on manifolds by minimizing the acceleration of a Bézier curve, Frontiers in Applied Mathematics and Statistics, 4, 59 (2018) · doi:10.3389/fams.2018.00059 |
| [13] | Bishop, RL, Decomposition of cut loci, Proc. Amer. Math. Soc., 65, 1, 133-136 (1977) · Zbl 0373.53019 · doi:10.2307/2042008 |
| [14] | Borisenko, A.A., Nikolaevskiĭ, Yu.A.: Grassmann manifolds and Grassmann image of submanifolds. Uspekhi Mat. Nauk 46(2(278)), 41-83, 240 (1991). doi:10.1070/RM1991v046n02ABEH002742 · Zbl 0742.53017 |
| [15] | Boumal, N.: Optimization and estimation on manifolds. PhD thesis, Université Catholique de Louvain (2014) |
| [16] | Boumal, N.; Absil, P-A, Low-rank matrix completion via preconditioned optimization on the Grassmann manifold, Linear Algebra Appl., 475, 200-239 (2015) · Zbl 1312.90092 · doi:10.1016/j.laa.2015.02.027 |
| [17] | Chakraborty, R.; Vemuri, BC, Statistics on the Stiefel manifold: theory and applications, Ann. Stat., 47, 1, 415-438 (2019) · Zbl 1419.62132 · doi:10.1214/18-AOS1692 |
| [18] | Criscitiello, C., Boumal, N.: Curvature and complexity: better lower bounds for geodesically convex optimization (2023). arXiv:2306.02959 · Zbl 07735215 |
| [19] | Dieci, L.; Eirola, T., On smooth decompositions of matrices, SIAM J. Matrix Anal. Appl., 20, 3, 800-819 (1999) · Zbl 0930.15014 · doi:10.1137/S0895479897330182 |
| [20] | do Carmo, M.P.: Riemannian geometry. Mathematics: Theory & Applications. Birkhäuser Boston (1992) · Zbl 0752.53001 |
| [21] | Edelman, A.; Arias, TA; Smith, ST, The geometry of algorithms with orthogonality constraints, SIAM J. Matrix Anal. Appl., 20, 2, 303-353 (1998) · Zbl 0928.65050 · doi:10.1137/S0895479895290954 |
| [22] | Fletcher, PT, Geodesic regression and the theory of least squares on Riemannian manifolds, Int. J. Comput. Vision, 105, 2, 171-185 (2013) · Zbl 1304.62092 · doi:10.1007/s11263-012-0591-y |
| [23] | Gallier, J.H.: Geometric methods and applications: for computer science and engineering. Texts in Applied Mathematics. Springer, New York (2011). doi:10.1007/978-1-4419-9961-0 · Zbl 1247.53001 |
| [24] | Gallivan, K.A., Srivastava, A., Liu, X., Van Dooren, P.: Efficient algorithms for inferences on Grassmann manifolds. In: IEEE workshop on statistical signal processing, pp. 315-318 (2003). doi:10.1109/SSP.2003.1289408 |
| [25] | Gillespie, M.: Variations on a theme of Schubert calculus, pp. 115-158. Springer International Publishing, Cham (2019). doi:10.1007/978-3-030-05141-9_4 · Zbl 1410.14044 |
| [26] | Godement, R.; Ray, U., Introduction to the theory of lie groups, Universitext. Springer International Publishing (2017) · Zbl 1367.22001 · doi:10.1007/978-3-319-54375-8 |
| [27] | Gousenbourger, P-Y; Massart, E.; Absil, P-A, Data fitting on manifolds with composite bézier-like curves and blended cubic splines, Journal of Mathematical Imaging and Vision, 61, 5, 645-671 (2019) · Zbl 1492.65047 · doi:10.1007/s10851-018-0865-2 |
| [28] | Hairer, E., Lubich, C., Wanner, G.: Geometric numerical integration, of Springer Series in Computational Mathematics, vol. 31, 2nd edn. Springer-Verlag, Berlin (2006). doi:10.1007/3-540-30666-8 · Zbl 1094.65125 |
| [29] | Hall, B.C.: Lie groups, lie algebras, and representations: an elementary introduction. Springer Graduate texts in Mathematics. Springer-Verlag, New York - Berlin - Heidelberg, 2nd edn. (2015). doi:10.1007/978-3-319-13467-3 · Zbl 1316.22001 |
| [30] | Hay, A.; Borggaard, JT; Pelletier, D., Local improvements to reduced-order models using sensitivity analysis of the proper orthogonal decomposition, J. Fluid Mech., 629, 41-72 (2009) · Zbl 1181.76045 · doi:10.1017/S0022112009006363 |
| [31] | Helgason, S.: Differential geometry, lie groups, and symmetric spaces. Crm Proceedings & Lecture Notes. American Mathematical Society (2001) · Zbl 0993.53002 |
| [32] | Helmke, U., Hüper, K., Trumpf, J.: Newton’s method on Graßmann manifolds (2007). arXiv:0709.2205 |
| [33] | Helmke, U., Moore, J.B.: Optimization and dynamical systems. Communications & Control Engineering. Springer-Verlag, London (1994). doi:10.1007/978-1-4471-3467-1 · Zbl 0984.49001 |
| [34] | Higham, N.J.: Functions of matrices: theory and computation. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2008). doi:10.1137/1.9780898717778 · Zbl 1167.15001 |
| [35] | Horn, R.A., Johnson, C.R.: Topics in matrix analysis. Cambridge University Press, Cambridge (1991). doi:10.1017/CBO9780511840371 · Zbl 0729.15001 |
| [36] | Kobayashi, S., Nomizu, K.: Foundations of differential geometry. vol. I & II. Wiley Classics Library. John Wiley & Sons, Inc., New York (1996). Reprint of the 1963 original · Zbl 0119.37502 |
| [37] | Koch, O.; Lubich, C., Dynamical low-rank approximation, SIAM J. Matrix Analysis Applications, 29, 434-454 (2007) · Zbl 1145.65031 · doi:10.1137/050639703 |
| [38] | Kozlov, E.S.: Geometry of real Grassmann manifolds. Part I - VI. Journal of Mathematical Sciences (2000 - 2001) |
| [39] | Lai, Z., Lim, L.-H., Ye, K.: Simpler Grassmannian optimization (2020). arXiv:2009.13502 |
| [40] | Lee, J.M.: Introduction to smooth manifolds. Graduate Texts in Mathematics. Springer New York (2012). doi:10.1007/978-1-4419-9982-5 · Zbl 1258.53002 |
| [41] | Lee, J.M.: Introduction to Riemannian manifolds, of Graduate Texts in Mathematics, vol. 176. Springer, Cham (2018). doi:10.1007/978-3-319-91755-9 · Zbl 1409.53001 |
| [42] | Leichtweiss, K., Zur Riemannschen Geometrie in Grassmannschen Mannigfaltigkeiten, Math. Z., 76, 334-366 (1961) · Zbl 0113.37102 · doi:10.1007/BF01210982 |
| [43] | Li, C., Wang, X., Wang, J., Yao, J.-C.: Convergence analysis of gradient algorithms on Riemannian manifolds without curvature constraints and application to Riemannian mass (2019). arXiv:1910.02280 · Zbl 1457.53022 |
| [44] | Machado, A., Salavessa, I.: Grassmannian manifolds as subsets of Euclidean spaces. In: Differential geometry (Santiago de Compostela, 1984), of Res. Notes in Math., vol. 131, pp. 85-102. Pitman, Boston, MA (1985) · Zbl 0648.53029 |
| [45] | Man Lui, Y., Advances in matrix manifolds for computer vision, Image Vis. Comput., 30, 6-7, 380-388 (2012) · doi:10.1016/j.imavis.2011.08.002 |
| [46] | Minh, H.Q., Murino, V.: Algorithmic advances in Riemannian geometry and applications: for machine learning, computer vision, statistics, and optimization. Advances in Computer Vision and Pattern Recognition. Springer International Publishing, Cham (2016). doi:10.1007/978-3-319-45026-1 · Zbl 1357.53004 |
| [47] | Nguyen, TS, A real time procedure for affinely dependent parametric model order reduction using interpolation on Grassmann manifolds, Int. J. Numer. Meth. Eng., 93, 8, 818-833 (2013) · Zbl 1352.93032 · doi:10.1002/nme.4408 |
| [48] | Nguyen, TS; Stykel, T., Model order reduction of parameterized circuit equations based on interpolation, Adv. Comput. Math., 41, 1321-1342 (2015) · Zbl 1336.93037 · doi:10.1007/s10444-015-9418-z |
| [49] | O’Neill, B.: Semi-Riemannian geometry - with applications to relativity, of Pure and Applied Mathematics, vol. 103. Academic Press, New York (1983) · Zbl 0531.53051 |
| [50] | Qiu, L.; Zhang, Y.; Li, C-K, Unitarily invariant metrics on the Grassmann space, SIAM J. Matrix Anal. Appl., 27, 2, 507-25 (2005) · Zbl 1099.15024 · doi:10.1137/040607605 |
| [51] | Rahman, IU; Drori, I.; Stodden, VC; Donoho, DL; Schröder, P., Multiscale representations for manifold-valued data, SIAM Journal on Multiscale Modeling and Simulation, 4, 4, 1201-1232 (2005) · Zbl 1236.65166 · doi:10.1137/050622729 |
| [52] | Rentmeesters, Q.: Algorithms for data fitting on some common homogeneous spaces. PhD thesis, Université Catholique de Louvain, Louvain, Belgium (2013). http://hdl.handle.net/2078.1/132587 |
| [53] | Saad, Y., Numerical methods for large eigenvalue problems (1992), Manchester, UK: Algortihms and Architectures for Advanced Scientific Computing. Manchester University Press, Manchester, UK · Zbl 0991.65039 |
| [54] | Sakai, T., On cut loci of compact symmetric spaces, Hokkaido Math. J., 6, 1, 136-161 (1977) · Zbl 0361.53048 · doi:10.14492/hokmj/1381758555 |
| [55] | Sakai, T., Riemannian Geometry, Fields Institute Communications. American Mathematical Soc. (1996) · Zbl 0886.53002 · doi:10.1090/mmono/149 |
| [56] | Srivastava, A., Liu, X.: Tools for application-driven linear dimension reduction. Neurocomputing 67, 136 - 160 (2005). Geometrical Methods in Neural Networks and Learning. doi:10.1016/j.neucom.2004.11.036 |
| [57] | Srivastava, A.; Turaga, PK, Riemannian computing in computer vision, Springer International Publishing (2015) · Zbl 1335.65003 · doi:10.1007/978-3-319-22957-7 |
| [58] | Usevich, K.; Markovsky, I., Optimization on a Grassmann manifold with application to system identification, Automatica, 50, 6, 1656-1662 (2014) · Zbl 1296.93043 · doi:10.1016/j.automatica.2014.04.010 |
| [59] | Walter, SF; Lehmann, L.; Lamour, R., On evaluating higher-order derivatives of the QR decomposition of tall matrices with full column rank in forward and reverse mode algorithmic differentiation, Optimization Methods and Software, 27, 2, 391-403 (2012) · Zbl 1242.65048 · doi:10.1080/10556788.2011.610454 |
| [60] | Wong, Y-C, Differential geometry of Grassmann manifolds, Proc. Natl. Acad. Sci. U.S.A., 57, 589-594 (1967) · Zbl 0154.21404 · doi:10.1073/pnas.57.3.589 |
| [61] | Wong, Y-C, Conjugate loci in Grassmann manifolds, Bull. Amer. Math. Soc., 74, 240-245 (1968) · Zbl 0161.41103 · doi:10.1090/S0002-9904-1968-11903-2 |
| [62] | Wong, Y-C, Sectional curvatures of Grassmann manifolds, Proc. Natl. Acad. Sci. U.S.A., 60, 1, 75-79 (1968) · Zbl 0169.23904 · doi:10.1073/pnas.60.1.75 |
| [63] | Wu, GL; Chen, WH, A matrix inequality and its geometric applications, Acta Math. Sinica, 31, 3, 348-355 (1988) · Zbl 0675.15006 |
| [64] | Ye, K.; Lim, L-H, Schubert varieties and distances between subspaces of different dimensions, SIAM J. Matrix Anal. Appl., 37, 3, 1176-1197 (2016) · Zbl 1365.14065 · doi:10.1137/15M1054201 |
| [65] | Zhang, D., Balzano, L.: Global convergence of a Grassmannian gradient descent algorithm for subspace estimation. Proceedings of the 19th international conference on artificial intelligence and statistics, AISTATS, pp. 1460-1468. Cadiz, Spain (2016) |
| [66] | Zhang, H., Sra, S.: First-order methods for geodesically convex optimization. In: Feldman, V., Rakhlin, A., Shamir, O. (eds.), 29th Annual Conference on Learning Theory, of Proceedings of Machine Learning Research, vol. 49, pp. 1617-1638, Columbia University, New York, USA. PMLR. Accessed 23-26 Jun 2016 (2016) |
| [67] | Zimmermann, R., A locally parametrized reduced order model for the linear frequency domain approach to time-accurate computational fluid dynamics, SIAM J. Sci. Comput., 36, 3, B508-B537 (2014) · Zbl 1347.76032 · doi:10.1137/130942462 |
| [68] | Zimmermann, R.; Peherstorfer, B.; Willcox, K., Geometric subspace updates with applications to online adaptive nonlinear model reduction, SIAM Journal on Matrix Analysis and Application, 39, 1, 234-261 (2018) · Zbl 1383.65034 · doi:10.1137/17M1123286 |
| [69] | Zimmermann, R.: Manifold interpolation. In: Benner, P., Grivet-Talocia, S., Quarteroni, A., Rozza, G., Schilders, W., Silveira, L.M. (eds.), vol. 1 system- and data-driven methods and algorithms, pp. 229-274. De Gruyter, Berlin, Boston (2021). doi:10.1515/9783110498967-007 · Zbl 1473.93004 |
| [70] | Zimmermann, R., Hermite interpolation and data processing errors on Riemannian matrix manifolds, SIAM J. Sci. Comput., 42, 5, A2593-A2619 (2020) · Zbl 1452.65085 · doi:10.1137/19M1282878 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
