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