Truncated Singular Value Decomposition

Overview


The singular value decomposition decomposes a matrix {% X %} into three other matrices multiplied together.
{% X = U \Sigma V %}
The truncated SVD takes the SVD decomposition and then truncates the matrices in the product, to form a new product.
{% X \approx \hat{U} \hat{\Sigma} \hat{V} %}
  • {% \hat{U} %} - the first {% r %} columns of {% U %}
  • {% \hat{V} %} - the first {% r %} columns of {% V %}
  • {% \hat{\Sigma} %} - the first {% r %} columns and {% n %} rows of {% \Sigma %}
({% r %} here is known as the truncation rank)

(see brunton chapt 1)

Vector Representation


{% A = \sum_{k=1}^r \sigma_k \vec{u}_k \vec{v}_k^T %}
where {% \vec{u}+k %} is the {% k^{th} %} row of {% U %} and {% \vec{v}_k %} is the {% k^{th} %} row of {% V %}. {% \sigma_i %} is the {% i^{th} %} diagonal value of {% \Sigma %}. The sum is taken over the truncation rank, {% r %}.

Properties


If the truncation rand {% r %} is chosen so that all the non-zero singular values are kept (that is, only zeros are discarded from {% \Sigma %}), then the truncated SVD exactly reproduces the matrix {% X %}, otherwise, the resulting matrix will be "close" to the original matrix.

Topics


  • Eckart Young Theorem - the truncated SVD is the best approximation of a matrix in the {% \mathcal{l}_2 %} sense

Implementation


The following code utilizes the linear algebra library to compute the svd decomposition. 


let la = await import('/lib/liniear-albgebra/v1.0.0/linear-algebra.mjs');
let svd = la.truncatedSVD(matrix1,2);

let test = la.multiply(svd.u, svd.sigma);
let result = la.multiply(test, la.transpose(svd.v));
Try it!