svd.hpp File Reference

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

#include "core/matrix.hpp"
#include "core/vector.hpp"
#include "core/policy.hpp"
#include "linalg/factorization/qr.hpp"
#include "core/util/math.hpp"
#include <cmath>
#include <algorithm>
#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ᵀ More...

Namespaces
namespace	num

Functions
SVDResult	num::svd (const Matrix &A, Backend backend=Backend::seq, real tol=1e-12, idx max_sweeps=100)
	Full SVD of an mxn matrix via one-sided Jacobi.
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ᵀ 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ᵀ * A (project A to k-dim subspace)
5. SVD of B = Ũ * Sigma * Vᵀ (small kxn problem)
6. U = Q * Ũ (lift back to full dimension)

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

Definition in file svd.hpp.