# Differentially Private Linear Algebra in the Streaming Model

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Sep 2014.

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

- [Single Pass Entrywise-Transformed Low Rank Approximation](https://mlsanity.com/paper/2107.07889/) (2021)
- [The Normal Distributions Indistinguishability Spectrum and its Application to Privacy-Preserving Machine Learning](https://mlsanity.com/paper/2309.01243/) (2023)
- [Data Analytics with Differential Privacy](https://mlsanity.com/paper/2311.16104/) (2023)
- [Private Sketches for Linear Regression](https://mlsanity.com/paper/2511.07365/) (2025)

## Abstract (arXiv)

Numerical linear algebra plays an important role in computer science. In this paper, we initiate the study of performing linear algebraic tasks while preserving privacy when the data is streamed online. Our main focus is the space requirement of the privacy-preserving data-structures. We give the first em sketch-based algorithm for differential privacy. We give optimal, up to logarithmic factor, space data-structures that can compute low rank approximation, linear regression, and matrix multiplication, while preserving differential privacy with better additive error bounds compared to the known results. Notably, we match the best known space bound in the non-private setting by Kane and Nelson (J. ACM, 61(1):4). Our mechanism for differentially private low-rank approximation em reuses the random Gaussian matrix in a specific way to provide a single-pass mechanism. We prove that the resulting distribution also preserve differential privacy. This can be of independent interest. We do not make any assumptions, like singular value separation or normalized row assumption, as made in the earlier works. The mechanisms for matrix multiplication and linear regression can be seen as the private analogues of the known non-private algorithms. All our mechanisms, in the form presented, can also be computed in the distributed setting.