In this paper we propose a new algorithm for streaming principal component analysis. With limited memory, small devices cannot store all the samples in the high-dimensional regime. Streaming principal component analysis aims to find the @math -dimensional subspace which can explain the most variation of the @math -dimensional data points that come into memory sequentially. In order to deal with large @math and large @math (number of samples), most streaming PCA algorithms update the current model using only the incoming sample and then dump the information right away to save memory. However the information contained in previously streamed data could be useful. Motivated by this idea, we develop a new streaming PCA algorithm called History PCA that achieves this goal. By using @math memory with @math being the block size, our algorithm converges much faster than existing streaming PCA algorithms. By changing the number of inner iterations, the memory usage can be further reduced to @math while maintaining a comparable convergence speed. We provide theoretical guarantees for the convergence of our algorithm along with the rate of convergence. We also demonstrate on synthetic and real world data sets that our algorithm compares favorably with other state-of-the-art streaming PCA methods in terms of the convergence speed and performance.
This is a tutorial on some basic non-asymptotic methods and concepts in random matrix theory. The reader will learn several tools for the analysis of the extreme singular values of random matrices with independent rows or columns. Many of these methods sprung off from the development of geometric functional analysis since the 1970's. They have applications in several fields, most notably in theoretical computer science, statistics and signal processing. A few basic applications are covered in this text, particularly for the problem of estimating covariance matrices in statistics and for validating probabilistic constructions of measurement matrices in compressed sensing. These notes are written particularly for graduate students and beginning researchers in different areas, including functional analysts, probabilists, theoretical statisticians, electrical engineers, and theoretical computer scientists. Let K be an isotropic convex body in Rn. Given e > 0, how many independent points Xi uniformly distributed on K are neededfor the empirical covariance matrix to approximate the identity up to e with overwhelming probability? Our paper answers this question from [12]. More precisely, let X ∈ Rn be a centered random vector with a log-concave distribution and with the identity as covariance matrix. An example of such a vector X is a random point in an isotropic convex body. We show that for any e > 0, there existsC(e) > 0, suﰁch that if N ∼ C(e)n and (Xi)i≤N are i.i.d. copies of ﱞﱞ1 N ﱞﱞ X, then ﱞN i=1 Xi ⊗ Xi − Idﱞ ≤ e, with probability larger than 1 − exp(−c√n).