Principal component analysis' (PCA) classical way is to do it on an input data matrix which columns have zero mean (then PCA can "maximize variance"). This can be achieved easily by centering the columns. Howenver, when the input matrix is sparse, the centered matrix will now longer be sparse, and - if the matrix is very big - will thus not fit into memory anymore. Is there an algorithmic solution for the storage problem?
$\begingroup$
$\endgroup$
3
-
5$\begingroup$ Even if full data matrix does not fit into memory, it can very well be that either covariance or the Gram matrix fits into memory. Those are enough to perform PCA. What size of the input data matrix are you thinking about? See also stats.stackexchange.com/questions/35185. $\endgroup$– amoebaCommented Jul 31, 2015 at 15:09
-
1$\begingroup$ @amoeba: I'm looking at 500K samples (rows) and 300K features (columns) $\endgroup$– RoyCommented Aug 2, 2015 at 12:03
-
$\begingroup$ As about software, Apache Spark has it spark.apache.org/docs/latest/… for sure the implementation deals with out-of-memory data $\endgroup$– TimCommented Jun 30, 2018 at 7:15
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Yes, it is possible.
If the data matrix does not fit into RAM, it is not the end of the world yet: there are efficient algorithms that can work with data stored on a hard drive. See e.g. randomized PCA as described in Halko et al., 2010, An algorithm for the principal component analysis of large data sets.
In Section 6.2 the authors mention that they tried their algorithm on 400k times 100k data matrix and that
The algorithm of the present paper required 12.3 hours to process all 150 GB of this data set stored on disk, using the laptop computer with 1.5 GB of RAM [...].
Note that this was in the old days of magnetic hard drives; today there are much faster solid state drives available, so I guess the same algorithm would perform considerably faster.
See also this old thread for more discussion of randomized PCA: Best PCA algorithm for huge number of features (>10K)? and this large 2011 review by Halko et al.: Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions.
