Nonconvex Factorization and Manifold Formulations Are Almost Equivalent in Low-Rank Matrix Optimization

References

• Absil PA, Baker CG, Gallivan KA (2007) Trust-region methods on Riemannian manifolds. Foundations Comput. Math. 7(3):303–330.Google Scholar
• Absil PA, Mahony R, Sepulchre R (2009) Optimization Algorithms on Matrix Manifolds (Princeton University Press, Princeton, NJ).Google Scholar
• Ahn K, Suarez F (2021) Riemannian perspective on matrix factorization. Preprint, submitted February 1, https://arxiv.org/abs/2102.00937.Google Scholar
• Bauch J, Nadler B, Zilber P (2021) Rank 2r iterative least squares: Efficient recovery of ill-conditioned low rank matrices from few entries. SIAM J. Math. Data Sci. 3(1):439–465.Google Scholar
• Bhatia R (2013) Matrix Analysis, vol. 169 (Springer Science & Business Media, New York).Google Scholar
• Bhojanapalli S, Kyrillidis A, Sanghavi S (2016a) Dropping convexity for faster semi-definite optimization. Feldman V, Rakhlin A, Shamir O, eds. 29th Annual Conf. Learn. Theory, Proceedings of Machine Learning Research (PMLR, New York), 530–582.Google Scholar
• Bhojanapalli S, Neyshabur B, Srebro N (2016b) Global optimality of local search for low rank matrix recovery. Lee D, Sugiyama M, Luxburg U, Guyon I, Garnett R, eds. Proc. 30th Internat. Conf. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 3880–3888.Google Scholar
• Bhojanapalli S, Boumal N, Jain P, Netrapalli P (2018) Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form. Bubeck S, Perchet V, Rigollet P, eds. Proc. 31st Conf. Learn. Theory, Proceedings of Machine Learning Research (PMLR, New York), 3243–3270.Google Scholar
• Bi S, Pan S, Sun D (2020) A multi-stage convex relaxation approach to noisy structured low-rank matrix recovery. Math. Programming Comput. 12(4):569–602.Google Scholar
• Boumal N (2023) An Introduction to Optimization on Smooth Manifolds (Cambridge University Press, Cambridge, UK).Google Scholar
• Boumal N, Absil PA (2011) RTRMC: A Riemannian trust-region method for low-rank matrix completion. Shawe-Taylor J, Zemel R, Bartlett P, Pereira F, Weinberger KQ, eds. Adv. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 406–414.Google Scholar
• Boumal N, Absil PA, Cartis C (2019) Global rates of convergence for nonconvex optimization on manifolds. IMA J. Numer. Anal. 39(1):1–33.Google Scholar
• Boumal N, Voroninski V, Bandeira AS (2020) Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs. Comm. Pure Appl. Math. 73(3):581–608.Google Scholar
• Burer S, Monteiro RD (2005) Local minima and convergence in low-rank semidefinite programming. Math. Programming 103(3):427–444.Google Scholar
• Cai JF, Wei K (2018a) Exploiting the structure effectively and efficiently in low-rank matrix recovery. Handbook Numer. Anal. 19:21–51.Google Scholar
• Cai JF, Wei K (2018b) Solving systems of phaseless equations via Riemannian optimization with optimal sampling complexity. Preprint, submitted September 8, https://arxiv.org/abs/1809.02773.Google Scholar
• Cai TT, Zhang A (2015) ROP: Matrix recovery via rank-one projections. Ann. Statist. 43(1):102–138.Google Scholar
• Candès EJ, Li X, Soltanolkotabi M (2015) Phase retrieval via Wirtinger flow: Theory and algorithms. IEEE Trans. Inform. Theory 61(4):1985–2007.Google Scholar
• Candès EJ, Strohmer T, Voroninski V (2013) Phaselift: Exact and stable signal recovery from magnitude measurements via convex programming. Comm. Pure Appl. Math. 66(8):1241–1274.Google Scholar
• Charisopoulos V, Chen Y, Davis D, Díaz M, Ding L, Drusvyatskiy D (2021) Low-rank matrix recovery with composite optimization: Good conditioning and rapid convergence. Foundations Comput. Math. 21(6):1505–1593.Google Scholar
• Chen Y, Candès EJ (2017) Solving random quadratic systems of equations is nearly as easy as solving linear systems. Comm. Pure Appl. Math. 70(5):822–883.Google Scholar
• Chen J, Li X (2019) Model-free nonconvex matrix completion: Local minima analysis and applications in memory-efficient kernel PCA. J. Machine Learn. Res. 20(142):1–39.Google Scholar
• Chen Y, Wainwright MJ (2015) Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees. Preprint, submitted September 10, https://arxiv.org/abs/1509.03025.Google Scholar
• Chen Y, Chi Y, Goldsmith AJ (2015) Exact and stable covariance estimation from quadratic sampling via convex programming. IEEE Trans. Inform. Theory 61(7):4034–4059.Google Scholar
• Chi Y, Lu YM, Chen Y (2019) Nonconvex optimization meets low-rank matrix factorization: An overview. IEEE Trans. Signal Processing 67(20):5239–5269.Google Scholar
• Clarke FH (1990) Optimization and Nonsmooth Analysis (SIAM, Philadelphia).Google Scholar
• Criscitiello C, Boumal N (2019) Efficiently escaping saddle points on manifolds. Wallach H, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox E, Garnett R, eds. Proc. 33rd Internat. Conf. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 7276–7286.Google Scholar
• Du SS, Hu W, Lee JD (2018) Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced. Bengio S, Wallach H, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Proc. 32nd Internat. Conf. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 382–393.Google Scholar
• Edelman A, Arias TA, Smith ST (1998) The geometry of algorithms with orthogonality constraints. SIAM J. Matrix Anal. Appl. 20(2):303–353.Google Scholar
• Fienup JR (1982) Phase retrieval algorithms: A comparison. Appl. Optics 21(15):2758–2769.Google Scholar
• Gao B, Absil PA (2022) A Riemannian rank-adaptive method for low-rank matrix completion. Comput. Optim. Appl. 81(1):67–90.Google Scholar
• Gao Y, Sun D (2010) A majorized penalty approach for calibrating rank constrained correlation matrix problems. Working paper, National University of Singapore, Singapore.Google Scholar
• Ge R, Jin C, Zheng Y (2017) No spurious local minima in nonconvex low rank problems: A unified geometric analysis. Precup D, Teh YW, eds. Proc. 34th Internat. Conf. Machine Learn., vol. 70 (JMLR), 1233–1242.Google Scholar
• Ge R, Huang F, Jin C, Yuan Y (2015) Escaping from saddle points-online stochastic gradient for tensor decomposition. Grünwald P, Hazan E, Kale S, eds. Proc. 28th Conf. Learn. Theory, vol. 40 (PMLR, New York), 797–842.Google Scholar
• 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.Google Scholar
• Han A, Gao J (2020) Escape saddle points faster on manifolds via perturbed Riemannian stochastic recursive gradient. Preprint, submitted October 28, https://arxiv.org/abs/2010.12191.Google Scholar
• Hardt M (2014) Understanding alternating minimization for matrix completion. 2014 IEEE 55th Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 651–660.Google Scholar
• Helmke U, Moore JB (2012) Optimization and Dynamical Systems (Springer Science & Business Media, New York).Google Scholar
• Hou TY, Li Z, Zhang Z (2021) Fast global convergence for low-rank matrix recovery via Riemannian gradient descent with random initialization. Preprint, submitted April 19, https://arxiv.org/abs/2012.15467.Google Scholar
• Hu J, Liu X, Wen ZW, Yuan YX (2020) A brief introduction to manifold optimization. J. Oper. Res. Soc. China 8(2):199–248.Google Scholar
• Huang W, Hand P (2018) Blind deconvolution by a steepest descent algorithm on a quotient manifold. SIAM J. Imaging Sci. 11(4):2757–2785.Google Scholar
• Jain P, Netrapalli P, Sanghavi S (2013) Low-rank matrix completion using alternating minimization. Precup D, Teh YW, eds. Proc. Forty-Fifth Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 665–674.Google Scholar
• Jin C, Ge R, Netrapalli P, Kakade SM, Jordan MI (2017) How to escape saddle points efficiently. Precup D, Teh YW, eds. Proc. 34th Internat. Conf. Machine Learn., vol. 70 (JMLR), 1724–1732.Google Scholar
• 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.Google Scholar
• Keshavan RH, Oh S, Montanari A (2010) Matrix completion from a few entries. IEEE Trans. Inform. Theory 56(6):2980–2998.Google Scholar
• Lee JM (2013) Smooth manifolds. Introduction to Smooth Manifolds, Graduate Texts in Mathematics, vol. 218 (Springer, New York), 1–31.Google Scholar
• 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.Google Scholar
• Li Z, Cai JF, Wei K (2019d) Toward the optimal construction of a loss function without spurious local minima for solving quadratic equations. IEEE Trans. Inform. Theory 66(5):3242–3260.Google Scholar
• Li Q, Zhu Z, Tang G (2019a) The non-convex geometry of low-rank matrix optimization. Inform. Inference 8(1):51–96.Google Scholar
• Li X, Ling S, Strohmer T, Wei K (2019b) Rapid, robust, and reliable blind deconvolution via nonconvex optimization. Appl. Comput. Harmonic Anal. 47(3):893–934.Google Scholar
• Li S, Li Q, Zhu Z, Tang G, Wakin MB (2020) The global geometry of centralized and distributed low-rank matrix recovery without regularization. IEEE Signal Processing Lett. 27:1400–1404.Google Scholar
• Li X, Lu J, Arora R, Haupt J, Liu H, Wang Z, Zhao T (2019c) Symmetry, saddle points, and global optimization landscape of nonconvex matrix factorization. IEEE Trans. Inform. Theory 65(6):3489–3514.Google Scholar
• Luo Y, Li X, Zhang AR (2024a) On geometric connections of embedded and quotient geometries in Riemannian fixed-rank matrix optimization. Math. Oper. Res. 49(2):782–825.Link, Google Scholar
• Luo Y, Huang W, Li X, Zhang A (2024b) Recursive importance sketching for rank constrained least squares: Algorithms and high-order convergence. Oper. Res. 72(1):237–256.Link, Google Scholar
• Ma C, Li Y, Chi Y (2021) Beyond procrustes: Balancing-free gradient descent for asymmetric low-rank matrix sensing. IEEE Trans. Signal Processing 69:867–877.Google Scholar
• Ma C, Wang K, Chi Y, Chen Y (2020) Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution. Foundations Comput. Math. 20(3):451–632.Google Scholar
• 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.Google Scholar
• Maunu T, Zhang T, Lerman G (2019) A well-tempered landscape for non-convex robust subspace recovery. J. Machine Learn. Res. 20(37):1–59.Google Scholar
• Meyer G, Bonnabel S, Sepulchre R (2011) Linear regression under fixed-rank constraints: A Riemannian approach. Getoor L, Scheffer T, eds. Proc. 28th Internat. Conf. Machine Learn. (Omnipress, Madison, WI), 545–552.Google Scholar
• Miao W, Pan S, Sun D (2016) A rank-corrected procedure for matrix completion with fixed basis coefficients. Math. Programming 159(1):289–338.Google Scholar
• Mishra B, Sepulchre R (2016) Riemannian preconditioning. SIAM J. Optim. 26(1):635–660.Google Scholar
• 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.Google Scholar
• Netrapalli P, Jain P, Sanghavi S (2013) Phase retrieval using alternating minimization. Burges CJ, Bottou L, Welling M, Ghahramani Z, Weinberger KQ, eds. Proc. 26th Internat. Conf. Neural Inform. Processing Systems, vol. 2 (Curran Associates Inc., Red Hook, NY), 2796–2804.Google Scholar
• O’Neill M, Wright SJ (2023) A line-search descent algorithm for strict saddle functions with complexity guarantees. J. Machine Learn. Res. 24(10):1–34.Google Scholar
• Park D, Kyrillidis A, Carmanis C, Sanghavi S (2017) Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach. Singh A, Zhu J, eds. Proc. 20th Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol. 54 (PMLR, New York), 65–74.Google Scholar
• Park D, Kyrillidis A, Caramanis C, Sanghavi S (2018) Finding low-rank solutions via nonconvex matrix factorization, efficiently and provably. SIAM J. Imaging Sci. 11(4):2165–2204.Google Scholar
• Paternain S, Mokhtari A, Ribeiro A (2019) A Newton-based method for nonconvex optimization with fast evasion of saddle points. SIAM J. Optim. 29(1):343–368.Google Scholar
• Sanghavi S, Ward R, White CD (2017) The local convexity of solving systems of quadratic equations. Results Math. 71(3–4):569–608.Google Scholar
• Sun R, Luo ZQ (2015) Guaranteed matrix completion via nonconvex factorization. 2015 IEEE 56th Annual Sympos. Foundations Comput. Sci. (FOCS) (IEEE), 270–289.Google Scholar
• Sun Y, Flammarion N, Fazel M (2019) Escaping from saddle points on Riemannian manifolds. Wallach H, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox E, Garnett R, eds. Proc. 33rd Internat. Conf. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY).Google Scholar
• Sun J, Qu Q, Wright J (2018) A geometric analysis of phase retrieval. Foundations Comput. Math. 18(5):1131–1198.Google Scholar
• Tong T, Ma C, Chi Y (2021a) Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent. J. Machine Learn. Res. 22(1):6639–6701.Google Scholar
• Tong T, Ma C, Chi Y (2021b) Low-rank matrix recovery with scaled subgradient methods: Fast and robust convergence without the condition number. IEEE Trans. Signal Processing 69:2396–2409.Google Scholar
• Tran-Dinh Q (2021) Extended Gauss-Newton and ADMM-Gauss-Newton algorithms for low-rank matrix optimization. J. Appl. Numer. Optim. 3(1):115–150.Google Scholar
• Tu S, Boczar R, Simchowitz M, Soltanolkotabi M, Recht B (2016) Low-rank solutions of linear matrix equations via Procrustes flow. Balcan M-F, Weinberger KQ, eds. Proc. 33rd Internat. Conf. Machine Learn., vol. 48 (JMLR), 964–973.Google Scholar
• Uschmajew A, Vandereycken B (2020) On critical points of quadratic low-rank matrix optimization problems. IMA J. Numer. Anal. 40(4):2626–2651.Google Scholar
• Vandereycken B (2013) Low-rank matrix completion by Riemannian optimization. SIAM J. Optim. 23(2):1214–1236.Google Scholar
• 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.Google Scholar
• Waldspurger I, d’Aspremont A, Mallat S (2015) Phase recovery, maxcut and complex semidefinite programming. Math. Programming 149(1–2):47–81.Google Scholar
• Wang G, Giannakis GB, Eldar YC (2017a) Solving systems of random quadratic equations via truncated amplitude flow. IEEE Trans. Inform. Theory 64(2):773–794.Google Scholar
• Wang L, Zhang X, Gu Q (2017b) A unified computational and statistical framework for nonconvex low-rank matrix estimation. Singh A, Zhu J, eds. Proc. 20th Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol. 54 (PMLR, New York), 981–990.Google Scholar
• 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.Google Scholar
• Wen Z, Yin W, Zhang Y (2012) Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm. Math. Programming Comput. 4(4):333–361.Google Scholar
• Yamakawa Y, Ikegami T, Fukuda EH, Yamashita N (2023) An equivalent nonlinear optimization model with triangular low-rank factorization for semidefinite programs. Optim. Methods Software 38(6):1296–1310.Google Scholar
• Ye T, Du SS (2024) Global convergence of gradient descent for asymmetric low-rank matrix factorization. Ranzato M, Beygelzimer A, Dauphin Y, Liang PS, Wortman Vaughan J, eds. Proc. 35th Internat. Conf. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 1429–1439.Google Scholar
• Zhang T, Yang Y (2018) Robust PCA by manifold optimization. J. Machine Learn. Res. 19(1):3101–3139.Google Scholar
• Zhang H, Bi Y, Lavaei J (2021) General low-rank matrix optimization: Geometric analysis and sharper bounds. Beygelzimer A, Dauphin Y, Liang P, Wortman Vaughan J, eds. Advances in Neural Information Processing Systems, vol. 34 (Curran Associates, Inc., Red Hook, NY), 27369–27380.Google Scholar
• Zhang Y, Qu Q, Wright J (2022) From symmetry to geometry: Tractable nonconvex problems. Preprint, submitted July 8, https://arxiv.org/abs/2007.06753.Google Scholar
• Zhang RY, Sojoudi S, Lavaei J (2019) Sharp restricted isometry bounds for the inexistence of spurious local minima in nonconvex matrix recovery. J. Machine Learn. Res. 20(114):1–34.Google Scholar
• Zhang X, Wang L, Yu Y, Gu Q (2018) A primal-dual analysis of global optimality in nonconvex low-rank matrix recovery. Dy J, Krause A, eds. Proc. 35th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 80 (PMLR, New York), 5862–5871.Google Scholar
• Zhao T, Wang Z, Liu H (2015) A nonconvex optimization framework for low rank matrix estimation. Cortes C, Lawrence N, Lee D, Sugiyama M, Garnett R, eds. Proc. 28th Internat. Conf. Neural Inform. Processing Systems, vol. 1 (MIT Press, Cambridge, MA), 559–567.Google Scholar
• Zheng Q, Lafferty J (2015) A convergent gradient descent algorithm for rank minimization and semidefinite programming from random linear measurements. Cortes C, Lawrence N, Lee D, Sugiyama M, Garnett R, eds. Proc. 28th Internat. Conf. Neural Inform. Processing Systems, vol. 1 (MIT Press, Cambridge, MA), 109–117.Google Scholar
• Zhou G, Huang W, Gallivan KA, Van Dooren P, Absil PA (2016) A Riemannian rank-adaptive method for low-rank optimization. Neurocomputing 192:72–80.Google Scholar
• Zhu Z, Li Q, Tang G, Wakin MB (2018) Global optimality in low-rank matrix optimization. IEEE Trans. Signal Processing 66(13):3614–3628.Google Scholar
• Zhu Z, Li Q, Tang G, Wakin MB (2021) The global optimization geometry of low-rank matrix optimization. IEEE Trans. Inform. Theory 67(2):1308–1331.Google Scholar