ECCC - TR26-301
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-301 | 4th November 2026 16:05

Asymptotic non-negative rank can be exponentially smaller than non-negative rank

RSS-Feed




TR26-301
Authors: Pavel Hrubes
Publication: 4th November 2026 18:25
Downloads: 42
Keywords: 


Abstract:

We investigate the behavior of the non-negative rank of a matrix, $\hbox{rk}_+$, on Kronecker product, $\times$. Beasley et al. [2013] constructed matrices with $\hbox{rk}_+(M\times M)$ strictly smaller than $\hbox{rk}_+(M)^2$.
We will show that i) there exists an $M$ with $\hbox{rk}_+(M\times M)\leq O(\hbox{rk}_+(M)\log(\hbox{rk}_+(M))$.

Defining asymptotic non-negative rank as $\overline{\hbox{rk}}_+(M):= \lim_{k\rightarrow \infty} \sqrt[k]{{\hbox{rk}}_+(M^{(k)})}$, where $M^{(k)}$ is the $k$-th Kronecker power, we show that
ii) there exists an $M$ with $\overline{\hbox{rk}}_+(M)\leq O(\log \hbox{rk}_+(M))$,
iii) there exist $M,N$ with $\overline{\hbox{rk}}_+(M\times N)<\overline{\hbox{rk}}_+(M)\overline{\hbox{rk}}_+(N)$.

We also refute a conjecture of Vandaele et al. [2016] that $\hbox{rk}_+(M\times M)\geq \Omega(\hbox{rk}_+(M)\hbox{rk}(M))$.



ISSN 1433-8092 | Imprint