Help
Cart
Skip main navigation

Available Issues

February 19, 2019 - May 1, 2026

Available Issues

February 19, 2019 - May 1, 2026

Geometric Analysis of Noisy Low-Rank Matrix Recovery in the Exact Parametrized and the Overparametrized Regimes

Published Online:14 Apr 2023https://doi.org/10.1287/ijoo.2023.0090

References

  • Amit Y, Fink M, Srebro N, Ullman S (2007) Uncovering shared structures in multiclass classification. Proc. 24th Internat. Conf. on Machine Learn. (ICML, San Diego), 17–24.Google Scholar
  • Bhojanapalli S, Neyshabur B, Srebro N (2016) Global optimality of local search for low rank matrix recovery. Adv. Neural Inform. Processing Systems 29:3880–3888.Google Scholar
  • Bi Y, Lavaei J (2020) Global and local analyses of nonlinear low-rank matrix recovery problems. Preprint, submitted October 9, https://arxiv.org/abs/2010.04349.Google Scholar
  • Bi Y, Zhang H, Lavaei J (2021) Local and global linear convergence of general low-rank matrix recovery problems. Preprint, submitted April 27, https://arxiv.org/abs/2104.13348.Google Scholar
  • Boumal N (2016) Nonconvex phase synchronization. SIAM J. Optim. 26(4):2355–2377.Google Scholar
  • Burer S, Monteiro RD (2003) A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Programming 95(2):329–357.Google Scholar
  • Candès EJ, Plan Y (2011) Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements. IEEE Trans. Inform. Theory 57(4):2342–2359.Google Scholar
  • Candès EJ, Recht B (2009) Exact matrix completion via convex optimization. Foundations Comput. Math. 9(6):717–772.Google Scholar
  • Candès EJ, Tao T (2010) The power of convex relaxation: Near-optimal matrix completion. IEEE Trans. Inform. Theory 56(5):2053–2080.Google Scholar
  • 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.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
  • Ge R, Jin C, Zheng Y (2017) No spurious local minima in nonconvex low rank problems: A unified geometric analysis. Proc. 34th Internat. Conf. on Machine Learn., vol. 70 (PMLR, New York), 1233–1242.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
  • Jin M, Lavaei J, Sojoudi S, Baldick R (2021) Boundary defense against cyber threat for power system state estimation. IEEE Trans. Inform. Forensics Security 16:1752–1767.Google Scholar
  • Jin M, Molybog I, Mohammadi-Ghazi R, Lavaei J (2019b) Toward robust and scalable power system state estimation. Proc. IEEE 58th Conf. on Decision and Control (IEEE, Piscataway, NJ), 3245–3252.Google Scholar
  • Jin C, Ge R, Netrapalli P, Kakade SM, Jordan MI (2017) How to escape saddle points efficiently. Proc. 34th Internat. Conf. on Machine Learn., vol. 70 (PMLR, New York), 1724–1732.Google Scholar
  • Jin C, Netrapalli P, Ge R, Kakade SM, Jordan MI (2019a) A short note on concentration inequalities for random vectors with subGaussian norm. Preprint, submitted February 11, https://arxiv.org/abs/1902.03736.Google Scholar
  • Li Y, Ma T, Zhang H (2018) Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations. Proc. Conf. on Learn. Theory (PMLR, New York), 2–47.Google Scholar
  • Li X, Zhu Z, Man-Cho So A, Vidal R (2020) Nonconvex robust low-rank matrix recovery. SIAM J. Optim. 30(1):660–686.Google Scholar
  • Ma Z, Bi Y, Lavaei J, Sojoudi S (2022) Sharp restricted isometry property bounds for low-rank matrix recovery problems with corrupted measurements. Proc. AAAI Conf. Artificial Intelligence, vol. 36, 7672–7681.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
  • Park D, Kyrillidis A, Carmanis C, Sanghavi S (2017) Non-square matrix sensing without spurious local minima via the Burer–Monteiro approach. Proc. 20th Internat. Conf. on Artificial Intelligence and Statist., vol. 54 (PMLR, New York), 65–74.Google Scholar
  • 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.Google Scholar
  • Rennie JD, Srebro N (2005) Fast maximum margin matrix factorization for collaborative prediction. Proc. 22nd Internat. Conf. on Machine Learn. (ICML, San Diego), 713–719.Google Scholar
  • Shechtman Y, Eldar YC, Cohen O, Chapman HN, Miao J, Segev M (2015) Phase retrieval with application to optical imaging: A contemporary overview. IEEE Signal Processing Magazine 32(3):87–109.Google Scholar
  • Singer A (2011) Angular synchronization by eigenvectors and semidefinite programming. Appl. Comput. Harmonic Anal. 30(1):20–36.Google Scholar
  • Stöger D, Soltanolkotabi M (2021) Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction. Adv. Neural Inform. Processing Systems 34:23831–23843.Google Scholar
  • Wang L, Zhang X, Gu Q (2017) A unified computational and statistical framework for nonconvex low-rank matrix estimation. Proc. 20th Internat. Conf. on Artificial Intelligence and Statist., vol. 54 (PMLR, New York), 981–990.Google Scholar
  • Zhang RY (2021) Sharp global guarantees for nonconvex low-rank matrix recovery in the overparameterized regime. Preprint, submitted April 21, https://arxiv.org/abs/2104.10790.Google Scholar
  • Zhang G, Zhang RY (2020) How many samples is a good initial point worth in low-rank matrix recovery? Adv. Neural Inform. Processing Systems 33:12583–12592.Google Scholar
  • Zhang H, Bi Y, Lavaei J (2021) General low-rank matrix optimization: Geometric analysis and sharper bounds. Adv. Neural Inform. Processing Systems.Google Scholar
  • Zhang Y, Madani R, Lavaei J (2017) Conic relaxations for power system state estimation with line measurements. IEEE Trans. Control Network Systems 5(3):1193–1205.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 RY, Josz C, Sojoudi S, Lavaei J (2018a) How much restricted isometry is needed in nonconvex matrix recovery? Adv. Neural Inform. Processing Systems 31:5591–5602.Google Scholar
  • Zhang X, Wang L, Yu Y, Gu Q (2018b) A primal-dual analysis of global optimality in nonconvex low-rank matrix recovery. Proc. 35th Internat. Conf. on Machine Learn., vol. 80 (PMLR, New York), 5862–5871.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
  • 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://arxiv.org/abs/2102.02756.Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree