# An Inversion Theorem for Buffered Linear Toeplitz (BLT) Matrices and Applications to Streaming Differential Privacy

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 20 references that are in the map.
- First posted on arXiv 30 Apr 2025.

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

- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams](https://mlsanity.com/paper/2202.08312/) (2022)
- [(Amplified) Banded Matrix Factorization: A unified approach to private training](https://mlsanity.com/paper/2306.08153/) (2023)
- [Constant matters: Fine-grained Complexity of Differentially Private Continual Observation](https://mlsanity.com/paper/2202.11205/) (2022)
- [Privacy Amplification for Matrix Mechanisms](https://mlsanity.com/paper/2310.15526/) (2023)
- [Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy](https://mlsanity.com/paper/2404.16706/) (2024)
- [Scaling up the Banded Matrix Factorization Mechanism for Differentially Private ML](https://mlsanity.com/paper/2405.15913/) (2024)
- [A Hassle-free Algorithm for Private Learning in Practice: Don't Use Tree Aggregation, Use BLTs](https://mlsanity.com/paper/2408.08868/) (2024)
- [Improved Differentially Private Continual Observation Using Group Algebra](https://mlsanity.com/paper/2412.02840/) (2024)

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

- [Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private SGD](https://mlsanity.com/paper/2505.12128/) (2025)
- [Private Continual Counting of Unbounded Streams](https://mlsanity.com/paper/2506.15018/) (2025)
- [Correlating Cross-Iteration Noise for DP-SGD using Model Curvature](https://mlsanity.com/paper/2510.05416/) (2025)

## Abstract (arXiv)

Buffered Linear Toeplitz (BLT) matrices are a family of parameterized lower-triangular matrices that play an important role in streaming differential privacy with correlated noise. Our main result is a BLT inversion theorem: the inverse of a BLT matrix is itself a BLT matrix with different parameters. We also present an efficient and differentiable O(d3) algorithm to compute the parameters of the inverse BLT matrix, where d is the degree of the original BLT (typically d < 10). Our characterization enables direct optimization of BLT parameters for privacy mechanisms through automatic differentiation.