Back

Random projection in dimensionality reduction: applications to image and text data

Ella BinghamH. Mannila

article2001KDD1,589 citations

Demonstrates through empirical evaluations on image processing and text retrieval that random projection preserves pairwise vector similarities comparably to principal component analysis while dramatically reducing computational cost, especially when using sparse projection matrices.

Listen

Modern data processing systems frequently encounter very high-dimensional data, such as high-resolution images and large text vocabularies. Traditional dimensionality reduction techniques like principal component analysis and singular value decomposition are statistically optimal for compressing this data, but they become computationally prohibitive as data volumes and dimensions grow. The article evaluates random projection—a technique that projects high-dimensional data into a lower-dimensional space using random matrices—as a practical, low-cost alternative for maintaining data relationships without burdensome calculations.

The authors conducted empirical experiments on two contrasting data types: 1,000 monochrome natural image windows and 2,262 text documents across four newsgroups with a 5,000-word vocabulary. The tests evaluated standard Gaussian random matrices and computationally simpler sparse random matrices against established methods like principal component analysis, singular value decomposition, discrete cosine transform, and median filtering across various target dimensions and noise levels.

The evaluation revealed several key findings. First, random projection preserved pairwise Euclidean distances in image data almost as well as principal component analysis, and it outperformed traditional techniques at very low target dimensions down to approximately 10 to 50 dimensions. Second, random projection was orders of magnitude faster and required significantly fewer computational operations than principal component analysis or singular value decomposition. Third, using a sparse random matrix achieved distance preservation comparable to Gaussian projections while enabling additional computational savings through integer arithmetic. Fourth, random projection proved resilient against impulse noise in images without blurring fine details, unlike standard median filtering. Finally, for text data, random projection maintained document similarities with minor error while avoiding the steep processing costs of singular value decomposition.

These findings indicate substantial performance and cost advantages for organizations managing large-scale, automated data pipelines. By replacing or preprocessing heavy matrix decompositions with random projections, technical teams can dramatically reduce processing timelines and hardware costs without meaningful loss of data fidelity. However, the technique is suitable specifically for distance-based automated tasks—such as machine vision change detection, clustering, or nearest-neighbor searches—and is not intended for human visual consumption, as reconstructed images exhibit noticeable visual distortion compared to standard compression techniques.

Organizations should consider adopting random projection or sparse random projection as a lightweight preprocessing step before applying heavier analytical workflows, especially for large document indexing and automated image surveillance. Future implementation decisions should incorporate pilot tests on specific downstream data mining tasks, such as clustering accuracy, and explore why empirical target dimensions perform well far below conservative theoretical thresholds. Decision-makers should maintain high confidence in the method for distance-preserving tasks, provided that inter-point distances in the raw data are inherently meaningful and dimensions are uniformly scaled.

Helsinki University of TechnologyLaboratory of Computer and Information ScienceNokia Research Centerdimensionality reduction methodhigh dimensionalityprincipal component analysis (pca)random projectiondimensionality reductionJohnson-Lindenstrauss lemma
Bingham et al (2001).pdf
Cover for Random projection in dimensionality reduction: applications to image and text data

Abstract

Random projections have recently emerged as a powerful method for dimensionality reduction. Theoretical results indicate that the method preserves distances quite nicely; however, empirical results are sparse. We present experimental results on using random projection as a dimensionality reduction tool in a number of cases, where the high dimensionality of the data would otherwise lead to burdensome computations. Our application areas are the processing of both noisy and noiseless images, and information retrieval in text documents. We show that projecting the data onto a random lower-dimensional subspace yields results comparable to conventional dimensionality reduction methods such as principal component analysis: the similarity of data vectors is preserved well under random projection. However, using random projections is computationally significantly less expensive than using, e.g., principal component analysis. We also show experimentally that using a sparse random matrix gives additional computational savings in random projection.

Topics

dimensionality reduction methodhigh dimensionalityprincipal component analysis (pca)random projectionstext datatext documenttheoretical resulttextual data

