# Kaleidoscope: An Efficient, Learnable Representation For All Structured Linear Maps

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Dec 2020.

## Built on by (most cited first, 30 of 36)

- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Neural Architecture Search: Insights from 1000 Papers](https://mlsanity.com/paper/2301.08727/) (2023)
- [Scatterbrain: Unifying Sparse and Low-rank Attention Approximation](https://mlsanity.com/paper/2110.15343/) (2021)
- [Parameter-Efficient Orthogonal Finetuning via Butterfly Factorization](https://mlsanity.com/paper/2311.06243/) (2023)
- [Monarch: Expressive Structured Matrices for Efficient and Accurate Training](https://mlsanity.com/paper/2204.00595/) (2022)
- [Learning to Grow Pretrained Models for Efficient Transformer Training](https://mlsanity.com/paper/2303.00980/) (2023)
- [Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models](https://mlsanity.com/paper/2112.00029/) (2021)
- [Initialization and Regularization of Factorized Neural Layers](https://mlsanity.com/paper/2105.01029/) (2021)
- [Hydra: Bidirectional State Space Models Through Generalized Matrix Mixers](https://mlsanity.com/paper/2407.09941/) (2024)
- [FlashFFTConv: Efficient Convolutions for Long Sequences with Tensor Cores](https://mlsanity.com/paper/2311.05908/) (2023)
- [Adaptable Butterfly Accelerator for Attention-based NNs via Hardware and Algorithm Co-design](https://mlsanity.com/paper/2209.09570/) (2022)
- [Rethinking Neural Operations for Diverse Tasks](https://mlsanity.com/paper/2103.15798/) (2021)
- [Efficient Architecture Search for Diverse Tasks](https://mlsanity.com/paper/2204.07554/) (2022)
- [Bridging The Gap between Low-rank and Orthogonal Adaptation via Householder Reflection Adaptation](https://mlsanity.com/paper/2405.17484/) (2024)
- [AANG: Automating Auxiliary Learning](https://mlsanity.com/paper/2205.14082/) (2022)
- [ButterflyFlow: Building Invertible Layers with Butterfly Matrices](https://mlsanity.com/paper/2209.13774/) (2022)
- [Black Box Lie Group Preconditioners for SGD](https://mlsanity.com/paper/2211.04422/) (2022)
- [Low-Rank Constraints for Fast Inference in Structured Models](https://mlsanity.com/paper/2201.02715/) (2022)
- [Deformable Butterfly: A Highly Structured and Sparse Linear Transform](https://mlsanity.com/paper/2203.13556/) (2022)
- [Symmetry-Based Structured Matrices for Efficient Approximately Equivariant Networks](https://mlsanity.com/paper/2409.11772/) (2024)
- [Self-Similarity Priors: Neural Collages as Differentiable Fractal Representations](https://mlsanity.com/paper/2204.07673/) (2022)
- [MonarchRT: Efficient Attention for Real-Time Video Generation](https://mlsanity.com/paper/2602.12271/) (2026)
- [Exploiting Sparsity in Pruned Neural Networks to Optimize Large Model Training](https://mlsanity.com/paper/2302.05045/) (2023)
- [Geometry is All You Need: A Unified Taxonomy of Matrix and Tensor Factorization for Compression of Generative Language Models](https://mlsanity.com/paper/2410.03040/) (2024)
- [Is the Number of Trainable Parameters All That Actually Matters?](https://mlsanity.com/paper/2109.11928/) (2021)
- [Nonlinear Initialization Methods for Low-Rank Neural Networks](https://mlsanity.com/paper/2202.00834/) (2022)
- [VMonarch: Efficient Video Diffusion Transformers with Structured Attention](https://mlsanity.com/paper/2601.22275/) (2026)
- [Efficient Identification of Butterfly Sparse Matrix Factorizations](https://mlsanity.com/paper/2110.01230/) (2021)
- [Factor Fitting, Rank Allocation, and Partitioning in Multilevel Low Rank Matrices](https://mlsanity.com/paper/2310.19214/) (2023)
- [MoRe Fine-Tuning with 10x Fewer Parameters](https://mlsanity.com/paper/2408.17383/) (2024)

## Abstract (arXiv)

Modern neural network architectures use structured linear transformations, such as low-rank matrices, sparse matrices, permutations, and the Fourier transform, to improve inference speed and reduce memory usage compared to general linear maps. However, choosing which of the myriad structured transformations to use (and its associated parameterization) is a laborious task that requires trading off speed, space, and accuracy. We consider a different approach: we introduce a family of matrices called kaleidoscope matrices (K-matrices) that provably capture any structured matrix with near-optimal space (parameter) and time (arithmetic operation) complexity. We empirically validate that K-matrices can be automatically learned within end-to-end pipelines to replace hand-crafted procedures, in order to improve model quality. For example, replacing channel shuffles in ShuffleNet improves classification accuracy on ImageNet by up to 5%. K-matrices can also simplify hand-engineered pipelines -- we replace filter bank feature computation in speech data preprocessing with a learnable kaleidoscope layer, resulting in only 0.4% loss in accuracy on the TIMIT speech recognition task. In addition, K-matrices can capture latent structure in models: for a challenging permuted image classification task, a K-matrix based representation of permutations is able to learn the right latent structure and improves accuracy of a downstream convolutional model by over 9%. We provide a practically efficient implementation of our approach, and use K-matrices in a Transformer network to attain 36% faster end-to-end inference speed on a language translation task.