= Singular Value Decomposition = The '''singular value decomposition''' ('''SVD''') is a decomposition that follows from the definition of [[LinearAlgebra/SingularValues|singular values]]. <> ---- == Description == Any [[LinearAlgebra/LinearMapping|linear transformation]] can be rewritten as a rotation (i.e., from the original [[LinearAlgebra/Basis|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 [[LinearAlgebra/SingularValues|singular values]] ('''''AV''' = '''UΣ''''') can be restated as '''''A''' = '''UΣV'''^-1^''. If the certain vectors ''v,,i,,'' are chosen to be [[LinearAlgebra/Orthogonality|orthogonal]] [[LinearAlgebra/Basis|bases]] of the row space, then it is also true that '''''A''' = '''UΣV'''^T^''. Note then that '''''A'''^T^'''A''' = ('''UΣV'''^T^)^T^'''UΣV'''^T^ = '''VΣ'''^T^'''U'''^T^'''UΣ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 ''σ^2^'' on the diagonal. Effectively, this is a [[LinearAlgebra/Diagonalization|diagonalization]] of '''''A'''^T^'''A'''''. '''''V''''' is the eigenbasis. '''''Λ''''' is equal to '''''Σ'''^T^'''Σ''''', therefore ''λ = σ^2^''. 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 [[LinearAlgebra/LowRankApproximation|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