Simple Relative Deviation Bounds for Covariance and Gram Matrices

Daniel Barzilai, Ohad Shamir

We provide non-asymptotic, relative deviation bounds for the eigenvalues of empirical covariance and Gram matrices in general settings. Unlike typical uniform bounds, which may fai…