3
$\begingroup$

I've been working on trying to perform dimensionality reduction on high-dimensional, high-volume datasets (with many rows and columns - around 100,000 - 1M rows and ~500 columns).

While the size of my dataset (m being the # of rows and n being the # of columns) doesn't prevent PCA from applying, PCA can take a fair bit of time to train and transform the data.

I was wondering whether splitting up the dataset into x batches (each of equal size m/x rows) and then partially fitting the IncrementalPCA() against each of those x batches one after the other would be faster than trying to fit a traditional PCA() against the entire dataset of size m rows?

I believe the runtime of PCA is O(m * n2) + O(n3), so effectively IncrementalPCA in this case would simply be dividing the inner factor with m/x and multiplying both terms outside by x, therefore leading to a higher overall time complexity and slower performance, with overall x * O(m/x * n2) + x * O(n3) = O(m * n2) + x * O(n3). So, naively it seems that this idea would not work.

However, could someone provide more analysis on whether such a speedup using mini-batches with IncrementalPCA is nonetheless feasible? I suspect my reasoning may be incomplete.

An alternative approach I've been trying out as well is random stratified sampling, which seems more standard, but I'm trying to combine various optimizations for achieving faster runtimes.

$\endgroup$

1 Answer 1

1
$\begingroup$

Incremental PCA typically only reduces the memory footprint of the algorithm. So it's used when your full dataset doesn't fit into memory. The time complexity remains the same.

If you want to speed up the computation you can look into randomized matrix decompositions. Sklearn, for example, implements it with the keyword svd_solver='randomized' where you only approximate the singular values you will ultimately keep.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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