Random projection

In mathematics and statistics, random projection is a technique used to reduce the dimensionality of a set of points which lie in Euclidean space. Random projection methods are powerful methods known for their simplicity and less erroneous output compared with other methods. According to experimental results, random projection preserve distances well, but empirical results are sparse. They have been applied to many natural language tasks under the name of random indexing.

Dimensionality reduction, as the name suggests, is reducing the number of random variables using various mathematical methods from statistics and machine learning. Dimensionality reduction is often used to reduce the problem of managing and manipulating large data sets. Dimensionality reduction techniques generally use linear transformations in determining the intrinsic dimensionality of the manifold as well as extracting its principal directions. For this purpose there are various related techniques, including: principal component analysis, linear discriminant analysis, canonical correlation analysis, discrete cosine transform, random projection, etc.

Random projection is a simple and computationally efficient way to reduce the dimensionality of data by trading a controlled amount of error for faster processing times and smaller model sizes. The dimensions and distribution of random projection matrices are controlled so as to approximately preserve the pairwise distances between any two samples of the dataset.

The core idea behind random projection is given in the Johnson-Lindenstrauss lemma, which states that if points in a vector space are of sufficiently high dimension, then they may be projected into a suitable lower-dimensional space in a way which approximately preserves the distances between the points.

In random projection, the original d-dimensional data is projected to a k-dimensional (k << d) subspace, using a random ${\displaystyle k\times d}$ - dimensional matrix R whose rows have unit lengths. Using matrix notation: If ${\displaystyle X_{d\times N}}$ is the original set of N d-dimensional observations, then ${\displaystyle X_{k\times N}^{RP}=R_{k\times d}X_{d\times N}}$ is the projection of the data onto a lower k-dimensional subspace. Random projection is computationally simple: form the random matrix "R" and project the ${\displaystyle d\times N}$ data matrix X onto K dimensions of order ${\displaystyle O(dkN)}$. If the data matrix X is sparse with about c nonzero entries per column, then the complexity of this operation is of order ${\displaystyle O(ckN)}$.

...
Wikipedia