Average-case linear matrix factorization and reconstruction of low width algebraic branching programs

Abstract

A matrix X is called a linear matrix if its entries are affine forms, i.e., degree one polynomials in n variables. What is a minimal-sized representation of a given matrix F as a product of linear matrices? Finding such a minimal representation is closely related to finding an optimal way to compute a given polynomial via an algebraic branching program. Here we devise an efficient algorithm for an average-case version of this problem. Specifically, given $w,d,n \in \mathbb{N}$ and blackbox access to the w² entries of a matrix product $F = X_1 \cdots X_d$, where each $X_i$ is a $w \times w$ linear matrix over a given finite field $\mathbb{F}_q$, we wish to recover a factorization $F = Y_1 \cdots Y_{d'}$, where every $Y_i$ is also a linear matrix over $\mathbb{F}_q$ (or a small extension of $\mathbb{F}_q$). We show that when the input F is sampled from a distribution defined by choosing random linear matrices $X_1, \ldots, X_d$ over $\mathbb{F}_q$ independently and taking their product and $n \geq 4w^2$ and ${\rm char}(\mathbb{F}_q) = (dn)^{\varOmega(1)}$, then an equivalent factorization $F = Y_1 \cdots Y_d$ can be recovered in (randomized) time $(dn \log q)^{O(1)}$. In fact, we give a (worst-case) polynomial time randomized algorithm to factor any non-degenerate or pure matrix product (a notion we define in the paper) into linear matrices; a matrix product $F = X_1 \cdots X_d$ is pure with high probability when the $X_i$'s are chosen independently at random. We also show that in this situation, if we are instead given a single entry of F rather than its w² correlated entries, then the recovery can be done in (randomized) time $(d^{w^3} n \log q)^{O(1)}$.