{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:41:23Z","timestamp":1740134483902,"version":"3.37.3"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"name":"Postdoctoral Fellowship","award":["12E8119N"]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"We propose a new numerical algorithm for computing the tensor rank decomposition or canonical polyadic decomposition of higher-order tensors subject to a rank and genericity constraint. Reformulating this computational problem as a system of polynomial equations allows us to leverage recent numerical linear algebra tools from computational algebraic geometry. We characterize the complexity of our algorithm in terms of an algebraic property of this polynomial system\u2014the multigraded regularity. We prove effective bounds for many tensor formats and ranks, which are of independent interest for overconstrained polynomial system solving. Moreover, we conjecture a general formula for the multigraded regularity, yielding a (parameterized) polynomial time complexity for the tensor rank decomposition problem in the considered setting. Our numerical experiments show that our algorithm can outperform state-of-the-art numerical algorithms by an order of magnitude in terms of accuracy, computation time, and memory consumption.<\/jats:p>","DOI":"10.1145\/3555369","type":"journal-article","created":{"date-parts":[[2022,8,10]],"date-time":"2022-08-10T12:15:51Z","timestamp":1660133751000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["A Normal Form Algorithm\u00a0for Tensor Rank Decomposition"],"prefix":"10.1145","volume":"48","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3459-5845","authenticated-orcid":false,"given":"Simon","family":"Telen","sequence":"first","affiliation":[{"name":"Max Planck Institute for Mathematics in the Sciences, Leipzig, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5692-4163","authenticated-orcid":false,"given":"Nick","family":"Vannieuwenhoven","sequence":"additional","affiliation":[{"name":"KU Leuven, Heverlee, Belgium"}]}],"member":"320","published-online":{"date-parts":[[2022,12,19]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_3_2_1","DOI":"10.1137\/18M1200531"},{"unstructured":"M. R. Bender and S. Telen. 2020. Toric eigenvalue methods for solving sparse polynomial systems. Retrieved from https:\/\/arXiv:2006.10654.","key":"e_1_3_3_3_1"},{"doi-asserted-by":"publisher","key":"e_1_3_3_4_1","DOI":"10.1145\/1993886.1993898"},{"doi-asserted-by":"publisher","key":"e_1_3_3_5_1","DOI":"10.1016\/j.jsc.2012.05.012"},{"doi-asserted-by":"publisher","key":"e_1_3_3_6_1","DOI":"10.1016\/j.matpur.2020.07.003"},{"doi-asserted-by":"publisher","key":"e_1_3_3_7_1","DOI":"10.1007\/s10231-013-0352-8"},{"doi-asserted-by":"publisher","key":"e_1_3_3_8_1","DOI":"10.1016\/j.laa.2010.06.046"},{"doi-asserted-by":"publisher","key":"e_1_3_3_9_1","DOI":"10.1090\/S0025-5718-1977-0428694-0"},{"doi-asserted-by":"publisher","key":"e_1_3_3_10_1","DOI":"10.1007\/978-3-662-03338-8"},{"doi-asserted-by":"publisher","key":"e_1_3_3_11_1","DOI":"10.1016\/j.jpaa.2010.11.010"},{"doi-asserted-by":"publisher","key":"e_1_3_3_12_1","DOI":"10.1112\/S0024610706022630"},{"doi-asserted-by":"publisher","key":"e_1_3_3_13_1","DOI":"10.1137\/110829180"},{"doi-asserted-by":"publisher","key":"e_1_3_3_14_1","DOI":"10.1137\/140961389"},{"doi-asserted-by":"publisher","key":"e_1_3_3_15_1","DOI":"10.1137\/16M1090132"},{"key":"e_1_3_3_16_1","series-title":"Graduate Texts in Mathematics","volume-title":"Using Algebraic Geometry","author":"Cox D. A.","year":"2006","unstructured":"D. A. Cox, J. Little, and D. O\u2019Shea. 2006. Using Algebraic Geometry. Graduate Texts in Mathematics, Vol. 185. Springer Science & Business Media."},{"key":"e_1_3_3_17_1","volume-title":"Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra","author":"Cox D. A.","year":"2013","unstructured":"D. A. Cox, J. Little, and D. O\u2019Shea. 2013. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer Science & Business Media."},{"doi-asserted-by":"publisher","key":"e_1_3_3_18_1","DOI":"10.1090\/gsm\/124"},{"doi-asserted-by":"publisher","key":"e_1_3_3_19_1","DOI":"10.1137\/040608830"},{"doi-asserted-by":"publisher","key":"e_1_3_3_20_1","DOI":"10.1137\/S0895479896305696"},{"doi-asserted-by":"publisher","key":"e_1_3_3_21_1","DOI":"10.1137\/120877258"},{"doi-asserted-by":"publisher","key":"e_1_3_3_22_1","DOI":"10.1137\/130916084"},{"doi-asserted-by":"publisher","key":"e_1_3_3_23_1","DOI":"10.1016\/j.laa.2016.10.019"},{"unstructured":"D. R. Grayson and M. E. Stillman. 2019. Macaulay2 a software system for research in algebraic geometry. software version: v1.18. Retrieved from http:\/\/www.math.uiuc.edu\/Macaulay2\/.","key":"e_1_3_3_24_1"},{"doi-asserted-by":"publisher","key":"e_1_3_3_25_1","DOI":"10.1007\/978-1-4613-9425-9"},{"unstructured":"S. Hendrikx M. Bouss\u00e9 N. Vervliet M. Vandecappelle R. Kenis and L. De Lathauwer. 2022. Tensorlab + . Retrieved from https:\/\/www.tensorlabplus.net.","key":"e_1_3_3_26_1"},{"doi-asserted-by":"publisher","key":"e_1_3_3_27_1","DOI":"10.1145\/2512329"},{"doi-asserted-by":"publisher","key":"e_1_3_3_28_1","DOI":"10.1002\/sapm192761164"},{"doi-asserted-by":"publisher","key":"e_1_3_3_29_1","DOI":"10.1007\/BFb0093426"},{"doi-asserted-by":"publisher","key":"e_1_3_3_30_1","DOI":"10.1137\/07070111x"},{"doi-asserted-by":"publisher","key":"e_1_3_3_31_1","DOI":"10.1016\/0024-3795(77)90069-6"},{"doi-asserted-by":"publisher","key":"e_1_3_3_32_1","DOI":"10.1016\/j.laa.2018.07.004"},{"key":"e_1_3_3_33_1","series-title":"Graduate Studies in Mathematics","volume-title":"Tensors: Geometry and Applications","author":"Landsberg J. M.","year":"2012","unstructured":"J. M. Landsberg. 2012. Tensors: Geometry and Applications. Graduate Studies in Mathematics, Vol. 128. AMS, Providence, RI."},{"doi-asserted-by":"publisher","key":"e_1_3_3_34_1","DOI":"10.1137\/0614071"},{"doi-asserted-by":"publisher","key":"e_1_3_3_35_1","DOI":"10.1021\/ac00289a052"},{"doi-asserted-by":"publisher","key":"e_1_3_3_36_1","DOI":"10.3792\/chmm\/1263317740"},{"issue":"571","key":"e_1_3_3_37_1","first-page":"179","article-title":"Multigraded castelnuovo-mumford regularity","volume":"2004","author":"Maclagan D.","year":"2004","unstructured":"D. Maclagan and G. G. Smith. 2004. Multigraded castelnuovo-mumford regularity. J. f\u00fcr die Reine und Angew. Math. 2004, 571 (2004), 179\u2013212.","journal-title":"J. f\u00fcr die Reine und Angew. Math."},{"key":"e_1_3_3_38_1","volume-title":"Combinatorial Commutative Algebra","author":"Miller E.","year":"2005","unstructured":"E. Miller and B. Sturmfels. 2005. Combinatorial Commutative Algebra. Vol. 227. Springer Science & Business Media."},{"doi-asserted-by":"publisher","key":"e_1_3_3_39_1","DOI":"10.1007\/s10208-017-9372-x"},{"doi-asserted-by":"publisher","key":"e_1_3_3_40_1","DOI":"10.1007\/s10208-015-9291-7"},{"doi-asserted-by":"publisher","key":"e_1_3_3_41_1","DOI":"10.1137\/060655894"},{"doi-asserted-by":"publisher","key":"e_1_3_3_42_1","DOI":"10.1007\/978-3-319-26765-4"},{"doi-asserted-by":"publisher","key":"e_1_3_3_43_1","DOI":"10.1002\/cem.1180040105"},{"doi-asserted-by":"publisher","key":"e_1_3_3_44_1","DOI":"10.1002\/1099-128X(200005\/06)14:3<229::AID-CEM587>3.0.CO;2-N"},{"doi-asserted-by":"publisher","key":"e_1_3_3_45_1","DOI":"10.1109\/TSP.2017.2690524"},{"doi-asserted-by":"publisher","key":"e_1_3_3_46_1","DOI":"10.1016\/j.jpaa.2020.106367"},{"key":"e_1_3_3_47_1","volume-title":"Solving Systems of Polynomial Equations","author":"Telen S.","year":"2020","unstructured":"S. Telen. 2020b. Solving Systems of Polynomial Equations. Ph.D. Dissertation. KU Leuven."},{"doi-asserted-by":"publisher","key":"e_1_3_3_48_1","DOI":"10.1137\/17M1162433"},{"doi-asserted-by":"publisher","key":"e_1_3_3_49_1","DOI":"10.1007\/BF02289464"},{"doi-asserted-by":"publisher","key":"e_1_3_3_50_1","DOI":"10.1137\/110836067"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3555369","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,2]],"date-time":"2023-01-02T07:19:52Z","timestamp":1672643992000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3555369"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,19]]},"references-count":49,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,12,31]]}},"alternative-id":["10.1145\/3555369"],"URL":"https:\/\/doi.org\/10.1145\/3555369","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"type":"print","value":"0098-3500"},{"type":"electronic","value":"1557-7295"}],"subject":[],"published":{"date-parts":[[2022,12,19]]},"assertion":[{"value":"2021-04-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-12-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}