A recent result by Liberty (2013) gives a deterministic matrix sketching algorithm that tightly preserves the covariance structure needed for PCA.
given a sketch size l, the algorithm computes Y ∈ R l×d such that This result guarantees that the error decreases in O(1/l); in contrast, other approximation techniques have a significantly worse convergence bound of O(1/ √ l).