Low-Rank Approximation

A low-rank approximation is an approximation of a matrix.

Description

Singular values reflect the relative contribution of certain rows and columns to a matrix. The natural extension of this interpretation is that small singular values correspond to rows and columns which don't contribute much.

Consider the example shown here:

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 first singular value is substantially larger than all others. Therefore using only the rows and columns corresponding to it should arrive at an approximation that captures a large part of the information. This is called the rank-1 approximation.

julia> A_1 = U[:,1] * S[1] * V[:,1]'
5×4 Matrix{Float64}:
 3.56819  1.88676   3.20837  2.13019
 3.73306  1.97393   3.35661  2.22861
 2.81919  1.4907    2.5349   1.68304
 1.77734  0.939804  1.59811  1.06106
 2.46753  1.30476   2.21869  1.4731

This approximation can be evaluated in terms of RMSE, which can be calculated through the Frobenius norm scaled by (mn)^-1.

julia> m,n = size(A)
(5, 4)

julia> rmse = norm(A_1 - A, 2)/sqrt(m*n)
1.6397741899653446

Approximations can be made for any rank k up to the actual rank of the SVD. As k increases, the approximation approaches A.

CategoryRicottone