Low rank matrix completion

We consider the problem of recovering a low rank matrix given a sampling of its entries. Such problems are of considerable interest in a diverse set of fields including control, system identification, statistics and signal processing. Although the general low rank matrix completion problem is NP-hard, there exist several heuristic methods that solve the problem approximately by solving the convex relaxation of the original problem. One particularly popular method is to use nuclear norm (sum of singular values) to approximate the rank of the matrix and formulate the problem as a semidefinite program that can be solved efficiently. In this thesis, we propose a local completion algorithm that searches for possible completion in the neighborhood of each unspecified entry given the rank of the matrix. Unlike existing methods, this algorithm requires only local information of the matrix if the rank is known. Critical in all low rank matrix completion algorithms is the sampling density. The denser the matrix is sampled, the more likely it can be recovered accurately. We then propose a condensation process that increases the sampling density in a specific part of the matrix through elementary row and column re-ordering. Hence we can solve a sub-problem of the original low rank matrix completion problem and gain information on the rank of the matrix. Then the local algorithm is readily applicable to recover the entire matrix. We also explore the effect of additional sampling structures on the completion rate of the low rank matrix completion problems. In particular, we show that imposing regularity in the sampling process leads to slightly better completion rates.

Department dc:contributor.department

Massachusetts Institute of Technology. Computation for Design and Optimization Program.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2009

Author dc:creator

• Nan, Feng, S.M. Massachusetts Institute of Technology

Advisor dc:contributor.advisor

• Pablo.A.Parrilo.

• Computation for Design and Optimization Program.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/55077

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/55077