{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:35:29Z","timestamp":1787333729215,"version":"build-2736575974"},"reference-count":68,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","funder":[{"DOI":"10.13039\/100000105","name":"Office of Advanced Cyberinfrastructure","doi-asserted-by":"publisher","award":["1931258"],"award-info":[{"award-number":["1931258"]}],"id":[{"id":"10.13039\/100000105","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>Canonical polyadic decomposition (CPD) is prevalent in chemometrics, signal processing, data mining, and many more fields. While many algorithms have been proposed to compute the CPD, alternating least squares (ALS) remains one of the most widely used algorithms for computing the decomposition. Recent works have introduced the notion of eigenvalues and singular values of a tensor and explored applications of eigenvectors and singular vectors in signal processing, data analytics, and various other fields. We introduce a new formulation for deriving singular values and vectors of a tensor by considering the critical points of a function differently from previous works. Computing these critical points in an alternating manner motivates an alternating optimization algorithm which corresponds to the ALS algorithm in the matrix case. However, for tensors with order greater than or equal to 3, it minimizes an objective function which is different from the commonly used least squares loss. Alternating optimization of this new objective leads to simple updates to the factor matrices with the same asymptotic computational cost as ALS. We show that a subsweep of this algorithm can achieve a superlinear convergence rate for exact CPD when the known rank is not larger than the mode lengths of the input tensor. We verify our theoretical arguments experimentally. We then view the algorithm as optimizing a Mahalanobis distance with respect to each factor with the ground metric dependent on the other factors. This perspective allows us to generalize our approach to interpolate between updates corresponding to the ALS and the new algorithm to manage the tradeoff between stability and fitness of the decomposition. Our experimental results show that for approximating synthetic and real-world tensors, this algorithm and its variants converge to a better conditioned decomposition with comparable and sometimes better fitness as compared to the ALS algorithm.<\/jats:p>","DOI":"10.1137\/22m1490739","type":"journal-article","created":{"date-parts":[[2023,11,3]],"date-time":"2023-11-03T04:31:21Z","timestamp":1698985881000},"page":"A2781-A2812","source":"Crossref","is-referenced-by-count":2,"title":["Alternating Mahalanobis Distance Minimization for Accurate and Well-Conditioned CP Decomposition"],"prefix":"10.1137","volume":"45","author":[{"given":"Navjot","family":"Singh","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6480-9066","authenticated-orcid":true,"given":"Edgar","family":"Solomonik","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2023,11,3]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1002\/cem.1335"},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"A. Afshar, K. Yin, S. Yan, C. Qian, J. C. Ho, H. Park, and J. Sun, Swift: Scalable Wasserstein factorization for sparse nonnegative tensors, in Proceedings of the AAAI Conference, 2021.","DOI":"10.1609\/aaai.v35i8.16811"},{"key":"ref3","first-page":"2773","volume":"15","author":"Anandkumar A.","year":"2014","journal-title":"J. Mach. Learn. Res."},{"key":"ref4","doi-asserted-by":"crossref","unstructured":"G. Ballard, K. Hayashi, and R. Kannan, Parallel Nonnegative CP Decomposition of Dense Tensors, preprint, arXiv:1806.07985, 2018.","DOI":"10.1109\/HiPC.2018.00012"},{"key":"ref5","doi-asserted-by":"crossref","unstructured":"G. Ballard, N. Knight, and K. Rouse, Communication lower bounds for matricized tensor times Khatri-Rao product, in Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS), IEEE, 2018, pp. 557\u2013567.","DOI":"10.1109\/IPDPS.2018.00065"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1137\/17M1112303"},{"key":"ref7","unstructured":"A. Bellet, A. Habrard, and M. Sebban, A Survey on Metric Learning for Feature Vectors and Structured Data, preprint, arXiv:1306.6709, 2013."},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1109\/78.554307"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1093\/jamia\/ocy131"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/17M1142880"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7439(97)00032-4"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/BF02310791"},{"key":"ref13","doi-asserted-by":"crossref","unstructured":"J. Choi, X. Liu, S. Smith, and T. Simon, Blocking optimization techniques for sparse tensor computation, in Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS), IEEE, 2018, pp. 568\u2013577.","DOI":"10.1109\/IPDPS.2018.00066"},{"key":"ref14","first-page":"77","volume":"27","author":"Comon P.","year":"1994","journal-title":"IFAC Proc."},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jneumeth.2015.03.018"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1137\/140962292"},{"key":"ref17","first-page":"533","volume":"15","author":"Cuturi M.","year":"2014","journal-title":"J. Mach. Learn. Res."},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7439(99)00047-7"},{"key":"ref19","first-page":"49","volume":"2","author":"Mahalanobis P. C.","year":"1936","journal-title":"Proc. Natl. Instit. Sci. India"},{"key":"ref20","unstructured":"N. Dewaele, P. Breiding, and N. Vannieuwenhoven, The Condition Number of Many Tensor Decompositions Is Invariant Under Tucker Compression, manuscript, 2021."},{"key":"ref21","volume-title":"Foundations of the PARAFAC Procedure: Models and Conditions for an Explanatory Multimodal Factor Analysis","author":"Harshman R. A.","year":"1970"},{"key":"ref22","doi-asserted-by":"crossref","unstructured":"K. Hayashi, G. Ballard, J. Jiang, and M. Tobia, Shared Memory Parallelization of MTTKRP for Dense Tensors, preprint, arXiv:1708.08976, 2017.","DOI":"10.1145\/3178487.3178522"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1145\/2512329"},{"key":"ref24","first-page":"164","volume":"6","author":"Hitchcock F. L.","year":"1927","journal-title":"Stud. Appl. Math."},{"key":"ref25","unstructured":"A. Hyv\u00e4rinen, Survey on Independent Component Analysis, manuscript, 1999."},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2015.10.002"},{"key":"ref27","unstructured":"O. Kaya, High Performance Parallel Algorithms for Tensor Decompositions, Ph.D. thesis, Universit\u00e9 de Lyon, 2017."},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0525-3"},{"key":"ref29","unstructured":"O. Kaya and B. U\u00e7ar, Parallel CP Decomposition of Sparse Tensors Using Dimension Trees, Ph.D. thesis, Inria-Research Centre Grenoble-Rh\u00f4ne-Alpes, 2016\n                      ."},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1109\/10.867928"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1137\/07070111X"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1137\/100801482"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1561\/2200000019"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1002\/nla.1877"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1137\/17M1116295"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1016\/j.camwa.2018.11.001"},{"key":"ref37","unstructured":"L.H. Lim, Singular values and eigenvalues of tensors: A variational approach, in Proceedings of the 1st IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, IEEE, 2005, pp. 129\u2013132."},{"key":"ref38","unstructured":"L. Ma and E. Solomonik, Accelerating Alternating Least Squares for Tensor Decomposition by Pairwise Perturbation, preprint, arXiv:1811.10573, 2018."},{"key":"ref39","doi-asserted-by":"crossref","unstructured":"L. Ma and E. Solomonik, Efficient parallel CP decomposition with pairwise perturbation and multi-sweep dimension tree, in Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS), IEEE, 2021, pp. 412\u2013421.","DOI":"10.1109\/IPDPS49936.2021.00049"},{"key":"ref40","doi-asserted-by":"crossref","unstructured":"K. Maruhashi, F. Guo, and C. Faloutsos, Multiaspectforensics: Pattern mining on large-scale heterogeneous networks with tensor analysis, in Proceedings of the International Conference on Advances in Social Networks Analysis and Mining, IEEE, 2011, pp. 203\u2013210.","DOI":"10.1109\/ASONAM.2011.80"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1002\/cem.1180080207"},{"key":"ref42","unstructured":"D. Mitchell, N. Ye, and H. De Sterck, Nesterov Acceleration of Alternating Least Squares for Canonical Tensor Decomposition, preprint, arXiv:1810.05846, 2018."},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2011.04.019"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1039\/c3ay41160e"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1016\/j.sigpro.2007.07.024"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7439(97)00031-2"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2013.2269903"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1137\/100808034"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-10-8058-6"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1137\/06065577"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1137\/140989340"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1080\/03081087.2016.1277508"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1137\/130907215"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2017.2690524"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1137\/20M1344561"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-015-9761-5"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1137\/120868323"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1080\/03081087.2015.1083933"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.1002\/wcms.1340"},{"key":"ref60","doi-asserted-by":"crossref","unstructured":"P. Tichavsk\u00fd, A. H. Phan, and A. Cichocki, A further improvement of a fast damped Gauss-Newton algorithm for CANDECOMP-PARAFAC tensor decomposition, in Proceedings of the International Conference on Acoustics, Speech and Signal Processing, IEEE, 2013, pp. 5964\u20135968.","DOI":"10.1109\/ICASSP.2013.6638809"},{"key":"ref61","doi-asserted-by":"publisher","DOI":"10.1016\/j.sigpro.2017.04.001"},{"key":"ref62","doi-asserted-by":"publisher","DOI":"10.1016\/j.chemolab.2004.07.003"},{"key":"ref63","doi-asserted-by":"publisher","DOI":"10.1016\/j.csda.2004.11.013"},{"key":"ref64","doi-asserted-by":"publisher","DOI":"10.1137\/110843587"},{"key":"ref65","doi-asserted-by":"publisher","DOI":"10.1137\/19M125950X"},{"key":"ref66","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2017.08.014"},{"key":"ref67","doi-asserted-by":"publisher","DOI":"10.1137\/14097968X"},{"key":"ref68","doi-asserted-by":"crossref","unstructured":"G. Zen, E. Ricci, and N. Sebe, Simultaneous ground metric learning and matrix factorization with earth mover\u2019s distance, in Proceedings of the 22nd International Conference on Pattern Recognition, IEEE, 2014, pp. 3690\u20133695.","DOI":"10.1109\/ICPR.2014.634"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/22M1490739","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:19:44Z","timestamp":1787332784000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M1490739"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,3]]},"references-count":68,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,12,31]]}},"alternative-id":["10.1137\/22M1490739"],"URL":"https:\/\/doi.org\/10.1137\/22m1490739","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,3]]}}}