# How to reduce the dimension of $10^8$ vectors

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?

• 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? – davidhigh Jul 4 '14 at 22:46
• @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. – EngrStudent Jul 8 '14 at 10:35
• @felix - when you zip your ~745 GB file, how small does it become. Do you get 30% compression or 99% compression? – EngrStudent Jul 8 '14 at 10:37
• @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. – davidhigh Jul 8 '14 at 11:03

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.