PCA By Determinant Optimization Has No Spurious Local Optima

Authors:
Raphael Hauser University of Oxford
Armin Eftekhari Alan Turing Institute
Heinrich Matzinger Georgia Institute of Technology

Introduction:

This paper studies Principal Component Analysis (PCA) .Classically, principal components of a dataset are interpreted as the directions that preserve most of its “energy”.In this paper, the authors consider one such interpretation of principal components as the directions that preserve most of the “volume” of the dataset.

Abstract:

Principal Component Analysis (PCA) finds the best linear representation for data and is an indispensable tool in many learning tasks. Classically, principal components of a dataset are interpreted as the directions that preserve most of its “energy”, an interpretation that is theoretically underpinned by the celebrated Eckart-Young-Mirsky Theorem. There are yet other ways of interpreting PCA that are rarely exploited in practice, largely because it is not known how to reliably solve the corresponding non-convex optimisation programs. In this paper, we consider one such interpretation of principal components as the directions that preserve most of the “volume” of the dataset. Our main contribution is a theorem that shows that the corresponding non-convex program has no spurious local optima, and is therefore amenable to many convex solvers. We also confirm our findings numerically.

You may want to know: