text: We consider the problem of reconstructing a low rank matrix from noisy observations of a subset of its entries. This task has applications in statistical learning, computer vision, and signal processing. In these contexts, "noise" generically refers to any contribution to the data that is not captured by the low-rank model. In most applications, the noise level is large compared to the underlying signal and it is important to avoid overfitting. In order to tackle this problem, we define a regularized cost function well suited for spectral reconstruction methods. Within a random noise model, and in the large system limit, we prove that the resulting accuracy undergoes a phase transition depending on the noise level and on the fraction of observed entries. The cost function can be minimized using OPTSPACE (a manifold gradient descent algorithm). Numerical simulations show that this approach is competitive with state-of-the-art alternatives.
  @cite_0: We present a novel approach to collaborative prediction, using low-norm instead of low-rank factorizations. The approach is inspired by, and has strong connections to, large-margin linear discrimination. We show how to learn low-norm factorizations by solving a semi-definite program, and discuss generalization error bounds for them.
  @cite_9: Maximum Margin Matrix Factorization (MMMF) was recently suggested (, 2005) as a convex, infinite dimensional alternative to low-rank approximations and standard factor models. MMMF can be formulated as a semi-definite programming (SDP) and learned using standard SDP solvers. However, current SDP solvers can only handle MMMF problems on matrices of dimensionality up to a few hundred. Here, we investigate a direct gradient-based optimization method for MMMF and demonstrate it on large collaborative prediction problems. We compare against results obtained by Marlin (2004) and find that MMMF substantially outperforms all nine methods he tested.
  @cite_2: 
summary: The importance of regularization in matrix completion is well known to practitioners. For instance, one important component of many algorithms competing for the Netflix challenge @cite_2 , consisted in minimizing the cost function @math (this is also known as @cite_0 @cite_9 ). Here the minimization variables are @math , @math . Unlike in , these matrices are not constrained to be orthogonal, and as a consequence the problem becomes significantly more degenerate. Notice that, in our approach, the orthogonality constraint fixes the norms @math , @math . This motivates the use of @math as a regularization term.