The Azimuth Project
Eckart-Young low rank approximation theorem

Eckart-Young Low Rank Approximation Theorem

Idea

The Eckart-Young Theorem states that the approximation matrix with matrix rank nn to a matrix AA which has an error matrix with the lowest Frobenius norm is formed by taking the sum of the biggest nn elements of the Singular Value Decomposition. This can be used for very, very basic factor analysis.

Details

Todo: explanation.

There is an interesting illustration of low-rank approximation of a matrix, in this case an image, on Staffan Liljegrens Azimuth page.

In the extreme case, given a matrix AA where A ij=f(x i,y j)A_{i j}=f(x_i,y_j) for some “tabulated function defined by data”, the Eckart-Young theorem for n=1n=1 can be used to find the lowest squared error approximate decomposition into A approx=σuv TA^{approx}=\sigma \mathbf{u} \mathbf{v}^T (where |u| 2=|v| 2=1|\mathbf{u}|_2=|\mathbf{v}|_2=1). This corresponds to an approximate decomposition A ij approx=σf x(x i)f y(y j)A_{i j}^{approx}=\sigma f_x(x_i) f_y(y_j) for some “tabulated functions” f xf_x and f yf_y . This can be analysed to see if a separable function decomposition of ff is likely (given most functions ff derived from data are contaminated by noise) and used in attempting to fit actual functions to the tables of f xf_x and f yf_y values. However this approach only deals with separable cases in two original variables.

References