Nonconvex Low-Rank Tensor Completion from Noisy Data

References

• Abbe E, Fan J, Wang K, Zhong Y (2017) Entrywise eigenvector analysis of random matrices with low expected rank. Ann. Statist. 48(3):1452–1474.Google Scholar
• Anandkumar A, Ge R, Janzamin M (2014b) Guaranteed non-orthogonal tensor decomposition via alternating rank-1 updates. Preprint, submitted February 21, https://arxiv.org/abs/1402.5180.Google Scholar
• Anandkumar A, Ge R, Hsu D, Kakade SM, Telgarsky M (2014a) Tensor decompositions for learning latent variable models. J. Machine Learn. Res. 15(1):2773–2832.Google Scholar
• Ashraphijuo M, Wang X (2017) Fundamental conditions for low-CP-rank tensor completion. J. Machine Learn. Res. 18(1):2116–2145.Google Scholar
• Barak B, Moitra A (2016) Noisy tensor completion via the sum-of-squares hierarchy. Proc. 29th Annual Conf. Learning Theory, New York, June 23–26, 417–445.Google Scholar
• Bubeck S (2015) Convex optimization: Algorithms and complexity. Foundations Trends Machine Learning 8(3–4):231–357.Crossref, Google Scholar
• Cai C, Li G, Poor HV, Chen Y (2019) Nonconvex low-rank tensor completion from noisy data. Wallach H, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox E, Garnett R, eds. Adv. Neural Inform. Processing Systems 32 (Curran Associates, Red Hook, NY), 1863–1874.Google Scholar
• Cai C, Li G, Chi Y, Poor HV, Chen Y (2021) Subspace estimation from unbalanced and incomplete data matrices: ℓ2,∞ statistical guarantees. Ann. Statist. 49(2):944–967.Crossref, Google Scholar
• Candès E, Recht B (2009) Exact matrix completion via convex optimization. Foundations Comput. Math. 9(6):717–772.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
• 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, Chi Y (2014) Robust spectral compressed sensing via structured matrix completion. IEEE Trans. Inform. Theory 60(10):6576–6601.Crossref, 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.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 J, Liu D, Li X (2019a) Nonconvex rectangular matrix completion via gradient descent without ℓ2,∞ regularization. Preprint, submitted January 18, https://arxiv.org/abs/1901.06116v1.Google Scholar
• Chen H, Raskutti G, Yuan M (2019b) Non-convex projected gradient descent for generalized low-rank tensor regression. J. Machine Learn. Res. 20(1):172–208.Google Scholar
• Chen Y, Chi Y, Fan J, Ma C (2019c) Gradient descent with random initialization: Fast global convergence for nonconvex phase retrieval. Math. Programming 176(1–2):5–37.Crossref, Google Scholar
• Chen Y, Fan J, Ma C, Wang K (2019d) Spectral method and regularized MLE are both optimal for top-K ranking. Ann. Statist. 47(4):2204–2235.Crossref, Google Scholar
• Chen Y, Fan J, Ma C, Yan Y (2019e) Inference and uncertainty quantification for noisy matrix completion. Proc. Natl. Acad. Sci. USA 116(46):22931–22937.Crossref, Google Scholar
• Chen Y, Chi Y, Fan J, Ma C, Yan Y (2021) Noisy matrix completion: Understanding statistical guarantees for convex relaxation via nonconvex optimization. SIAM J. Optim. 30(4):3098–3121.Google Scholar
• Cheng JY, Zhang T, Alley MT, Uecker M, Lustig M, Pauly JM, Vasanawala SS (2017) Comprehensive multi-dimensional MRI for the simultaneous assessment of cardiopulmonary anatomy and physiology. Sci. Rep. 7(1):5330.Crossref, Google Scholar
• Chi Y, Lu Y, Chen Y (2019) Nonconvex optimization meets low-rank matrix factorization: An overview. IEEE Trans. Signal Processing 67(20):5239–5269.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
• Ding L, Chen Y (2018) Leave-one-out approach for matrix completion: Primal and dual analysis. Preprint, submitted March 20, https://arxiv.org/abs/1803.07554.Google Scholar
• Driggs D, Becker S, Boyd-Graber J (2019) Tensor robust principal component analysis: Better recovery with atomic norm regularization. Preprint, submitted January 30, https://arxiv.org/abs/1901.10991.Google Scholar
• El Karoui N (2015) On the impact of predictor geometry on the performance on high-dimensional ridge-regularized generalized robust regression estimators. Probab. Theory Related Fields 170:95–175.Crossref, Google Scholar
• Ely G, Aeron S, Hao N, Kilmer ME (2013) 5D and 4D pre-stack seismic data completion using tensor nuclear norm (TNN). SEG Tech. Program Expanded Abstr. (Society of Exploration Geophysicists, Tulsa, OK), 3639–3644.Crossref, Google Scholar
• Farias VF, Li AA (2019) Learning preferences with side information. Management Sci. 65(7):3131–3149.Link, Google Scholar
• Gandy S, Recht B, Yamada I (2011) Tensor completion and low-n-rank tensor recovery via convex optimization. Inverse Problems 27(2):025010.Crossref, Google Scholar
• Ge R, Ma T (2017) On the optimization landscape of tensor decompositions. von Luxburg U, Guyon I, Bengio S, Wallach H, Fergus R, eds. Adv. Neural Inform. Processing Systems 31 (Curran Associates, Red Hook, NY), 3653–3663.Google Scholar
• Ge R, Huang F, Jin C, Yuan Y (2015) Escaping from saddle points: Online stochastic gradient for tensor decomposition. Proc. 28th Conf. Learning Theory, Paris, July 3–6, 797–842.Google Scholar
• Gilboa D, Buchanan S, Wright J (2018) Efficient dictionary learning with gradient descent. Preprint, submitted September 27, https://arxiv.org/abs/1809.10313.Google Scholar
• Goldfarb D, Qin Z (2014) Robust low-rank tensor recovery: Models and algorithms. SIAM J. Matrix Anal. Appl. 35(1):225–253.Crossref, Google Scholar
• Gross D (2011) Recovering low-rank matrices from few coefficients in any basis. IEEE Trans. Inform. Theory 57(3):1548–1566.Crossref, Google Scholar
• Hao B, Zhang A, Cheng G (2020) Sparse and low-rank tensor estimation via cubic sketchings. IEEE Trans. Inform. Theory 66(9):5927–5964.Crossref, Google Scholar
• Hao B, Wang B, Wang P, Zhang J, Yang J, Sun WW (2019) Sparse tensor additive regression. Submitted March 31, https://arxiv.org/abs/1904.00479.Google Scholar
• Hillar CJ, Lim LH (2013) Most tensor problems are np-hard. J. ACM 60(6):45.Crossref, Google Scholar
• Hopkins SB, Schramm T, Shi J, Steurer D (2016) Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors. Proc.48th Annual ACM Sympos. Theory Comput. (ACM, New York), 178–191.Google Scholar
• Huang B, Mu C, Goldfarb D, Wright J (2015) Provable models for robust low-rank tensor completion. Pacific J. Optim. 11(2):339–364.Google Scholar
• Jain P, Oh S (2014) Provable tensor factorization with missing data. Ghahramani Z, Welling M, Cortes C, Lawrence N, Weinberger KQ, eds. Adv. Neural Inform. Processing Systems 27 (Curran Associates, Red Hook, NY), 1431–1439.Google Scholar
• Ji TY, Huang TZ, Zhao XL, Ma TH, Liu G (2016) Tensor completion using total variation and low-rank matrix factorization. Inform. Sci. 326:243–257.Crossref, Google Scholar
• Kasai H, Mishra B (2016) Low-rank tensor completion: a riemannian manifold preconditioning approach. Balcan MF, Weinberger KQ, eds. Proc. 33rd Internat. Conf. Machine Learning, New York, June 20–22, 1012–1021.Google Scholar
• Keshavan RH, Montanari A, Oh S (2010a) Matrix completion from a few entries. IEEE Trans. Inform. Theory 56(6):2980–2998.Crossref, Google Scholar
• Keshavan RH, Montanari A, Oh S (2010b) Matrix completion from noisy entries. J. Machine Learn. Res. 11(69):2057–2078.Google Scholar
• Kilmer ME, Braman K, Hao N, Hoover RC (2013) Third-order tensors as operators on matrices: A theoretical and computational framework with applications in imaging. SIAM J. Matrix Anal. Appl. 34(1):148–172.Crossref, Google Scholar
• Kim HJ, Ollila E, Koivunen V, Croux C (2013) Robust and sparse estimation of tensor decompositions. Proc. 2013 IEEE Global Conf. Signal Inform. Processing (IEEE, Piscataway, NJ), 965–968.Google Scholar
• Kolda TG (2001) Orthogonal tensor decompositions. SIAM J. Matrix Anal. Appl. 23(1):243–255.Crossref, Google Scholar
• Kolda TG, Bader BW (2009) Tensor decompositions and applications. SIAM Rev. 51(3):455–500.Crossref, Google Scholar
• Kreimer N, Stanton A, Sacchi MD (2013) Tensor completion based on nuclear norm minimization for 5d seismic data reconstruction. Geophysics 78(6):273–284.Crossref, Google Scholar
• Krishnamurthy A, Singh A (2013) Low-rank matrix and tensor completion via adaptive sampling. Burges CJC, Bottou L, Welling M, Ghahramani Z, Weinberger KQ, eds. Adv. Neural Inform. Processing Systems 26 (Curran Associates, Red Hook, NY), 836–844.Google Scholar
• Li Q, Tang G (2017) Convex and nonconvex geometries of symmetric tensor factorization. Proc. 51st Asilomar Conf. Signals Systems Comput. (IEEE, Piscataway, NJ), 305–309.Google Scholar
• Li X, Ye Y, Xu X (2017) Low-rank tensor completion with total variation for visual data inpainting. Singh S, Markovitch S, eds. Proc. 31st AAAI Conf. Artificial Intelligence (AAAI Press, San Francisco), 2210–2216.Google Scholar
• Li Q, Zhu Z, Tang G (2019) The non-convex geometry of low-rank matrix optimization. Inform. Inference 8(1):51–96.Crossref, Google Scholar
• Liu J, Musialski P, Wonka P, Ye J (2013) Tensor completion for estimating missing values in visual data. IEEE Trans. Pattern Anal. Machine Intelligence 35(1):208–220.Crossref, Google Scholar
• Liu Y, Shang F, Cheng H, Cheng J, Tong H (2014) Factor matrix trace norm minimization for low-rank tensor completion. Zaki M, Obradovic Z, Tan PN, Banerjee A, Kamath C, Parthasarathy S, eds. Proc. 2014 SIAM Internat. Conf. Data Mining (SIAM, Philadelphia), 866–874.Google Scholar
• Lounici K (2014) High-dimensional covariance matrix estimation with missing observations. Bernoulli 20(3):1029–1058.Crossref, Google Scholar
• Lu C, Feng J, Chen Y, Liu W, Lin Z, Yan S (2016) Tensor robust principal component analysis: Exact recovery of corrupted low-rank tensors via convex optimization. Proc. IEEE Conf. Comput. Vision Pattern Recognition (IEEE, Piscataway, NJ), 5249–5257.Google Scholar
• Ma C, Wang K, Chi Y, Chen Y (2017) Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion and blind deconvolution. Foundations Comput. Math. 20:451–463.Crossref, Google Scholar
• Mišić VV, Perakis G (2020) Data analytics in operations management: A review. Manufacturing Service Oper. Management 22(1):158–169.Link, Google Scholar
• Montanari A, Sun N (2018) Spectral algorithms for tensor completion. Comm. Pure Appl. Math. 71(11):2381–2425.Crossref, Google Scholar
• Mu C, Huang B, Wright J, Goldfarb D (2014) Square deal: Lower bounds and improved relaxations for tensor recovery. Xing EP, Jebara T, eds. Proc. 31st Internat. Conf. Machine Learning, Beijing, June 22–24, 73–81.Google Scholar
• Pananjady A, Wainwright MJ (2019) Instance-dependent ℓ∞-bounds for policy evaluation. Preprint, submitted September 19, https://arxiv.org/abs/1909.08749.Google Scholar
• Pawlowski C (2019) Machine learning for problems with missing and uncertain data with applications to personalized medicine. Unpublished doctoral dissertation, Massachusetts Institute of Technology.Google Scholar
• Potechin A, Steurer D (2017) Exact tensor completion with sum-of-squares. Kale S, Shamir O, eds. Proc. 2017 Conf. Learning Theory, Amsterdam, July 7–10, 1619–1673.Google Scholar
• Rauhut H, Schneider R, Stojanac Ž (2017) Low rank tensor recovery via iterative hard thresholding. Linear Algebra Appl. 523:220–262.Crossref, Google Scholar
• Richard E, Montanari A (2014) A statistical model for tensor PCA. Ghahramani Z, Welling M, Cortes C, Lawrence ND, Weinberger KQ, eds. Adv. Neural Inform. Processing, Systems 27 (Curran Associates, Red Hook, NY), 2897–2905.Google Scholar
• Romera-Paredes B, Pontil M (2013) A new convex relaxation for tensor completion. Burges CJC, Bottou L, Welling M, Ghahramani Z, Weinberger KQ, eds. Adv. Neural Inform. Processing Systems 26 (Curran Associates, Red Hook, NY), 2967–2975.Google Scholar
• Semerci O, Hao N, Kilmer ME, Miller EL (2014) Tensor-based formulation and nuclear norm regularization for multienergy computed tomography. IEEE Trans. Image Processing 23(4):1678–1693.Crossref, Google Scholar
• Shah D, Yu CL (2019) Iterative collaborative filtering for sparse noisy tensor estimation. Preprint, submitted August 3, https://arxiv.org/abs/1908.01241.Google Scholar
• Sidiropoulos ND, De Lathauwer L, Fu X, Huang K, Papalexakis EE, Faloutsos C (2017) Tensor decomposition for signal processing and machine learning. IEEE Trans. Signal Processing 65(13):3551–3582.Crossref, Google Scholar
• Soroushmehr SR, Najarian K (2016) Transforming big data into computational models for personalized medicine and healthcare. Dialogues Clinical Neuroscience 18(3):339–343.Crossref, Google Scholar
• Steinlechner M (2016) Riemannian optimization for high-dimensional tensor completion. SIAM J. Sci. Comput. 38(5):S461–S484.Crossref, 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
• Sun WW, Lu J, Liu H, Cheng G (2017) Provable sparse tensor decomposition. J. Royal Statist. Soc. Ser. B. Statist. Methodology 79(3):899–916.Crossref, Google Scholar
• Tan YS, Vershynin R (2019) Online stochastic gradient descent with arbitrary initialization solves non-smooth, non-convex phase retrieval. Preprint, submitted October 28, https://arxiv.org/abs/1910.12837.Google Scholar
• Tang G, Shah P (2015) Guaranteed tensor decomposition: A moment approach. Bach F, Blei D, eds. Proc. 32nd Internat. Conf. Machine Learning, Lille, France, July 7–9, 1491–1500.Google Scholar
• Tomioka R, Hayashi K, Kashima H (2010) Estimation of low-rank tensors via convex optimization. Preprint, submitted October 5, https://arxiv.org/abs/1010.0789.Google Scholar
• Wang W, Aggarwal V, Aeron S (2016) Tensor completion by alternating minimization under the tensor train (TT) model. Preprint, submitted September 19, https://arxiv.org/abs/1609.05587.Google Scholar
• Xia D, Yuan M (2017) On polynomial time methods for exact low rank tensor completion. Preprint, submitted February 22, https://arxiv.org/abs/1702.06980.Google Scholar
• Xia D, Yuan M, Zhang CH (2017) Statistically optimal and computationally efficient low rank tensor completion from noisy entries. Preprint, submitted November 14, https://arxiv.org/abs/1711.04934.Google Scholar
• Xu Y, Yin W (2013) A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion. SIAM J. Imaging Sci. 6(3):1758–1789.Crossref, Google Scholar
• Xu Y, Hao R, Yin W, Su Z (2015) Parallel matrix factorization for low-rank tensor completion. Inverse Problems Imaging 9(2):601–624.Crossref, Google Scholar
• Yao Q (2018) Scalable tensor completion with nonconvex regularization. Preprint, submitted July 23, https://arxiv.org/abs/1807.08725v1.Google Scholar
• Yi X, Park D, Chen Y, Caramanis C (2016) Fast algorithms for robust PCA via gradient descent. Lee D, Sugiyama M, Luxburg U, Guyon I, Garnett R, eds. Adv. Neural Inform. Processing Systems 29 (Curran Associates, Red Hook, NY), 4152–4160.Google Scholar
• Ying J, Lu H, Wei Q, Cai JF, Guo D, Wu J, Chen Z, Qu X (2017) Hankel matrix nuclear norm regularized tensor completion for n-dimensional exponential signals. IEEE Trans. Signal Processing 65(14):3702–3717.Crossref, Google Scholar
• Yuan M, Zhang CH (2016) On tensor completion via nuclear norm minimization. Found. Comput. Math. 16(4):1031–1068.Crossref, Google Scholar
• Yuan M, Zhang CH (2017) Incoherent tensor norms and their applications in higher order tensor completion. IEEE Trans. Inform. Theory 63(10):6753–6766.Crossref, Google Scholar
• Zhang A (2019) Cross: Efficient low-rank tensor completion. Ann. Statist. 47(2):936–964.Crossref, Google Scholar
• Zhang Z, Aeron S (2017) Exact tensor completion using t-SVD. IEEE Trans. Signal Processing 65(6):1511–1526.Crossref, Google Scholar
• Zhang A, Xia D (2018) Tensor SVD: Statistical and computational limits. IEEE Trans. Inform. Theory 64(11):7311–7338.Crossref, Google Scholar
• Zhong Y, Boumal N (2018) Near-optimal bound for phase synchronization. SIAM J. Optim. 28(2):989–1016.Crossref, Google Scholar
• Zoubir AM, Koivunen V, Ollila E, Muma M (2018) Robust Statistics for Signal Processing (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar