Paper ID: 901 Title: Matrix Completion From any Given Set of Observations
Reviews

Submitted by Assigned_Reviewer_4

Q1: Comments to author(s). First provide a summary of the paper, and then address the following criteria: Quality, clarity, originality and significance. (For detailed reviewing guidelines, see http://nips.cc/PaperInformation/ReviewerInstructions)
Existing bounds for matrix completion from the trace and \gamma_2 norms require that the observed sample positions be chosen either randomly or from a specific deterministic strategy. This paper, in contrast, considers the matrix completion problem when the set of observed samples is arbitrary. A bound is derived on the error of the reconstructed unobserved entries in terms of a probability distribution over those entries which must satisfy certain conditions, and the error bound improves with the complexity of the observed sample set. The probability distribution involved in the bound can be optimized in order to provide the tightest reconstruction guarantee.

Quality: This paper considers an important problem and derives a novel bound that applies to matrix reconstruction using any norm that satisfies a certain property (including the trace and \ell_2 norms). The bounds in this paper can be somewhat difficult to interpret at first glance, but the author(s) do a satisfactory job in helping the reader interpret the results. The fact that the probability distribution involved in the bound can be optimized is a plus.

Clarity: This paper is clearly written, and the proof of the main result is surprisingly concise.

Originality: Existing bounds for matrix completion from the trace and \gamma_2 norms require that the observed sample positions be chosen either randomly or from a specific deterministic strategy. This paper is original in allowing the sample positions to be chosen arbitrarily.

Significance: Extending the literature on matrix completion guarantees to allow for arbitrary sample positions is a significant contribution. The bounds themselves in this paper can be somewhat difficult to interpret, and it is conceivable that other researchers may derive bounds of different flavors in the future. However, this paper seems like a strong first step in a new direction.

Some minor comments: Line 045: Figure 3 should be Figure 1? Line 070-071: missing a minus sign in exponent? Line 100: do the author(s) really do anything to "enhance" Alg1 in this paper? Line 185: the result depends on \gamma_2(Y). Could the author(s) mention whether it is possible to relate this to \gamma_2(X)? Line 195: should \lambda be \Lambda? Lines 211-213 and 235-238: sometimes symbols are lowercase, sometimes uppercase. Is this intentional?

UPDATE: Thanks to the authors for their notes in the rebuttal period.
This paper provides bounds on matrix completion when the set of observed samples is arbitrary. The bounds themselves in this paper can be somewhat difficult to interpret, but this paper seems like a strong first step in a new direction.

Submitted by Assigned_Reviewer_5

Q1: Comments to author(s). First provide a summary of the paper, and then address the following criteria: Quality, clarity, originality and significance. (For detailed reviewing guidelines, see http://nips.cc/PaperInformation/ReviewerInstructions)
The authors provide a novel norm minimization algorithm for low-rank matrix completion for a fixed, deterministic set of observed entries, Alg2, which can be seen as a generalization of trace norm minimization. They prove reconstruction guarantees in the noise-free case for arbitrary norms, including the popular trace norm, which describe the reconstruction error in terms of the complexity of the set of observed entries.

The paper is well-written with minor typos (mostly, formatting such as the single section 3.1, or line breaks in weird places), and the results appear to be correct.

The results are novel and original; they seem to provide a break-through in the understanding of matrix completion. Since any assumption that the positions of the observations are random of special kind (e.g., Bernoulli, uniform) are a-posteriori uncheckable, algorithms and theoretical guarantees for fixed sets of observations are the only way of taking the structure of the given observations into account.

While the theoretical results are in my opinion very nice and strong enough to stand for themselves, the paper does not validate Alg2 on synthetic or real data, nor does it relate the bounds to known sampling scenarios (e.g. the Candès/Tao results). Therefore it is not easy to judge the impact and the effectivity of the results.
A paper providing a novel and original algorithm for low-rank matrix completion with exact reconstruction guarantees for any fixed set of observations, likely to have seminal impact.

Submitted by Assigned_Reviewer_6

Q1: Comments to author(s). First provide a summary of the paper, and then address the following criteria: Quality, clarity, originality and significance. (For detailed reviewing guidelines, see http://nips.cc/PaperInformation/ReviewerInstructions)
Summary:
The paper discusses bounds on matrix completion problem under the assumption that the entries of the matrix are no necessarily sampled at random. This is done by optimizing the probability distributions on pairs of entries and using that to compute the error bounds according to complexity of the observed entries. The authors show that these results can be extended to other standard matrix norms.