Revisiting the Principal Component Analysis: New Insights and Algorithms

Abstract:

This talk consists of two parts. In the first part, we discuss an alternative formulation of the principal component analysis (PCA)using determinants and present the corresponding version of the Eckart-Young-Mirsky Theorem. This alternative formulation of PCA is known but not used in practice because it is not clear how to solve the underlying non-convex optimisation program. Our main contribution here is to show that this non-convex program has no spurious local optima; it therefore behaves like a convex program and is amenable toa variety of convex solvers. We apply a number of these solvers and find that it often provides a competitive alternative to the state of the art in computing principal components of data. These findings also pave the way for entirely new approaches to sparse PCA and nonnegative matrix factorization.

In the second part of the talk, we present MOSES, a streaming and memory-limited algorithm for PCA in scenarios where (high-dimensional)data is presented sequentially and limited storage is available. We study the performance of MOSES in a deterministic and then a stochastic setup similar to the spiked covariance model. We also find that MOSES empirically improves over the state of the art.

This is joint work with Raphael Hauser at Oxford University.

Biography:
Armin Eftekhari received his PhD from Colorado School of Mines in2015, under the supervision of Michael Wakin. Before joining the Alan Turing Institute as a Research Fellow in 2016, he was a Peter O'Donnell, Jr. Postdoctoral Fellow at the University of Texas at Austin.