{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:15Z","timestamp":1740109275991,"version":"3.37.3"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,11,2]],"date-time":"2020-11-02T00:00:00Z","timestamp":1604275200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,11,2]],"date-time":"2020-11-02T00:00:00Z","timestamp":1604275200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1652491","1637585"],"award-info":[{"award-number":["1652491","1637585"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,6]]},"DOI":"10.1007\/s10107-020-01577-z","type":"journal-article","created":{"date-parts":[[2020,11,2]],"date-time":"2020-11-02T14:53:53Z","timestamp":1604328833000},"page":"549-599","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Smoothed analysis for tensor methods in unsupervised learning"],"prefix":"10.1007","volume":"193","author":[{"given":"Aditya","family":"Bhaskara","sequence":"first","affiliation":[]},{"given":"Aidao","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Aidan","family":"Perreault","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9734-3779","authenticated-orcid":false,"given":"Aravindan","family":"Vijayaraghavan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,11,2]]},"reference":[{"key":"1577_CR1","unstructured":"Anderson, J., Belkin, M., Goyal, N., Rademacher, L., Voss, J.R.: The more, the merrier: the blessing of dimensionality for learning large Gaussian mixtures. In: Proceedings of The 27th Conference on Learning Theory, COLT 2014, Barcelona, Spain, June 13\u201315, 2014, pp. 1135\u20131164 (2014)"},{"key":"1577_CR2","doi-asserted-by":"crossref","unstructured":"Angel, O., Bubeck, S., Peres, Y., Wei, F.: Local max-cut in smoothed polynomial time. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pp. 429\u2013437, New York, NY, USA. ACM (2017)","DOI":"10.1145\/3055399.3055402"},{"key":"1577_CR3","unstructured":"Anari, N., Daskalakis, C., Maass, W., Papadimitriou, C., Saberi, A., Vempala, S.: Smoothed analysis of discrete tensor decomposition and assemblies of neurons. In: Advances in Neural Information Processing Systems, pp. 10880\u201310890 (2018)"},{"key":"1577_CR4","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.laa.2004.05.007","volume":"391","author":"L Albera","year":"2004","unstructured":"Albera, L., Ferr\u00e9ol, A., Comon, P., Chevalier, P.: Blind identification of overcomplete mixtures of sources (biome). Linear Algebra Appl. 391, 3\u201330 (2004)","journal-title":"Linear Algebra Appl."},{"key":"1577_CR5","doi-asserted-by":"crossref","unstructured":"Anandkumar, A., Ge, R., Hsu, D., Kakade, S.M., Telgarsky, M.: Tensor decompositions for learning latent variable models. arXiv preprint arXiv:1210.7559 (2012)","DOI":"10.21236\/ADA604494"},{"key":"1577_CR6","unstructured":"Anandkumar, A., Hsu, D., Kakade, S.M.: A method of moments for mixture models and hidden markov models. arXiv preprint arXiv:1203.0683 (2012)"},{"issue":"6A","key":"1577_CR7","doi-asserted-by":"publisher","first-page":"3099","DOI":"10.1214\/09-AOS689","volume":"37","author":"ES Allman","year":"2009","unstructured":"Allman, E.S., Matias, C.R., John, A.: Identifiability of parameters in latent structure models with many observed variables. Ann. Stat. 37(6A), 3099\u20133132 (2009)","journal-title":"Ann. Stat."},{"issue":"2","key":"1577_CR8","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1137\/18M1200531","volume":"40","author":"C Beltr\u00e1n","year":"2019","unstructured":"Beltr\u00e1n, C., Breiding, P., Vannieuwenhoven, N.: Pencil-based algorithms for tensor rank decomposition are not stable. SIAM J. Matrix Anal. Appl. 40(2), 739\u2013773 (2019)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"1577_CR9","doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Charikar, M., Moitra, A., Vijayaraghavan, A.: Smoothed analysis of tensor decompositions. In Proceedings of the 46th Symposium on Theory of Computing (STOC). ACM (2014)","DOI":"10.1145\/2591796.2591881"},{"key":"1577_CR10","doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Chen, A., Perreault, A., Vijayaraghavan, A.: Smoothed analysis in unsupervised learning through decoupling. In: 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, pp. 582\u2013610. IEEE (2019)","DOI":"10.1109\/FOCS.2019.00043"},{"key":"1577_CR11","doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Charikar, M., Vijayaraghavan, A.: Uniqueness of tensor decompositions with applications to polynomial identifiability. In: Proceedings of the Conference on Learning Theory (COLT) (2014)","DOI":"10.1145\/2591796.2591881"},{"key":"1577_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0653-8","volume-title":"Matrix Analysis","author":"R Bhatia","year":"1997","unstructured":"Bhatia, R.: Matrix Analysis, vol. 169. Springer, Berlin (1997)"},{"key":"1577_CR13","doi-asserted-by":"crossref","unstructured":"Barak, B., Kelner, J.\u00a0A., Steurer, D.: Dictionary learning and tensor decomposition via the sum-of-squares method. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC \u201915, pp. 143\u2013151. ACM, New York (2015)","DOI":"10.1145\/2746539.2746605"},{"issue":"4","key":"1577_CR14","doi-asserted-by":"publisher","first-page":"855","DOI":"10.1137\/S0097539705447268","volume":"35","author":"R Beier","year":"2006","unstructured":"Beier, R., V\u00f6cking, B.: Typical properties of winners and losers in discrete optimization. SIAM J. Comput. 35(4), 855\u2013881 (2006)","journal-title":"SIAM J. Comput."},{"key":"1577_CR15","doi-asserted-by":"crossref","unstructured":"Cardoso, J.: Super-symmetric decomposition of the fourth-order cumulant tensor. blind identification of more sources than sensors. In: [Proceedings] ICASSP 91: 1991 International Conference on Acoustics, Speech, and Signal Processing, pp. 3109\u20133112 vol. 5 (1991)","DOI":"10.1109\/ICASSP.1991.150113"},{"issue":"3","key":"1577_CR16","doi-asserted-by":"publisher","first-page":"1254","DOI":"10.1137\/060661569","volume":"30","author":"P Comon","year":"2008","unstructured":"Comon, P., Golub, G., Lim, L., Mourrain, B.: Symmetric tensors and symmetric tensor rank. SIAM J. Matrix Anal. Appl. 30(3), 1254\u20131279 (2008)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"3","key":"1577_CR17","doi-asserted-by":"publisher","first-page":"1018","DOI":"10.1137\/110829180","volume":"33","author":"L Chiantini","year":"2012","unstructured":"Chiantini, L., Ottaviani, G.: On generic identifiability of 3-tensors of small rank. SIAM J. Matrix Anal. Appl. 33(3), 1018\u20131037 (2012)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"4","key":"1577_CR18","doi-asserted-by":"publisher","first-page":"1265","DOI":"10.1137\/140961389","volume":"35","author":"L Chiantini","year":"2014","unstructured":"Chiantini, L., Ottaviani, G., Vannieuwenhoven, N.: An algorithm for generic and low-rank specific identifiability of complex tensors. SIAM J. Matrix Anal. Appl. 35(4), 1265\u20131287 (2014)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"3","key":"1577_CR19","doi-asserted-by":"publisher","first-page":"233","DOI":"10.4310\/MRL.2001.v8.n3.a1","volume":"8","author":"A Carbery","year":"2001","unstructured":"Carbery, A., Wright, J.: Distributional and $$L^q$$ norm inequalities for polynomials over convex bodies in $$\\mathbb{R}^n$$. Math. Res. Lett. 8(3), 233\u2013248 (2001)","journal-title":"Math. Res. Lett."},{"key":"1577_CR20","unstructured":"Donoho, D.L., Huber, P.: J: The notion of breakdown point. A Festschrift Erich L. Lehmann 157184 (1983)"},{"issue":"1","key":"1577_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0707001","volume":"7","author":"C Davis","year":"1970","unstructured":"Davis, C., Kahan, W.M.: The rotation of eigenvectors by a perturbation. III. SIAM J. Numer. Anal. 7(1), 1\u201346 (1970)","journal-title":"III. SIAM J. Numer. Anal."},{"issue":"6","key":"1577_CR22","doi-asserted-by":"publisher","first-page":"2965","DOI":"10.1109\/TSP.2007.893943","volume":"55","author":"L De Lathauwer","year":"2007","unstructured":"De Lathauwer, L., Castaing, J., Cardoso, J.: Fourth-order cumulant-based blind identification of underdetermined mixtures. IEEE Trans. Signal Process. 55(6), 2965\u20132973 (2007)","journal-title":"IEEE Trans. Signal Process."},{"issue":"2","key":"1577_CR23","doi-asserted-by":"crossref","first-page":"806","DOI":"10.1214\/aop\/1176988291","volume":"23","author":"VH de la Pena","year":"1995","unstructured":"de la Pena, V.H., Montgomery-Smith, S.J.: Decoupling inequalities for the tail probabilities of multivariate $$u$$-statistics. Ann. Probab. 23(2), 806\u2013816 (1995)","journal-title":"Ann. Probab."},{"issue":"3","key":"1577_CR24","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/S0959-440X(96)80056-X","volume":"6","author":"SR Eddy","year":"1996","unstructured":"Eddy, S.R.: Hidden markov models. Curr. Opin. Struct. Biol. 6(3), 361\u2013365 (1996)","journal-title":"Curr. Opin. Struct. Biol."},{"issue":"2","key":"1577_CR25","doi-asserted-by":"publisher","first-page":"25:1","DOI":"10.1145\/3011870","volume":"13","author":"M Etscheid","year":"2017","unstructured":"Etscheid, M., R\u00f6glin, H.: Smoothed analysis of local search for the maximum-cut problem. ACM Trans. Algorithms 13(2), 25:1\u201325:12 (2017)","journal-title":"ACM Trans. Algorithms"},{"key":"1577_CR26","doi-asserted-by":"crossref","unstructured":"Ge, R., Huang, Q., Kakade, S.M.: Learning mixtures of Gaussians in high dimensions. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, pp. 761\u2013770. Portland (2015)","DOI":"10.1145\/2746539.2746616"},{"key":"1577_CR27","doi-asserted-by":"crossref","unstructured":"Goyal, N., Vempala, S., Xiao, Y.: Fourier PCA and robust tensor decomposition. In: Symposium on Theory of Computing, STOC 2014, pp. 584\u2013593 , New York (2014)","DOI":"10.1145\/2591796.2591875"},{"issue":"3","key":"1577_CR28","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1561\/2000000004","volume":"1","author":"M Gales","year":"2008","unstructured":"Gales, M., Young, S.: The application of hidden Markov models in speech recognition. Found Trends Signal Process 1(3), 195\u2013304 (2008)","journal-title":"Found Trends Signal Process"},{"key":"1577_CR29","unstructured":"Harshman, R.A.: Foundations of the parafac procedure: models and conditions for an explanatory multimodal factor analysis (1970)"},{"issue":"4","key":"1577_CR30","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1016\/0196-6774(90)90014-6","volume":"11","author":"J H\u00e5stad","year":"1990","unstructured":"H\u00e5stad, J.: Tensor rank is np-complete. J. Algorithms 11(4), 644\u2013654 (1990)","journal-title":"J. Algorithms"},{"key":"1577_CR31","doi-asserted-by":"crossref","unstructured":"Huang, Q., Ge, R., Kakade, S., Dahleh, M.: Minimal realization problems for hidden markov models (2015)","DOI":"10.1109\/ALLERTON.2014.7028428"},{"key":"1577_CR32","unstructured":"Hsu, D., Kakade, S.M.: Learning Gaussian mixture models: moment methods and spectral decompositions. arXiv preprint arXiv:1206.5766 (2012)"},{"key":"1577_CR33","unstructured":"Hardt, M., Moitra, A.: Algorithms and hardness for robust subspace recovery. In: Conference on Learning Theory, pp. 354\u2013375 (2013)"},{"key":"1577_CR34","doi-asserted-by":"crossref","unstructured":"Hopkins, S.B., Schramm, T., Shi, J., Steurer, D.: Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors. In: Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, STOC \u201916, pp. 178\u2013191. ACM, New York (2016)","DOI":"10.1145\/2897518.2897529"},{"issue":"2","key":"1577_CR35","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0024-3795(77)90069-6","volume":"18","author":"JB Kruskal","year":"1977","unstructured":"Kruskal, J.B.: Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics. Linear Algebra Appl. 18(2), 95\u2013138 (1977)","journal-title":"Linear Algebra Appl."},{"key":"1577_CR36","doi-asserted-by":"crossref","unstructured":"Kalai, A.T., Samorodnitsky, A., Teng, S.: Learning and smoothed analysis. In: 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 395\u2013404 (2009)","DOI":"10.1109\/FOCS.2009.60"},{"key":"1577_CR37","first-page":"182","volume":"17","author":"S Lovett","year":"2010","unstructured":"Lovett, S.: An elementary proof of anti-concentration of polynomials in Gaussian variables. Electron. Colloq. Comput. Complex. 17, 182 (2010)","journal-title":"Electron. Colloq. Comput. Complex."},{"key":"1577_CR38","doi-asserted-by":"crossref","unstructured":"Moitra, A., O\u2019Donnell, R.: Pareto optimal solutions for smoothed analysts. In: Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC \u201911, pp. 225\u2013234. ACM, New York, NY (2011)","DOI":"10.1145\/1993636.1993667"},{"key":"1577_CR39","doi-asserted-by":"crossref","unstructured":"Ma, T., Shi, J., Steurer, D.: Polynomial-time tensor decompositions with sum-of-squares. In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 438\u2013446. IEEE (2016)","DOI":"10.1109\/FOCS.2016.54"},{"key":"1577_CR40","doi-asserted-by":"crossref","unstructured":"Moitra, A., Valiant, G.: Settling the polynomial learnability of mixtures of Gaussians. In: 2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 93\u2013102. IEEE (2010)","DOI":"10.1109\/FOCS.2010.15"},{"issue":"2","key":"1577_CR41","first-page":"214","volume":"14","author":"F Nazarov","year":"2003","unstructured":"Nazarov, F., Sodin, M., Vol\u2019berg, A.: The geometric Kannan-Lov\u00e1sz-Simonovits lemma, dimension-free estimates for the distribution of the values of polynomials, and the distribution of the zeros of random analytic functions. St. Petersbg. Math. J. 14(2), 214\u2013234 (2003)","journal-title":"St. Petersbg. Math. J."},{"issue":"4","key":"1577_CR42","doi-asserted-by":"publisher","first-page":"1556","DOI":"10.1137\/16M1063708","volume":"37","author":"Y Qi","year":"2016","unstructured":"Qi, Y., Comon, P., Lim, L.-H.: Semialgebraic geometry of nonnegative tensor rank. SIAM J. Matrix Analy. Appl. 37(4), 1556\u20131580 (2016)","journal-title":"SIAM J. Matrix Analy. Appl."},{"key":"1577_CR43","volume-title":"Robust Regression and Outlier Detection","author":"PJ Rousseeuw","year":"2005","unstructured":"Rousseeuw, P.J., Leroy, A.M.: Robust Regression and Outlier Detection, vol. 589. Wiley, Hoboken (2005)"},{"issue":"388","key":"1577_CR44","doi-asserted-by":"publisher","first-page":"871","DOI":"10.1080\/01621459.1984.10477105","volume":"79","author":"PJ Rousseeuw","year":"1984","unstructured":"Rousseeuw, P.J.: Least median of squares regression. J. Am. Stat. Assoc. 79(388), 871\u2013880 (1984)","journal-title":"J. Am. Stat. Assoc."},{"issue":"2","key":"1577_CR45","doi-asserted-by":"publisher","first-page":"600","DOI":"10.1016\/j.aim.2008.01.010","volume":"218","author":"M Rudelson","year":"2008","unstructured":"Rudelson, M., Vershynin, R.: The littlewood-offord problem and invertibility of random matrices. Adv. Math. 218(2), 600\u2013633 (2008)","journal-title":"Adv. Math."},{"key":"1577_CR46","unstructured":"Sharan, V., Kakade, S., Liang, P., Valiant, G.: Learning overcomplete hmms. CoRR. arXiv:1711.02309 (2017)"},{"issue":"3","key":"1577_CR47","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"DA Spielman","year":"2004","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM 51(3), 385\u2013463 (2004)","journal-title":"J. ACM"},{"key":"1577_CR48","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1016\/0024-3795(83)90041-1","volume":"52","author":"V Strassen","year":"1983","unstructured":"Strassen, V.: Rank and optimal computation of generic tensors. Linear Algebra Appl. 52, 645\u2013685 (1983)","journal-title":"Linear Algebra Appl."},{"key":"1577_CR49","unstructured":"Terence T. Topics in random matrix theory. Book By Terry Tao (2011)"},{"issue":"1","key":"1577_CR50","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF01932678","volume":"12","author":"Per-\u00c5ke Wedin","year":"1972","unstructured":"Wedin, Per-\u00c5ke: Perturbation bounds in connection with singular value decomposition. BIT Numer. Math. 12(1), 99\u2013111 (1972)","journal-title":"BIT Numer. Math."},{"issue":"2","key":"1577_CR51","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1093\/biomet\/asv008","volume":"102","author":"Y Yu","year":"2015","unstructured":"Yu, Y., Wang, T., Samworth, R.J.: A useful variant of the Davis\u2013Kahan theorem for statisticians. Biometrika 102(2), 315\u2013323 (2015)","journal-title":"Biometrika"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01577-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01577-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01577-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T14:25:31Z","timestamp":1654871131000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01577-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,2]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["1577"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01577-z","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2020,11,2]]},"assertion":[{"value":"3 December 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 October 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 November 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}