Three randomized low-rank approximation algorithms written from scratch in Python and compared with the exact SVD on synthetic and boundary integral kernel matrices. The SRHT sketch has fewer operations than the Gaussian one, but it was slower and used much more memory in my tests.
Singular Value Decomposition (SVD) is a fundamental algorithm in numerical linear algebra. In this post, I will show how to factorize a matrix and use low-rank approximation to compress a high-resolution image, using Python. The Mathematics of SVD Every real matrix $A$ of dimensions $m \times n$ can be factored into three matrix: $$A = U \Sigma V^T$$ Where: $U$ is an $m \times m$ orthogonal matrix of left singular vectors. $\Sigma$ is an $m \times n$ diagonal matrix containing the singular values ($\sigma_i$) in descending order. $V^T$ is an $n \times n$ orthogonal matrix of right singular vectors. By keeping only the largest $k$ singular values (where $k < \text{rank}(A)$), we can form a truncated approximation $A_k$ that captures the maximum possible “energy” (or variance) of original matrix: ...