Keywords

random projectiondimensionality reductionJohnson-Lindenstrauss lemmaprincipal component analysislatent semantic indexingnearest-neighbor searchrandom mappinginformation retrievalhigh-dimensional datanoise reduction

Table of Contents

  • 1. INTRODUCTION
  • 1.1 Related work
  • 2. METHODS FOR DIMENSIONALITY REDUCTION
  • 2.1 Random projection
  • 2.2 PCA, SVD and LSI
  • 2.3 Discrete cosine transform
  • 3. RESULTS ON IMAGE DATA
  • 3.1 Noiseless image data
  • 3.2 Noise reduction in images
  • 4. RESULTS ON TEXT DATA
  • 5. CONCLUSIONS
  • 6. REFERENCES

Knowls

  1. Knowl 1 — Random Projection Linear Mapping and Scaled Distance Estimation

    model/method

    Random projection reduces the dimensionality of a data matrix X∈Rd×NX \in \mathbb{R}^{d \times N}, containing NN observations of dimension dd, to a target dimension k≪dk \ll d using a linear transformation:

    XRP=RXX^{RP} = R X

    where R∈Rk×dR \in \mathbb{R}^{k \times d} is a random matrix whose columns have unit Euclidean length.

    To approximate the Euclidean distance ∥x1−x2∥\|x_1 - x_2\| between two original vectors x1,x2∈Rdx_1, x_2 \in \mathbb{R}^d, the Euclidean distance in the reduced kk-dimensional space is multiplied by a scaling factor d/k\sqrt{d/k}:

    dist(x1,x2)≈dk∥Rx1−Rx2∥\text{dist}(x_1, x_2) \approx \sqrt{\frac{d}{k}} \|R x_1 - R x_2\|

    This factor compensates for the contraction of vector norms under projection, as the expected squared norm of the projection of a unit vector is k/dk/d.

    Although RR is generally not strictly orthogonal, vectors in high-dimensional spaces are almost orthogonal (RTR≈IR^T R \approx I). The mean squared difference between RTRR^T R and the identity matrix is approximately 1/k1/k per element. The computational complexity of generating RR and projecting XX is O(dkN)O(d k N) for dense data, and O(ckN)O(c k N) for sparse data having an average of cc non-zero entries per column.

  2. Knowl 2 — Sparse Random Projection Matrix Distribution

    model/method

    Instead of sampling entries from a continuous Gaussian distribution, the projection matrix R∈Rk×dR \in \mathbb{R}^{k \times d} can be constructed from independent and identically distributed discrete entries rijr_{ij} drawn from the sparse distribution:

    rij=3×{+1with probability 160with probability 23−1with probability 16r_{ij} = \sqrt{3} \times \begin{cases} +1 & \text{with probability } \frac{1}{6} \\ 0 & \text{with probability } \frac{2}{3} \\ -1 & \text{with probability } \frac{1}{6} \end{cases}

    This distribution has zero mean and unit variance, satisfying the Johnson-Lindenstrauss distance preservation properties while setting two-thirds of the entries to zero. This sparsity allows projections to be computed via integer additions and subtractions without floating-point multiplications, reducing computational overhead while achieving empirical distance preservation comparable to Gaussian random matrices.

  3. Knowl 3 — Experimental Setups for Image and Text Dimensionality Reduction

    experimental setup

    The empirical performance of random projection was evaluated across two benchmark datasets:

    1. Natural Scene Image Data: N=1000N = 1000 image patches of size 50×5050 \times 50 pixels (d=2500d = 2500 dimensions) randomly extracted from 13 monochrome natural scene images of size 256×256256 \times 256 pixels. Pixel brightness values follow an approximately bell-shaped Gaussian distribution. In a noisy test condition, salt-and-pepper impulse noise was added by setting each pixel to black or white with probability 0.20.2.

    2. Text Document Data: N=2262N = 2262 document vectors with a vocabulary size of d=5000d = 5000 terms drawn from four newsgroups of the 20 Newsgroups corpus (sci.crypt, sci.med, sci.space, and soc.religion.christian). Documents were converted to term frequency vectors using Rainbow toolkit (excluding common stop words, without stemming) and normalized to unit Euclidean length without mean centering or variance normalization. The text data is sparse, non-negative, and positively skewed.

  4. Knowl 4 — Pairwise Euclidean Distance Preservation on Image Data

    empirical result

    On natural scene image patches (d=2500d = 2500, N=1000N = 1000) across reduced dimensions k∈[1,800]k \in [1, 800], random projection using Gaussian matrices (RP) and sparse matrices (SRP) preserved pairwise Euclidean distances with accuracy comparable to Principal Component Analysis (PCA), evaluated over 100 random vector pairs with 95% confidence intervals:

    • At dimensions k>600k > 600, RP, SRP, and PCA all yield low distance approximation error, whereas the Discrete Cosine Transform (DCT) exhibits substantial distortion.
    • At small target dimensions (k<100k < 100 down to k=10k = 10), RP and SRP outperform both PCA and DCT. PCA error increases at low kk because it omits variance without rescaling, whereas RP maintains low error due to the d/k\sqrt{d/k} scaling factor.
    • Sparse random projection (SRP) and Gaussian random projection (RP) achieve virtually indistinguishable distance preservation across all tested dimensions kk.

  5. Knowl 5 — Computational Operation Costs of RP, SRP, PCA, and DCT

    empirical result

    Evaluation of floating-point operations across reduced dimensions k∈[1,800]k \in [1, 800] on natural scene image data (d=2500d = 2500) shows that:

    • Principal Component Analysis (PCA) is the most computationally expensive method, requiring 101110^{11} to 101210^{12} floating-point operations due to the eigenvalue decomposition of the d×dd \times d covariance matrix.
    • Gaussian Random Projection (RP) and Sparse Random Projection (SRP) require between 10710^7 and 10910^9 operations, which is 3 to 4 orders of magnitude lower than PCA.
    • Discrete Cosine Transform (DCT) applied to target data vectors requires 10610^6 to 10810^8 operations, but incurs substantially higher distance distortion than RP and SRP at moderate-to-high dimensions.

  6. Knowl 6 — Robustness of Random Projection to Impulse Noise in Images

    empirical result

    When natural scene image windows are corrupted with salt-and-pepper impulse noise (probability 0.20.2 per pixel) and projected to k∈[1,800]k \in [1, 800] dimensions, scaled Euclidean distances d/k∥Rx1−Rx2∥\sqrt{d/k}\|Rx_1 - Rx_2\| between noisy projected vectors closely approximate the distances between the corresponding original noiseless high-dimensional vectors.

    By contrast, standard 3×33 \times 3 median filtering on the noisy images introduces a large constant distance distortion relative to noiseless vectors (error of approximately −30-30) due to the blurring of fine structural details. Random projection remains insensitive to impulse noise and preserves underlying geometric distances without requiring explicit non-linear spatial filtering.

  7. Knowl 7 — Text Document Similarity Preservation under Random Projection vs SVD

    empirical result

    On text document vectors from the 20 Newsgroups dataset (d=5000d = 5000, N=2262N = 2262, normalized to unit Euclidean length), similarity preservation was evaluated as the difference between document inner products before and after dimensionality reduction across k∈[1,700]k \in [1, 700] over 100 document pairs:

    • Singular Value Decomposition (SVD / Latent Semantic Indexing) achieves lower inner product error than Gaussian random projection across all values of kk.
    • Random projection yields low average inner product error (within ±0.05\pm 0.05 across most kk), which is sufficient for information retrieval and query matching applications.
    • Computing SVD remains orders of magnitude more computationally expensive than RP even when using sparse numerical solvers.
    • RP can be applied as a fast pre-processing dimensionality reduction step before applying SVD/LSI, and does not require strictly orthogonal projection matrices.

  8. Knowl 8 — Empirical Target Dimensionality vs Johnson-Lindenstrauss Theoretical Bounds

    empirical result

    For natural scene image data with original dimension d=2500d = 2500, the theoretical lower bound on target dimension kk derived from worst-case proofs of the Johnson-Lindenstrauss lemma with distortion parameter ϵ=0.2\epsilon = 0.2 is:

    k≥1600k \ge 1600

    Empirical experiments show that target dimensions as low as k≈50k \approx 50 (and down to k=10k = 10) suffice to preserve pairwise Euclidean distances with negligible error. This indicates that real-world data distributions allow effective dimensionality reduction at target dimensions substantially lower than theoretical worst-case bounds suggest.

  9. Knowl 9 — Image Reconstruction via Transpose Inversion and Domain Scope

    limitation

    Because the random projection matrix R∈Rk×dR \in \mathbb{R}^{k \times d} is approximately orthogonal (RRT≈IR R^T \approx I), an image reduced to XRP=RXX^{RP} = R X can be approximately reconstructed in the original pixel space via the transpose:

    Xnew=RTXRPX^{\text{new}} = R^T X^{RP}

    However, the reconstructed image is visually degraded and noisy to the human eye compared to transform-based compression methods such as the Discrete Cosine Transform (DCT). Consequently, random projection is effective for automated machine vision, clustering, and similarity search where distance preservation is required, but is unsuitable for lossy image compression intended for human visualization.

Coverage note — No substantial contributed material was omitted from the extracted knowls.

References

  1. 1.D. Achlioptas. Database-friendly random projections. In Proc. ACM Symp. on the Principles of Database Systems, pages 274–281, 2001.
  2. 2.C. C. Aggarwal, J. L. Wolf, and P. S. Yu. A new method for similarity indexing of market basket data. In Proc. 1999 ACM SIGMOD Int. Conf. on Management of data, pages 407–418, 1999.
  3. 3.R. Agrawal, C. Faloutsos, and A. Swami. Efficient similarity search in sequence databases. In Proc. 4th Int. Conf. of Data Organization and Algorithms, pages 69–84. Springer, 1993.
  4. 4.R. I. Arriaga and S. Vempala. An algorithmic theory of learning: robust concepts and random projection. In Proc. 40th Annual Symp. on Foundations of Computer Science, pages 616–623. IEEE Computer Society Press, 1999.
  5. 5.M.-W. Berry. Large-scale sparse singular value computations. International Journal of Super-Computer Applications, 6(1):13–49, 1992.
  6. 6.S. Dasgupta. Learning mixtures of Gaussians. In 40th Annual IEEE Symp. on Foundations of Computer Science, pages 634–644, 1999.
  7. 7.S. Dasgupta. Experiments with random projection. In Proc. Uncertainty in Artificial Intelligence, 2000.
  8. 8.S. Dasgupta and A. Gupta. An elementary proof of the Johnson-Lindenstrauss lemma. Technical Report TR-99-006, International Computer Science Institute, Berkeley, California, USA, 1999.
  9. 9.S. Deerwester, S.T. Dumais, G.W. Furnas, and T.K. Landauer. Indexing by latent semantic analysis. Journal of the Am. Soc. for Information Science, 41(6):391–407, 1990.
  10. 10.P. Frankl and H. Maehara. The Johnson-Lindenstrauss lemma and the sphericity of some graphs. Journal of Combinatorial Theory, Ser. B, 44:355–362, 1988.
  11. 11.G.H. Golub and C.F. van Loan. Matrix Computations. North Oxford Academic, Oxford, UK, 1983.
  12. 12.A. Graps. An introduction to wavelets. IEEE Computational Science and Engineering, 2(2):50–61, 1995.
  13. 13.R. Hecht-Nielsen. Context vectors: general purpose approximate meaning representations self-organized from raw data. In J.M. Zurada, R.J. Marks II, and C.J. Robinson, editors, Computational Intelligence: Imitating Life, pages 43–56. IEEE Press, 1994.
  14. 14.P. Indyk and R. Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proc. 30th Symp. on Theory of Computing, pages 604–613. ACM, 1998.
  15. 15.W.B. Johnson and J. Lindenstrauss. Extensions of Lipshitz mapping into Hilbert space. In Conference in modern analysis and probability, volume 26 of Contemporary Mathematics, pages 189–206. Amer. Math. Soc., 1984.
  16. 16.S. Kaski. Data exploration using self-organizing maps. In Acta Polytechnica Scandinavica, Mathematics, Computing and Management in Engineering Series, number 82. 1997. Dr.Tech. thesis, Helsinki University of Technology, Finland.
  17. 17.S. Kaski. Dimensionality reduction by random mapping. In Proc. Int. Joint Conf. on Neural Networks, volume 1, pages 413–418, 1998.
  18. 18.E. J. Keogh and M. J. Pazzani. A simple dimensionality reduction technique for fast similarity search in large time series databases. In 4th Pacific-Asia Conf. on Knowledge Discovery and Data Mining, 2000.
  19. 19.J.M. Kleinberg. Two algorithms for nearest-neighbor search in high dimensions. In Proc. 29th ACM Symp. on Theory of Computing, pages 599–608, 1997.
  20. 20.M. Kurimo. Indexing audio documents by using latent semantic analysis and SOM. In E. Oja and S. Kaski, editors, Kohonen Maps, pages 363–374. Elsevier, 1999.
  21. 21.R. Ostrovsky and Y. Rabani. Polynomial time approximation schemens for geometric k-clustering. In Proc. 41st Symp. on Foundations of Computer Science, pages 349–358. IEEE, 2000.
  22. 22.C.H. Papadimitriou, P. Raghavan, H. Tamaki, and S. Vempala. Latent semantic indexing: A probabilistic analysis. In Proc. 17th ACM Symp. on the Principles of Database Systems, pages 159–168, 1998.
  23. 23.K.R. Rao and P. Yip. Discrete Cosine Transform: Algorithms, Advantages, Applications. Academic Press, 1990.
  24. 24.S. Roweis. EM algorithms for PCA and SPCA. In Neural Information Processing Systems 10, pages 626–632, 1997.
  25. 25.G. Salton and M.J. McGill. Introduction to modern information retrieval. McGraw-Hill, 1983.
  26. 26.L. Sirovich and R. Everson. Management and analysis of large scientific datasets. Int. Journal of Supercomputer Applications, 6(1):50–68, spring 1992.
  27. 27.M. Sonka, V. Hlavac, and R. Boyle. Image processing, analysis, and machine vision. PWS Publishing, 1998.
  28. 28.S. Vempala. Random projection: a new approach to VLSI layout. In Proc. 39th Annual Symp. on Foundations of Computer Science. IEEE Computer Society Press, 1998.

Citation

MLA
Bingham, E., and H. Mannila. “Random Projection in Dimensionality Reduction”. Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2001, pp. 245–50, https://doi.org/10.1145/502512.502546.
APA
Bingham, E., & Mannila, H. (2001). Random projection in dimensionality reduction. Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 245–250. https://doi.org/10.1145/502512.502546
Chicago
Bingham, E., and H. Mannila. 2001. “Random Projection in Dimensionality Reduction”. Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 245–50. https://doi.org/10.1145/502512.502546.
Harvard
Bingham, E. and Mannila, H. (2001) “Random projection in dimensionality reduction”, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp. 245–250. Available at: https://doi.org/10.1145/502512.502546.
Vancouver
1. Bingham E, Mannila H (2001) Random projection in dimensionality reduction. In: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 245–250

BibTeX

@inproceedings{Bingham_2001, series={KDD01}, title={Random projection in dimensionality reduction: applications to image and text data}, url={http://dx.doi.org/10.1145/502512.502546}, DOI={10.1145/502512.502546}, booktitle={Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining}, publisher={ACM}, author={Bingham, Ella and Mannila, Heikki}, year={2001}, month=Aug, pages={245–250}, collection={KDD01} }
Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF