Error-Minimizing Estimates and Universal Entry-Wise Error Bounds for Low-Rank Matrix Completion
We propose a general framework for reconstructing and denoising single entries of incomplete and noisy entries. We describe: effective algorithms for deciding if and entry can be reconstructed and, if so, for reconstructing and denoising it; and a priori bounds on the error of each entry, individually. In the noiseless case our algorithm is exact. For rank-one matrices, the new algorithm is fast, admits a highly-parallel implementation, and produces an error minimizing estimate that is qualitatively close to our theoretical and the state-of-the-art Nuclear Norm and OptSpace methods.
The paper studies the noisy matrix completion problem, 
      focusing on entry-wise error guarantees. Via algebraic connections, they 
      derive an algorithm for computing the minimum variance unbiased estimator 
      for any missing entry. They also provide an explicit expression for the 
      minimum variance, show how these results can be extended to higher rank 
      matrices, and show promising comparisons with state-of-the-art matrix 
      completion algorithms. The paper is inspired by a recent paper on 
      noiseless matrix completion, which shows that the set of entries 
      recoverable depends only on the mask and in the rank-one case, this 
      dependence is made explicit by the connectivity properties of the 
      bipartite graph induced by the mask. In the noiseless case, one can 
      recover entries by solving a system of polynomial equations defined by 
      paths in the bipartite graph. With the appropriate noise model (they use 
      multiplicatively-centered finite variance noise) this algebraic connection 
      suggests that a polynomial expression from any path between i,j in the 
      mask yields an unbiased estimator of the entry A_{ij}. Minimizing 
      the variance involves taking the appropriate linear combinations of the 
      polynomials defined by paths between i,j. To do this, the authors first 
      give an explicit expression for the variance depending only on the 
      coefficients, the graph itself, and the the variance of the entries of the 
      matrix (assumed to be known). Minimizing this expression leads to the 
      MVUE. For higher rank matrices, the polynomial equations aren't 
      given by paths and cycles but by higher-order subgraphs, but the same 
      arguments can be applied. The simulations conducted show how the 
      variance of individual entries depends on the structure of the mask and 
      also compare their estimation procedure with the nuclear norm minimization 
      and the OptSpace algorithm. In the latter, this approach is favorable in 
      the low noise regime, but their error estimates are useful independently 
      of algorithm choice. The paper presents a novel analysis of noisy 
      matrix completion and uses nice connections to algebraic combinatorics and 
      graph theory to arrive at interesting results about estimation. The paper 
      is well written and fairly easy to understand, addresses an interesting 
      problem with original techniques. Focusing on the rank-one case limits the 
      direct applicability of the work but at the same time it significantly 
      aids readability and extensions to higher rank settings seem easy enough 
      if one can construct a basis for the relevant "circuits." Another 
      potential weakness is the use of multiplicative noise rather than additive 
      noise, which is much more standard in the statistics community and the 
      existing works on matrix completion. It would be nice to give 
      frobenius norm error bounds under random sampling as a function of the 
      noise variance. I suspect this is not too challenging in the model 
      specified using results from random graph theory but it would be even 
      better if it could be done with additive noise, which would enable precise 
      comparisons with related matrix completion papers.