# Batch-efficient EigenDecomposition for Small and Medium Matrices

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 50 references that are in the map.
- First posted on arXiv 9 Jul 2022.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [The Unreasonable Effectiveness of Deep Features as a Perceptual Metric](https://mlsanity.com/paper/1801.03924/) (2018)
- [Image-to-Image Translation with Conditional Adversarial Networks](https://mlsanity.com/paper/1611.07004/) (2016)
- [Universal Style Transfer via Feature Transforms](https://mlsanity.com/paper/1705.08086/) (2017)
- [DSAC - Differentiable RANSAC for Camera Localization](https://mlsanity.com/paper/1611.05705/) (2016)
- [Bilinear CNNs for Fine-grained Visual Recognition](https://mlsanity.com/paper/1504.07889/) (2015)
- [RobustNet: Improving Domain Generalization in Urban-Scene Segmentation via Instance Selective Whitening](https://mlsanity.com/paper/2103.15597/) (2021)
- [Switchable Whitening for Deep Representation Learning](https://mlsanity.com/paper/1904.09739/) (2019)
- [Iterative Normalization: Beyond Standardization towards Efficient Whitening](https://mlsanity.com/paper/1904.03441/) (2019)
- [Decorrelated Batch Normalization](https://mlsanity.com/paper/1804.08450/) (2018)
- [Towards Faster Training of Global Covariance Pooling Networks by Iterative Matrix Square Root Normalization](https://mlsanity.com/paper/1712.01034/) (2017)
- [Image-to-Image Translation via Group-wise Deep Whitening-and-Coloring Transformation](https://mlsanity.com/paper/1812.09912/) (2018)
- [Is Second-order Information Helpful for Large-scale Visual Recognition?](https://mlsanity.com/paper/1703.08050/) (2017)
- [Deep CNNs Meet Global Covariance Pooling: Better Representation and Generalization](https://mlsanity.com/paper/1904.06836/) (2019)
- [Diversified Arbitrary Style Transfer via Deep Feature Perturbation](https://mlsanity.com/paper/1909.08223/) (2019)
- [Solving the Blind Perspective-n-Point Problem End-To-End With Robust Differentiable Geometric Optimization](https://mlsanity.com/paper/2007.14628/) (2020)
- [Improved Bilinear Pooling with CNNs](https://mlsanity.com/paper/1707.06772/) (2017)
- [Backpropagation-Friendly Eigendecomposition](https://mlsanity.com/paper/1906.09023/) (2019)
- [Why Approximate Matrix Square Root Outperforms Accurate SVD in Global Covariance Pooling?](https://mlsanity.com/paper/2105.02498/) (2021)
- [Robust Differentiable SVD](https://mlsanity.com/paper/2104.03821/) (2021)
- [Fast Differentiable Matrix Square Root and Inverse Square Root](https://mlsanity.com/paper/2201.12543/) (2022)
- [An Investigation into the Stochasticity of Batch Whitening](https://mlsanity.com/paper/2003.12327/) (2020)
- [Fast Differentiable Matrix Square Root](https://mlsanity.com/paper/2201.08663/) (2022)
- [Group Whitening: Balancing Learning Efficiency and Representational Capacity](https://mlsanity.com/paper/2009.13333/) (2020)
- [Temporal-attentive Covariance Pooling Networks for Video Recognition](https://mlsanity.com/paper/2110.14381/) (2021)
- [On the Eigenvalues of Global Covariance Pooling for Fine-grained Visual Recognition](https://mlsanity.com/paper/2205.13282/) (2022)
- [Eigendecomposition-Free Training of Deep Networks for Linear Least-Square Problems](https://mlsanity.com/paper/2004.07931/) (2020)

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

- [Orthogonal SVD Covariance Conditioning and Latent Disentanglement](https://mlsanity.com/paper/2212.05599/) (2022)
- [A Short Note on Batch-efficient Divide-and-Conquer Algorithm for EigenDecomposition](https://mlsanity.com/paper/2604.27325/) (2026)

## Abstract (arXiv)

EigenDecomposition (ED) is at the heart of many computer vision algorithms and applications. One crucial bottleneck limiting its usage is the expensive computation cost, particularly for a mini-batch of matrices in the deep neural networks. In this paper, we propose a QR-based ED method dedicated to the application scenarios of computer vision. Our proposed method performs the ED entirely by batched matrix/vector multiplication, which processes all the matrices simultaneously and thus fully utilizes the power of GPUs. Our technique is based on the explicit QR iterations by Givens rotation with double Wilkinson shifts. With several acceleration techniques, the time complexity of QR iterations is reduced from O(n5) to O(n3). The numerical test shows that for small and medium batched matrices (e.g., dim<32) our method can be much faster than the Pytorch SVD function. Experimental results on visual recognition and image generation demonstrate that our methods also achieve competitive performances.