Reproduce “Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Tri Dao, Albert Gu, Matthew Eichhorn, Atri Rudra, Christopher Ré
This research from Stanford University and the University at Buffalo introduces a method for automatically learning fast algorithms for linear transforms using butterfly factorizations. The approach successfully recovers known fast transforms to high precision and, when integrated into neural networks, achieves higher accuracy on tasks like CIFAR-10 while using significantly fewer parameters and offering faster inference.
Key insights
- Fast algorithms for many structured linear transforms can be accurately represented and learned through a recursive butterfly factorization structure, which naturally encodes their O(N log N) complexity.
- Encoding a specific structural prior (butterfly factorization) within a differentiable framework allows for automated discovery and implementation of efficient algorithms without extensive prior knowledge of the target transform.
- Structured layers based on butterfly factorizations can provide beneficial inductive biases to neural networks, leading to improved generalization and higher accuracy, in addition to significant compression and speedup.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.