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 \({\rm exp}(n^{1-\Omega(1/d)})\) of a family \(\{M_n\}\) of \(n \times n\) matrices which cannot be expressed as a product \(M_n = A_1 \cdots A_d\) where the total sparsity of \(A_1,\ldots,A_d\) is less than \(n^{1+1/(2d)}\). In other words, any depth-d linear circuit computing the linear transformation \(M_n\cdot {\bf x}\) has size at least \(n^{1+\Omega(1/d)}\). The prior best lower bounds for this problem were barely super-linear, and were obtained by a long line of research based on the study of super-concentrators. We improve these lower bounds at the cost of a blow up in the time required to construct these matrices. Previously, however, such constructions were not known even in time \(2^{O(n)}\) with the aid of an NP oracle.
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Manindra Agrawal (2005). Proving Lower Bounds Via Pseudo-random Generators. In Proceedings of the 25th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2005),, 92–105. URL https://doi.org/10.1007/11590156_6
Manindra Agrawal, Rohit Gurjar, Arpita Korwar & Nitin Saxena (2015). Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits. SIAM J. Comput. 44(3), 669–697. URL https://doi.org/10.1137/140975103
Manindra Agrawal & V. Vinay (2008). Arithmetic Circuits: A Chasm at Depth Four. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008),, 67–75. URL https://doi.org/10.1109/FOCS.2008.32
Josh Alman & Lijie Chen (2019). Efficient Construction of Rigid Matrices Using an NP Oracle. InProceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2019), 1034–1055. IEEE Computer Society. URL https://doi.org/10.1109/FOCS.2019.00067
Josh Alman & R. Ryan Williams (2017). Probabilistic rank and matrix rigidity. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC 2017),, 641–652. ACM. URL https://doi.org/10.1145/3055399.3055484
Noga Alon & Pavel Pudlák (1994). Superconcentrators of Depths 2 and 3; Odd Levels Help (Rarely). J. Comput. Syst. Sci. 48(1), 194–202. URL https://doi.org/10.1016/S0022-0000(05)80027-3
Bruce Anderson, Jeffrey Jackson & Meera Sitharam (1998). Descartes' rule of signs revisited. Amer. Math. Monthly 105(5), 447–451. ISSN 0002-9890. URL https://doi.org/10.2307/3109807
Walter Baur & Volker Strassen (1983). The Complexity of Partial Derivatives. Theoretical Computer Science 22, 317–330. URL https://doi.org/10.1016/0304-3975(83)90110-X
Avraham Ben-Aroya, Dean Doron & Amnon Ta-Shma (2017). An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC 2017),, 1185–1194. ACM. URL https://doi.org/10.1145/3055399.3055423
Amey Bhangale, Prahladh Harsha, Orr Paradise & Avishay Tal (2020). Rigid Matrices From Rectangular PCPs or: Hard Claims Have Complex Proofs. In Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2020),, 858–869. URL https://doi.org/10.1109/FOCS46700.2020.00084
Nader H. Bshouty (2014). Testers and their applications. In Innovations in Theoretical Computer Science, ITCS'14, 2014, 327–352. URL https://doi.org/10.1145/2554797.2554828
Peter Bürgisser, Michael Clausen & Mohammad A. Shokrollahi (1997). Algebraic Complexity Theory, volume 315 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag. URL https://doi.org/10.1007/978-3-662-03338-8
Eshan Chattopadhyay & David Zuckerman (2019). Explicit two-source extractors and resilient functions. Ann. of Math. (2) 189(3), 653–705. ISSN 0003-486X. URL https://doi.org/10.4007/annals.2019.189.3.1
Bernard Chazelle (2001). The discrepancy method - randomness and complexity. Cambridge University Press. ISBN 978-0-521-00357-5. URL https://www.cs.princeton.edu/~chazelle/pubs/book.pdf
Gil Cohen (2017). Towards optimal two-source extractors and Ramsey graphs. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC 2017),, 1157–1170. ACM. URL https://doi.org/10.1145/3055399.3055429
Danny Dolev, Cynthia Dwork, Nicholas Pippenger & Avi Wigderson (1983). Superconcentrators, Generalizers and Generalized Connectors with Limited Depth (Preliminary Version). In Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC 1983),, 42–51. ACM. https://doi.org/10.1145/800061.808731
Zeev Dvir & Benjamin L. Edelman (2019). Matrix Rigidity and the Croot-Lev-Pach Lemma. Theory Comput. 15, 1–7. URL https://doi.org/10.4086/toc.2019.v015a008
Zeev Dvir, Alexander Golovnev & Omri Weinstein (2019). Static data structure lower bounds imply rigidity. In Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC 2019),, 967–978. ACM. URL https://doi.org/10.1145/3313276.3316348
Zeev Dvir & Allen Liu (2020). Fourier and Circulant Matrices are Not Rigid. Theory Comput. 16, 1–48. URL https://doi.org/10.4086/toc.2020.v016a020
Michael A. Forbes & Amir Shpilka (2012). On identity testing of tensors, low-rank recovery and compressed sensing. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC 2012),, Howard J. Karloff & Toniann Pitassi, editors, 163–172. ACM. URL https://doi.org/10.1145/2213977.2213995
Michael L. Fredman (1982). The Complexity of Maintaining an Array and Computing Its Partial Sums. J. ACM 29(1), 250–260. URL https://doi.org/10.1145/322290.322305
Michael L. Fredman & Michael E. Saks (1989). The Cell Probe Complexity of Dynamic Data Structures. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC 1989),, David S. Johnson, editor, 345–354. ACM. URL https://doi.org/10.1145/73007.73040
Joel Friedman (1993). A note on matrix rigidity. Combinatorica 13(2), 235–239. URL https://doi.org/10.1007/BF01303207
Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák & Emanuele Viola (2013). Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates. IEEE Trans. Information Theory 59(10), 6611–6627. URL https://doi.org/10.1109/TIT.2013.2270275
Ankit Gupta, Pritish Kamath, Neeraj Kayal & Ramprasad Saptharishi (2016). Arithmetic Circuits: A Chasm at Depth 3. SIAM J. Comput. 45(3), 1064–1079. URL https://doi.org/10.1137/140957123
Venkatesan Guruswami, Atri Rudra & Madhu Sudan (2018). Essential Coding Theory. URL https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/
Joos Heintz & Claus-Peter Schnorr (1980). Testing Polynomials which Are Easy to Compute (Extended Abstract). In Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC 1980),, 262–272. URL https://doi.org/10.1145/800141.804674
Stasys Jukna & Igor Sergeev (2013). Complexity of Linear Boolean Operators. Foundations and Trends in Theoretical Computer Science 9(1), 1–123. ISSN 1551-305X. URL https://doi.org/10.1561/0400000063
Erich Kaltofen & Michael F. Singer (1991). Size efficient parallel algebraic circuits for partial derivatives. In IV International Conference on Computer Algebra in Physical Research, 133–145. URL https://users.cs.duke.edu/~elk27/bibliography/91/KaSi91.pdf
Pascal Koiran (2012). Arithmetic Circuits: The Chasm at Depth Four Gets Wider. Theoretical Computer Science 448, 56–65. URL https://doi.org/10.1016/j.tcs.2012.03.041
Mrinal Kumar & Ben Lee Volk (2020). Lower Bounds for Matrix Factorization. In Proceedings of the 35th Annual Computational Complexity Conference (CCC 2020),, volume 169, 5:1–5:20. URL https://doi.org/10.4230/LIPIcs.CCC.2020.5
Kasper Green Larsen (2012). The cell probe complexity of dynamic range counting. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC 2012),, 85–94. ACM. URL https://doi.org/10.1145/2213977.2213987
Kasper Green Larsen (2014). On Range Searching in the Group Model and Combinatorial Discrepancy. SIAM J. Comput. 43(2), 673–686. URL https://doi.org/10.1137/120865240
Kasper Green Larsen, Omri Weinstein & Huacheng Yu (2018). Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC 2018),, 978–989. ACM. URL https://doi.org/10.1145/3188745.3188790
Daniel D. Lee & H. Sebastian Seung (2000). Algorithms for Non-negative Matrix Factorization. In Advances in Neural Information Processing Systems 13, Papers from Neural Information Processing Systems (NIPS) 2000, 556–562. MIT Press. URL http://proceedings.neurips.cc/paper/1861-algorithms-for-non-negative-matrix-factorization
Xin Li (2019). Non-Malleable Extractors and Non-Malleable Codes: Partially Optimal Constructions. In Proceedings of the 34th Annual Computational Complexity Conference (CCC 2019),, volume 137, 28:1–28:49. URL https://doi.org/10.4230/LIPIcs.CCC.2019.28
Satyanarayana V. Lokam (2009). Complexity Lower Bounds using Linear Algebra. Foundations and Trends in Theoretical Computer Science 4(1-2), 1–155. URL https://doi.org/10.1561/0400000011
Julien Mairal, Francis R. Bach, Jean Ponce & Guillermo Sapiro (2009). Online dictionary learning for sparse coding. In Proceedings of the 26th Annual International Conference on Machine Learning, ICML 2009, volume 382 of ACM International Conference Proceeding Series, 689–696. ACM. URL https://doi.org/10.1145/1553374.1553463
Jacques Morgenstern (1973). Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform. J. ACM 20(2), 305–306. URL https://doi.org/10.1145/321752.321761
Behnam Neyshabur & Rina Panigrahy (2013). Sparse Matrix Factorization. CoRR abs/1311.3315. URL http://arxiv.org/abs/1311.3315
Mihai Pǎtraşcu (2007). Lower bounds for 2-dimensional range counting. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC 2007),, 40–46. ACM. URL https://doi.org/10.1145/1250790.1250797
Mihai Pǎtraşcu & Erik D. Demaine (2006). Logarithmic Lower Bounds in the Cell-Probe Model. SIAM J. Comput. 35(4), 932–963. URL https://doi.org/10.1137/S0097539705447256
Nicholas Pippenger (1977). Superconcentrators. SIAM J. Comput. 6(2), 298–304. URL https://doi.org/10.1137/0206022
Nicholas Pippenger (1982). Superconcentrators of Depth 2. J. Comput. Syst. Sci. 24(1), 82–90. URL https://doi.org/10.1016/0022-0000(82)90056-3
Pavel Pudlák (1994). Communication in Bounded Depth Circuits. Combinatorica 14(2), 203–216. URL https://doi.org/10.1007/BF01215351
Pavel Pudlák (2000). A note on the use of determinant for proving lower bounds on the size of linear circuits. Inf. Process. Lett. 74(5-6), 197–201. URL https://doi.org/10.1016/S0020-0190(00)00058-2
Jaikumar Radhakrishnan & Amnon Ta-Shma (2000). Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators. SIAM J. Discrete Math. 13(1), 2–24. URL https://doi.org/10.1137/S0895480197329508
Ran Raz (2010). Elusive Functions and Lower Bounds for Arithmetic Circuits. Theory of Computing 6(1), 135–177. URL https://doi.org/10.4086/toc.2010.v006a007
Ran Raz & Amir Shpilka (2003). Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates. SIAM J. Comput. 32(2), 488–513. URL https://doi.org/10.1137/S009753970138462X
Mohammad Amin Shokrollahi, Daniel A. Spielman & Volker Stemann (1997). A Remark on Matrix Rigidity. Inf. Process. Lett. 64(6), 283–285. URL https://doi.org/10.1016/S0020-0190(97)00190-7
Victor Shoup (1990). New Algorithms for Finding Irreducible Polynomials over Finite Fields. Mathematics of Computation 54, 435–447. URL https://www.ams.org/journals/mcom/1990-54-189/S0025-5718-1990-0993933-0/S0025-5718-1990-0993933-0.pdf
Victor Shoup & Roman Smolensky (1996). Lower bounds for polynomial evaluation and interpolation problems. Computational Complexity 6(4), 301–311. URL https://doi.org/10.1007/BF01270384
Amir Shpilka & Amir Yehudayoff (2010). Arithmetic Circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science 5, 207–388. ISSN 1551-305X. URL https://doi.org/10.1561/0400000039
Volker Strassen (1973). Die Berechnungskomplexität Von Elementarsymmetrischen Funktionen Und Von Interpolationskoeffizienten. Numerische Mathematik 20(3), 238–251. ISSN 0029-599X. URL https://doi.org/10.1007/BF01436566
Sébastien Tavenas (2015). Improved bounds for reduction to depth 4 and depth 3. Inf. Comput. 240, 2–11. URL https://doi.org/10.1016/j.ic.2014.09.004. 2013
Leslie G. Valiant (1975). On Non-linear Lower Bounds in Computational Complexity. In Proceedings of the 7th Annual ACM Symposium on Theory of Computing (STOC 1975),, 45–53. ACM. URL http://doi.acm.org/10.1145/800116.803752
Leslie G. Valiant (1977). Graph-Theoretic Arguments in Low-Level Complexity. In Proceedings of the 2nd Internationl Symposium on the Mathematical Foundations of Computer Science (MFCS 1977),, volume 53 of Lecture Notes in Computer Science, 162–176. Springer. URL https://doi.org/10.1007/3-540-08353-7_135
Acknowledgements
We thank Swastik Kopparty for an insightful discussion on explicit construction of Sidon sets over finite fields. We also thank Rohit Gurjar, Nutan Limaye, Srikanth Srinivasan and Joel Tropp for helpful discussions, and to the anonymous reviewers for many useful comments which have improved the presentation of this paper.
A part of this work was done while the first named author was at the semester on Lower Bounds in Computational Complexity at Simons Institute for the Theory of Computing, Berkeley, USA, and at the Department of Computer Science, University of Toronto, Canada; and while the second named author was at the Center for the Mathematics of Information, California Institute of Technology, USA.
A preliminary version of this paper has appeared in the proceedings of CCC 2020 (Kumar & Volk 2020).
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Volk, B.L., Kumar, M. Lower Bounds for Matrix Factorization. comput. complex. 30, 6 (2021). https://doi.org/10.1007/s00037-021-00205-2
Received:
Published:
DOI: https://doi.org/10.1007/s00037-021-00205-2