{"id":1506,"date":"2023-06-12T14:25:57","date_gmt":"2023-06-12T14:25:57","guid":{"rendered":"https:\/\/www.ethanepperly.com\/?p=1506"},"modified":"2025-06-16T23:36:37","modified_gmt":"2025-06-16T23:36:37","slug":"low-rank-approximation-toolbox-randomized-svd","status":"publish","type":"post","link":"https:\/\/www.ethanepperly.com\/index.php\/2023\/06\/12\/low-rank-approximation-toolbox-randomized-svd\/","title":{"rendered":"Low-Rank Approximation Toolbox: Randomized SVD"},"content":{"rendered":"\n

The randomized SVD and its relatives are workhorse algorithms for low-rank approximation. In this post, I hope to provide a fairly brief introduction to this useful method. In the following post, we’ll look into its analysis.<\/p>\n\n\n\n

The randomized SVD is dead-simple to state: To approximate an \"m\times n\" matrix \"B\" by a rank-\"k\" matrix, perform the following steps:<\/p>\n\n\n\n

    \n
  1. Collect information.<\/strong> Form \"Y = B\Omega\" where \"\Omega\" is an appropriately chosen \"n\times k\" random<\/em> matrix.<\/li>\n\n\n\n
  2. Orthogonalize.<\/strong> Compute an orthonormal basis \"Q\" for the column space of \"Y\" by, e.g., thin QR factorization<\/a>.<\/li>\n\n\n\n
  3. Project.<\/strong> Form \"C \coloneqq Q^*B\". (Here, \"{}^*\" denotes the conjugate transpose<\/a> of a complex matrix, which reduces to the ordinary transpose<\/a> if the matrix is real.)<\/li>\n<\/ol>\n\n\n\n

    If all one cares about is a low-rank approximation to the matrix \"B\", one can stop the randomized SVD here, having obtained the approximation<\/p>\n\n\n\n

      <\/span>   <\/span>\"\[B \approx X \coloneqq Q C.\]\"<\/p><\/p>\n\n\n\n

    As the name “randomized SVD” suggests, one can easily “upgrade” the approximation \"X = QC\" to a compact SVD<\/a> format:<\/p>\n\n\n\n

      \n
    1. SVD.<\/strong> Compute a compact SVD<\/a> of the matrix \"C\": \"C = \hat{U}\Sigma V^*\" where \"\hat{U}\" and \"\Sigma\" and \"k\times k\" and \"V\" is \"n\times k\".<\/li>\n\n\n\n
    2. Clean up.<\/strong> Set \"U \coloneqq Q\hat{U}\".<\/li>\n<\/ol>\n\n\n\n

      We now have approximated \"B\" by a rank-\"k\" matrix \"X\" in compact SVD form:<\/p>\n\n\n\n

        <\/span>   <\/span>\"\[B \approx X = QC = U\Sigma V^*.\]\"<\/p><\/p>\n\n\n\n

      One can use the factors \"U\", \"\Sigma\", and \"V\" of the approximation \"X \approx B\" as estimates of the singular vectors<\/a> and values<\/a> of the matrix \"B\".<\/p>\n\n\n\n

      What Can You Do with the Randomized SVD?<\/h2>\n\n\n\n

      The randomized SVD has many uses. Pretty much anywhere you would ordinarily use an SVD is a candidate for the randomized SVD. Applications include model reduction<\/a>, fast direct solvers<\/a>, computational biology<\/a>, uncertainty quantification<\/a>, among numerous others.<\/p>\n\n\n\n

      To speak in broad generalities, there are two ways to use the randomized SVD:<\/p>\n\n\n\n