Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits
Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits
We give new and efficient black-box reconstruction algorithms for some classes of depth-3 arithmetic circuits. As a consequence, we obtain the first efficient algorithm for computing the tensor rank and for finding the optimal tensor decomposition as a sum of rank-one tensors when then input is a constant-rank tensor. More …