Computing the nc-rank via discrete convex optimization on CAT(0) spaces

In this paper, we address the noncommutative rank (nc-rank) computation of a linear symbolic matrix $$A=A_1{x}_1+A_2{x}_2+\cdots +A_m{x}_m,$$ where each $A_i$ is an $n\times n$ matrix over a field $\mathbb{K}$, and $x_i$ $(i=1,2,\dots ,m)$ are noncommutative variables. For this problem, polynomial time algorithms were given by Garg, Gurvits, Oliveira, and Wigderson for $\mathbb{K}=\mathbb{Q}$, and by Ivanyos, Qiao, and Subrahmanyam for an arbitrary field $\mathbb{K}$. We present a significantly different polynomial time algorithm that works on an arbitrary field $\mathbb{K}$. Our algorithm is based on a combination of submodular optimization on modular lattices and convex optimization on CAT(0) spaces.