An Improvement on Ranks of Explicit Tensors

2011/02/02 by Benjamin Weitz, Weitz, Benjamin
Computer Science · Mathematics · #Algebra over a field #Algorithms and Data Compression #Combinatorics #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Corollary #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Mathematics #Pure mathematics #Rank (graph theory) #Simple (philosophy) #Tensor (intrinsic definition) #Tensor decomposition and applications #Tensor product #cs.CC #cs.DM

paper · pdf · doi:10.48550/arxiv.1102.0580

published in arXiv (Cornell University) (Cornell University)

openalex publication_date 2011/02/02 · arxiv created 2011/02/10 · arxiv updated 2011/02/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04

Abstract

We give constructions of n^k x n^k x n tensors of rank at least 2n^k - O(n^(k-1)). As a corollary we obtain an [n]^r shaped tensor with rank at least 2n^(r/2) - O(n^(r/2)-1) when r is odd. The tensors are constructed from a simple recursive pattern, and the lower bounds are proven using a partitioning theorem developed by Brockett and Dobkin. These two bounds are improvements over the previous best-known explicit tensors that had ranks n^k and n^(r/2) respectively

Related

• Explicit tensors of border rank at least 2n-1
• Tensor rank and dimension expanders
• Rank of tensors with size 2 x ... x 2
• A simple estimation of the maximal rank of tensors with two slices by row and column operations, symmetrization and induction
• Upper bound of typical ranks of m x n x ((m-1)n-1) tensors over the real number field