The Eckart-Young Theorem

The Eckart-Young Theorem: Given an n by m matrix X of rank r £ m £ n, and its singular value decomposition, ULV', where U is an n by m matrix, L is an m by m diagonal matrix of singular values, and V is an m by m matrix such that

U'U = I_n and V'V = VV' = I_m

with the singular values arranged in decreasing sequence

l₁ ³ l₂ ³ l₃ ³ ... ³ l_m ³ 0

then there exists an n by m matrix B of rank s, s £ r, which minimizes the sum of the squared error between the elements of X and the corresponding elements of B when

B = UL_sV'

where the diagonal elements of the m by m diagonal matrix L_s are

l₁ ³ l₂ ³ l₃ ³ ... ³ l_s > l_s+1 = l_s+2 = ... = l_m = 0

Geometrically, the Eckart-Young Theorem states that the least squares approximation in s dimensions of a matrix X can be found by replacing the smallest m-s roots of L with zeroes and remultiplying ULV'.

For example, given:



the rank 2 approximation is:

---

svd_matrix.txt -- Simple 4 by 3 matrix.

#
# file: svd_example.r
#
# Purpose: Simple R program showing Singular
#          Value Decomposition
#
#
rm(list=ls(all=TRUE))
#
#
rc.file <- "c:/ucsd_course/svd_matrix.txt"
#
# Standard fields and their widths
#
rc.fields <- c("y1","y2","y3") 
#
rc.fieldWidths <- c(3,3,3)
#    
# Read the vote data from fwf
#
T <- read.fwf(file=rc.file,widths=rc.fieldWidths,as.is=TRUE,col.names=rc.fields)
dim(T)
#
nrow <- length(T[,1])
ncol <- length(T[1,])
#
xsvd <- svd(T)
#
#  The Two Lines Below Put the Singular Values in a
#    Diagonal Matrix -- The first one creates an 
#    identity matrix and the second command puts
#    the singular values on the diagonal
#
Lambda <- diag(ncol)
diag(Lambda) <- xsvd$d
#
#  Compute U*LAMBDA*V' for check below
#
XX <- xsvd$u %*% Lambda %*% t(xsvd$v)
#
xerror <- sum(abs(T-XX))
#