BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Matrix Completion from Fewer Entries
DTSTART:20090625T141500
DTSTAMP:20260408T071001Z
UID:d0473903d8ca8276280a9882a07051cc5db34c82e49fa591ae5c4884
CATEGORIES:Conferences - Seminars
DESCRIPTION:Andrea Montanari\, Stanford University\nLow-rank models are fr
 equently used in machine learning and statistics. An important domain of a
 pplication is provided by collaborative filtering\, whereby a low-rank mat
 rix describes the ratings that a large set of users attribute to a large s
 et of products. The problem is in this case to predict future ratings from
  a sparse subset currently available. The dataset released for the Netflix
  challenge provides an ideal testbed for theory and algorithms for learnin
 g low-rank matrices. Given M\, a random n x n matrix of rank r\, we assume
  that a uniformly random subset E of its entries is observed. We describe 
 an efficient procedure that reconstructs M from |E| = O(rn) observed entri
 es with arbitrarily small root mean square error\, whenever M is satisfies
  an appropriate incoherence condition. If r = O(1)\, the algorithm reconst
 ructs M exactly from O(n log n) entries. This settles a recent open proble
 m by Candes and Recht. In the process of proving these statements\, we obt
 ain a generalization of a celebrated result by Friedman-Kahn-Szemeredi and
  Feige-Ofek on the spectrum of sparse random matrices. [Based on joint wor
 k with R. H. Keshavan and S. Oh] \nProf. Montanari's homepage
LOCATION:BC 01 https://plan.epfl.ch/?room==BC%2001
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR