pydiodon.svd_grp

pydiodon.svd_grp(A, k)

SVD of a (large) matrix by Gaussian Random Projection

Parameters:

Aa 2D numpy array

the matrix to be studied (dimension \(n \\times p\))

kan integer

the number of components to be computed

Returns:

Ua 2D numpy array

(dimension \(n \\times k\))

Sa 1D numpy array

(k values)

Va 2D numpy array

(dimension \(p \\times k\))

Notes

Builds the SVD of A as \(A = U\Sigma V^t\) where \(\Sigma\) is the diagonal matrix with diagonal S and \(V^t\) is the transpose of V.

Here are the different steps of the computation:

1. A is a \(n \\times p\) matrix

2. builds \(\Omega\), a \(p \\times k\) random matrix (Gaussian)

3. computes Y = A\(\Omega\) (dimension \(n \\times k\))

4. computes a QR decomposition of Y

   Y = QR, with

   Q is orthonormal (\(n \\times k\))

   R is upper triangular (:math:`k \times k)

5. computes B = Q^t A

   B is :math:`k \times p (with k < p) and its SVD is supposed to be close to the one of A

6. \(U_B\), S, and V are SVD of B:

   \(B = U_B S V'\), S is diagonal

7. then, \(U_A\), S and V are close to svd of A : \(A = U_A S V'\)

Sizes and computation of the matrices

matrix	value	size
A	input	\(n \\times p\)
\(\Omega\)	random	\(p \\times k\)
Y	\(A\Omega\)	\(n \\times k\)
Q	Y = QR	\(n \\times k\)
B	B = Q^t A	\(k \\times p\)
\(U_B\)	\(B = U_BSV^t\)	\(k \\times k\)
U	\(U = QU_B\)	\(n \\times k\)

References

[1] Halko & al., 2011, SIAM Reviews, 53(2): 217-288

af, rp, fp 21.03.21; 22.06.16, 22.10.28