# OptSpace: OptSpace : an algorithm for matrix reconstruction from a... In ROptSpace: Matrix Reconstruction from a Few Entries

## 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 ≤ C(α)√{nr/|E|}

## Usage

 1 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

\insertRef

keshavan_matrix_2010ROptSpace

## Examples

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 ## 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) 

ROptSpace documentation built on Aug. 16, 2021, 9:06 a.m.