4
$\begingroup$

I have $10^8$ vectors in $1000$ dimensions each. I would like to drastically reduce their dimensions. However PCA seems computationally infeasible. Are there near linear time methods to do dimensionality reduction?

$\endgroup$
  • $\begingroup$ Here is a constant time method: discard all but 10000 vectors. Seriously, is there any need for so many data sets? Where do they arise from, what is their content (real, integer, boolean,...), what is your goal? $\endgroup$ – davidhigh Jul 4 '14 at 22:46
  • $\begingroup$ @davidhigh - If he doesn't know his data then throwing away 99.99% of the samples is no better than throwing away 100%. Entropy is what resists compression - structure what enables it. Without knowing the nature of the internal structure or the nature of noise sources the compression is going to be hard. $\endgroup$ – EngrStudent - Reinstate Monica Jul 8 '14 at 10:35
  • $\begingroup$ @felix - when you zip your ~745 GB file, how small does it become. Do you get 30% compression or 99% compression? $\endgroup$ – EngrStudent - Reinstate Monica Jul 8 '14 at 10:37
  • $\begingroup$ @EngrStudent: the comment was not meant all too seriously, see my answer below. It shows that a full singular value decomposition possibly might be feasible due to the relatively small second dimension. If not, you can try an online SVD (maybe with random data access) and hope for early convergence ... I guess it will converge early if the points you mentioned are satisfied. $\endgroup$ – davidhigh Jul 8 '14 at 11:03
3
$\begingroup$

The answer heavily depends on the application and goals you want to achieve with the data. Until you state these more clearly, I'll try for a rather general answer.

First, as the column dimension is only 1000, the computation seems not completely infeasible. A main issue is that you cannot store the matrix in memory, so standard (dense) SVD solver won't work. However, you can use the following algorithm for the SVD of the matrix $\mathbf A = \mathbf U^T \mathbf S \mathbf V$:

First, compute the eigenvalues of $\mathbf A^T \mathbf A = \mathbf V^T \mathbf S^2 \mathbf V$. This corresponds to an eigenvalue problem of a matrix of dimension 1000. Next, evaluate $\mathbf U = \mathbf A \mathbf V \mathbf S^{-1}$.

Alternatively, you can also use an online SVD algorithm, see here for example, which brings similar computational advantages as the matrix need not be stored in memory.

EDIT: corrected link

$\endgroup$
1
$\begingroup$

You have 10^11 numbers. That is huge. At double precision that is 6.4e12 bits or about 745 GB. Likely this will spend the majority of its life in swap or on a hard drive. If it is entirely in RAM, then you likely have a supercomputer. Nice computer there.

Lets say you have low entropy data. Though there are lot of options for unique values in a double precision number, lets say that you don't use many of them. If you were to take each vector and make an empirical cdf, how many unique elements would it have? With some clever rounding you can often reduce the number by several orders of magnitude. If you do this for the 1000 vectors, then you can do histogram-informed subsampling and get informative subsample of elements that is on the order of 1e6 elements. With that reduced set you can find the centroid and variance for your scale-detrend preprocess of PCA. You can then perform a PCA on them, and determine the eigenvectors of relevance. If you have say ... less than 1000 eigenvectors of relevance (sometimes 10 gets you what you want) then you can index each value of the original set as a linear sum of eigenvectors - remap it as the weight of eigenvectors that most nearly reconstructs it. If it was 10 eigenvectors then you have reduced your space from 1000 dimensions to 10 (or whatever).

Best of luck.

$\endgroup$
  • $\begingroup$ You do realise you can fit 745 GB on a 60 dollar hard drive these days? :) $\endgroup$ – felix Jul 6 '14 at 7:50
  • $\begingroup$ If you try to buy that in RAM, then you need a special motherboard. Most PC's do 16Gb. eurocom.com/ec/configure(1,234,0)ec The "supercomputer laptop" only has 32 GB. How many computers do you know of with 745 Gb in RAM? $\endgroup$ – EngrStudent - Reinstate Monica Jul 6 '14 at 22:10
  • 1
    $\begingroup$ Right, you can't store it all in RAM at once. So you have to be cleverer about how you process it. $\endgroup$ – felix Jul 7 '14 at 21:41

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.