A recursive butterfly factorization with optimality guarantees
arXiv:2607.29361
2026
Architecture
2 ideas extracted · analyzed Aug 31, 2026
What the math gives to ML
The paper gives a recursive representation of matrices whose row and column index trees have complementary low-rank blocks. Its transferable asset is not merely low rank, but a multiscale factorization in which block-diagonal orthonormal transfers surround recursively smaller butterfly cores, reducing parameters while retaining structured global interactions. The quasi-optimality guarantee suggests a principled replacement for dense neural-network linear maps rather than an ad hoc sparse parameterization. The randomized matrix-free construction also provides a practical route for compressing pretrained dense layers using only matrix-vector products.
Ideas from this paper
△ Mechanism confirmed, baseline not beaten
2026
Replace a square dense projection in a Transformer or MLP with a trainable recursive butterfly matrix. The layer preserves multiscale channel interactions while constraining every complementary row-column block to rank at most k, reducing parameters and enabling recursive structured matrix-vector products. Unlike an arbitrary sparse layer, the construction has an explicit recursive factorization and a quasi-optimal approximation guarantee among matrices with the same butterfly rank.
Useful8/10
Difficulty6/10
Novelty5/10
△ Mechanism confirmed, baseline not beaten
2026
Compress an existing dense neural-network weight matrix into a recursive butterfly operator using Gaussian sketches of complementary blocks. This is useful for deployment or distillation: the dense model provides an oracle for matrix-vector products, while the compressed model stores only recursive transfer bases and small cores. The generalized Nyström identity gives exact reconstruction for rank-k blocks and a principled approximation route for numerically low-rank blocks.
Useful7/10
Difficulty7/10
Novelty6/10