Practical Johnson-Lindenstrauss Transforms via Algebraic Geometry Codes

摘要

Johnson-Lindenstrauss (JL) transformations is a powerful tool for dimension reduction, particularly for projecting a large set of vectors in a high-dimensional space into a low-dimensional space so that all the pairwise distances of the vectors in the set are preserved up to a given factor with high probability. Kane and Neslon (2014) give a construction of sparse matrices via error-correcting codes so that the number of random bit used in the matrices are small and the projected dimension is optimal (up to a constant factor). This paper extends their their work on code-based construction and make contributions in two aspects: one is to provide a better bound on success probability, thus reducing the projected dimension by a constant factor; the other is to demonstrate that algebraic geometry codes exist and can be used to compute JL transformations with only an negligible storage requirement, both are of practical importance.