Source-linked AI summary
Tensor surgery and tensor rank
Matthias Christandl, Jeroen Zuiddam
TL;DR
The paper studies rank and exponent bounds for graph tensors, extending beyond the previously known odd cycles of size at most five. It introduces tensor surgery and proves nontrivial bounds for odd-cycle tensors, with exponent bounds optimal when ω = 2.
Problem
The exponent of graph tensors is an open question, and results for larger cycle tensors had previously been known only for odd k ≤5.
Source: §1.2 · pp. 5–6Method
Tensor surgery transforms a decomposition of a starting tensor by splitting a tensor leg and taking a tensor product with another tensor, tracking the resulting rank increase.
Source: §1.1 · p. 3Results
For every odd k, the k-cycle tensor has nontrivial tensor rank, and the odd-cycle exponent bounds are optimal when ω = 2.
Source: §1.2 · p. 5Takeaways & Limitations
The approach reaches graph tensors without triangles, where directly upgrading Strassen’s triangle decomposition does not work.
Source: §1.1 · p. 2For decompositions attaining exponent k −1 + ε, tensor surgery cannot be improved by using local-rank information.
Source: §3.2 · p. 16
Abstract
from arXiv · showhide
We introduce a method for transforming low-order tensors into higher-order tensors and apply it to tensors defined by graphs and hypergraphs. The transformation proceeds according to a surgery-like procedure that splits vertices, creates and absorbs virtual edges and inserts new vertices and edges. We show that tensor surgery is capable of preserving the low rank structure of an initial tensor decomposition and thus allows to prove nontrivial upper bounds on tensor rank, border rank and asymptotic rank of the final tensors. We illustrate our method with a number of examples. Tensor surgery on the triangle graph, which corresponds to the matrix multiplication tensor, leads to nontrivial rank upper bounds for all odd cycle graphs, which correspond to the tensors of iterated matrix multiplication. In the asymptotic setting we obtain upper bounds in terms of the matrix multiplication exponent $\omega$ and the rectangular matrix multiplication parameter $\alpha$. These bounds are optimal if $\omega$ equals two. We also give examples that illustrate that tensor surgery on general graphs might involve the absorption of virtual hyperedges and we provide an example of tensor surgery on a hypergraph. Besides its relevance in algebraic complexity theory, our work has applications in quantum information theory and communication complexity.
1 Introduction
The paper develops tensor surgery to turn known decompositions into upper bounds for graph and hypergraph tensors. It applies the method to odd cycles, obtaining nontrivial rank bounds and exponent bounds that remain uniformly below the cycle length, and connects graph-tensor rank to quantum information and communication complexity.
1.1 Illustration
- Unlike direct upgrading of Strassen’s decomposition, which does not work for graphs without triangles, surgery gives nontrivial rank bounds for tensors of such graphs.The paper uses the five-cycle as an example of a graph without triangles.Source: §1.1 · pp. 2–3
1 Introduction
- Tensor surgery transforms a known decomposition by splitting a tensor leg and inserting another tensor, while tracking the resulting rank increase.The transformed decomposition then gives a bound for the goal tensor.Source: §1 · p. 1, §1.1 · p. 3
1.1 Illustration
- For the five-cycle tensor, the construction gives rank at most 31, improving on the trivial decomposition of size 32.The example combines six rank-4 terms with one rank-7 term.Source: §1.1 · p. 4
1.2 Main results
- For every odd cycle, the paper obtains nontrivial tensor-rank upper bounds; this was previously known only for odd k ≤5.It also proves an upper bound on odd-cycle exponents in terms of the dual matrix multiplication exponent α.Source: §1.2 · p. 5
- Odd-cycle exponents are bounded away from the cycle length, and if ω = 2 then ω_k = k −1 for all odd k.The paper also reports that R(T2(C5)) lies between 25 and 31.Source: §1.2 · p. 5
- Tensor surgery also extends to hypergraphs by inserting a hypergraph in place of a graph.The paper explores this variant and derives asymptotic-rank results similar to those for cycle graphs.Source: §1.2 · pp. 5–6
1.3 Connections to other work
- Graph-tensor rank has applications in quantum information, where graph tensors represent shared EPR pairs, and in communication complexity, where they correspond to graphwise equality problems.The paper relates bounds on graph-tensor rank to bounds on the complexity of these problems.Source: §1.3 · p. 6
2 Preliminaries
The preliminaries define graph tensors and rank-related measures, then establish flattening-based lower bounds for graph tensors. They also situate cycle-tensor exponents relative to matrix multiplication and prior lower-bound methods.
2 Preliminaries
- The preliminaries introduce graph tensors, tensor-rank notions, exponent characterizations, and flattening and Young-flattening lower-bound methods.They also review the matrix multiplication tensor and rectangular matrix multiplication parameters used in discussing cycle exponents.Source: §2 · p. 7, §2.2 · p. 9
2.1 Graph tensors
- Graph tensors Tn(G) assign a tensor leg to each vertex and share a summed index across each edge; the construction extends to hypergraphs and tensor powers correspond to multigraph copies.The tensor is unchanged in rank by vertex or edge ordering, up to local GL-action.Source: §2.1 · pp. 7–8
2.2 Tensor rank and exponent
- Tensor rank is the minimum number of simple tensors in a decomposition, while border rank allows approximation; asymptotic exponent measures rank growth, and subexponent measures conversion from unit tensors by restriction.For graph tensors, the paper focuses on bounding cycle exponents beyond the triangle, whose exponent is the matrix multiplication exponent ω.Source: §2.2 · pp. 8–9
2.3 Lower bound methods
- A maximum-cut flattening of Tn(G) has matrix rank n^f(G), yielding lower bounds on tensor rank and exponent; for bipartite graphs, the inequalities are equalities.For odd cycles, the stated bounds are n^(k−1) ≤ R(Tn(Ck)) and k − 1 ≤ ω(T2(Ck)); Young flattenings improve the border-rank bound for odd k, but no known Young flattening improves the asymptotic maximum-cut bound.Source: §2.3 · pp. 10–11
3 Tensor surgery on cycles
Tensor surgery yields rank bounds for odd-cycle tensors and asymptotic exponent bounds using matrix multiplication parameters. The cycle results rely on tracking local ranks through surgery, while covering and distilling provides another route to exponent bounds.
3.1 Tensor rank
- For every odd k, T(Ck) has rank at most 2^k−1, with a decomposition whose first tensor leg has local rank 1 in 2^k−2 summands and rank 2 in one.The proof inductively applies surgery to a cycle tensor, using four summands for rank-1 local-rank legs and seven for the rank-2 case.Source: §3.1 · pp. 11–12
- R(T4(C5)) ≤937 and its border rank is at most 910, by applying surgery to matrix-multiplication tensor decompositions.The respective bounds use rank inputs 26 and 49, versus border-rank inputs 24 and 46.Source: §3.1 · p. 13
3.2 Exponent
- If the matrix multiplication exponent ω equals 2, then every odd-cycle exponent satisfies ωk=k−1.More generally, surgery gives ωk+ℓ−1 ≤ ωk + ωℓ.Source: §3.2 · p. 14
- When β is bounded away from k−1, average and maximum local rank have a gap, making improvement through local-rank analysis possible.However, decompositions attaining exponent k−1+ε in the weighted-cycle setting must have near-maximal local ranks, so that analysis cannot improve the surgery bound there.Source: §3.2 · pp. 15–16
- The exponent bound for odd cycles converges to k−α as k grows, and from k=11 onward Theorem 3.9 gives the best listed upper bound.The proof starts with unbalanced cycle tensors and cyclically symmetrizes them to obtain balanced cycles.Source: §3.2 · pp. 15–16
3.3 Covering and distilling
- By the asymptotic sum inequality for cycles (Proposition 27 in [BCZ17]), ω(T(C5)) ≤ (10ω − 2·3)/3, which is at most 5.90955.For Ck, covering by unbalanced triangles with edge-multiplicities (1, 1, α), costing 2 each, and distilling a k-cycle with multiplicity α yields ω(T(Ck)) ≤ k − α.Source: §3.3 · p. 17
4 Tensor surgery on general graphs and hypergraphs
The examples show tensor surgery on general graphs and hypergraphs, including absorption of a virtual hyperedge. The authors state that the bounds in this section cannot be obtained using only the previously mentioned covering and distilling technique.
4.1 The dome tensor
- ω(T(dome1,1)) = 3ω, while ω(T(dome1,4)⊗2) ≤ 24.These bounds are established in the dome-tensor examples.Source: §4.1 · p. 18
4.2 Tensor surgery for graphs with hypergraph insertion
- For the graph example, ω(T(G)) = 32 when ω = 2, and tensor surgery independently proves ω(T(G)) ≤ 32.The lower bound is 32; the surgery upper bound is 4 · 2 + 2 · 12 = 32.Source: §4.2 · p. 19
4.3 Tensor surgery for hypergraphs
- For the hypergraph example, surgery gives ω(T(G)) ≤ 3ω.The proof bounds the cost by 2ω(T(dome1,1)) ≤ 3ω.Source: §4.3 · p. 20
- Replacing dome1,1 with dome1,4 yields an exact result analogous to Proposition 4.3.A reviewer also notes that the Proposition 4.4 upper bound can be obtained by covering with cycle graphs and distilling 3-cycles to obtain the doubled hypergraph.Source: §4.3 · p. 20