# LU decomposition and Toeplitz decomposition of a neural network

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 37 references that are in the map.
- First posted on arXiv 25 Nov 2022.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Learning both Weights and Connections for Efficient Neural Networks](https://mlsanity.com/paper/1506.02626/) (2015)
- [Pruning Filters for Efficient ConvNets](https://mlsanity.com/paper/1608.08710/) (2016)
- [Linear Mode Connectivity and the Lottery Ticket Hypothesis](https://mlsanity.com/paper/1912.05671/) (2019)
- [The Expressive Power of Neural Networks: A View from the Width](https://mlsanity.com/paper/1709.02540/) (2017)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [Proving the Lottery Ticket Hypothesis: Pruning is All You Need](https://mlsanity.com/paper/2002.00585/) (2020)
- [Universal Approximation with Deep Narrow Networks](https://mlsanity.com/paper/1905.08539/) (2019)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [Universality of Deep Convolutional Neural Networks](https://mlsanity.com/paper/1805.10769/) (2018)
- [1D Convolutional Neural Networks and Applications: A Survey](https://mlsanity.com/paper/1905.03554/) (2019)
- [Approximating Continuous Functions by ReLU Nets of Minimal Width](https://mlsanity.com/paper/1710.11278/) (2017)
- [One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizers](https://mlsanity.com/paper/1906.02773/) (2019)
- [Minimum Width for Universal Approximation](https://mlsanity.com/paper/2006.08859/) (2020)
- [ResNet with one-neuron hidden layers is a Universal Approximator](https://mlsanity.com/paper/1806.10909/) (2018)
- [Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity](https://mlsanity.com/paper/1810.07770/) (2018)
- [Deep, Skinny Neural Networks are not Universal Approximators](https://mlsanity.com/paper/1810.00393/) (2018)

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

- [Toeplitz MLP Mixers are Low Complexity, Information-Rich Sequence Models](https://mlsanity.com/paper/2605.06683/) (2026)

## Abstract (arXiv)

It is well-known that any matrix A has an LU decomposition. Less well-known is the fact that it has a 'Toeplitz decomposition' A = T1 T2 cdots Tr where Ti's are Toeplitz matrices. We will prove that any continuous function f : ℝn → ℝm has an approximation to arbitrary accuracy by a neural network that takes the form L1 σ1 U1 σ2 L2 σ3 U2 cdots Lr σ2r-1 Ur, i.e., where the weight matrices alternate between lower and upper triangular matrices, σi(x) := σ(x - bi) for some bias vector bi, and the activation σ may be chosen to be essentially any uniformly continuous nonpolynomial function. The same result also holds with Toeplitz matrices, i.e., f ≈ T1 σ1 T2 σ2 cdots σr-1 Tr to arbitrary accuracy, and likewise for Hankel matrices. A consequence of our Toeplitz result is a fixed-width universal approximation theorem for convolutional neural networks, which so far have only arbitrary width versions. Since our results apply in particular to the case when f is a general neural network, we may regard them as LU and Toeplitz decompositions of a neural network. The practical implication of our results is that one may vastly reduce the number of weight parameters in a neural network without sacrificing its power of universal approximation. We will present several experiments on real data sets to show that imposing such structures on the weight matrices sharply reduces the number of training parameters with almost no noticeable effect on test accuracy.