ROptSpace (version 0.2.3)

OptSpace: 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_matrix_2010ROptSpace

Examples

# NOT RUN {
## 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)

# }