Faster & Deterministic FPT Algorithm for Worst-Case Tensor Decomposition

Tensors, higher-dimensional analogs of matrices, are multi-dimensional arrays with entries from a field $𝔽$. For instance, a 3-dimensional tensor can be written as $𝒯=({\alpha }_{i,j,k})\in {𝔽}^{n_1\times n_2\times n_3}$. The notion of tensor rank and tensor decomposition are one of the most important tools in modern science. Tensor rank and decomposition have become fundamental tools in various branches of science, with applications in machine learning, statistics, signal processing, and computational complexity. Even within machine learning theory, tensor decomposition algorithms are leveraged to give efficient algorithms for phylogenetic reconstruction [40], topic modeling [2], community detection [3], independent component analysis [39], and learning various mixture models [27, 30]. For more details on the applications of tensor decomposition and the rich theory of tensors in general, we refer the reader to the detailed monograph by Landsberg [37] and the references therein.

We will work with general $d$-dimensional tensors $𝒯=({\alpha }_{j_1,j_2,\mathrm{\dots },j_d})\in {𝔽}^{n_1\times \mathrm{\cdots }\times n_d}$. The rank of a tensor $𝒯$ is defined as the smallest $r$ for which $𝒯$ can be written as a sum of $r$ tensors of rank 1, where a rank-1 tensor is a tensor of the form $v_1\otimes \mathrm{\cdots }\otimes v_d$ with $v_i\in {𝔽}^{n_i}$. Here, $\otimes$ denotes the Kronecker (outer) product, also known as the tensor product. The expression of $𝒯$ as a sum of such rank-1 tensors over the field $𝔽$ is called $𝔽$-tensor decomposition, or simply tensor decomposition.

Tensor decomposition is a notoriously¹¹1The seminal work of Lim and Hiller [26] aptly justifies the use of this adjective. difficult problem. Håstad [25] showed that determining the tensor rank is an NP-hard problem over $\mathbb{Q}$ and NP-complete over finite fields. The follow-up work of Schafer and Stefankovic [42] further improved our understanding by giving a very tight reduction from algebraic system solving. Formally, they show that for any field $𝔽$, given a system $S$ of algebraic equations over $𝔽$, we can in polynomial time construct a 3-dimensional tensor ${\tau }_S$ and an integer $k$ such that $S$ has a solution in $𝔽$ iff ${\tau }_S$ has rank at most $k$ over $𝔽$.

Despite the known hardness results, tensor decomposition remains widely studied due to its broad applicability. There is a rich history of tensor decomposition algorithms in the literature. Most of these algorithms are average-case (i.e., they work when the entries are sampled randomly from a distribution), or they work when the input is non-degenerate (i.e., when the tensor components are chosen from a Zariski open set), or they are heuristic. See, for instance, [14, 4, 36]. This area also includes interesting active research directions, such as making these algorithms noise-resilient and studying their smoothed analysis [6, 43, 16].
On the other hand, tensor decomposition in the worst-case scenario has only recently started to receive attention. Firstly, the work of Bhargava, Saraf, and Volkovich [11] provided an $n^{k^k}$ time algorithm to decompose rank-$k$ tensors, showing that an efficient algorithm exists to decompose fixed-rank tensors. The next natural step in furthering the understanding of this NP-hard problem is studying its Fixed Parameter Tractability (FPT). In the FPT setting, the input instance comes with a parameter $k$ with specific quantities (e.g., the optimum treewidth of a graph). In our case of tensor decomposition, this parameter is the tensor rank. This setting treats $k$ as a parameter much smaller than the instance size $n$, thus relaxing the required runtime of the algorithm from $n^{𝒪(1)}$ to $f(k)\cdot n^{𝒪(1)}$, for any computable function $f$. The class FPT comprises parameterized problems that admit an algorithm with this running time.

Peleg, Shpilka, and Volk [41] designed a randomized FPT algorithm for decomposing rank-$k$ tensors. Specifically, they provided a randomized $k^{k^{k^{𝒪(k)}}}\mathrm{poly}(n,d)$ time algorithm for decomposing rank-$k$ tensors. As a direct consequence, they demonstrated that tensors can be decomposed in polynomial time even beyond the constant tensor rank up to $𝒪(\log \log \log n/\log \log \log \log n)$.

Both these works use a standard connection between tensor decomposition and reconstruction of a special case of depth-3 circuits. We start by describing this connection below.

As described in the previous section, the problem of worst-case tensor decomposition, or equivalently, proper learning of $\mathrm{\Sigma }\mathrm{\Pi }{\mathrm{\Sigma }}_{\left\{{\bigsqcup }_j{X}_j\right\}}(k)$ circuits, was studied in [11], where the authors presented a deterministic algorithm with a running time of $\text{poly}(d^{k^3},k^{k^{k^{10}}},n)$. This algorithm runs in polynomial time when $k$ is a constant. This was extended beyond constant rank in the recent work of [41], where they proposed a randomized algorithm with a running time of $k^{k^{k^{𝒪(k)}}}\cdot \text{poly}(n,d)$. This algorithm runs in randomized polynomial time for tensor rank $k=𝒪\left(\frac{\log \log \log n}{\log \log \log \log n}\right)$.

