Random Embeddings with Optimal Accuracy
This work provides optimal Johnson-Lindenstrauss embeddings, which are foundational for dimensionality reduction in machine learning and data science, improving the accuracy for practitioners and researchers.
This work constructs Johnson-Lindenstrauss embeddings with optimal accuracy, achieving the best possible variance, mean-squared error, and exponential concentration of length distortion. They provide matching and efficiently samplable constructions based on orthogonal matrices, accompanied by lower bounds for any data and embedding dimensions.
This work constructs Jonson-Lindenstrauss embeddings with best accuracy, as measured by variance, mean-squared error and exponential concentration of the length distortion. Lower bounds for any data and embedding dimensions are determined, and accompanied by matching and efficiently samplable constructions (built on orthogonal matrices). Novel techniques: a unit sphere parametrization, the use of singular-value latent variables and Schur-convexity are of independent interest.