svd.hpp File Reference

Singular Value Decomposition – dense and randomized truncated. More...

#include "core/matrix.hpp"
#include "core/policy.hpp"
#include "core/util/math.hpp"
#include "core/vector.hpp"
#include "linalg/factorization/qr.hpp"
#include <algorithm>
#include <cmath>
#include <stdexcept>

Go to the source code of this file.

Classes
struct	num::SVDResult
	Result of a Singular Value Decomposition: A = U * diag(S) * V^T. More...

Namespaces
namespace	num

Functions
SVDResult	num::svd (const Matrix &A, Backend backend=lapack_backend, real tol=1e-12, idx max_sweeps=100)
	Full SVD of an mxn matrix.
SVDResult	num::svd_truncated (const Matrix &A, idx k, Backend backend=default_backend, idx oversampling=10, Rng *rng=nullptr)
	Randomized truncated SVD – top-k singular triplets.

Detailed Description

Singular Value Decomposition – dense and randomized truncated.

Two algorithms:

svd(A) Full SVD via one-sided Jacobi: A = U * diag(S) * V^T svd_truncated(A,k) Randomized truncated SVD: top-k singular triplets

Full SVD (one-sided Jacobi)

The one-sided Jacobi algorithm applies Givens rotations to the columns of A (from the right) until the columns are mutually orthogonal.

Randomized truncated SVD

For large A where only the top-k singular triplets are needed. Algorithm (Halko, Martinsson, Tropp 2011):

1. Draw Omega in R^{nx(k+p)} (Gaussian random sketch, p=10 oversampling)
2. Y = A * Omega (sample the range of A)
3. Q = QR(Y) (orthonormal basis for approx. range)
4. B = Q^T * A (project A to k-dim subspace)
5. SVD of B = U~ * Sigma * V^T (small kxn problem)
6. U = Q * U~ (lift back to full dimension)

Cost: O(mnk) vs O(mn*min(m,n)) for full SVD.

Definition in file svd.hpp.