Perturbation of linear forms of singular vectors under Gaussian noise

Abstract

Let $A\in {\mathbb{R}}^{m\times n}$ be a matrix of rank $r$ with singular value decomposition (SVD) $A={\sum }_{k=1}^r{\sigma }_k(u_k\otimes v_k),$ where $\{{\sigma }_k,k=1,\dots ,r\}$ are singular values of $A$ (arranged in a non-increasing order) and $u_k\in {\mathbb{R}}^m,v_k\in {\mathbb{R}}^n,k=1,\dots ,r$ are the corresponding left and right orthonormal singular vectors. Let $\tilde{A}=A+X$ be a noisy observation of $A,$ where $X\in {\mathbb{R}}^{m\times n}$ is a random matrix with i.i.d. Gaussian entries, $X_{ij}\sim \mathcal{N}(0,{\tau }^2),$ and consider its SVD $\tilde{A}={\sum }_{k=1}^{m\wedge n}{\tilde{\sigma }}_k({\tilde{u}}_k\otimes {\tilde{v}}_k)$ with singular values ${\tilde{\sigma }}_1\ge \dots \ge {\tilde{\sigma }}_{m\wedge n}$ and singular vectors ${\tilde{u}}_k,{\tilde{v}}_k,k=1,\dots ,m\wedge n.$ The goal of this paper is to develop sharp concentration bounds for linear forms $⟨{\tilde{u}}_k,x⟩,x\in {\mathbb{R}}^m$ and $⟨{\tilde{v}}_k,y⟩,y\in {\mathbb{R}}^n$ of the perturbed (empirical) singular vectors in the case when the singular values of $A$ are distinct and, more generally, concentration bounds for bilinear forms of projection operators associated with SVD. In particular, the results imply upper bounds of the order $O\left(\sqrt{\frac{\log (m+n)}{m\vee n}}\right)$ (holding with a high probability) on $$\underset{1\le i\le m}{\max }|⟨{\tilde{u}}_k-\sqrt{1+b_k}{u}_k,e_i^m⟩|\mathrm{and}\underset{1\le j\le n}{\max }|⟨{\tilde{v}}_k-\sqrt{1+b_k}{v}_k,e_j^n⟩|,$$ where $b_k$ are properly chosen constants characterizing the bias of empirical singular vectors ${\tilde{u}}_k,{\tilde{v}}_k$ and $\{e_i^m,i=1,\dots ,m\},\{e_j^n,j=1,\dots ,n\}$ are the canonical bases of ${\mathbb{R}}^m,{\mathbb{R}}^n,$ respectively.