# Re-Analyze Gauss: Bounds for Private Matrix Approximation via Dyson Brownian Motion

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 54 references that are in the map.
- First posted on arXiv 11 Nov 2022.

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

- [PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization](https://mlsanity.com/paper/1905.13727/) (2019)
- [On the computability of continuous maximum entropy distributions with applications](https://mlsanity.com/paper/2004.07403/) (2020)

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

- [Optimal Differentially Private PCA and Estimation for Spiked Covariance Matrices](https://mlsanity.com/paper/2401.03820/) (2024)
- [Continual Release Moment Estimation with Differential Privacy](https://mlsanity.com/paper/2502.06597/) (2025)
- [Differentially Private Low-dimensional Synthetic Data from High-dimensional Datasets](https://mlsanity.com/paper/2305.17148/) (2023)
- [Private Covariance Approximation and Eigenvalue-Gap Bounds for Complex Gaussian Perturbations](https://mlsanity.com/paper/2306.16648/) (2023)
- [Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy](https://mlsanity.com/paper/2510.25670/) (2025)
- [Perturbation Bounds for Low-Rank Inverse Approximations under Noise](https://mlsanity.com/paper/2510.25571/) (2025)
- [Adaptive Power Iteration Method for Differentially Private PCA](https://mlsanity.com/paper/2602.11454/) (2026)
- [Expectation Error Bounds for Transfer Learning in Linear Regression and Linear Neural Networks](https://mlsanity.com/paper/2603.28739/) (2026)

## Abstract (arXiv)

Given a symmetric matrix M and a vector λ, we present new bounds on the Frobenius-distance utility of the Gaussian mechanism for approximating M by a matrix whose spectrum is λ, under (varepsilon,δ)-differential privacy. Our bounds depend on both λ and the gaps in the eigenvalues of M, and hold whenever the top k+1 eigenvalues of M have sufficiently large gaps. When applied to the problems of private rank-k covariance matrix approximation and subspace recovery, our bounds yield improvements over previous bounds. Our bounds are obtained by viewing the addition of Gaussian noise as a continuous-time matrix Brownian motion. This viewpoint allows us to track the evolution of eigenvalues and eigenvectors of the matrix, which are governed by stochastic differential equations discovered by Dyson. These equations allow us to bound the utility as the square-root of a sum-of-squares of perturbations to the eigenvectors, as opposed to a sum of perturbation bounds obtained via Davis-Kahan-type theorems.