Randomized SVD

2.1 Motivation

2.2 Algorithm

1. Draw random projection matrix $\mathbf{\Omega} \in \mathbb{R}^{n\times (k+p)}$
2. Compute $\mathbf{Y} = \mathbf{A}\mathbf{\Omega}$
3. Compute QR factorization: $\mathbf{Y} = \mathbf{Q}\mathbf{R}$
4. Project: $\mathbf{B} = \mathbf{Q}^T\mathbf{A}$
5. Compute SVD of small matrix $\mathbf{B} = \mathbf{U}_B \mathbf{\Sigma}_B \mathbf{V}_B^T$
6. Result: $\mathbf{A} \approx (\mathbf{Q}\mathbf{U}_B) \mathbf{\Sigma}_B \mathbf{V}_B^T$

Python Implementation

python
Run Inline
import numpy as np
def randomized_svd(A, k, p=5):
    n, m = A.shape
    Omega = np.random.randn(m, k + p)
    Y = A @ Omega
    Q, _ = np.linalg.qr(Y)
    B = Q.T @ A
    U_B, S, Vt = np.linalg.svd(B, full_matrices=False)
    U = Q @ U_B[:, :k]
    return U[:, :k], S[:k], Vt[:k, :]
# Example
A = np.random.randn(1000, 500)
k = 10
U, S, Vt = randomized_svd(A, k)
print(f"Original: {A.shape}, Compressed: {U.shape} x {S.shape}")

2.3 Error Bound