University of Minnesota
University Relations
myU OneStop

Go to unit's home.

Home | Seminars and Symposia | Past seminars/symposia: Thursday, October 16, 2014

DTC Seminar Series

Principal Component Analysis: offline, online, and distributed


Christos Boutsidis
Yahoo Labs
New York, NY

Thursday, October 16, 2014
5:00 p.m. reception
5:30 p.m. seminar

401/402 Walter Library

We will discuss the foundations as well as some applications of the well known Principal Component Analysis (PCA) technique.

First, we review PCA in the standard model: for a set of high dimensional vectors x_1, x_2,...,x_n, PCA finds a set of low dimensional vectors y_1, y_2,...,y_n via computing the Singular Value Decomposition (SVD) of the matrix X containing x_1, x_2,...,x_n in its columns.

Then, we discuss two different models of computation for PCA:

  1. Online PCA: where, for every presented input vector x_i the algorithm must return the low dimensional vector y_i before receiving the next input vector x_{i+1}.
  2. Distributed PCA: where, the vectors x_1, x_2,...,x_n are distributed among different machines and one wants to compute the PCA and minimize the communication cost.

We present novel, provably correct, PCA algorithms for the above two models of computation that find "approximate" low dimensional vectors y_1, y_2,...,y_n in polynomial time.


Christos Boutsidis is a Research Scientist at Yahoo Labs in New York, NY, where he belongs to the Scalable Machine Learning group. Before that he was a Research Staff Member at the Business Analytics and Mathematical Sciences Department of the IBM T. J. Watson Research Center in Yorktown Heights, NY. Dr. Boutsidis earned a Ph.D. in Computer Science from Rensselaer Polytechnic Institute in May of 2011 and a BS in Computer Engineering and Informatics from the University of Patras, Greece in July of 2006. Dr Boutsidis's research interests lie in the design and analysis of fast approximation algorithms for matrix computations and applications of those to machine learning and data analysis problems. Dr. Boutsidis has published over 25 articles in conferences and journals in numerical linear algebra, theoretical computer science, and statistical data analysis.