Paper ID: | 521 |
---|---|

Title: | A New Theory for Matrix Completion |

The authors study matrix completion from a few entries. They propose a new
proprty of (matrix,sampling pattern) which they term "Isomery". They show that
the well known (incoherence,low rank,random sampling) assumption implies this
condition. The authors then consider a nonconvex bilinear program for matrix
completion. Under the Isomery assumption, they prove that the exact solution is
a critical point of this program (with no assumptions on rank, it seems). Some
empirical evidence are presented, whereby the nonconvex program is superior to
the convex Nuclear Norm minimization method for a certain pattern of nonuniform
sampling.
The paper is relatively well written (see comments on English below). The
results are novel as far as I can tell, and interesting. This work touches on
fundamental aspects of matrix recovery, and can certainly lead to new research.
There are a few major comments I'd be happy to see addressed. That said, I vote
accept.
Major comments:
1. The authors say nothing about the natural questions: Can the Isometry
condition be verified in practice? Is it a reasonable assumption to make?
2. The authors discuss in the introduction reasons why random sampling may not
be a reasonable assumption, with some real data examples. It would be nice if,
for a real full data matrix, and a sampling pattern of the kind shown, the
authors can verify the Isomry assumption.
3. The matrix recovery problem, as well as all the algorithms discussed in this
paper, are invariant under row and col permutations. The authors discuss
sampling patterns which are "concentrated around the main diagonal" - this
condition is not invariant under permutations. Only invariant conditions make
sense.
4. The main contributions claimed (l.79) are not backed up by the paper itself.
Specifically,
- it's unclear what is meant by "our theories are more flexible and
powerful"
- the second bullet point in the main contribution list (l.83) referes
to "nonconvex programs" in general
- The third bullet point (l.87) is not actuallty proved, and should not be
advertised as a main contribution. The authors
proved Theorem 3.1, but its connection to matrix completion is only vageuly described
in the paragraph above Theorem 3.1.
minor comments:
- English throughout
- Theorem 3.2: formally define "with high probability"
- The word "theory" and "theories" in the title and throughout: I'm a non-native English speaker, yet I don't see
why you use the word.
- l.56: "incoherent assumption" -> "incoherence assumption"
- l.75 "by the commonly used" -> "of the commonly used"
- l.79 "hypothesis" -> condition
- l.92, l.129 "proof processes" -> "proofs"
- l.188 "where it denotes" -> "where we denote"
- l.208 "that" -??
- Eq. (8) and Eq. (9) - maybe missing =0 on the right hand side?
- Figure 2: label vertical axis
- what do you mean by "proof of theory" (eg line 92)?