Entry-wise dissipation for singular vector perturbation bounds

04/01/2023
by   Abhinav Bhardwaj, et al.
0

Consider a random, symmetric perturbation of a symmetric, low rank matrix. The goal of this paper is to present entry-wise bounds on the perturbation of the singular vectors. In particular, our result shows that, under common incoherence assumptions, the entry-wise error is evenly dissipated. This improves a number of previous results and has algorithmic applications for many well known clustering problems, including the hidden clique, planted coloring, and planted bipartition.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset