Document Open Access Logo

Lower Bounds for Matrix Factorization

Authors Mrinal Kumar, Ben Lee Volk

PDF
Thumbnail PDF

File

LIPIcs.CCC.2020.5.pdf
  • Filesize: 0.57 MB
  • 20 pages

Document Identifiers

Author Details

Mrinal Kumar
  • Department of Computer Science and Engineering, IIT Bombay, India
Ben Lee Volk
  • Center for the Mathematics of Information, California Institute of Technology, Pasadena, CA, USA

Acknowledgements

A part of this work was done while the first 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. 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.

Cite As Get BibTex

Mrinal Kumar and Ben Lee Volk. Lower Bounds for Matrix Factorization. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.CCC.2020.5

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 depth-d 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 super-linear, and were obtained by a long line of research based on the study of super-concentrators (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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
  • Theory of computation → Circuit complexity
Keywords
  • Algebraic Complexity
  • Linear Circuits
  • Matrix Factorization
  • Lower Bounds

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Manindra Agrawal. 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), pages 92-105, 2005. URL: https://doi.org/10.1007/11590156_6.
  2. Manindra Agrawal, Rohit Gurjar, Arpita Korwar, and Nitin Saxena. Hitting-sets for ROABP and sum of set-multilinear circuits. SIAM J. Comput., 44(3):669-697, 2015. URL: https://doi.org/10.1137/140975103.
  3. Manindra Agrawal and V. Vinay. Arithmetic circuits: A chasm at depth four. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008), pages 67-75, 2008. URL: https://doi.org/10.1109/FOCS.2008.32.
  4. Josh Alman and Lijie Chen. Efficient construction of rigid matrices using an np oracle. In Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2019), 2019. URL: http://joshalman.com/AlmanChenFOCS19.pdf.
  5. Josh Alman and R. Ryan Williams. Probabilistic rank and matrix rigidity. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC 2017), pages 641-652. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055484.
  6. Noga Alon and Pavel Pudlák. Superconcentrators of depths 2 and 3; odd levels help (rarely). J. Comput. Syst. Sci., 48(1):194-202, 1994. URL: https://doi.org/10.1016/S0022-0000(05)80027-3.
  7. Walter Baur and Volker Strassen. The complexity of partial derivatives. Theoretical Computer Science, 22:317-330, 1983. URL: https://doi.org/10.1016/0304-3975(83)90110-X.
  8. Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma. 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), pages 1185-1194. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055423.
  9. Nader H. Bshouty. Testers and their applications. In Innovations in Theoretical Computer Science, ITCS'14, 2014, pages 327-352, 2014. URL: https://doi.org/10.1145/2554797.2554828.
  10. Peter Bürgisser, Michael Clausen, and Mohammad A. Shokrollahi. Algebraic Complexity Theory, volume 315 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag, 1997. URL: https://doi.org/10.1007/978-3-662-03338-8.
  11. Eshan Chattopadhyay and David Zuckerman. Explicit two-source extractors and resilient functions. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC 2016), pages 670-683. ACM, 2016. URL: https://doi.org/10.1145/2897518.2897528.
  12. Bernard Chazelle. The discrepancy method - randomness and complexity. Cambridge University Press, 2001. URL: https://www.cs.princeton.edu/~chazelle/pubs/book.pdf.
  13. Gil Cohen. Towards optimal two-source extractors and ramsey graphs. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC 2017), pages 1157-1170. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055429.
  14. Danny Dolev, Cynthia Dwork, Nicholas Pippenger, and Avi Wigderson. Superconcentrators, generalizers and generalized connectors with limited depth (preliminary version). In Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC 1983), pages 42-51. ACM, 1983. URL: https://doi.org/10.1145/800061.808731.
  15. Zeev Dvir and Benjamin Edelman. Matrix rigidity and the croot-lev-pach lemma. CoRR, abs/1708.01646, 2017. URL: http://arxiv.org/abs/1708.01646.
  16. Zeev Dvir, Alexander Golovnev, and Omri Weinstein. Static data structure lower bounds imply rigidity. Electronic Colloquium on Computational Complexity (ECCC), 25:188, 2018. URL: https://eccc.weizmann.ac.il/report/2018/188.
  17. Zeev Dvir and Allen Liu. Fourier and circulant matrices are not rigid. CoRR, abs/1902.07334, 2019. URL: http://arxiv.org/abs/1902.07334.
  18. Michael A. Forbes and Amir Shpilka. On identity testing of tensors, low-rank recovery and compressed sensing. In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC 2012), pages 163-172. ACM, 2012. URL: https://doi.org/10.1145/2213977.2213995.
  19. Michael L. Fredman. The complexity of maintaining an array and computing its partial sums. J. ACM, 29(1):250-260, 1982. URL: https://doi.org/10.1145/322290.322305.
  20. Michael L. Fredman and Michael E. Saks. The cell probe complexity of dynamic data structures. In David S. Johnson, editor, Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC 1989), pages 345-354. ACM, 1989. URL: https://doi.org/10.1145/73007.73040.
  21. Joel Friedman. A note on matrix rigidity. Combinatorica, 13(2):235-239, June 1993. URL: https://doi.org/10.1007/BF01303207.
  22. Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák, and Emanuele Viola. Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. IEEE Trans. Information Theory, 59(10):6611-6627, 2013. URL: https://doi.org/10.1109/TIT.2013.2270275.
  23. Anna Gál and Peter Bro Miltersen. The cell probe complexity of succinct data structures. Theor. Comput. Sci., 379(3):405-417, 2007. URL: https://doi.org/10.1016/j.tcs.2007.02.047.
  24. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Arithmetic circuits: A chasm at depth 3. SIAM J. Comput., 45(3):1064-1079, 2016. URL: https://doi.org/10.1137/140957123.
  25. Venkatesan Guruswami, Atri Rudra, and Madhu Sudan. Essential coding theory, 2018. URL: https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/.
  26. Joos Heintz and Claus-Peter Schnorr. Testing Polynomials which Are Easy to Compute (Extended Abstract). In Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC 1980), pages 262-272, 1980. URL: https://doi.org/10.1145/800141.804674.
  27. Stasys Jukna and Igor Sergeev. Complexity of linear boolean operators. Foundations and Trends in Theoretical Computer Science, 9(1):1-123, 2013. URL: https://doi.org/10.1561/0400000063.
  28. Erich Kaltofen and Michael F. Singer. Size efficient parallel algebraic circuits for partial derivatives. In IV International Conference on Computer Algebra in Physical Research, pages 133-145, 1991. URL: https://users.cs.duke.edu/~elk27/bibliography/91/KaSi91.pdf.
  29. Pascal Koiran. Arithmetic circuits: The chasm at depth four gets wider. Theoretical Computer Science, 448:56-65, 2012. URL: https://doi.org/10.1016/j.tcs.2012.03.041.
  30. Kasper Green Larsen. The cell probe complexity of dynamic range counting. In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC 2012), pages 85-94. ACM, 2012. URL: https://doi.org/10.1145/2213977.2213987.
  31. Kasper Green Larsen. On range searching in the group model and combinatorial discrepancy. SIAM J. Comput., 43(2):673-686, 2014. URL: https://doi.org/10.1137/120865240.
  32. Kasper Green Larsen, Omri Weinstein, and Huacheng Yu. 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), pages 978-989. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188790.
  33. Daniel D. Lee and H. Sebastian Seung. Algorithms for non-negative matrix factorization. In Advances in Neural Information Processing Systems 13, Papers from Neural Information Processing Systems (NIPS) 2000, pages 556-562. MIT Press, 2000. URL: http://papers.nips.cc/paper/1861-algorithms-for-non-negative-matrix-factorization.
  34. Xin Li. Non-malleable extractors and non-malleable codes: Partially optimal constructions. CoRR, abs/1804.04005, 2018. URL: http://arxiv.org/abs/1804.04005.
  35. Satyanarayana V. Lokam. Complexity lower bounds using linear algebra. Foundations and Trends in Theoretical Computer Science, 4(1-2):1-155, 2009. URL: https://doi.org/10.1561/0400000011.
  36. Julien Mairal, Francis R. Bach, Jean Ponce, and Guillermo Sapiro. 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, pages 689-696. ACM, 2009. URL: https://doi.org/10.1145/1553374.1553463.
  37. Jacques Morgenstern. Note on a lower bound on the linear complexity of the fast fourier transform. J. ACM, 20(2):305-306, 1973. URL: https://doi.org/10.1145/321752.321761.
  38. Behnam Neyshabur and Rina Panigrahy. Sparse matrix factorization. CoRR, abs/1311.3315, 2013. URL: http://arxiv.org/abs/1311.3315.
  39. Mihai Pǎtraşcu. Lower bounds for 2-dimensional range counting. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC 2007), pages 40-46. ACM, 2007. URL: https://doi.org/10.1145/1250790.1250797.
  40. Mihai Pǎtraşcu and Erik D. Demaine. Logarithmic lower bounds in the cell-probe model. SIAM J. Comput., 35(4):932-963, 2006. URL: https://doi.org/10.1137/S0097539705447256.
  41. Nicholas Pippenger. Superconcentrators. SIAM J. Comput., 6(2):298-304, 1977. URL: https://doi.org/10.1137/0206022.
  42. Nicholas Pippenger. Superconcentrators of depth 2. J. Comput. Syst. Sci., 24(1):82-90, 1982. URL: https://doi.org/10.1016/0022-0000(82)90056-3.
  43. Pavel Pudlák. Communication in bounded depth circuits. Combinatorica, 14(2):203-216, 1994. URL: https://doi.org/10.1007/BF01215351.
  44. Pavel Pudlák. 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, 2000. URL: https://doi.org/10.1016/S0020-0190(00)00058-2.
  45. Jaikumar Radhakrishnan and Amnon Ta-Shma. Bounds for dispersers, extractors, and depth-two superconcentrators. SIAM J. Discrete Math., 13(1):2-24, 2000. URL: https://doi.org/10.1137/S0895480197329508.
  46. Ran Raz. Elusive functions and lower bounds for arithmetic circuits. Theory of Computing, 6(1):135-177, 2010. URL: https://doi.org/10.4086/toc.2010.v006a007.
  47. Mohammad Amin Shokrollahi, Daniel A. Spielman, and Volker Stemann. A remark on matrix rigidity. Inf. Process. Lett., 64(6):283-285, 1997. URL: https://doi.org/10.1016/S0020-0190(97)00190-7.
  48. Victor Shoup. New algorithms for finding irreducible polynomials over finite fields. Mathematics of Computation, 54:435-447, 1990. URL: https://www.ams.org/journals/mcom/1990-54-189/S0025-5718-1990-0993933-0/S0025-5718-1990-0993933-0.pdf.
  49. Victor Shoup and Roman Smolensky. Lower bounds for polynomial evaluation and interpolation problems. Computational Complexity, 6(4):301-311, December 1996. URL: https://doi.org/10.1007/BF01270384.
  50. Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5:207-388, March 2010. URL: https://doi.org/10.1561/0400000039.
  51. Volker Strassen. Die berechnungskomplexität von elementarsymmetrischen funktionen und von interpolationskoeffizienten. Numerische Mathematik, 20(3):238-251, June 1973. URL: https://doi.org/10.1007/BF01436566.
  52. Sébastien Tavenas. Improved bounds for reduction to depth 4 and depth 3. Inf. Comput., 240:2-11, 2015. Preliminary version in the 38th Internationl Symposium on the Mathematical Foundations of Computer Science (MFCS 2013). URL: https://doi.org/10.1016/j.ic.2014.09.004.
  53. Leslie G. Valiant. On non-linear lower bounds in computational complexity. In Proceedings of the 7th Annual ACM Symposium on Theory of Computing (STOC 1975), pages 45-53. ACM, 1975. URL: https://doi.org/10.1145/800116.803752.
  54. Leslie G. Valiant. 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, pages 162-176. Springer, 1977. URL: https://doi.org/10.1007/3-540-08353-7_135.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact