Timezone: »

 
Poster
Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA
Ilias Diakonikolas · Daniel Kane · Ankit Pensia · Thanasis Pittas

Tue Jul 25 05:00 PM -- 06:30 PM (PDT) @ Exhibit Hall 1 #610
in Poster Session 2 »
We study principal component analysis (PCA), where given a dataset in $\mathbb R^d$ from a distribution, the task is to find a unit vector $v$ that approximately maximizes the variance of the distribution after being projected along $v$. Despite being a classical task, standard estimators fail drastically if the data contains even a small fraction of outliers, motivating the problem of robust PCA. Recent work has developed computationally-efficient algorithms for robust PCA that either take super-linear time or have sub-optimal error guarantees. Our main contribution is to develop a nearly linear time algorithm for robust PCA with near-optimal error guarantees. We also develop a single-pass streaming algorithm for robust PCA with memory usage nearly-linear in the dimension.
[ PDF] 

Author Information

Ilias Diakonikolas (University of Wisconsin-Madison)
Ilias Diakonikolas

Ilias Diakonikolas is a faculty member in the CS Department at UW Madison. He obtained a Diploma in electrical and computer engineering from the National Technical University of Athens and a Ph.D. in computer science from Columbia University. Before moving to UW, Ilias was Andrew and Erna Viterbi Early Career Chair at USC, and prior to that he spent two years at UC Berkeley as a Simons fellow in theoretical computer science. His research focuses on designing efficient algorithms for various fundamental problems in machine learning. Ilias is a recipient of a Sloan Fellowship, an NSF CAREER Award, a Google Faculty Research Award, a Marie Curie Fellowship, the best paper award at NeurIPS 2019, the IBM Research Pat Goldberg best paper award, and an honorable mention in the George Nicholson competition from the INFORMS society.

Daniel Kane (UCSD)
Ankit Pensia (University of Wisconsin-Madison)
Thanasis Pittas (University of Wisconsin-Madison)

More from the Same Authors