Generalization Error Bounds for Collaborative Prediction with Low-Rank Matrices
Nathan Srebro, Noga Alon, Tommi Jaakkola · 2004
We prove generalization error bounds for predicting entries in a partially observed matrix by approximating the observed entries with a low-rank matrix. To do so, we bound the number of sign configurations of lowrank matrices using a result about realizable oriented matroids.