Matrix Completion From any Given Set of Observations
In the matrix completion problem the aim is to recover an unknown real matrix from a subset of its entries. This problem comes up in many application areas, and has received a great deal of attention in the context of the netflix prize. A central approach to this problem is to output a matrix of lowest possible complexity (e.g. rank or trace norm) that agrees with the partially specified matrix. The performance of this approach under the assumption that the revealed entries are sampled randomly has received considerable attention (e.g. [1,2,3,4,5,6,7,8]). In practice, often the set of revealed entries is not chosen at random and these results do not apply. We are therefore left with no guarantees on the performance of the algorithm we are using. We present a means to obtain performance guarantees with respect to any set of initial observations. The first step remains the same: find a matrix of lowest possible complexity that agrees with the partially specified matrix. We give a new way to interpret the output of this algorithm by next finding a probability distribution over the non-revealed entries with respect to which a bound on the generalization error can be proven. The more complex the set of revealed entries according to a certain measure, the better the bound on the generalization error.
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.