{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T04:16:35Z","timestamp":1773116195787,"version":"3.50.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2019,1,7]],"date-time":"2019-01-07T00:00:00Z","timestamp":1546819200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2019,12]]},"DOI":"10.1007\/s10208-018-09408-6","type":"journal-article","created":{"date-parts":[[2019,1,8]],"date-time":"2019-01-08T22:03:29Z","timestamp":1546985009000},"page":"1265-1313","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":31,"title":["On Polynomial Time Methods for Exact Low-Rank Tensor Completion"],"prefix":"10.1007","volume":"19","author":[{"given":"Dong","family":"Xia","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ming","family":"Yuan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,1,7]]},"reference":[{"key":"9408_CR1","doi-asserted-by":"crossref","unstructured":"P.\u00a0Absil, R.\u00a0Mahony, and R.\u00a0Sepulchre. Optimization Algorithms on Matrix Manifolds. Princeton University Press, 2008.","DOI":"10.1515\/9781400830244"},{"key":"9408_CR2","unstructured":"Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham\u00a0M Kakade, and Matus Telgarsky. Tensor decompositions for learning latent variable models. Journal of Machine Learning Research, 15(1):2773\u20132832, 2014."},{"key":"9408_CR3","unstructured":"Boaz Barak and Ankur Moitra. Noisy tensor completion via the sum-of-squares hierarchy. In 29th Annual Conference on Learning Theory, pages 417\u2013445, 2016."},{"issue":"6","key":"9408_CR4","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1016\/S1631-073X(02)02292-6","volume":"334","author":"Olivier Bousquet","year":"2002","unstructured":"Olivier Bousquet. A Bennett concentration inequality and its application to suprema of empirical processes. Comptes Rendus Mathematique, 334(6):495\u2013500, 2002.","journal-title":"Comptes Rendus Mathematique"},{"issue":"6","key":"9408_CR5","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1007\/s10208-009-9045-5","volume":"9","author":"Emmanuel J. Cand\u00e8s","year":"2009","unstructured":"Emmanuel\u00a0J Cand\u00e8s and Benjamin Recht. Exact matrix completion via convex optimization. Foundations of Computational mathematics, 9(6):717\u2013772, 2009.","journal-title":"Foundations of Computational Mathematics"},{"issue":"5","key":"9408_CR6","doi-asserted-by":"publisher","first-page":"2053","DOI":"10.1109\/TIT.2010.2044061","volume":"56","author":"Emmanuel J. Candes","year":"2010","unstructured":"Emmanuel\u00a0J Cand\u00e8s and Terence Tao. The power of convex relaxation: Near-optimal matrix completion. IEEE Transactions on Information Theory, 56(5):2053\u20132080, 2010.","journal-title":"IEEE Transactions on Information Theory"},{"key":"9408_CR7","unstructured":"S.\u00a0Cohen and M.\u00a0Collins. Tensor decomposition for fast parsing with latent-variable PCFGS. In Advances in Neural Information Processing Systems, 2012."},{"key":"9408_CR8","doi-asserted-by":"crossref","unstructured":"Victor de\u00a0la Pena and Evarist Gin\u00e9. Decoupling: from dependence to independence. Springer Science & Business Media, 1999.","DOI":"10.1007\/978-1-4612-0537-1"},{"key":"9408_CR9","doi-asserted-by":"crossref","unstructured":"Victor\u00a0H de\u00a0la Pe\u00f1a and Stephen\u00a0J Montgomery-Smith. Decoupling inequalities for the tail probabilities of multivariate U-statistics. The Annals of Probability, pages 806\u2013816, 1995.","DOI":"10.1214\/aop\/1176988291"},{"issue":"3","key":"9408_CR10","doi-asserted-by":"publisher","first-page":"1084","DOI":"10.1137\/06066518X","volume":"30","author":"Vin Silva de","year":"2008","unstructured":"Vin de\u00a0Silva and Lek-Heng Lim. Tensor rank and the ill-posedness of the best low-rank approximation problem. SIAM Journal on Matrix Analysis and Applications, 30(3):1084\u20131127, 2008.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"issue":"2","key":"9408_CR11","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1137\/S0895479895290954","volume":"20","author":"Alan Edelman","year":"1998","unstructured":"Alan Edelman, Tom\u00e1s\u00a0A Arias, and Steven\u00a0T Smith. The geometry of algorithms with orthogonality constraints. SIAM journal on Matrix Analysis and Applications, 20(2):303\u2013353, 1998.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"issue":"2","key":"9408_CR12","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1137\/070688316","volume":"31","author":"Lars Eld\u00e9n","year":"2009","unstructured":"Lars Elden and Berkant Savas. A Newton-Grassmann method for computing the best multilinear rank-(\n$$r_1,r_2,r_3$$\n\n\n\n\n\nr\n1\n\n,\n\nr\n2\n\n,\n\nr\n3\n\n\n\n\n\n) approximation of a tensor. SIAM Journal on Matrix Analysis and Applications, 31(2):248\u2013271, 2009.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"issue":"2","key":"9408_CR13","doi-asserted-by":"publisher","first-page":"025010","DOI":"10.1088\/0266-5611\/27\/2\/025010","volume":"27","author":"Silvia Gandy","year":"2011","unstructured":"Silvia Gandy, Benjamin Recht, and Isao Yamada. Tensor completion and low-n-rank tensor recovery via convex optimization. Inverse Problems, 27(2):025010, 2011.","journal-title":"Inverse Problems"},{"issue":"3","key":"9408_CR14","doi-asserted-by":"publisher","first-page":"1548","DOI":"10.1109\/TIT.2011.2104999","volume":"57","author":"David Gross","year":"2011","unstructured":"David Gross. Recovering low-rank matrices from few coefficients in any basis. IEEE Transactions on Information Theory, 57(3):1548\u20131566, 2011.","journal-title":"IEEE Transactions on Information Theory"},{"key":"9408_CR15","doi-asserted-by":"crossref","unstructured":"C.\u00a0Hillar and Lek-Heng Lim. Most tensor problems are NP-hard. Journal of ACM, 60(6):45, 2013.","DOI":"10.1145\/2512329"},{"key":"9408_CR16","unstructured":"Prateek Jain and Sewoong Oh. Provable tensor factorization with missing data. In Advances in Neural Information Processing Systems, pages 1431\u20131439, 2014."},{"key":"9408_CR17","doi-asserted-by":"crossref","unstructured":"Raghunandan\u00a0H Keshavan, Sewoong Oh, and Andrea Montanari. Matrix completion from a few entries. In 2009 IEEE International Symposium on Information Theory, pages 324\u2013328. IEEE, 2009.","DOI":"10.1109\/ISIT.2009.5205567"},{"issue":"2","key":"9408_CR18","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/s10543-013-0455-z","volume":"54","author":"Daniel Kressner","year":"2014","unstructured":"Daniel Kressner, Michael Steinlechner, and Bart Vandereycken. Low-rank tensor completion by Riemannian optimization. BIT Numerical Mathematics, 54(2):447\u2013468, 2014.","journal-title":"BIT Numerical Mathematics"},{"key":"9408_CR19","doi-asserted-by":"crossref","unstructured":"N.\u00a0Li and B.\u00a0Li. Tensor completion for on-board compression of hyperspectral images. In 17th IEEE International Conference on Image Processing (ICIP), pages 517\u2013520, 2010.","DOI":"10.1109\/ICIP.2010.5651225"},{"issue":"1","key":"9408_CR20","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1109\/TPAMI.2012.39","volume":"35","author":"Ji Liu","year":"2013","unstructured":"Ji\u00a0Liu, Przemyslaw Musialski, Peter Wonka, and Jieping Ye. Tensor completion for estimating missing values in visual data. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(1):208\u2013220, 2013.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"9408_CR21","doi-asserted-by":"crossref","unstructured":"David\u00a0G Luenberger and Yinyu Ye. Linear and nonlinear programming, volume 228. Springer, 2015.","DOI":"10.1007\/978-3-319-18842-3"},{"key":"9408_CR22","unstructured":"Andrea Montanari and Nike Sun. Spectral algorithms for tensor completion. Communications on Pure and Applied Mathematics, 2016."},{"key":"9408_CR23","first-page":"1","volume":"1","author":"Mu Cun","year":"2014","unstructured":"Cun Mu, Bo\u00a0Huang, John Wright, and Donald Goldfarb. Square deal: Lower bounds and improved convex relaxations for tensor recovery. Journal of Machine Learning Research, 1:1\u201348, 2014.","journal-title":"Journal of Machine Learning Research"},{"key":"9408_CR24","unstructured":"Holger Rauhut and \u017deljka Stojanac. Tensor theta norms and low rank recovery. arXiv preprint\n\narXiv:1505.05175\n\n, 2015."},{"key":"9408_CR25","unstructured":"Holger Rauhut, Reinhold Schneider, and Zeljka Stojanac. Low rank tensor recovery via iterative hard thresholding. arXiv preprint\n\narXiv:1602.05217\n\n, 2016."},{"key":"9408_CR26","unstructured":"Benjamin Recht. A simpler approach to matrix completion. Journal of Machine Learning Research, 12(Dec):3413\u20133430, 2011."},{"issue":"6","key":"9408_CR27","first-page":"3352","volume":"32","author":"Berkant Savas","year":"2010","unstructured":"Berkant Savas and Lek-Heng Lim. Quasi-newton methods on Grassmannians and multilinear approximations of tensors. SIAM Journal on Matrix Analysis and Applications, 32(6):3352\u20133393, 2010.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"9408_CR28","doi-asserted-by":"publisher","first-page":"1678","DOI":"10.1109\/TIP.2014.2305840","volume":"23","author":"O Semerci","year":"2014","unstructured":"O.\u00a0Semerci, N.\u00a0Hao, M.\u00a0Kilmer, and E.\u00a0Miller. Tensor-based formulation and nuclear norm regularization for multienergy computed tomography. IEEE Transactions on Image Processing, 23:1678\u20131693, 2014.","journal-title":"IEEE Transactions on Image Processing"},{"key":"9408_CR29","doi-asserted-by":"publisher","first-page":"5693","DOI":"10.1109\/TSP.2010.2058802","volume":"58","author":"ND Sidiropoulos","year":"2010","unstructured":"N.D. Sidiropoulos and N.\u00a0Nion. Tensor algebra and multi-dimensional harmonic retrieval in signal processing for mimo radar. IEEE Transactions on Signal Processing, 58:5693\u20135705, 2010.","journal-title":"IEEE Transactions on Signal Processing"},{"key":"9408_CR30","unstructured":"Ryota Tomioka, Kohei Hayashi, and Hisashi Kashima. Estimation of low-rank tensors via convex optimization. arXiv preprint\n\narXiv:1010.0789\n\n, 2010."},{"key":"9408_CR31","doi-asserted-by":"crossref","unstructured":"Joel\u00a0A Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics, 12(4):389\u2013434, 2012.","DOI":"10.1007\/s10208-011-9099-z"},{"issue":"2","key":"9408_CR32","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1093\/biomet\/asv008","volume":"102","author":"Y. Yu","year":"2015","unstructured":"Yi\u00a0Yu, Tengyao Wang, and Richard\u00a0J Samworth. A useful variant of the Davis\u2013Kahan theorem for statisticians. Biometrika, 102(2):315\u2013323, 2015.","journal-title":"Biometrika"},{"key":"9408_CR33","doi-asserted-by":"crossref","unstructured":"Ming Yuan and Cun-Hui Zhang. On tensor completion via nuclear norm minimization. Foundations of Computational Mathematics, pages 1031\u20131068, 2016.","DOI":"10.1007\/s10208-015-9269-5"},{"issue":"10","key":"9408_CR34","doi-asserted-by":"publisher","first-page":"6753","DOI":"10.1109\/TIT.2017.2724549","volume":"63","author":"Ming Yuan","year":"2017","unstructured":"Ming Yuan and Cun-Hui Zhang. Incoherent tensor norms and their applications in higher order tensor completion. IEEE Transactions on Information Theory, 63(10):6753\u20136766, 2017.","journal-title":"IEEE Transactions on Information Theory"}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-018-09408-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10208-018-09408-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-018-09408-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,7]],"date-time":"2020-01-07T00:04:57Z","timestamp":1578355497000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10208-018-09408-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,7]]},"references-count":34,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["9408"],"URL":"https:\/\/doi.org\/10.1007\/s10208-018-09408-6","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,7]]},"assertion":[{"value":"7 January 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}