This will hopefully the last post in the matrix completion problems. But since the MBI inequality is widely used, I decided to squeeze in one more application of Community Detection problem in this as well (yay!) in the future post. So first the matrix completion. problem, we will see how a simple algorithm can yield exact results. To that end, since the problem as stated is ill posed, we will first make some assumptions on the matrix that we are completing, namely, the low rank assumption (we will discuss the case where the matrix we are completing is square).
Assume be a random matrix with . The algorithm to completing the missing entries is as follows: 1. Set the entries that are missing to be ; 2. Compute the best low rank approximation for . Then we can prove the following theorem.
Theorem: Assuming that the entries are missing at random observed with probability , we can show that where is the best rank approximation of, observed entries and , , fill the unknown entries with . In essence, matrix completion works if we observe entries.
Proof: 1. , here note that the first term is always less than (or equal to) the second term since is the best possible matrix. So we have that,
. Here is the matrix with entries, independent with mean . Hence by observing the fact that . This further implies that .
2. Now operator norm can be easily bounded since . So we have that , dividing both the sides gives us the result.
The proof as of now just consists of equations and math, I’ll try to add more explanations soon.