Private Matrix Approximation and Geometry of Unitary Orbits
Consider the following optimization problem: Given $n \times n$ matrices $A$
and $\Lambda$, maximize $\langle A, U\Lambda U^*\rangle$ where $U$ varies over
the unitary group $\mathrm{U}(n)$. This problem seeks to approximate $A$ by a
matrix whose spectrum is the same as $\Lambda$ and, by setting $\Lambda$ to be
appropriate diagonal matrices, one can recover matrix approximation problems
such as PCA and rank-$k$ approximation. We study the problem of designing
differentially private algorithms for this optimization problem in settings
where the matrix $A$ is constructed using users' private data. We give
efficient and private algorithms that come with upper and lower bounds on the
approximation error. Our results unify and improve upon several prior works on
private matrix approximation problems. They rely on extensions of
packing/covering number bounds for Grassmannians to unitary orbits which should
be of independent interest.