Matrix Completion via Thresholding

Convex, Non-convex and NP hard matrix completion algorithms

Description

Contains three matrix completion algorithms and a demo script for running them. Also compares against other matrix completion algorithms - Singular Value Thresholding and Fixed Point Iteration.
Solves the following three optimization problems:
min rank(X) subject to ||y - M(X)||_2<err via Iterated Hard Thresholding
min nuclear-norm(X) subject to ||y - M(X)||_2<err via Iterated Soft Thresholding
min ||S||_p subject to ||y - M(X)||_2<err, where S = svd(X) via Iterated Soft Thresholding
Requires Sparco since the masking operator has been defined in according to the Sparco framework.
http://www.cs.ubc.ca/labs/scl/sparco/
The algorithms are general enough to work with any other linear operator, and not only the masking operator. The masking operator is just a special case when the problem boils down to one of matrix completion.
For comparing the results with other algorithms download the Singular Value Thresholding toolbox
http://svt.caltech.edu/

• MATLAB release: MATLAB 7.8 (R2009a)
• Other requirements: Sparco: http://www.cs.ubc.ca/labs/scl/sparco/ SVT: http://svt.caltech.edu/