Both Random Projection and PCA is used to reduce dimension. It is obvious that the computation of PC Projections need more time than generating a Random Projection matrix knowing that RP don't depend on the training data. Is this computation cost a serious advantage of RP over PCA, especially one can say that the PCA can be computed off-line of training the model?
The advantage is a nice speedup in computations, at the cost of a possible small loss in accuracy. To understand the speedup you can compare the time complexity of the two approaches [1]. For a Nxd matrix of data, with N observations of dimensionality d, time complexity of (full) PCA is O(d^2N)+O(d^3), although it can be simplified if you only want a subset of the eigenvectors. Instead, time complexity of RP is O(dkN) where k is the resulting dimensionality. The difference can become quite big for large d. The possible loss in accuracy derives from the fact that PCA is the optimal linear transformation in the least-square sense.
The RP method has some interesting properties when your data is a mixture of Gaussians [2], and a dramatic improvement in computing time when you consider its sparse versions [3].
[1] Bingham, Ella, and Heikki Mannila. "Random projection in dimensionality reduction: applications to image and text data." Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2001.
[2] Dasgupta, Sanjoy. "Experiments with random projection." Proceedings of the Sixteenth conference on Uncertainty in artificial intelligence. Morgan Kaufmann Publishers Inc., 2000.
[3] Li, Ping, Trevor J. Hastie, and Kenneth W. Church. "Very sparse random projections." Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2006.
The advantage is a nice speedup in computations, at the cost of a possible small loss in accuracy. To understand the speedup you can compare the time complexity of the two approaches [1]. For a Nxd matrix of data, with N observations of dimensionality d, time complexity of (full) PCA is O(d^2N)+O(d^3), although it can be simplified if you only want a subset of the eigenvectors. Instead, time complexity of RP is O(dkN) where k is the resulting dimensionality. The difference can become quite big for large d. The possible loss in accuracy derives from the fact that PCA is the optimal linear transformation in the least-square sense.
The RP method has some interesting properties when your data is a mixture of Gaussians [2], and a dramatic improvement in computing time when you consider its sparse versions [3].
[1] Bingham, Ella, and Heikki Mannila. "Random projection in dimensionality reduction: applications to image and text data." Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2001.
[2] Dasgupta, Sanjoy. "Experiments with random projection." Proceedings of the Sixteenth conference on Uncertainty in artificial intelligence. Morgan Kaufmann Publishers Inc., 2000.
[3] Li, Ping, Trevor J. Hastie, and Kenneth W. Church. "Very sparse random projections." Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2006.
- Badges
- Science topic