Fast Dimension Reduction Using Rademacher Series on Dual BCH Codes

摘要

ABSTRACT: The Fast Johnson-Lindenstrauss Transform (FJLT) was recently discovered by Ailon and Chazelle as a novel technique for performing fast dimension reduction with small distortion. The connection between geometry and discrete coding theory discussed here is interesting in its own right and may be useful in other algorithmic applications as well. Introduction: Applying random matrices is by now a well known technique for reducing dimensionality of vectors in Euclidean space while preserving certain properties (most notably distance information). Beginning with the classic work of Johnson and Lindenstrauss who used projections onto random subspaces, other variants of the technique using different distributions are known and have been used in many algorithms.