{
  "id": "1506.02764",
  "version": "v1",
  "published": "2015-06-09T03:26:27.000Z",
  "updated": "2015-06-09T03:26:27.000Z",
  "title": "Perturbation of linear forms of singular vectors under Gaussian noise",
  "authors": [
    "Vladimir Koltchinskii",
    "Dong Xia"
  ],
  "categories": [
    "math.PR"
  ],
  "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,\\ldots,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,\\ldots, 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\\geq\\ldots\\geq\\tilde{\\sigma}_{m\\wedge n}$ and singular vectors $\\tilde{u}_k,\\tilde{v}_k,k=1,\\ldots, m\\wedge n.$ The goal of this paper is to develop sharp concentration bounds for linear forms $\\langle \\tilde u_k,x\\rangle, x\\in {\\mathbb R}^m$ and $\\langle \\tilde v_k,y\\rangle, 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\\biggl(\\sqrt{\\frac{\\log(m+n)}{m\\vee n}}\\biggr)$ (holding with a high probability) on $$\\max_{1\\leq i\\leq m}\\big|\\big<\\tilde{u}_k-\\sqrt{1+b_k}u_k,e_i^m\\big>\\big|\\ \\ {\\rm and} \\ \\ \\max_{1\\leq j\\leq n}\\big|\\big<\\tilde{v}_k-\\sqrt{1+b_k}v_k,e_j^n\\big>\\big|,$$ 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,\\ldots,m\\}, \\{e_j^n,j=1,\\ldots,n\\}$ are the canonical bases of $\\mathbb{R}^m, {\\mathbb R}^n,$ respectively.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-06-09T03:26:27.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "gaussian noise",
      "right orthonormal singular vectors",
      "perturbation",
      "sharp concentration bounds",
      "singular value decomposition"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}