Computationally Efficient Estimators for Dimension Reductions Using Stable Random Projections

Details Computationally Efficient Estimators for Dimension Reductions Using Stable Random Projections Computationally Efficient Estimators for Dimension Reductions Using Stable Random Projections

2008-06-27

arxiv.org/abs/0806.4422v1

Computer Science

Learning

Scientific paper

The method of stable random projections is a tool for efficiently computing the $l_\alpha$ distances using low memory, where $0<\alpha \leq 2$ is a tuning parameter. The method boils down to a statistical estimation task and various estimators have been proposed, based on the geometric mean, the harmonic mean, and the fractional power etc. This study proposes the optimal quantile estimator, whose main operation is selecting, which is considerably less expensive than taking fractional power, the main operation in previous estimators. Our experiments report that the optimal quantile estimator is nearly one order of magnitude more computationally efficient than previous estimators. For large-scale learning tasks in which storing and computing pairwise distances is a serious bottleneck, this estimator should be desirable. In addition to its computational advantages, the optimal quantile estimator exhibits nice theoretical properties. It is more accurate than previous estimators when $\alpha>1$. We derive its theoretical error bounds and establish the explicit (i.e., no hidden constants) sample complexity bound.

Affiliated with

Also associated with

No associations

Rating

Computationally Efficient Estimators for Dimension Reductions Using Stable Random Projections does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computationally Efficient Estimators for Dimension Reductions Using Stable Random Projections, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computationally Efficient Estimators for Dimension Reductions Using Stable Random Projections will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-692333