arXiv:2105.01751

Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

제출 2021-05-04

원문 초록

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 specifically, we provide efficient learning algorithms that run in randomized polynomial time over general fields and in deterministic polynomial time over the reals and the complex numbers for the following classes: (1) Set-multilinear depth-$3$ circuits of constant top fan-in $\Sigma\Pi\Sigma\{\sqcup_j X_j\}(k)$ circuits). As a consequence of our algorithm, we obtain the first polynomial time algorithm for tensor rank computation and optimal tensor decomposition of constant-rank tensors. This result holds for $d$ dimensional tensors for any $d$, but is interesting even for $d=3$. (2) Sums of powers of constantly many linear forms ($\Sigma\wedge\Sigma$ circuits). As a consequence we obtain the first polynomial-time algorithm for tensor rank computation and optimal tensor decomposition of constant-rank symmetric tensors. (3) Multilinear depth-3 circuits of constant top fan-in (multilinear $\Sigma\Pi\Sigma(k)$ circuits). Our algorithm works over all fields of characteristic 0 or large enough characteristic. Prior to our work the only efficient algorithms known were over polynomially-sized finite fields (see. Karnin-Shpilka 09'). Prior to our work, the only polynomial-time or even subexponential-time algorithms known (deterministic or randomized) for subclasses of $\Sigma\Pi\Sigma(k)$ circuits that also work over large/infinite fields were for the setting when the top fan-in $k$ is at most $2$ (see Sinha 16' and Sinha 20').

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.