In [41, Section 1.4], two open problems were posed: Firstly, to understand how the tractability of tensor decomposition changes as tensor rank increases; and secondly, whether a deterministic fixed-parameter tractable (FPT) algorithm exists for worst-case tensor decomposition.

We make significant progress in answering the first question and completely resolve the second. We now state our result for learning set-multilinear $\mathrm{\Sigma }\mathrm{\Pi }\mathrm{\Sigma }(k)$ arithmetic circuits.

As a direct consequence of the above theorem, we get the following corollary.

Note that just reading the entries of the tensor will require $n^d$ time. However, the above corollary states that in the low-rank case, we can learn the decomposition with much fewer measurements of the tensor.

As a direct consequence of the above result, we can perform the tensor decomposition for any tensor with tensor rank $k=𝒪({(\log n)}^{1/C})$ in $\text{poly}(n,d)$ time for a fixed constant $C$. This substantially improves the previously known tensor rank bound of $k=𝒪\left(\frac{\log \log \log n}{\log \log \log \log n}\right)$.

On the intractability/hardness side, using Håstad’s [25] tight reduction between tensor rank and SAT, we see that even testing tensor rank will require $2^{\mathrm{\Omega }(k)}\cdot \text{poly}(n,d)$ time assuming the Exponential Time Hypothesis (ETH, [29]). This demonstrates that our time complexity is somewhat tight (with respect to the parameter $k$). We formalize this in the observation below.

As the introduction mentions, we will use the connection between tensor rank and set multilinear depth-3 circuits. For readers who are not very familiar with the algebraic circuit representation of tensors, we emphasize that we are simply performing standard efficient operations on tensors and use this notation solely for ease of analysis. We refer the reader to subsection 1 to familiarize themselves with this notation. Overall, we are simply performing weighted contractions (partial evaluations) on our tensor after a change of basis (variable reduction) to first learn most of the vectors in the decomposition. We then use the uniqueness of low-rank tensor decomposition in high-dimensional settings to learn the remaining vectors in the decomposition. We now give a detailed sketch of our algorithm using set-multilinear depth-3 circuits terminology.

Recall that we only need black-box access to $f_{\tau }$, i.e., we can query evaluations of $f_{\tau }$ at fixed points in ${𝔽}^n$ in constant time, rather than requiring a dense representation of the tensor/polynomial.

Through some preprocessing, we can assume the following:

• $\mathrm{■}$

  We know $k$, the rank of the tensor or equivalently the minimum $k$ such that $f_{\tau }$ is computable by a $\mathrm{\Sigma }\mathrm{\Pi }{\mathrm{\Sigma }}_{\left\{{\bigsqcup }_j{X}_j\right\}}(k)$. Indeed, we can assume the value of $k$ and output the first $k$ for which the learning algorithm works, since we can always test if our output is correct deterministically using an existing black-box PIT algorithm. This affects the time complexity by a multiple of $k$.

• $\mathrm{■}$

  We can strip off $f_{\tau }$ with any linear factors ($\mathrm{Lin}(f_{\tau }):=\{\mathrm{\ell }:\mathrm{\ell }|f_{\tau }\}$), since any optimal decomposition(with tensor rank $k$) of $\mathrm{NonLin}(f_{\tau })=\frac{f_{\tau }}{{\prod }_{\mathrm{\ell }\in \mathrm{Lin}(f_{\tau })}\mathrm{\ell }}$ gives an optimal decomposition for $f_{\tau }$ as well. This comes from a result of the factoring of $\mathrm{\Sigma }\mathrm{\Pi }{\mathrm{\Sigma }}_{\left\{{\bigsqcup }_j{X}_j\right\}}(k)$ circuits from [45] described in Lemma 10 that shows that if $f_{\tau }$ is computable by a $\mathrm{\Sigma }\mathrm{\Pi }{\mathrm{\Sigma }}_{\left\{{\bigsqcup }_j{X}_j\right\}}(k)$ circuit then any irreducible factor $\mathrm{NonLin}(f_{\tau })$ can also be computed by a product of $\mathrm{\Sigma }\mathrm{\Pi }{\mathrm{\Sigma }}_{\left\{{\bigsqcup }_j{X}_j\right\}}(k)$ circuits. It also describes how to obtain black-box access to these irreducible factors in $2^{𝒪({\log }^{2}k)}\cdot \mathrm{poly}(n,d)$ time.

• $\mathrm{■}$

  We can assume that $|X_j|\le k$. This follows from the width reduction step, see [11, Section 5.1] and Lemma 11. In the low-degree reconstruction in Lemma 12, the system of polynomial equations has $kwd$ variables, which go into the exponent in the running time required to find a solution. Therefore we must be able to reduce the width to $k$, so we can obtain an FPT algorithm.

