Research map / Learning theory and algorithms / Matrix and tensor methods
Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the unstructured hidden-layer matrix with complex BPBP | Single hidden-layer network · CIFAR-10 | test accuracy: 46.03 -> 49.93 | Helped |
| Replace the unstructured hidden-layer matrix with real BPBP | Single hidden-layer network · CIFAR-10 | test accuracy: 46.03 -> 48.69 | Helped |
| Use complex rather than real BPBP | Single hidden-layer network · CIFAR-10 | test accuracy: 48.69 -> 49.93 | Helped |
| Replace the unstructured hidden-layer matrix with complex BPBP | Single hidden-layer network · MNIST-bg-rot | test accuracy: 44.08 -> 46.26 | Helped |
| Replace the unstructured hidden-layer matrix with complex BPBP | Single hidden-layer network · MNIST-noise | test accuracy: 65.15 -> 77.00 | Helped |
| Use complex BPBP instead of LDR-TD | Single hidden-layer network · MNIST-noise | test accuracy: 78.45 -> 77.00 | Hurt |
| Add a BPBP layer before the final fully connected layer | ResNet18 · CIFAR-10 | accuracy: 93.58 ± 0.15 -> 94.01 ± 0.09 | Helped |
| Add a fully connected layer before the final fully connected layer | ResNet18 · CIFAR-10 | accuracy: 93.58 ± 0.15 -> 93.89 ± 0.19 | Helped |
| Learn the DFT using a butterfly factorization | BP · DFT (N = 1024) | RMSE: 5.7e-05 | Helped |
| Learn convolution using BPBP | BPBP · Convolution (N = 512) | RMSE: 6.3e-05 | Helped |
| Scale convolution learning to N = 1024 | BPBP · Convolution | RMSE: 6.3e-05 -> 1.9e-02 | Hurt |
| Approximate the Legendre transform using a butterfly factorization | BP · Legendre (N = 1024) | RMSE: 1.6e-03 | Mixed |
Closest papers by meaning
- Linear Transformers Implicitly Discover Unified Numerical Algorithms (NeurIPS 2025 · similarity 0.87)
- Schwarz–Schur Involution: Lightspeed Differentiable Sparse Linear Solvers (ICML 2025 · similarity 0.86)
- Learning to Discover Iterative Spectral Algorithms (NeurIPS 2026 · similarity 0.86)
- Searching for Efficient Linear Layers over a Continuous Space of Structured Matrices (NeurIPS 2024 · similarity 0.85)
- Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions (ICLR 2025 · similarity 0.85)
- CODA: Rewriting Transformer Blocks as GEMM-Epilogue Programs (NeurIPS 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.