BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Oja's algorithm for sparse PCA - Purnamrita Sarkar\, University of
  Texas\, Austin
DTSTART:20240607T130000Z
DTEND:20240607T140000Z
UID:TALK213475@talks.cam.ac.uk
CONTACT:Dr Sergio Bacallado
DESCRIPTION:Oja's algorithm for streaming Principal Component Analysis (PC
 A) for n data points in a d-dimensional space achieves the same sin-square
 d error as the offline algorithm in O(d) space and O(nd) time and a single
  pass through the data points.  Under this computational budget\, we consi
 der the problem of sparse PCA\, where the principal eigenvector of the pop
 ulation covariance matrix Sigma is s-sparse\, and the effective rank of Si
 gma can be large. In this setting\, to our knowledge\, there are no known 
 single-pass algorithms that achieve the minimax error bound in O(d) space 
 and O(nd) time without either requiring strong initialisation conditions o
 r assuming further structure (e.g.\, spiked) of the covariance matrix. We 
 show that a simple single-pass procedure that thresholds the output of Oja
 's algorithm (the Oja vector) can achieve the minimax error bound under so
 me regularity conditions in the aforementioned computational budget.\n\nOu
 r results are centred around a nontrivial and novel analysis of the entrie
 s of the unnormalised Oja vector\, which involves projecting a product of 
 independent random matrices on a random initial vector. This is completely
  different from previous analyses of Oja's algorithm and matrix products\,
  which have been done when the effective rank is relatively small or bound
 ed. \n\nThis is joint work with Syamantak Kumar.
LOCATION:MR12\, Centre for Mathematical Sciences
END:VEVENT
END:VCALENDAR