A universal expectation bound on empirical projections of deformed random matrices

Abstract

Let $C$ be a real-valued $M\times M$ matrix with singular values ${\lambda }_1\ge ...\ge {\lambda }_M$ and $E$ a random matrix of centered i.i.d. entries with finite fourth moment. In this paper we give a universal upper bound on the expectation of $||{\hat{\pi }}_{r}X|{|}_{S_2}^2-||{\pi }_{r}X|{|}_{S_2}^2$, where $X:=C+E$ and ${\hat{\pi }}_r$ (resp. ${\pi }_r$) is a rank-$r$ projection maximizing the Hilbert-Schmidt norm $||{\tilde{\pi }}_{r}X|{|}_{S_2}$ (resp. $||{\tilde{\pi }}_{r}C|{|}_{S_2}$) over the set ${\S }_{M,r}$ of all orthogonal rank-$r$ projections. This result is a generalization of a theorem for Gaussian matrices due to Rohde (2012). Our approach differs substantially from the techniques of the mentioned article. We analyze $||{\hat{\pi }}_{r}X|{|}_{S_2}^2-||{\pi }_{r}X|{|}_{S_2}^2$ from a rather deterministic point of view by an upper bound on $||{\hat{\pi }}_{r}X|{|}_{S_2}^2-||{\pi }_{r}X|{|}_{S_2}^2$, whose randomness is totally determined by the largest singular value of $E$.

The final publication is available at link.springer.com/article/10.1007%2Fs10959-013-0517-9