Singular Value Projection (SVP-1.0)
===================================
SVP is a Matlab implementation of the Singular Value Projection Method. SVP solves the problem of low-rank matrix completion by using a variant of the classical projected gradient method. It uses PROPACK (written by Rasmus Munk Larsen) for computing SVD at each step for projection. We have modified the wrapper files lansvd and lanbpro file of PROPACK to suit our needs.
1. Installation
Change directory to svp. Type install_svp on the Matlab console.
2. Quick-start
Type test_svp.
3. Using the code
[U S V t err] = svp (Omega, b, m, n, k, params)
Return the result of solving min \| b - X(Omega) \|_F^2 , s.t rank(X) <= k
Inputs:
Omega - indices of known entries.
b - values of known entries
k - approximate rank. We only work with matrices of rank up to rank k.
params - parameter structure containing the following fields:
tol,vtol,mxitr - stopping criteria
defaults = 1e-2 (tol), 1e-3 (vtol), 100 (mxitr)
verbosity - verbosity level
default = 1
eta - step size
default = 3/(4p) where p=fraction of entries available
Outputs:
U - Left singular vectors of the optimal matrix X
S - Singular values of X
V - Right singular vectors of X
t - Number of iterations required
err - RMSE over the known values
FAQ:
1) install_svp gives the following error: "g95:command not found. mex: compile of dbdqr.f failed".
Ans: Mex needs a fortran compiler for all the .f files in the private folder. By default it assumes g95 is the fortran compiler. You can change the compiler name by changing "FC" variable in the mexopts.sh file (on most linux distributions you can find mexopts.sh in "~/.matlab/Version/" directory, where "Version" is the version of the Matlab you are using.
You can also find a "typical" mexopts.sh file on our webpage where fortran compiler name is assumed to be gfortran.
For CS UT machine users: copy mexopts.sh in the "~/.matlab/R2007b/" directory.
2) I receive the error message saying "Divergence!!!".
Ans: SVP can diverge if the number of samples is very small. However, you can try decreasing the step size in params.eta variable to make SVP converge. Although RMSE might suffer in this case.
Reference:
Raghu Meka, Prateek Jain, Inderjit S. Dhillon.
"Guaranteed Rank Minimization via Singular Value Projection"
Arxiv:0909.5457