Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy Phuc Tran VinUniversity Nisheeth K. Vishnoi Yale University Van H. Vu Yale University

A central challenge in machine learning is to understand how noise or measurement errors affect low-rank approximations--particularly in the spectral norm. This question is especially important in differentially private low-rank approximation, where one aims to preserve the top-pstructure of a data-derived matrix while ensuring privacy.