Faster Dimension Reduction

doi:10.1145/1646353.1646379

2010-02-01

PRE

Nir Ailon

Bernard Chazelle

DOI：10.1145/1646353.1646379

原文链接

原文求助

摘要

En 中文

Data represented geometrically in high-dimensional vector spaces can be found in many applications. Images and videos, are often represented by assigning a dimension for every pixel (and time). Text documents may be represented in a vector space where each word in the dictionary incurs a dimension. The need to manipulate such data in huge corpora such as the web and to support various query types gives rise to the question of how to represent the data in a lower-dimensional space to allow more space and time efficient computation. Linear mappings are an attractive approach to this problem because the mapped input can be readily fed into popular algorithms that operate on linear spaces (such as principal-component analysis, PCA) while avoiding the curse of dimensionality. The fact that such mappings even exist became known in computer science following seminal work by Johnson and Lindenstrauss in the early 1980s. The underlying technique is often called random projection. The complexity of the mapping itself, essentially the product of a vector with a dense matrix, did not attract much attention until recently. In 2006, we discovered a way to sparsify the matrix via a computational version of Heisenberg's Uncertainty Principle. This led to a significant speedup, which also retained the practical simplicity of the standard Johnson-Lindenstrauss projection. We describe the improvement in this article, together with some of its applications.

Keyword:

APPROXIMATE NEAREST-NEIGHBOR

FAST RANDOMIZED ALGORITHM

JOHNSON-LINDENSTRAUSS

LINEAR COMPLEXITY

QUERIES

TRANSFORM

MATRICES

GRAPHS

SPACES