On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-Rank Matrix Optimization

References

• [1] Abraham R, Marsden JE, Ratiu T (2012) Manifolds, Tensor Analysis, and Applications (Springer Science, New York).Google Scholar
• [2] Absil PA, Amodei L, Meyer G (2014) Two Newton methods on the manifold of fixed-rank matrices endowed with Riemannian quotient geometries. Comput. Statist. 29(3):569–590.Crossref, Google Scholar
• [3] Absil PA, Mahony R, Sepulchre R (2009) Optimization Algorithms on Matrix Manifolds (Princeton University Press, Princeton, NJ).Google Scholar
• [4] Absil PA, Mahony R, Trumpf J (2013) An extrinsic look at the Riemannian Hessian. Proc. Internat. Conf. Geometric Sci. Inform. (Springer, Berlin), 361–368.Google Scholar
• [5] Absil PA, Ishteva M, De Lathauwer L, Van Huffel S (2009) A geometric Newton method for Oja’s vector field. Neural Comput. 21(5):1415–1433.Crossref, Google Scholar
• [6] Ahn K, Suarez F (2021) Riemannian perspective on matrix factorization. Preprint, submitted February 1, https://doi.org/10.48550/arXiv.2102.00937.Google Scholar
• [7] Bhatia R (2013) Matrix Analysis (Springer, New York).Google Scholar
• [8] Bhojanapalli S, Kyrillidis A, Sanghavi S (2016) Dropping convexity for faster semi-definite optimization. Proc. Machine Learning Res. 49:530–582.Google Scholar
• [9] Bonnabel S, Sepulchre R (2010) Riemannian metric and geometric mean for positive semidefinite matrices of fixed rank. SIAM J. Matrix Anal. Appl. 31(3):1055–1070.Crossref, Google Scholar
• [10] Boumal N (2023) An Introduction to Optimization on Smooth Manifolds (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [11] Boumal N, Absil PA (2011) Rtrmc: A Riemannian trust-region method for low-rank matrix completion. Adv. Neural Inform. Processing Syst. 24:406–414.Google Scholar
• [12] Boumal N, Absil PA, Cartis C (2019) Global rates of convergence for nonconvex optimization on manifolds. IMA J. Numer. Anal. 39(1):1–33.Crossref, Google Scholar
• [13] Cai JF, Wei K (2018) Exploiting the structure effectively and efficiently in low-rank matrix recovery. Handbook Numer. Anal. 19:21–51.Google Scholar
• [14] Cai TT, Zhang A (2013) Compressed sensing and affine rank minimization under restricted isometry. IEEE Trans. Signal Processing 61(13):3279–3290.Crossref, Google Scholar
• [15] Chen Y, Chi Y (2018) Harnessing structures in big data via guaranteed low-rank matrix estimation: Recent theory and fast algorithms via convex and nonconvex optimization. IEEE Signal Processing Magazine 35(4):14–31.Crossref, Google Scholar
• [16] Chi Y, Lu YM, Chen Y (2019) Nonconvex optimization meets low-rank matrix factorization: An overview. IEEE Trans. Signal Processing 67(20):5239–5269.Crossref, Google Scholar
• [17] Criscitiello C, Boumal N (2019) Efficiently escaping saddle points on manifolds. Adv. Neural Inform. Processing Systems 32:5987–5997.Google Scholar
• [18] Douik A, Hassibi B (2021) Low-rank Riemannian optimization for graph-based clustering applications. IEEE Trans. Pattern Anal. Machine Intelligence 44:5133–5148.Google Scholar
• [19] Edelman A, Arias TA, Smith ST (1998) The geometry of algorithms with orthogonality constraints. SIAM J. Matrix Anal. Appl. 20(2):303–353.Crossref, Google Scholar
• [20] Gao Y, Sun D (2010) A majorized penalty approach for calibrating rank constrained correlation matrix problems. Working paper, National University of Singapore, Singapore, https://www.polyu.edu.hk/ama/profile/dfsun/MajorPen.pdf.Google Scholar
• [21] Ge R, Ma T (2022) On the optimization landscape of tensor decompositions. Math. Programming 193(2):713–759.Crossref, Google Scholar
• [22] Ge R, Huang F, Jin C, Yuan Y (2015) Escaping from saddle points-online stochastic gradient for tensor decomposition. Preprint, submitted March 6, https://doi.org/10.48550/arXiv.1503.02101.Google Scholar
• [23] Grubisić I, Pietersz R (2007) Efficient rank reduction of correlation matrices. Linear Algebra Appl. 422(2–3):629–653.Crossref, Google Scholar
• [24] Ha W, Liu H, Barber RF (2020) An equivalence between critical points for rank constraints vs. low-rank factorizations. SIAM J. Optim. 30(4):2927–2955.Crossref, Google Scholar
• [25] Helmke U, Moore JB (2012) Optimization and Dynamical Systems (Springer, New York).Google Scholar
• [26] Hou TY, Li Z, Zhang Z (2020) Fast global convergence for low-rank matrix recovery via Riemannian gradient descent with random initialization. Preprint, submitted December 31, https://doi.org/10.48550/arXiv.2012.15467.Google Scholar
• [27] Hu J, Liu X, Wen ZW, Yuan YX (2020) A brief introduction to manifold optimization. J. Oper. Res. Soc. China 8(2):199–248.Crossref, Google Scholar
• [28] Huang W, Hand P (2018) Blind deconvolution by a steepest descent algorithm on a quotient manifold. SIAM J. Imaging Sci. 11(4):2757–2785.Crossref, Google Scholar
• [29] Huang W, Gallivan KA, Zhang X (2017) Solving phaselift by low-rank Riemannian optimization methods for complex semidefinite constraints. SIAM J. Sci. Comput. 39(5):B840–B859.Crossref, Google Scholar
• [30] Jain P, Meka R, Dhillon IS (2010) Guaranteed rank minimization via singular value projection. Adv. Neural Inform. Processing Systems 23:937–945.Google Scholar
• [31] Jain P, Netrapalli P, Sanghavi S (2013) Low-rank matrix completion using alternating minimization. Proc. 45th Annual ACM Sympos. Theory Comput. (ACM, New York), 665–674.Google Scholar
• [32] Journée M, Bach F, Absil PA, Sepulchre R (2010) Low-rank optimization on the cone of positive semidefinite matrices. SIAM J. Optim. 20(5):2327–2351.Crossref, Google Scholar
• [33] Lee JD, Panageas I, Piliouras G, Simchowitz M, Jordan MI, Recht B (2019) First-order methods almost always avoid strict saddle points. Math. Programming 176(1–2):311–337.Crossref, Google Scholar
• [34] Lee JM (2013) Introduction to Smooth Manifolds (Springer, Berlin).Google Scholar
• [35] Levin E, Kileel J, Boumal N (2022) The effect of smooth parametrizations on nonconvex optimization landscapes. Preprint, submitted July 7, https://doi.org/10.48550/arXiv.2207.03512.Google Scholar
• [36] Li X, Lu J, Arora R, Haupt J, Liu H, Wang Z, Zhao T (2019) Symmetry, saddle points, and global optimization landscape of nonconvex matrix factorization. IEEE Trans. Inform. Theory 65(6):3489–3514.Crossref, Google Scholar
• [37] Luo Y, Li X, Zhang AR (2021) Nonconvex factorization and manifold formulations are almost equivalent in low-rank matrix optimization. Preprint, submitted August 3, https://doi.org/10.48550/arXiv.2108.01772.Google Scholar
• [38] Luo Y, Huang W, Li X, Zhang AR (2020) Recursive importance sketching for rank constrained least squares: Algorithms and high-order convergence. Preprint, submitted November 17, https://doi.org/10.48550/arXiv.2011.08360.Google Scholar
• [39] Ma C, Wang K, Chi Y, Chen Y (2019) Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution. Foundations Comput. Math. 20:451–632.Crossref, Google Scholar
• [40] Massart E, Absil PA (2020) Quotient geometry with simple geodesics for the manifold of fixed-rank positive-semidefinite matrices. SIAM J. Matrix Anal. Appl. 41(1):171–198.Crossref, Google Scholar
• [41] Maunu T, Zhang T, Lerman G (2019) A well-tempered landscape for non-convex robust subspace recovery. J. Machine Learning Res. 20:1–59.Google Scholar
• [42] Meyer G (2011) Geometric optimization algorithms for linear regression on fixed-rank matrices. Unpublished doctoral dissertation, Université de Liège, Belgium.Google Scholar
• [43] Meyer G, Bonnabel S, Sepulchre R (2011) Linear regression under fixed-rank constraints: A Riemannian approach. Proc. 28th Internat. Conf. Machine Learning (Omnipress, Madison, WI), 545–552.Google Scholar
• [44] Meyer G, Bonnabel S, Sepulchre R (2011) Regression on fixed-rank positive semidefinite matrices: A Riemannian approach. J. Machine Learning Res. 12:593–625.Google Scholar
• [45] Mishra B, Sepulchre R (2016) Riemannian preconditioning. SIAM J. Optim. 26(1):635–660.Crossref, Google Scholar
• [46] Mishra B, Apuroop KA, Sepulchre R (2012) A Riemannian geometry for low-rank matrix completion. Preprint, submitted November 7, https://doi.org/10.48550/arXiv.1211.1550.Google Scholar
• [47] Mishra B, Meyer G, Sepulchre R (2011) Low-rank optimization for distance matrix completion. Proc. 50th IEEE Conf. Decision Control Eur. Control Conf. (IEEE, Piscataway, NJ), 4455–4460.Google Scholar
• [48] Mishra B, Meyer G, Bach F, Sepulchre R (2013) Low-rank optimization with trace norm penalty. SIAM J. Optim. 23(4):2124–2149.Crossref, Google Scholar
• [49] Mishra B, Meyer G, Bonnabel S, Sepulchre R (2014) Fixed-rank matrix factorizations and Riemannian low-rank optimization. Comput. Statist. 29(3–4):591–621.Crossref, Google Scholar
• [50] Ngo T, Saad Y (2012) Scaled gradients on Grassmann manifolds for matrix completion. Adv. Neural Inform. Processing Systems 25:1412–1420.Google Scholar
• [51] Petersen P (2006) Riemannian Geometry (Springer, Berlin).Google Scholar
• [52] Recht B, Fazel M, Parrilo PA (2010) Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52(3):471–501.Crossref, Google Scholar
• [53] Shalit U, Weinshall D, Chechik G (2012) Online learning in the embedded manifold of low-rank matrices. J. Machine Learning Res. 13:429–458.Google Scholar
• [54] Sun J, Qu Q, Wright J (2018) A geometric analysis of phase retrieval. Foundations Comput. Math. 18(5):1131–1198.Crossref, Google Scholar
• [55] Sun R, Luo ZQ (2015) Guaranteed matrix completion via nonconvex factorization. Proc. 56th IEEE Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 270–289.Google Scholar
• [56] Sun Y, Flammarion N, Fazel M (2019) Escaping from saddle points on Riemannian manifolds. Adv. Neural Inform. Processing Systems 32:7276–7286.Google Scholar
• [57] Tong T, Ma C, Chi Y (2021) Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent. J. Machine Learning Res. 22(150):1–63.Google Scholar
• [58] Tu S, Boczar R, Simchowitz M, Soltanolkotabi M, Recht B (2016) Low-rank solutions of linear matrix equations via Procrustes flow. Proc. Machine Learning Res. 48:964–973.Google Scholar
• [59] Uschmajew A, Vandereycken B (2020) On critical points of quadratic low-rank matrix optimization problems. IMA J. Numer. Anal. 40(4):2626–2651.Crossref, Google Scholar
• [60] Vandereycken B (2013) Low-rank matrix completion by Riemannian optimization. SIAM J. Optim. 23(2):1214–1236.Crossref, Google Scholar
• [61] Vandereycken B, Vandewalle S (2010) A Riemannian optimization approach for computing low-rank solutions of Lyapunov equations. SIAM J. Matrix Anal. Appl. 31(5):2553–2579.Crossref, Google Scholar
• [62] Vandereycken B, Absil PA, Vandewalle S (2013) A Riemannian geometry with complete geodesics for the set of positive semidefinite matrices of fixed rank. IMA J. Numer. Anal. 33(2):481–514.Crossref, Google Scholar
• [63] Wei K, Cai JF, Chan TF, Leung S (2016) Guarantees of Riemannian optimization for low rank matrix recovery. SIAM J. Matrix Anal. Appl. 37(3):1198–1222.Crossref, Google Scholar
• [64] Zhang J, Fattahi S, Zhang RY (2021) Preconditioned gradient descent for over-parameterized nonconvex matrix factorization. Adv. Neural Inform. Processing Systems 34:5985–5996.Google Scholar
• [65] Zhang Y, Qu Q, Wright J (2020) From symmetry to geometry: Tractable nonconvex problems. Preprint, submitted July 14, https://doi.org/10.48550/arXiv.2007.06753.Google Scholar
• [66] Zheng S, Huang W, Vandereycken B, Zhang X (2022) Riemannian optimization using three different metrics for Hermitian PSD fixed-rank constraints: An extended version. Preprint, submitted April 16, https://doi.org/10.48550/arXiv.2204.07830.Google Scholar
• [67] Zhuo J, Kwon J, Ho N, Caramanis C (2021) On the computational and statistical complexity of over-parameterized matrix sensing. Preprint, submitted January 27, https://doi.org/10.48550/arXiv.2102.02756.Google Scholar