Faster search for tensor decomposition over finite fields

2025/02/17 by Yang, Jason
#Computational Complexity (cs.CC) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2502.12390

Abstract

We present an O^*(|\mathbbF|^min\R, ∑_{d≥ 2} n_d\ + (R-n₀)(∑_{d≠ 0} n_d))-time algorithm for determining whether the rank of a concise tensor T∈\mathbbF^n₀×…× n_D-1 is ≤ R, assuming n₀≥…≥ n_D-1 and R≥ n₀. For 3-dimensional tensors, we have a second algorithm running in O^*(|\mathbbF|^{n₀+n₂ + (R-n₀+1-r_*)(n₁+n₂)+r_*2}) time, where r_*:=\lfloor(R)/(n₀)\rfloor+1. Both algorithms use polynomial space and improve on our previous work, which achieved running time O^*(|\mathbbF|^{n₀+(R-n₀)(∑_d n_d)}).

Related

• Depth-first search for tensor rank and border rank over finite fields
• Low-Rank Tensor Decomposition over Finite Fields
• Overcomplete Tensor Decomposition via Koszul-Young Flattenings
• On the complexity of finding tensor ranks
• Fast algorithm for overcomplete order-3 tensor decomposition