< prev | up | next >

PDF logo Tensor rank: some lower and upper bounds

by Boris Alexeev, Michael Forbes, and Jacob Tsimerman

Abstract

The results of Strassen and Raz show that good enough tensor rank lower bounds have implications for algebraic circuit/formula lower bounds.

We explore tensor rank lower and upper bounds, focusing on explicit tensors. For odd \(d\), we construct field-independent explicit \(0/1\) tensors \(T\colon [n]^d\to \mathbb{F}\) with rank at least \(2n^{\lfloor d/2\rfloor}+n-\Theta(d \lg n)\). This matches (over \(\mathbb{F}_2\)) or improves (all other fields) known lower bounds for \(d=3\) and improves (over any field) for odd \(d>3\).

We also explore a generalization of permutation matrices, which we denote permutation tensors. We show, by counting, that there exists an order-3 permutation tensor with super-linear rank. We also explore a natural class of permutation tensors, which we call group tensors. For any group \(G\), we define the group tensor \(T_G^d\colon G^d\to \mathbb{F}\), by \(T_G^d(g_1,\dotsc,g_d)=1\) iff \(g_1 \dotsb g_d=1_G\). We give two upper bounds for the rank of these tensors. The first uses representation theory and works over large fields \(\mathbb{F}\), showing (among other things) that \(\operatorname{rank}_{\mathbb{F}}(T_G^d) \le \lvert G\rvert^{d/2}\). We also show that if this upper bound is tight, then super-linear tensor rank lower bounds would follow. The second upper bound uses interpolation and only works for abelian \(G\), showing that over any field \(\mathbb{F}\) that \(\operatorname{rank}_{\mathbb{F}}(T_G^d) \le O(\lvert G\rvert^{1+\lg d}\lg^{d-1}\lvert G\rvert)\). In either case, this shows that many permutation tensors have far from maximal rank, which is very different from the matrix case and thus eliminates many natural candidates for high tensor rank.

We also explore monotone tensor rank. We give explicit \(0/1\) tensors \(T\colon [n]^d\to \mathbb{F}\) that have tensor rank at most \(dn\) but have monotone tensor rank exactly \( n^{d-1} \). This is a nearly optimal separation.

Approximate citation

Boris Alexeev, Michael Forbes, and Jacob Tsimerman
Tensor rank: some lower and upper bounds
IEEE Conference on Computational Complexity 26 (2011), 283–291.

Useful links

PDF logoDirect PDF link
Journal icon Published journal version
DOI icon Persistent document object identifier (DOI)
arXiv icon arXiv online preprint server version
MathSciNet icon Math Reviews (MathSciNet) review
ECCC icon Electronic Colloquium on Computational Complexity (ECCC) version
Google Scholar icon Google Scholar entry
BiBTeX icon Individual BiBTex entry
< prev | up | next >