OptSpace {ROptSpace}

OptSpace : an algorithm for matrix reconstruction from a partially revealed set

Description

Let's assume an ideal matrix M with (m\times n) entries with rank r and we are given a partially observed matrix M\_E which contains many missing entries. Matrix reconstruction - or completion - is the task of filling in such entries. OptSpace is an efficient algorithm that reconstructs M from |E|=O(rn) observed elements with relative root mean square error (RMSE)

RMSE \le C(\alpha)\sqrt{nr/|E|}

Usage

OptSpace(A, ropt = NA, niter = 50, tol = 1e-06, showprogress = TRUE)

Arguments

A

an (n\times m) matrix whose missing entries should be flaged as NA.

ropt

NA to guess the rank, or a positive integer as a pre-defined rank.

niter

maximum number of iterations allowed.

tol

stopping criterion for reconstruction in Frobenius norm.

showprogress

a logical value; TRUE to show progress, FALSE otherwise.

Value

a named list containing

X

an (n \times r) matrix as left singular vectors.

S

an (r \times r) matrix as singular values.

Y

an (m \times r) matrix as right singular vectors.

dist

a vector containing reconstruction errors at each successive iteration.

References

Keshavan RH, Montanari A, Oh S (2010). “Matrix Completion From a Few Entries.” IEEE Transactions on Information Theory, 56(6), 2980–2998. ISSN 0018-9448.

Examples

## Parameter Settings
n = 1000;
m = 100;
r = 3;
tolerance = 1e-7
eps = 10*r*log10(n)

## Generate a matrix with given data
U = matrix(rnorm(n*r),nrow=n)
V = matrix(rnorm(m*r),nrow=m)
Sig = diag(r)
M0 = U%*%Sig%*%t(V)

## Set some entries to be NA with probability eps/sqrt(m*n)
E = 1 - ceiling(matrix(rnorm(n*m),nrow=n) - eps/sqrt(m*n))
M_E = M0
M_E[(E==0)] = NA

## Create a noisy version
noiselevel = 0.1
M_E_noise  = M_E + matrix(rnorm(n*m),nrow=n)*noiselevel

## Use OptSpace for reconstruction
res1 = OptSpace(M_E,tol=tolerance)
res2 = OptSpace(M_E_noise,tol=tolerance)

## Compute errors for both cases using Frobenius norm
err_clean = norm(res1$X%*%res1$S%*%t(res1$Y)-M0,'f')/sqrt(m*n)
err_noise = norm(res2$X%*%res2$S%*%t(res2$Y)-M0,'f')/sqrt(m*n)

## print out the results
m1 = sprintf('RMSE without noise         : %e',err_clean)
m2 = sprintf('RMSE with noise of %.2f    : %e',noiselevel,err_noise)
print(m1)
print(m2)