CoChat
Sign Up
PreprintCited by 43Advanced Neural Network ApplicationsNeural Networks and ApplicationsStochastic Gradient Optimization Techniques

Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations

Open access
Dao, Tri, Gu, Albert, Eichhorn, Matthew, Rudra, Atri, Ré, Christopher·2019·arXiv
DOI 10.48550/arxiv.1903.05895arXiv 1903.05895PMC PMC6879380
Open this paper in CoChat — free account

Abstract

Fast linear transforms are ubiquitous in machine learning, including the discrete Fourier transform, discrete cosine transform, and other structured transformations such as convolutions. All of these transforms can be represented by dense matrix-vector multiplication, yet each has a specialized and highly efficient (subquadratic) algorithm. We ask to what extent hand-crafting these algorithms and implementations is necessary, what structural priors they encode, and how much knowledge is required to automatically learn a fast algorithm for a provided structured transform. Motivated by a characterization of fast matrix-vector multiplication as products of sparse matrices, we introduce a parameterization of divide-and-conquer methods that is capable of representing a large class of transforms. This generic formulation can automatically learn an efficient algorithm for many important transforms; for example, it recovers the $O(N \log N)$ Cooley-Tukey FFT algorithm to machine precision, for dimensions $N$ up to $1024$. Furthermore, our method can be incorporated as a lightweight replacement of generic matrices in machine learning pipelines to learn efficient and compressible transformations. On a standard task of compressing a single hidden-layer network, our method exceeds the classification accuracy of unconstrained matrices on CIFAR-10 by 3.9 points -- the first time a structured approach has done so -- with 4X faster inference speed and 40X fewer parameters.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1903.05895

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Butterfly matrices and their products have been shown to be able to express any structured matrices with almost optimal runtime and number of parameters.

    “The butterfly pattern we use for our block-sparse attention is motivated by the fact that butterfly matrices [15, 64] and their products have been shown to be able to express any structured matrices with almost optimal runtime and number of parameters [16, 20].”

    From FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness (2022) · cites this paper as [15]

    Section 3.3 (pp. 6–7) says the butterfly-product hierarchy represents several important transforms at low depth and can represent all square matrices at linear depth. The Introduction (p. 1) gives O(N) parameters and O(N log N) multiplication for a class of structured matrices. These passages do not establish that *any* structured matrix has a butterfly representation with almost-optimal runtime and parameter count; §4.1 (p. 7) says some structured matrices are not perfectly captured by the BPBP class. (LLM, conf=0.86)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

No references could be resolved yet.

