Online {PCA} with Spectral Bounds
Zohar S. Karnin, Edo Liberty · 2015
This paper revisits the online PCA problem. Given a stream of n vectors xt ∈ Rd (columns of X) the algorithm must output yt ∈ R ` (columns of Y) before receiving xt+1. The goal of online PCA is to simultaneously minimize the target dimension ` and the error ‖X − (XY +)Y ‖2. We describe two simple and deterministic algorithms. The first, receives a parameter ∆ and guaranties that ‖X − (XY +)Y ‖2 is not significantly larger than ∆. It requires a target dimension of ` = O(k/ε) for any k, ε such that ∆ ≥ εσ21 +σ2k+1. The second receives k and ε and guaranties that ‖X − (XY +)Y ‖2 ≤ εσ21 + σ2k+1. It requires a target dimension of O(k logn/ε2). Different models and algorithms for Online PCA were considered in the past. This is the first that achieves a bound on the spectral norm of the residual matrix.