Tensor rank and dimension expanders

Abstract

We prove a lower bound on the rank of tensors constructed from families of linear maps that `expand' the dimension of every subspace. Such families, called {\em dimension expanders} have been studied for many years with several known explicit constructions. Using these constructions we show that one can construct an explicit $[D]\times [n]\times [n]$-tensor with rank at least $(2-\hat{I}\mu )n$, with $D$ a constant depending on $\hat{I}\mu$. Our results extend to border rank over the real or complex numbers.

9 pages