• $\mathrm{■}$

  Note that there can be multiple optimal $\mathrm{\Sigma }\mathrm{\Pi }{\mathrm{\Sigma }}_{\left\{{\bigsqcup }_j{X}_j\right\}}$ decompositions for $f_{\tau }$, but for the sake of argument, we will fix one representation $C$ and argue the proof using this fixed representation $C$.

In this section, we will define notations and develop the basic preliminaries in Algebraic complexity and reconstruction required to understand this work. An experienced reader can presumably skip to Section 5. A more detailed set of preliminaries with Notations can be found in the full version.

We will be clustering all gates close to the gate $T_1$ to create a representation with a cluster of gates containing $T_1$, such that the remaining gates are far from the cluster. The gates clubbed together will be represented by a set $A\subseteq [k]$, with $C_A={\sum }_{i\in A}{T}_i$, fulfilling the properties described in Lemma 15.

For any set of gates $A\subseteq [k]$ of circuit $C$, we can only consider the initial representation of $C$ such that $Lin(C_A)$ and the gcd of the gates in $A$ are the same, i.e., $sim(C_A)$ has no linear factors. Such a representation will always exist for the polynomial computed by $C_A$ with a depth 3 set-multilinear circuit and the same top fan-in, which can be inferred from Lemma 10.

Next, we introduce the following definition of distance that we will be using to define the cluster representation.

We will use the cluster representation with the properties described in the following lemma.

Due to space constraints, we defer the formal proof of the above lemma to the full version of the paper.

Check out the full version to compare it to previously known clusterings.

Given a $\mathrm{\Sigma }\mathrm{\Pi }{\mathrm{\Sigma }}_{{\cup }_j{X}_j}(k)$ circuit $C=T_1+T_2+\mathrm{\dots }+T_k={\sum }_{i\in [k]}{\prod }_{j\in [d]}{\mathrm{\ell }}_{i,j}$ computing polynomial $f$, we can use the techniques in [11] to learn a circuit $C^{\prime }=T_1^{\prime }+\mathrm{\dots }+T_k^{\prime }$ such that .

We briefly explain how such a $C^{\prime }$ is obtained in time $k^{𝒪(k)}\cdot Sy{s}_{𝔽}(k^{𝒪(1)})\cdot \text{poly}(n,d)$. We will use Lemma 12 to do deterministic reconstruction when the degree is $d\le k^3$ in time $Sy{s}_{𝔽}(k^{2}d,k^d,d)$. Now, similar to Lemma 5.6 in [11], we set all but $k^2$ variable parts to some random values and reconstruct the polynomial, which will be close to $C$ (on the variable parts that were not fixed), to obtain 2 independent linear forms ${\mathrm{\ell }}_1,{\mathrm{\ell }}_2\in C$ such that they are supported on the same variable part $X_i$. By setting ${\mathrm{\ell }}_1,{\mathrm{\ell }}_2$ to $0$ one at a time, and recursively calling reconstruction for set-multilinear $\mathrm{\Sigma }\mathrm{\Pi }\mathrm{\Sigma }(k-1)$ circuits, we obtain representations close to $C$. These close representations have each multiplication gate that is close to a multiplication gate in $C$ due to rank bounds as the gates that contain ${\mathrm{\ell }}_1$ are obtained when we go $mod{\mathrm{\ell }}_2$, and vice versa. As described in Lemma 5.7 of [11], we obtain $S=\{M_1,\mathrm{\dots },M_{|S|}\}$ of at most $2k-2$ $\mathrm{\Pi }\mathrm{\Sigma }$ circuits such that $\forall i\in [k],\exists j\in [2k-2]$ such that . Working with $k^{2k-2}$ possibilities, we get at least one circuit $C^{\prime }=T_1^{\prime }+\mathrm{\dots }+T_k^{\prime }$ such that .

The focus of this section will be on learning the cluster $C_A$ (which contains $T_1$). Due to our clustering algorithm ⁵⁵5We actually never run the clustering algorithm; it is just used for existential arguments., we know there exists a representation of $C=T_1+\mathrm{\dots }+T_k=C_A+{\sum }_{i\notin A}{T}_i$ such that $\mathrm{\Delta }(C_A)\le k^4+k^3$ and ${\mathrm{\Delta }}_A(C_A,T_i)\ge k^2+k$.

We will now define our useful variable parts by excluding from $\mathrm{Consistent}\text{-}\mathrm{VarPart}(C,C^{\prime })$ the partitions for which the linear forms in $C_A$ are not part of $Lin(C_A)$. Therefore, we define

As $\text{rk}(sim(C_A))\le k^4+k^3$, we have $|S(C,C^{\prime })|\ge d-k^4-k^3-k^2$. Our target remains to find a set of variable parts in $S$, such that we can fix them to some values that vanish other gates, but $C_A$ remains non-zero. We define any such fixing of variables $X_i$ to ${𝜶}_i$, contained as tuples in a set denoted by $ℒ$, that keeps gates $G$ (containing $T_1$) alive and sets the rest to $0$ as a $T_1$-isolating projection.

The goal of our computation will be getting black-box access to $C_A$, thus we define a good $T_1$-isolating projection which let’s us compute the black-box access to $C_A$.