Research works printed but not linked: 47

  1. [1][1] Bartlett, P. L., Maiorov, V., and Meir, R. Almost linear VC dimension bounds for piecewise polynomial networks. In Advances in Neural Information Processing Systems , pp. 190-196, 1999. -
  2. [3][3] B¨ urgisser, P., Clausen, M., and Shokrollahi, M. A. Algebraic complexity theory , volume 315. Springer Science & Business Media, 2013. -
  3. [4][4] Cand` es, E. J., Li, X., Ma, Y., and Wright, J. Robust principal component analysis? Journal of the ACM (JACM) , 58(3):11, 2011. -
  4. [5][5] Chen, W., Wilson, J., Tyree, S., Weinberger, K., and Chen, Y. Compressing neural networks with the hashing trick. In Bach, F. and Blei, D. (eds.), Proceedings of the 32nd International Conference on Machine Learning , volume 37 of Proceedings of Machine Learning Research , pp. 2285-2294, Lille, France, 07-09 Jul 2015. PMLR. URL http://proceedings.mlr.press/v37/chenc15.html . -
  5. [6][6] Cheng, Y., Yu, F. X., Feris, R. S., Kumar, S., Choudhary, A., and Chang, S.-F. An exploration of parameter redundancy in deep networks with circulant projections. In Proceedings of the IEEE International Conference on Computer Vision , pp. 2857-2865, 2015. -
  6. [8][8] De Sa, C., Gu, A., Puttagunta, R., R´ e, C., and Rudra, A. A two-pronged progress in structured dense matrix vector multiplication. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pp. 1060-1079. SIAM, 2018. -
  7. [9][9] Denil, M., Shakibi, B., Dinh, L., De Freitas, N., et al. Predicting parameters in deep learning. In Advances in Neural Information Processing Systems , pp. 2148-2156, 2013. -
  8. [10][10] Ding, C., Liao, S., Wang, Y., Li, Z., Liu, N., Zhuo, Y., Wang, C., Qian, X., Bai, Y., Yuan, G., et al. CirCNN: accelerating and compressing deep neural networks using block-circulant weight matrices. In Proceedings of the 50th Annual IEEE/ACM International Symposium on Microarchitecture , pp. 395-408. ACM, 2017. -
  9. [11][11] Dongarra, J. and Sullivan, F. Guest editors' introduction: The top 10 algorithms. Computing in Science & Engineering , 2(1):22-23, 2000. -
  10. [12][12] Driscoll, J. R., Healy, Jr., D. M., and Rockmore, D. N. Fast discrete polynomial transforms with applications to data analysis for distance transitive graphs. SIAM J. Comput. , 26(4):1066-1099, August 1997. ISSN 0097-5397. doi: 10.1137/S0097539792240121. URL http://dx.doi.org/10.1137/ S0097539792240121 . - · DOI
  11. [13][13] Egner, S. and P¨ uschel, M. Automatic generation of fast discrete signal transforms. IEEE Transactions on Signal Processing , 49(9):1992-2002, 2001. -
  12. [14][14] Egner, S. and P¨ uschel, M. Symmetry-based matrix factorization. Journal of Symbolic Computation , 37 (2):157-186, 2004. -
  13. [15][15] Grandvalet, Y. and Bengio, Y. Semi-supervised learning by entropy minimization. In Saul, L. K., Weiss, Y., and Bottou, L. (eds.), Advances in Neural Information Processing Systems 17 , pp. 529-536. MIT Press, 2005. -
  14. [16][16] Grover, A., Wang, E., Zweig, A., and Ermon, S. Stochastic optimization of sorting networks via continuous relaxations. In International Conference on Learning Representations , 2019. URL https: //openreview.net/forum?id=H1eSS3CcKX . -
  15. [17][17] Harvey, N., Liaw, C., and Mehrabian, A. Nearly-tight VC-dimension bounds for piecewise linear neural networks. In Kale, S. and Shamir, O. (eds.), Proceedings of the 2017 Conference on Learning Theory , volume 65 of Proceedings of Machine Learning Research , pp. 1064-1068, Amsterdam, Netherlands, 07-10 Jul 2017. PMLR. URL http://proceedings.mlr.press/v65/harvey17a.html . -
  16. [18][18] He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition , pp. 770-778, 2016. -
  17. [19][19] Hsieh, J.-T., Zhao, S., Eismann, S., Mirabella, L., and Ermon, S. Learning neural PDE solvers with convergence guarantees. In International Conference on Learning Representations , 2019. -
  18. [20][20] Jing, L., Shen, Y., Dubcek, T., Peurifoy, J., Skirlo, S., LeCun, Y., Tegmark, M., and Soljaˇ ci´ c, M. Tunable efficient unitary neural networks (eunn) and their application to rnns. In Proceedings of the 34th International Conference on Machine Learning-Volume 70 , pp. 1733-1741. JMLR. org, 2017. -
  19. [21][21] Jurafsky, D. and Martin, J. H. Speech and language processing , volume 3. Pearson London, 2014. -
  20. [22][22] Kailath, T., Kung, S.-Y., and Morf, M. Displacement ranks of matrices and linear equations. Journal of Mathematical Analysis and Applications , 68(2):395-407, 1979. -
  21. [23][23] Kingma, D. P. and Welling, M. Auto-encoding variational bayes. In Proceedings of the Second International Conference on Learning Representations (ICLR 2014) , April 2014. -
  22. [24][24] Le, Q., Sarlos, T., and Smola, A. Fastfood - computing Hilbert space expansions in loglinear time. In Dasgupta, S. and McAllester, D. (eds.), Proceedings of the 30th International Conference on Machine Learning , volume 28 of Proceedings of Machine Learning Research , pp. 244-252, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR. URL http://proceedings.mlr.press/v28/le13.html . -
  23. [25][25] Le Magoarou, L. and Gribonval, R. Chasing butterflies: In search of efficient dictionaries. In 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) , pp. 3287-3291, April 2015. doi: 10.1109/ICASSP.2015.7178579. - · DOI
  24. [26][26] Le Magoarou, L. and Gribonval, R. Flexible multilayer sparse approximations of matrices and applications. IEEE Journal of Selected Topics in Signal Processing , 10(4):688-700, June 2016. ISSN 1932-4553. doi: 10.1109/JSTSP.2016.2543461. - · DOI
  25. [27][27] Li, L., Jamieson, K., DeSalvo, G., Rostamizadeh, A., and Talwalkar, A. Hyperband: A novel bandit-based approach to hyperparameter optimization. The Journal of Machine Learning Research , 18(1):6765-6816, 2017. -
  26. [28][28] Li, Y., Yang, H., Martin, E. R., Ho, K. L., and Ying, L. Butterfly factorization. Multiscale Modeling & Simulation , 13(2):714-732, 2015. -
  27. [29][29] Mairal, J., Ponce, J., Sapiro, G., Zisserman, A., and Bach, F. R. Supervised dictionary learning. In Koller, D., Schuurmans, D., Bengio, Y., and Bottou, L. (eds.), Advances in Neural Information Processing Systems 21 , pp. 1033-1040. Curran Associates, Inc., 2009. URL http://papers.nips.cc/ paper/3448-supervised-dictionary-learning.pdf . -
  28. [30][30] Makhoul, J. A fast cosine transform in one and two dimensions. IEEE Transactions on Acoustics, Speech, and Signal Processing , 28(1):27-34, February 1980. ISSN 0096-3518. doi: 10.1109/TASSP.1980.1163351. - · DOI
  29. [31][31] Mena, G., Belanger, D., Linderman, S., and Snoek, J. Learning latent permutations with GumbelSinkhorn networks. In International Conference on Learning Representations , 2018. URL https: //openreview.net/forum?id=Byt3oJ-0W . -
  30. [32][32] Munkhoeva, M., Kapushev, Y., Burnaev, E., and Oseledets, I. Quadrature-based features for kernel approximation. In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 31 , pp. 9165-9174. Curran Associates, Inc., 2018. -
  31. [33][33] Neyshabur, B. and Panigrahy, R. Sparse matrix factorization. arXiv preprint arXiv:1311.3315 , 2013. - · arXiv
  32. [34][34] Olshevsky, V. and Shokrollahi, M. A. Matrix-vector product for confluent cauchy-like matrices with application to confluent rational interpolation. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA , pp. 573-581, 2000. doi: 10.1145/335305.335380. URL http://doi.acm.org/10.1145/335305.335380 . - · DOI
  33. [35][35] Pan, V. Y. Structured Matrices and Polynomials: Unified Superfast Algorithms . Springer-Verlag New York, Inc., New York, NY, USA, 2001. ISBN 0-8176-4240-4. -
  34. [37][37] Pascanu, R., Mikolov, T., and Bengio, Y. On the difficulty of training recurrent neural networks. In International Conference on Machine Learning , pp. 1310-1318, 2013. -
  35. [38][38] Proakis, J. G. Digital signal processing: principles algorithms and applications . Pearson Education India, 2001. -
  36. [39][39] Puschel, M. and Moura, J. M. Algebraic signal processing theory. IEEE Transactions on Signal Processing , 56(8):3572-3585, 2008. -
  37. [40][40] Sindhwani, V., Sainath, T., and Kumar, S. Structured transforms for small-footprint deep learning. In Advances in Neural Information Processing Systems , pp. 3088-3096, 2015. -
  38. [42][42] Thomas, A., Gu, A., Dao, T., Rudra, A., and R´ e, C. Learning compressed transforms with low displacement rank. In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 31 , pp. 9066-9078. Curran Associates, Inc., 2018. -
  39. [43][43] Trask, A., Hill, F., Reed, S. E., Rae, J., Dyer, C., and Blunsom, P. Neural arithmetic logic units. In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 31 , pp. 8046-8055. Curran Associates, Inc., 2018. -
  40. [44][44] Tschannen, M., Khanna, A., and Anandkumar, A. StrassenNets: Deep learning with a multiplication budget. In Dy, J. and Krause, A. (eds.), Proceedings of the 35th International Conference on Machine Learning , volume 80 of Proceedings of Machine Learning Research , pp. 4985-4994. PMLR, 10-15 Jul 2018. URL http://proceedings.mlr.press/v80/tschannen18a.html . -
  41. [45][45] Voronenko, Y. and Puschel, M. Algebraic signal processing theory: Cooley-Tukey type algorithms for real DFTs. IEEE Transactions on Signal Processing , 57(1):205-222, 2009. -
  42. [46][46] Xu, J., Zhang, Z., Friedman, T., Liang, Y., and Van den Broeck, G. A semantic loss function for deep learning with symbolic knowledge. In Dy, J. and Krause, A. (eds.), Proceedings of the 35th International Conference on Machine Learning , volume 80 of Proceedings of Machine Learning Research , pp. 5502-5511. PMLR, 10-15 Jul 2018. URL http://proceedings.mlr.press/v80/xu18h.html . -
  43. [47][47] Yang, Z., Moczulski, M., Denil, M., de Freitas, N., Smola, A., Song, L., and Wang, Z. Deep fried convnets. In Proceedings of the IEEE International Conference on Computer Vision , pp. 1476-1483, 2015. -
  44. [48][48] Ye, K. and Lim, L.-H. Every matrix is a product of toeplitz matrices. Foundations of Computational Mathematics , 16(3):577-598, Jun 2016. ISSN 1615-3383. doi: 10.1007/s10208-015-9254-z. URL https://doi.org/10.1007/s10208-015-9254-z . - · DOI
  45. [49][49] Yu, F. X., Kumar, S., Rowley, H. A., and Chang, S. Compact nonlinear maps and circulant extensions. CoRR , abs/1503.03893, 2015. - · arXiv
  46. [50][50] Yu, F. X. X., Suresh, A. T., Choromanski, K. M., Holtmann-Rice, D. N., and Kumar, S. Orthogonal random features. In Lee, D. D., Sugiyama, M., Luxburg, U. V., Guyon, I., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 29 , pp. 1975-1983. Curran Associates, Inc., 2016. -
  47. [51][51] Zou, H., Hastie, T., and Tibshirani, R. Sparse principal component analysis. Journal of computational and graphical statistics , 15(2):265-286, 2006. Table 3: Formulas for transforms considered in Section 4.1 and Figure 3.

Cited by

Sorted by citations

Authors
Dao, T., Gu, A., Eichhorn, M., Rudra, A., & Ré, C.
Affiliations
  • Stanford University (US)
  • University at Buffalo, State University of New York (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2019
Volume
97
Pages
1517-1527
DOI
10.48550/arxiv.1903.05895
arXiv
1903.05895
PMC
PMC6879380
OpenAlex
W2963061092
Cited by
43
References
0
Citations by year
2025: 2 · 2024: 6 · 2023: 8 · 2022: 6 · 2021: 10 · 2020: 10 · 2019: 1
FWCI
3.02
Type
journal article
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • PubMed (publishedVersion)
  • Europe PMC (PubMed Central) (acceptedVersion)
  • PubMed Central (acceptedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
  • PubMed
Funders
  • National Science Foundation (1763315, 1563078, 1763481)
  • Gordon and Betty Moore Foundation
  • Accenture
  • VMware
  • Swiss Re
  • Ant Financial Services Group
  • National Institutes of Health (N000141712266, CCF1563078, CCF1763315)
  • Defense Advanced Research Projects Agency (FA8750-17-2-0095, FA86501827865)
  • Office of Naval Research (N000141712266)
  • National Institute of Biomedical Imaging and Bioengineering (U54EB020405)
Topics
  • Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Advanced Neural Network Applications
  • Physical Sciences › Computer Science › Artificial Intelligence › Neural Networks and Applications
  • Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
Keywords
linear operators, fast algorithms, structured matrices, neural network compression, inference speed, parameter reduction

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review