Computing The Nc-Rank Via Discrete Convex Optimization On Cat(0) Spaces

          @misc{ scivideos_18803,
            doi = {},
            url = {https://simons.berkeley.edu/talks/computing-nc-rank-discrete-convex-optimization-cat0-spaces},
            author = {},
            keywords = {},
            language = {en},
            title = {Computing The Nc-Rank Via Discrete Convex Optimization On Cat(0) Spaces},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2021},
            month = {nov},
            note = {18803 see, \url{https://scivideos.org/index.php/Simons-Institute/18803}}
          }
          

Abstract

In this paper, we address the noncommutative rank (nc-rank) computation of a linear symbolic matrix A=A1 x1+A2 x2 +⋯+ Am xm, where each Ai is an n x n matrix over a field K, and xi (i=1,2,…,m) are noncommutative variables. For this problem, polynomial time algorithms were given by Garg, Gurvits, Oliveira, and Wigderson for K=Q, and by Ivanyos, Qiao, and Subrahmanyam for an arbitrary field K. We present a significantly different polynomial time algorithm that works on an arbitrary field K. Our algorithm is based on a combination of submodular optimization on modular lattices and convex optimization on CAT(0) spaces.