Name
Title | ||
|---|---|---|
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 w2 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 w2
correlated entries, then the recovery can be done in (randomized)
time \((d^{w^3} n \log q)^{O(1)}\). |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/s00037-019-00189-0 | Electronic Colloquium on Computational Complexity (ECCC) |
Keywords | Field | DocType |
Algebraic branching programs, equivalence testing, matrix factorization, pseudorandom polynomial families, 68Q05, 68Q15, 68Q17, 68Q32 | Discrete mathematics,Algebraic number,Matrix decomposition,Mathematics,Branching (version control) | Journal |
Volume | Issue | ISSN |
25 | 4 | 1420-8954 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Neeraj Kayal | 1 | 263 | 19.39 |
| Vineet Nair | 2 | 5 | 2.11 |
| Chandan Saha | 3 | 227 | 16.91 |