Low-Rank Optimization Methods Based on Projected Projected-Gradient Descent That Accumulate at Bouligand Stationary Points

References

• [1] Abernethy J, Bach F, Evgeniou T, Vert JP (2009) A new approach to collaborative filtering: Operator estimation with spectral regularization. J. Machine Learn. Res. 10(29):803–826.Google Scholar
• [2] Absil PA, Mahony R, Sepulchre R (2008) Optimization Algorithms on Matrix Manifolds (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• [3] Arbarello E, Cornalba M, Griffiths PA, Harris J (1985) Geometry of Algebraic Curves: Volume I (Springer, New York).Crossref, Google Scholar
• [4] Boţ RI, Dao MN, Li G (2022) Extrapolated proximal subgradient algorithms for nonconvex and nonsmooth fractional programs. Math. Oper. Res. 47(3):2415–2443.Link, Google Scholar
• [5] Bruns W, Vetter U (1988) Determinantal Rings (Springer, Berlin).Crossref, Google Scholar
• [6] Burer S, Monteiro R (2003) A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Programming 95(2):329–357.Crossref, Google Scholar
• [7] Burer S, Monteiro R (2005) Local minima and convergence in low-rank semidefinite programming. Math. Program. 103(3):427–444.Crossref, Google Scholar
• [8] Carlsson M, Gerosa D, Olsson C (2022) An unbiased approach to low rank recovery. SIAM J. Optim. 32(4):2969–2996.Crossref, Google Scholar
• [9] 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
• [10] Cohen E, Hallak N, Teboulle M (2022) A dynamic alternating direction of multipliers for nonconvex minimization with nonlinear functional equality constraints. J. Optim. Theory Appl. 193:324–353.Crossref, Google Scholar
• [11] Cui Y, Pang JS (2021) Modern Nonconvex Nondifferentiable Optimization (SIAM, Philadelphia).Crossref, Google Scholar
• [12] De Marchi A (2023) Proximal gradient methods beyond monotony. J. Nonsmooth Anal. Optim. 4.Google Scholar
• [13] Demmel J (2000) Singular value decomposition. Bai Z, Demmel J, Dongarra J, Ruhe A, van der Vorst H, eds. Templates for the Solution of Algebraic Eigenvalue Problems (SIAM, Philadelphia), 135–147.Crossref, Google Scholar
• [14] Ding L, Chen Y (2020) Leave-one-out approach for matrix completion: Primal and dual analysis. IEEE Trans. Inform. Theory 66(11):7274–7301.Crossref, Google Scholar
• [15] Ding L, Drusvyatskiy D, Fazel M, Harchaoui Z (2024) Flat minima generalize for low-rank matrix recovery. Inform. Inference 13(2):iaae009.Crossref, Google Scholar
• [16] Eckart C, Young G (1936) The approximation of one matrix by another of lower rank. Psychometrika 1(3):211–218.Crossref, Google Scholar
• [17] Facchinei F, Kungurtsev V, Lampariello L, Scutari G (2021) Ghost penalties in nonconvex constrained optimization: Diminishing stepsizes and iteration complexity. Math. Oper. Res. 46(2):595–627.Link, Google Scholar
• [18] Feppon F, Lermusiaux PFJ (2018) A geometric approach to dynamical model order reduction. SIAM J. Matrix Anal. Appl. 39(1):510–538.Crossref, Google Scholar
• [19] Freund RM, Grigas P, Mazumder R (2017) An extended Frank–Wolfe method with “in-face” directions, and its application to low-rank matrix completion. SIAM J. Optim. 27(1):319–346.Crossref, Google Scholar
• [20] Gao B, Absil PA (2022) A Riemannian rank-adaptive method for low-rank matrix completion. Comput. Optim. Appl. 81(1):67–90.Crossref, Google Scholar
• [21] Gillis N, Glineur F (2011) Low-rank matrix approximation with weights or missing data is NP-hard. SIAM J. Matrix Anal. Appl. 32(4):1149–1165.Crossref, Google Scholar
• [22] Goldfarb D, Ma S (2011) Convergence of fixed-point continuation algorithms for matrix rank minimization. Foundations Comput. Math. 11(2):183–210.Crossref, Google Scholar
• [23] Golub GH, Van Loan CF (2013) Matrix Computations, 4th ed. (Johns Hopkins University Press, Baltimore).Crossref, Google Scholar
• [24] Ha W, Liu H, Barber RF (2020) An equivalence between critical points for rank constraints versus low-rank factorizations. SIAM J. Optim. 30(4):2927–2955.Crossref, Google Scholar
• [25] Hackbusch W (2019) Tensor Spaces and Numerical Tensor Calculus, 2nd ed. (Springer, Cham, Switzerland).Crossref, Google Scholar
• [26] Harris J (1992) Algebraic Geometry: A First Course (Springer, New York).Crossref, Google Scholar
• [27] Horn RA, Johnson CR (2012) Matrix Analysis, 2nd ed. (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [28] Hosseini S, Uschmajew A (2019) A gradient sampling method on algebraic varieties and application to nonsmooth low-rank optimization. SIAM J. Optim. 29(4):2853–2880.Crossref, Google Scholar
• [29] Hosseini S, Luke DR, Uschmajew A (2019) Tangent and normal cones for low-rank matrices. Hosseini S, Mordukhovich B, Uschmajew A, eds. Nonsmooth Optimization and Its Applications (Birkhäuser, Cham, Switzerland), 45–53.Crossref, Google Scholar
• [30] Jain P, Meka R, Dhillon I (2010) Guaranteed rank minimization via singular value projection. Lafferty J, Williams C, Shawe-Taylor J, Zemel R, Culotta A, eds. Adv. Neural Inform. Processing Systems, vol. 23 (Curran Associates, Inc., Red Hook, NY), 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. (Association for Computing Machinery, New York), 665–674.Google Scholar
• [32] Jia X, Kanzow C, Mehlitz P, Wachsmuth G (2023) An augmented Lagrangian method for optimization problems with structured geometric constraints. Math. Programming 199:1365–1415.Crossref, Google Scholar
• [33] 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
• [34] Kanzow C, Mehlitz P (2022) Convergence properties of monotone and nonmonotone proximal gradient methods revisited. J. Optim. Theory Appl. 195(2):624–646.Crossref, Google Scholar
• [35] Lakshmibai V, Brown J (2015) The Grassmannian Variety: Geometric and Representation-Theoretic Aspects (Springer, New York).Google Scholar
• [36] Lee JM (2003) Introduction to Smooth Manifolds, 1st ed. (Springer, New York).Crossref, Google Scholar
• [37] Lee JM (2018) Introduction to Riemannian Manifolds, 2nd ed. (Springer, Cham, Switzerland).Crossref, Google Scholar
• [38] Levin E, Kileel J, Boumal N (2023) Finding stationary points on bounded-rank matrices: A geometric hurdle and a smooth remedy. Math. Programming 199:831–864.Crossref, Google Scholar
• [39] Levin E, Kileel J, Boumal N (2025) The effect of smooth parametrizations on nonconvex optimization landscapes. Math. Programming 209:63–111.Crossref, Google Scholar
• [40] Li X, Luo Z (2023) Normal cones intersection rule and optimality analysis for low-rank matrix optimization with affine manifolds. SIAM J. Optim. 33(3):1333–1360.Crossref, Google Scholar
• [41] Li G, Pong TK (2015) Global convergence of splitting methods for nonconvex composite optimization. SIAM J. Optim. 25(4):2434–2460.Crossref, Google Scholar
• [42] Li J, So AMC, Ma WK (2020) Understanding notions of stationarity in nonsmooth optimization: A guided tour of various constructions of subdifferential for nonsmooth functions. IEEE Signal Processing Magazine 37(5):18–31.Crossref, Google Scholar
• [43] Li X, Song W, Xiu N (2019) Optimality conditions for rank-constrained matrix optimization. J. Oper. Res. Soc. China 7(2):285–301.Crossref, Google Scholar
• [44] Liu H, Barber RF (2020) Between hard and soft thresholding: Optimal iterative thresholding algorithms. Inform. Inference 9(4):899–933.Crossref, Google Scholar
• [45] Luenberger DG, Ye Y (2021) Linear and Nonlinear Programming, 5th ed. (Springer, Cham, Switzerland).Crossref, Google Scholar
• [46] Nesterov Y (2018) Lectures on Convex Optimization, 2nd ed. (Springer, Cham, Switzerland).Crossref, Google Scholar
• [47] Nguyen LT, Kim J, Shim B (2019) Low-rank matrix completion: A contemporary survey. IEEE Access 7:94215–94237.Crossref, Google Scholar
• [48] Olikier G, Absil PA (2022) On the continuity of the tangent cone to the determinantal variety. Set-Valued Var. Anal. 30:769–788.Crossref, Google Scholar
• [49] Olikier G, Absil PA (2023) An apocalypse-free first-order low-rank optimization algorithm with at most one rank reduction attempt per iteration. SIAM J. Matrix Anal. Appl. 44(3):1421–1435.Crossref, Google Scholar
• [50] Olikier G, Waldspurger I (2025) Projected gradient descent accumulates at Bouligand stationary points. SIAM J. Optim. 35(2):1004–1029.Crossref, Google Scholar
• [51] Olikier G, Gallivan KA, Absil PA (2022) An apocalypse-free first-order low-rank optimization algorithm. Preprint, submitted January 11, https://arxiv.org/abs/2201.03962v1.Google Scholar
• [52] Olikier G, Uschmajew A, Vandereycken B (2025) Gauss–Southwell type descent methods for low-rank matrix optimization. J. Optim. Theory Appl. 206:6.Crossref, Google Scholar
• [53] Olikier G, Mlinarić P, Absil PA, Uschmajew A (2026) The tangent cone to the real determinantal variety: Various expressions and a proof. Set-Valued Var. Anal. 34(8).Google Scholar
• [54] Pang JS, Razaviyayn M, Alvarado A (2017) Computing B-stationary points of nonsmooth DC programs. Math. Oper. Res. 42(1):95–118.Link, Google Scholar
• [55] 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.Crossref, Google Scholar
• [56] Pauwels E (2024) A note on stationarity in constrained optimization. Preprint, submitted February 15, https://arxiv.org/abs/2402.09831.Google Scholar
• [57] Polak E (1971) Computational Methods in Optimization: A Unified Approach (Academic Press, New York).Google Scholar
• [58] Rebjock Q, Boumal N (2024) Optimization over bounded-rank matrices through a desingularization enables joint global and local guarantees. Preprint, submitted June 20, https://arxiv.org/abs/2406.14211.Google Scholar
• [59] Rockafellar RT, Wets RJB (1998) Variational Analysis, corrected 3rd printing 2009 (Springer, Berlin).Crossref, Google Scholar
• [60] Scheel H, Scholtes S (2000) Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity. Math. Oper. Res. 25(1):1–22.Link, Google Scholar
• [61] Schneider R, Uschmajew A (2015) Convergence results for projected line-search methods on varieties of low-rank matrices via Łojasiewicz inequality. SIAM J. Optim. 25(1):622–646.Crossref, Google Scholar
• [62] Srebro N, Jaakkola T (2003) Weighted low-rank approximations. Fawcett T, Mishra N, eds. Proc. 20th Internat. Conf. Machine Learn. (AAAI Press, Palo Alto, CA), 720–727.Google Scholar
• [63] Tanner J, Wei K (2013) Normalized iterative hard thresholding for matrix completion. SIAM J. Sci. Comput. 35(5):S104–S125.Crossref, Google Scholar
• [64] Tong T, Ma C, Chi Y (2021) Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent. J. Machine Learn. Res. 22(150):1–63.Google Scholar
• [65] Tsakiris MC (2024) Results on the algebraic matroid of the determinantal variety. Trans. Amer. Math. Soc. 377(1):731–751.Google Scholar
• [66] Uschmajew A, Vandereycken B (2015) Greedy rank updates combined with Riemannian descent methods for low-rank optimization. 2015 Internat. Conf Sampling Theory Appl. (IEEE, Piscataway, NJ), 420–424.Google Scholar
• [67] Uschmajew A, Vandereycken B (2020) Geometric methods on low-rank matrix and tensor manifolds. Grohs P, Holler M, Weinmann A, eds. Handbook of Variational Methods for Nonlinear Geometric Data (Springer, Cham, Switzerland), 261–313.Crossref, Google Scholar
• [68] 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
• [69] Vandereycken B (2013) Low-rank matrix completion by Riemannian optimization. SIAM J. Optim. 23(2):1214–1236.Crossref, Google Scholar
• [70] Wang Y, Yin W, Zeng J (2019) Global convergence of ADMM in nonconvex nonsmooth optimization. J. Sci. Comput. 78:29–63.Crossref, Google Scholar
• [71] 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
• [72] Yang Y, Feng Y, Suykens JAK (2018) Correntropy based matrix completion. Entropy 20(3):171.Crossref, Google Scholar
• [73] Zhang RY (2025) Sharp global guarantees for nonconvex low-rank recovery in the noisy overparameterized regime. SIAM J. Optim. 35(3):2128–2154.Crossref, Google Scholar
• [74] Zhou X, Yang C, Zhao H, Yu W (2015) Low-rank modeling and its applications in image analysis. ACM Comput. Surveys 47(2).Crossref, Google Scholar
• [75] 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.Crossref, Google Scholar
• [76] 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.Crossref, Google Scholar