Tensor rank and dimension expanders
By: Zeev Dvir
Potential Business Impact:
Makes computers understand complex math better.
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 - \epsilon)n$, with $D$ a constant depending on $\epsilon$. Our results extend to border rank over the real or complex numbers.
Similar Papers
Tensor rank and dimension expanders
Combinatorics
Makes computers understand complex math problems better.
The Fascinating World of 2 $\times$ 2 $\times$ 2 Tensors: Its Geometry and Optimization Challenges
Numerical Analysis
Explains how special math shapes differ from regular ones.
Slice rank and partition rank of the determinant
Combinatorics
Finds shorter ways to calculate big math problems.