# Deformable Butterfly: A Highly Structured and Sparse Linear Transform

arXiv: https://arxiv.org/abs/2203.13556 · HTML: https://mlsanity.com/paper/2203.13556/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 44 references that are in the map.
- First posted on arXiv 25 Mar 2022.

## Builds on (most cited first, 19 of 19)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Going Deeper with Convolutions](https://mlsanity.com/paper/1409.4842/) (2014)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [Pruning Filters for Efficient ConvNets](https://mlsanity.com/paper/1608.08710/) (2016)
- [XNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networks](https://mlsanity.com/paper/1603.05279/) (2016)
- [Data-Free Quantization Through Weight Equalization and Bias Correction](https://mlsanity.com/paper/1906.04721/) (2019)
- [Tensorizing Neural Networks](https://mlsanity.com/paper/1509.06569/) (2015)
- [Compression of Deep Convolutional Neural Networks for Fast and Low Power Mobile Applications](https://mlsanity.com/paper/1511.06530/) (2015)
- [Fast Algorithms for Convolutional Neural Networks](https://mlsanity.com/paper/1509.09308/) (2015)
- [Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations](https://mlsanity.com/paper/1903.05895/) (2019)
- [Fastfood: Approximate Kernel Expansions in Loglinear Time](https://mlsanity.com/paper/1408.3060/) (2014)
- [Kaleidoscope: An Efficient, Learnable Representation For All Structured Linear Maps](https://mlsanity.com/paper/2012.14966/) (2020)
- [Deep Fried Convnets](https://mlsanity.com/paper/1412.7149/) (2014)
- [Exploiting Elasticity in Tensor Ranks for Compressing Neural Networks](https://mlsanity.com/paper/2105.04218/) (2021)

## Built on by (most cited first, 8 of 8)

- [Monarch: Expressive Structured Matrices for Efficient and Accurate Training](https://mlsanity.com/paper/2204.00595/) (2022)
- [Simple Hardware-Efficient Long Convolutions for Sequence Modeling](https://mlsanity.com/paper/2302.06646/) (2023)
- [Can sparsity improve the privacy of neural networks?](https://mlsanity.com/paper/2304.07234/) (2023)
- [Sparsity in neural networks can improve their privacy](https://mlsanity.com/paper/2304.10553/) (2023)
- [Lite it fly: An All-Deformable-Butterfly Network](https://mlsanity.com/paper/2311.08125/) (2023)
- [Dimension Mixer: Group Mixing of Input Dimensions for Efficient Function Approximation](https://mlsanity.com/paper/2311.18735/) (2023)
- [Fast Inference with Kronecker-Sparse Matrices](https://mlsanity.com/paper/2405.15013/) (2024)
- [Efficient Tensor Completion Algorithms for Highly Oscillatory Operators](https://mlsanity.com/paper/2510.17734/) (2025)

## Abstract (arXiv)

We introduce a new kind of linear transform named Deformable Butterfly (DeBut) that generalizes the conventional butterfly matrices and can be adapted to various input-output dimensions. It inherits the fine-to-coarse-grained learnable hierarchy of traditional butterflies and when deployed to neural networks, the prominent structures and sparsity in a DeBut layer constitutes a new way for network compression. We apply DeBut as a drop-in replacement of standard fully connected and convolutional layers, and demonstrate its superiority in homogenizing a neural network and rendering it favorable properties such as light weight and low inference complexity, without compromising accuracy. The natural complexity-accuracy tradeoff arising from the myriad deformations of a DeBut layer also opens up new rooms for analytical and practical research. The codes and Appendix are publicly available at: https://github.com/ruilin0212/DeBut.