Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-Order Convergence

References

• Absil PA, Malick J (2012) Projection-like retractions on matrix manifolds. SIAM J. Optim. 22(1):135–158.Crossref, Google Scholar
• Absil PA, Mahony R, Sepulchre R (2008) Optimization Algorithms on Matrix Manifolds (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Ahmed A, Recht B, Romberg J (2013) Blind deconvolution using convex programming. IEEE Trans. Inform. Theory 60(3):1711–1732.Crossref, 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.Crossref, Google Scholar
• Bhojanapalli S, Neyshabur B, Srebro N (2016) Global optimality of local search for low rank matrix recovery. Adv. Neural Inform. Processing Systems 30:3873–3881.Google Scholar
• Boumal N, Absil PA (2011) RTRMC: A Riemannian trust-region method for low-rank matrix completion. Adv. Neural Inform. Processing Systems 24:406–414.Google Scholar
• Breiding P, Vannieuwenhoven N (2018) Convergence analysis of Riemannian Gauss–Newton methods and its connection with the geometric condition number. Appl. Math. Lett. 78:42–50.Crossref, 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.Crossref, Google Scholar
• Burke JV (1985) Descent methods for composite nondifferentiable optimization problems. Math. Programming 33(3):260–279.Crossref, Google Scholar
• Cai TT, Zhang A (2013) Sharp RIP bound for sparse signal and low-rank matrix recovery. Appl. Comput. Harmonic Anal. 35(1):74–93.Crossref, Google Scholar
• Cai TT, Zhang A (2014) Sparse representation of a polytope and recovery of sparse signals and low-rank matrices. IEEE Trans. Inform. Theory 60(1):122–132.Crossref, Google Scholar
• Cai TT, Zhang A (2015) ROP: Matrix recovery via rank-one projections. Ann. Statist. 43(1):102–138.Crossref, Google Scholar
• Cai TT, Zhou WX (2013) A max-norm constrained minimization approach to 1-bit matrix completion. J. Machine Learn. Res. 14(1):3619–3647.Google Scholar
• Candès EJ (2008) The restricted isometry property and its implications for compressed sensing. Comptes Rendus Mathematique 346(9–10):589–592.Crossref, 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.Crossref, 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.Crossref, 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.Crossref, 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.Crossref, 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.Crossref, 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.Crossref, 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.Crossref, 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.Crossref, Google Scholar
• Clarkson KL, Woodruff DP (2017) Low-rank approximation and regression in input sparsity time. J. ACM 63(6):1–45.Crossref, Google Scholar
• Davenport MA, Romberg J (2016) An overview of low-rank matrix recovery from incomplete observations. IEEE J. Selected Topics Signal Processing 10(4):608–622.Crossref, Google Scholar
• Dobriban E, Liu S (2019) Asymptotics for sketching in least squares regression. Adv. Neural Inform. Processing Systems 33:3675–3685.Google Scholar
• Drineas P, Magdon-Ismail M, Mahoney MW, Woodruff DP (2012) Fast approximation of matrix coherence and statistical leverage. J. Machine Learn. Res. 13:3475–3506.Google Scholar
• Duchi JC, Ruan F (2019) Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval. Inform. Inference 8(3):471–529.Crossref, Google Scholar
• Erdogdu MA, Montanari A (2015) Convergence rates of sub-sampled Newton methods. Adv. Neural Inform. Processing Systems 28:3052–3060.Google Scholar
• Fienup JR (1982) Phase retrieval algorithms: A comparison. Appl. Optics 21(15):2758–2769.Crossref, Google Scholar
• Fornasier M, Rauhut H, Ward R (2011) Low-rank matrix recovery via iteratively reweighted least squares minimization. SIAM J. Optim. 21(4):1614–1640.Crossref, Google Scholar
• Gao B, Xu Z (2017) Phaseless recovery using the Gauss–Newton method. IEEE Trans. Signal Processing 65(22):5885–5896.Crossref, 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. Machine Learn., 1233–1242.Google Scholar
• 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
• 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
• Hardt M (2014) Understanding alternating minimization for matrix completion. 2014 IEEE 55th Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 651–660.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.Crossref, Google Scholar
• Huang W, Absil PA, Gallivan KA (2017a) Intrinsic representation of tangent vectors and vector transports on matrix manifolds. Numerische Mathematik 136(2):523–543.Crossref, Google Scholar
• Huang W, Gallivan KA, Zhang X (2017b) Solving phaselift by low-rank Riemannian optimization methods for complex semidefinite constraints. SIAM J. Sci. Comput. 39(5):B840–B859.Crossref, Google Scholar
• Jain P, Meka R, Dhillon IS (2010) Guaranteed rank minimization via singular value projection. Adv. Neural Inform. Processing Systems 23:937–945.Google Scholar
• 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
• Jiang K, Sun D, Toh KC (2014) A partial proximal point algorithm for nuclear norm regularized matrix least squares problems. Math. Programming Comput. 6(3):281–325.Crossref, Google Scholar
• Keshavan RH, Oh S, Montanari A (2009) Matrix completion from a few entries. 2009 IEEE Internat. Sympos. Inform. Theory (IEEE, Piscataway, NJ), 324–328.Google Scholar
• Koltchinskii V, Lounici K, Tsybakov AB (2011) Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion. Ann. Statist. 39(5):2302–2329.Crossref, Google Scholar
• Kümmerle C, Sigl J (2018) Harmonic mean iteratively reweighted least squares for low-rank matrix recovery. J. Machine Learn. Res. 19(1):1815–1863.Google Scholar
• Lange K (2010) Numerical Analysis for Statisticians (Springer Science & Business Media).Crossref, Google Scholar
• Lee JM (2013) Introduction to Smooth Manifolds (Springer).Google Scholar
• Lee JD, Recht B, Srebro N, Tropp J, Salakhutdinov RR (2010) Practical large-scale optimization for max-norm regularization. Adv. Neural Inform. Processing Systems 23:1297–1305.Google Scholar
• Lewis AS, Wright SJ (2016) A proximal method for composite minimization. Math. Programming 158(1–2):501–546.Crossref, Google Scholar
• Li Q, Zhu Z, Tang G (2019a) The non-convex geometry of low-rank matrix optimization. Inform. Inference 8(1):51–96.Crossref, 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.Crossref, Google Scholar
• Li X, Zhu Z, Man-Cho So A, Vidal R (2020a) Nonconvex robust low-rank matrix recovery. SIAM J. Optim. 30(1):660–686.Crossref, Google Scholar
• Li Y, Chi Y, Zhang H, Liang Y (2020b) Non-convex low-rank matrix recovery with arbitrary outliers via median-truncated gradient descent. Inform. Inference 9(2):289–325.Crossref, Google Scholar
• Luo Y, Zhang AR (2021) Low-rank tensor estimation via Riemannian Gauss-Newton: Statistical optimality and second-order convergence. Preprint, submitted April 24, https://arxiv.org/abs/2104.12031.Google Scholar
• 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
• Mahoney MW (2011) Randomized algorithms for matrices and data. Foundations Trends Machine Learn. 3(2):123–224.Google Scholar
• Meyer G, Bonnabel S, Sepulchre R (2011) Linear regression under fixed-rank constraints: A Riemannian approach. Proc. 28th Internat. Conf. Machine Learn. (ACM, New York), 545–552.Google Scholar
• Miao W, Pan S, Sun D (2016) A rank-corrected procedure for matrix completion with fixed basis coefficients. Math. Program. 159(1):289–338.Crossref, 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.Crossref, Google Scholar
• Mohan K, Fazel M (2012) Iterative reweighted algorithms for matrix rank minimization. J. Machine. Learn. Res. 13(1):3441–3473.Google Scholar
• Netrapalli P, Jain P, Sanghavi S (2013) Phase retrieval using alternating minimization. Adv. Neural Inform. Processing Systems 26:2796–2804.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.Crossref, Google Scholar
• Pilanci M, Wainwright MJ (2016) Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares. J. Machine Learn. Res. 17(1):1842–1879.Google Scholar
• Pilanci M, Wainwright MJ (2017) Newton sketch: A near linear-time optimization algorithm with linear-quadratic convergence. SIAM J. Optim. 27(1):205–245.Crossref, Google Scholar
• Raskutti G, Mahoney MW (2016) A statistical perspective on randomized sketching for ordinary least-squares. J. Machine Learn. Res. 17(1):7508–7538.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.Crossref, 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.Crossref, 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.Crossref, Google Scholar
• Song Z, Woodruff DP, Zhong P (2017) Low rank approximation with entrywise l1-norm error. Proc. 49th Annual ACM Sympos. Theory Comput. (ACM, New York), 688–701.Google Scholar
• Sun R, Luo ZQ (2016) Guaranteed matrix completion via non-convex factorization. IEEE Trans. Inform. Theory 62(11):6535–6579.Crossref, Google Scholar
• Tanner J, Wei K (2013) Normalized iterative hard thresholding for matrix completion. SIAM J. Sci. Comput. 35(5):S104–S125.Crossref, Google Scholar
• Toh KC, Yun S (2010) An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems. Pacific J. Optim. 6(3):615–640.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(150):1–63.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.Crossref, Google Scholar
• Tran-Dinh Q (2021) Extended Gauss-Newton and ADMM-Gauss-Newton algorithms for low-rank matrix optimization. J. Appl. Numerical 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. Internat. Conf. Machine Learn., 964–973.Google Scholar
• Uschmajew A, Vandereycken B (2020) On critical points of quadratic low-rank matrix optimization problems. IMA J. Numerical Anal. 40(4):2626–2651.Crossref, Google Scholar
• Vandereycken B (2013) Low-rank matrix completion by Riemannian optimization. SIAM J. Optim. 23(2):1214–1236.Crossref, 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.Crossref, Google Scholar
• Waldspurger I, d’Aspremont A, Mallat S (2015) Phase recovery, maxcut and complex semidefinite programming. Math. Programming 149(1–2):47–81.Crossref, 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.Crossref, Google Scholar
• Wang L, Zhang X, Gu Q (2017c) A unified computational and statistical framework for nonconvex low-rank matrix estimation. Proc. 20th Internat. Conf. Artificial Intelligence Statist. (PMLR, New York), 981–990.Google Scholar
• Wang J, Lee JD, Mahdavi M, Kolar M, Srebro N (2017b) Sketching meets random projection in the dual: A provable recovery algorithm for big and high-dimensional data. Electronic J. Statist. 11(2):4896–4944.Crossref, 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.Crossref, 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.Crossref, Google Scholar
• Woodruff DP (2014) Sketching as a tool for numerical linear algebra. Foundations Trends Theoretical Comput. Sci. 10(1–2):1–157.Crossref, 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 AR, Luo Y, Raskutti G, Yuan M (2020) ISLET: Fast and optimal low-rank tensor regression via importance sketching. SIAM J. Math. Data Sci. 2(2):444–479.Crossref, Google Scholar
• Zhao T, Wang Z, Liu H (2015) A nonconvex optimization framework for low rank matrix estimation. Adv. Neural Inform. Processing Systems 28:559–567.Google Scholar
• Zheng Q, Lafferty J (2015) A convergent gradient descent algorithm for rank minimization and semidefinite programming from random linear measurements. Adv. Neural Inform. Processing Systems 28:109–117.Google Scholar
• Zheng Y, Liu G, Sugimoto S, Yan S, Okutomi M (2012) Practical low-rank matrix approximation under robust l1-norm. 2012 IEEE Conf. Comput. Vision Pattern Recognition (IEEE, Piscataway, NJ), 1410–1417.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.Crossref, 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.Crossref, Google Scholar