10
$\begingroup$

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?

$\endgroup$
  • 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$ – amoeba says Reinstate Monica Jul 31 '15 at 15:09
  • 1
    $\begingroup$ @amoeba: I'm looking at 500K samples (rows) and 300K features (columns) $\endgroup$ – Roy Aug 2 '15 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$ – Tim Jun 30 '18 at 7:15
11
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.