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?
 A: 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
A: 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.
