arXiv (Cornell University) · 2009 · 206 citations · 22 references
ComputingComputer ScienceAlgorithmsMachine LearningOptimizationApproximation AlgorithmsCollaborative FilteringDimension ReductionDimensionality ReductionMatrix ComputationMatrix FactorizationLow-rank ApproximationLow-rank OptimizationLow-rank ReconstructionMatrix CompletionSparse Matrix AlgorithmsSparse Matrix Techniques
Given a matrix M of low-rank, we consider the problem of reconstructing it from noisy observations of a small, random subset of its entries. The problem arises in a variety of applications, from collaborative filtering (the `Netflix problem') to structure-from-motion and positioning. We study a low complexity algorithm introduced by Keshavan et al.(2009), based on a combination of spectral techniques and manifold optimization, that we call here OptSpace. We prove performance guarantees that are order-optimal in a number of circumstances.
22
Probabilistic Matrix Factorization
Andriy Mnih, Ruslan Salakhutdinov · Neural Information Processing Systems · 2007 · 3.6K citations
Restricted Boltzmann machines for collaborative filtering
Ruslan Salakhutdinov, Andriy Mnih, Geoffrey E. Hinton · 2007 · 1.9K citations