// HACKER NEWS — CYBERSECURITY
Truncated SVD (2023)
Principal Component Analysis (PCA) is the subject of a previous post of mine, so I will only summarize it here.
Data reduction via PCA is accomplished by linearly transforming the data into a new coordinate system where (most of) the variation in the data can be described with fewer dimensions than the initial data.
Without getting into the details, this involves an eigen-decomposition of the covariance matrix.
Singular Value Decomposition (SVD) is a matrix factorization technique that factors a real matrix M into three matrices U, Σ, and V such that M=U*Σ*V^T.
If M is mxn, then U is mxm, Σ is mxn and V is nxn. Both U and V are orthonormal, and Σ is rectangular-diagonal with non-negative coefficients.
This is very similar to PCA, excepting that the factorization for SVD is done on the data matrix, whereas for PCA, the factorization is done on the covariance matrix.
The diagonal coefficients of Σ are known as the singular values of M and it is common practice to rearrange the SVD so the singular values are given in decreasing order. The number of non-zero singular values is equal to the rank of M.
Let’s try with a 1024x1024 grayscale image of the moon:
Such an image can be interpreted as 1024 vectors of 1024 components each. i.e., a set of 1024 vectors in a 1024-dimension space.
If we run PCA/SVD on this set, the three matrices U, Σ, V will be 1024x1024. In particular, Σ will be a square-diagonal matrix. i.e., only the coefficients in the diagonal are potentially non-zero. It is common practice to rearrange the three matrices so the diagonal indices in Σ are sorted from greater (top-left) to lower (bottom-right).