2026-08-17T08:54:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5339 2024-03-06T10:36:21Z ddc:004 open_access

Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms Ge, Rong Ma, Tengyu sum of squares overcomplete tensor decomposition Tensor rank and low-rank tensor decompositions have many applications in learning and complexity theory. Most known algorithms use unfoldings of tensors and can only handle rank up to n^{\lfloor p/2 \rceil} for a p-th order tensor. Previously no efficient algorithm can decompose 3rd order tensors when the rank is super-linear in the dimension. Using ideas from sum-of-squares hierarchy, we give the first quasi-polynomial time algorithm that can decompose a random 3rd order tensor decomposition when the rank is as large as n^{3/2}/poly log n. We also give a polynomial time algorithm for certifying the injective norm of random low rank tensors. Our tensor decomposition algorithm exploits the relationship between injective norm and the tensor components. The proof relies on interesting tools for decoupling random variables to prove better matrix concentration bounds. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rong Ge and Tengyu Ma 2015 Is Part Of LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2015.829 urn:nbn:de:0030-drops-53394 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.829 eng https://creativecommons.org/licenses/by/3.0/legalcode