Abstract
This paper studies the following question: where should an adversary place an outlier of a given magnitude in order to maximize the error of the subspace estimated by PCA? We give the exact location of this worst possible outlier, and the exact expression of the maximum possible error. Equivalently, we determine the information-theoretic bounds on how much an outlier can tilt a subspace in its direction. This in turn provides universal (worst-case) error bounds for PCA under arbitrary noisy settings. Our results also have several implications on adaptive PCA, online PCA, and rank-one updates. We illustrate our results with a subspace tracking experiment
This was my first real technical contribution to mathematics or theoretical computer science. I spent months on the proof of the base case, it never made it to the final version of the paper. Daniel wrote a significantly cleaner and simpler base case proof -- giving me my first lesson on how to write a proper technical document.