Computer Science – Learning
Scientific paper
2009-02-23
Computer Science
Learning
19 pages
Scientific paper
The problem of completing a low-rank matrix from a subset of its entries is often encountered in the analysis of incomplete data sets exhibiting an underlying factor model with applications in collaborative filtering, computer vision and control. Most recent work had been focused on constructing efficient algorithms for exact or approximate recovery of the missing matrix entries and proving lower bounds for the number of known entries that guarantee a successful recovery with high probability. A related problem from both the mathematical and algorithmic point of view is the distance geometry problem of realizing points in a Euclidean space from a given subset of their pairwise distances. Rigidity theory answers basic questions regarding the uniqueness of the realization satisfying a given partial set of distances. We observe that basic ideas and tools of rigidity theory can be adapted to determine uniqueness of low-rank matrix completion, where inner products play the role that distances play in rigidity theory. This observation leads to an efficient randomized algorithm for testing both local and global unique completion. Crucial to our analysis is a new matrix, which we call the completion matrix, that serves as the analogue of the rigidity matrix.
Cucuringu Mihai
Singer Amit
No associations
LandOfFree
Uniqueness of Low-Rank Matrix Completion by Rigidity Theory does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Uniqueness of Low-Rank Matrix Completion by Rigidity Theory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Uniqueness of Low-Rank Matrix Completion by Rigidity Theory will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-584009