Singular Value Decomposition

The singular value decomposition (SVD) is a decomposition that follows from the definition of singular values.

Description

Any linear transformation can be rewritten as a rotation (i.e., from the original basis onto a convenient basis), a scaling and stretching, and another rotation (i.e., from the convenient basis onto the destination basis). Therefore A = UΣV^T.

Solution

The definition of singular values (AV = UΣ) can be restated as A = UΣV^-1. If the certain vectors v_i are chosen to be orthogonal bases of the row space, then it is also true that A = UΣV^T.

Note then that A^TA = (UΣV^T)^TUΣV^T = VΣ^TU^TUΣV^T = VΣ^TΣV^T. Because Σ is a diagonal matrix with values of σ on the diagonal, Σ^TΣ evaluates to a diagonal matrix with values of σ² on the diagonal.

Effectively, this is a diagonalization of A^TA. V is the eigenbasis. Λ is equal to Σ^TΣ, therefore λ = σ².

With V and Σ known, U can be solved for. Alternatively, repeat the above method on AA^T. U will be that eigenbasis. The eigenvalues will be the same.

Interpretation

Singular values reflect the relative contribution of certain rows and columns to a matrix. Recall that singular values are ordered from largest to smallest by convention; the first indicates the greatest influence. This singular value corresponds to the first column of U. The larger magnitudes in that column identify the rows of A that take most from this relation. Similarly, this singular value corresponds to the first row of V^T. The larger magnitudes in that row indicate the columns of A that take most from this relation.

In the below example, the first singular value (10.4) connects the first through third rows of A to the first and third column of A.

julia> using LinearAlgebra

julia> A = [4 1 4 1; 5 1 4 0; 3 0 3 2; 0 2 1 4; 1 5 0 4]
5×4 Matrix{Int64}:
 4  1  4  1
 5  1  4  0
 3  0  3  2
 0  2  1  4
 1  5  0  4

julia> U, S, V = svd(A)
SVD{Float64, Float64, Matrix{Float64}, Vector{Float64}}
U factor:
5×4 Matrix{Float64}:
 -0.538764  -0.241808  -0.00729024  -0.568448
 -0.563657  -0.387293   0.366464     0.0616337
 -0.425671  -0.129738  -0.530012     0.687406
 -0.268361   0.484868  -0.589901    -0.388298
 -0.372573   0.734578   0.486575     0.223082
singular values:
4-element Vector{Float64}:
 10.354844862115025
  6.904143550221138
  2.415275359549066
  0.5257705364748064
Vt factor:
4×4 Matrix{Float64}:
 -0.639597  -0.3382    -0.575099  -0.381835
 -0.370551   0.581321  -0.350623   0.633894
  0.289698   0.667521  -0.307725  -0.613023
  0.608016  -0.319535  -0.672035   0.276737

The natural extension of this interpretation is that small singular values correspond to rows and columns which don't contribute much, and could potentially even be removed without changing A substantially. This leads to the low-rank approximation.

Consider if A has an interpretable design. The rows are individuals, the columns are films, and cell (i,j) is the score assigned to film j by individual i. These rows and columns are connected by topics or clusters; there are types of films that certain individuals prefer, or there are types of individuals which prefer certain films.

In the above example and using this interpretation, there are two meaningful topics. Individuals 1, 2, and 3 prefer films 1 and 3. Individuals 4 and 5 prefer films 2 and 4.

Already this starts to look like a film recommendation algorithm. It can be taken further through a low-rank approximation, and then identifying the zero-rated films (i.e., unwatched films) with the largest error. These properties lead to model-based approaches for collaborative filtering.

CategoryRicottone