Private Covariance Approximation and Eigenvalue-Gap Bounds for Complex
  Gaussian Perturbations
Oren Mangoubi Nisheeth K. Vishnoi
We consider the problem of approximating a $d \times d$ covariance matrix $M$
with a rank-$k$ matrix under $(\varepsilon,\delta)$-differential privacy. We
present and analyze a complex variant of the Gaussian mechanism and show that
the Frobenius norm of the difference between the matrix output by this
mechanism and the best rank-$k$ approximation to $M$ is bounded by roughly
$\tilde{O}(\sqrt{kd})$, whenever there is an appropriately large gap between
the $k$'th and the $k+1$'th eigenvalues of $M$. This improves on previous work
that requires that the gap between every pair of top-$k$ eigenvalues of $M$ is
at least $\sqrt{d}$ for a similar bound. Our analysis leverages the fact that
the eigenvalues of complex matrix Brownian motion repel more than in the real
case, and uses Dyson's stochastic differential equations governing the
evolution of its eigenvalues to show that the eigenvalues of the matrix $M$
perturbed by complex Gaussian noise have large gaps with high probability. Our
results contribute to the analysis of low-rank approximations under
average-case perturbations and to an understanding of eigenvalue gaps for
random matrices, which may be of independent interest.