Abstract
We study the problem of constructing explicit families of matrices which cannot be expressed as a product of a few sparse matrices. In addition to being a natural mathematical question on its own, this problem appears in various incarnations in computer science; the most significant being in the context of lower bounds for algebraic circuits which compute linear transformations, matrix rigidity and data structure lower bounds.
We first show, for every constant d, a deterministic construction in time exp(n^(1Ω(1/d))) of a family {M_n} of n × n matrices which cannot be expressed as a product M_n = A_1 ⋯ A_d where the total sparsity of A_1,…,A_d is less than n^(1+1/(2d)). In other words, any depthd linear circuit computing the linear transformation M_n⋅ 𝐱 has size at least n^(1+Ω(1/d)). This improves upon the prior best lower bounds for this problem, which are barely superlinear, and were obtained by a long line of research based on the study of superconcentrators (albeit at the cost of a blow up in the time required to construct these matrices).
We then outline an approach for proving improved lower bounds through a certain derandomization problem, and use this approach to prove asymptotically optimal quadratic lower bounds for natural special cases, which generalize many of the common matrix decompositions.
BibTeX  Entry
@InProceedings{kumar_et_al:LIPIcs:2020:12557,
author = {Mrinal Kumar and Ben Lee Volk},
title = {{Lower Bounds for Matrix Factorization}},
booktitle = {35th Computational Complexity Conference (CCC 2020)},
pages = {5:15:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771566},
ISSN = {18688969},
year = {2020},
volume = {169},
editor = {Shubhangi Saraf},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12557},
URN = {urn:nbn:de:0030drops125578},
doi = {10.4230/LIPIcs.CCC.2020.5},
annote = {Keywords: Algebraic Complexity, Linear Circuits, Matrix Factorization, Lower Bounds}
}
Keywords: 

Algebraic Complexity, Linear Circuits, Matrix Factorization, Lower Bounds 
Collection: 

35th Computational Complexity Conference (CCC 2020) 
Issue Date: 

2020 
Date of publication: 

17.07.2020 