Take an \(n \times m\) matrix \(X\). The factorized form using singular value decomposition is \(U\Sigma V^T\) where \(U\) is a \(n \times m\) matrix, \(\Sigma\) and \(V^T\) are \(m \times m\) matrices.
Properties of the matrices, \(U\), \(V\) and \(\Sigma\)
Both \(U\) and \(V\) are orthogonal matrices, \(U^T U = I\), \(V^T V = V V^T = I\).
Singular values:
The diagonal matrix \(\Sigma\) has all entries off the main diagonal as zero. \(\sigma_{11} \geq \sigma_{22} \geq \ldots \geq \sigma_{nn} \geq 0\)
low rank approximation:
The best approximation for \(X \in p\) dimensions, \(p < n\) is \(U_p\Sigma_p V_p^T\), the first \(p\) columns of \(\Sigma\)
Principal Component Analysis
\(X = U\Sigma V^T\)
\(U\Sigma = XV\)
Other forms:
\(X^T X = (U\Sigma V^T)^T U\Sigma V^T = V\Sigma U^TU\Sigma V^T = V\Sigma^2 V^T\)
\((X^T X)^{-1} = V\Sigma^{-2} V^T\)
\(X(X^T X)^{-1}X^T = U\Sigma V^T V\Sigma^{-2}V^T V\Sigma U^T = UU^T\)
Eigendecomposition
For symmetric \(A = X^T\), \(X = V\Sigma^2 V^T\), and \(B = XX^T = U\Sigma V^T(V\Sigma U^T) = U\Sigma^2U^T\)
The eigenvalues of \(A\) and \(B\) are \(\Sigma\Sigma^T\) and \(\Sigma^T\Sigma\) respectively with eigenvectors \(U\) and \(V^T\).
x = np.randn((100, 50))
u = np.randn(100)
v = np.randn(50)
for _ in range(500):
u = x@v
u = u/sqrt(np.sum(u**2))
v = x.T@u
v = v/sqrt(np.sum(v**2))