# Beyond Nystr"omformer -- Approximation of self-attention by Spectral Shifting

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 28 references that are in the map.
- First posted on arXiv 9 Mar 2021.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [ALBERT: A Lite BERT for Self-supervised Learning of Language Representations](https://mlsanity.com/paper/1909.11942/) (2019)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context](https://mlsanity.com/paper/1901.02860/) (2019)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [Training Deep Nets with Sublinear Memory Cost](https://mlsanity.com/paper/1604.06174/) (2016)
- [Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attention](https://mlsanity.com/paper/2102.03902/) (2021)
- [Large Memory Layers with Product Keys](https://mlsanity.com/paper/1907.05242/) (2019)
- [Baseline Needs More Love: On Simple Word-Embedding-Based Models and Associated Pooling Mechanisms](https://mlsanity.com/paper/1805.09843/) (2018)
- [Adaptive Sampled Softmax with Kernel Based Sampling](https://mlsanity.com/paper/1712.00527/) (2017)
- [Nystr"om landmark sampling and regularized Christoffel functions](https://mlsanity.com/paper/1905.12346/) (2019)
- [SPSD Matrix Approximation vis Column Selection: Theories, Algorithms, and Extensions](https://mlsanity.com/paper/1406.5675/) (2014)

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

- [T-EMDE: Sketching-based global similarity for cross-modal retrieval](https://mlsanity.com/paper/2105.04242/) (2021)

## Abstract (arXiv)

Transformer is a powerful tool for many natural language tasks which is based on self-attention, a mechanism that encodes the dependence of other tokens on each specific token, but the computation of self-attention is a bottleneck due to its quadratic time complexity. There are various approaches to reduce the time complexity and approximation of matrix is one such. In Nystr"omformer, the authors used Nystr"om based method for approximation of softmax. The Nystr"om method generates a fast approximation to any large-scale symmetric positive semidefinite (SPSD) matrix using only a few columns of the SPSD matrix. However, since the Nystr"om approximation is low-rank when the spectrum of the SPSD matrix decays slowly, the Nystr"om approximation is of low accuracy. Here an alternative method is proposed for approximation which has a much stronger error bound than the Nystr"om method. The time complexity of this same as Nystr"omformer which is Oleft(nright).