2019/06/08 by Michael P. Casey, Casey, Michael P.
Computer Science · Mathematics · #46B85 #60 (Primary) 46B09 #60E07 #60G50 (Secondary) #FOS: Mathematics #Functional Analysis (math.FA) #Mathematical Analysis and Transform Methods #Probability (math.PR) #Random Matrices and Applications #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1906.03536
openalex publication_date 2019/06/08 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
For any finite point set in D-dimensional space equipped with the 1-norm,\nwe present random linear embeddings to k-dimensional space, with a new\nmetric, having the following properties. For any pair of points from the point\nset that are not too close, the distance between their images is a strictly\nconcave increasing function of their original distance, up to multiplicative\nerror. The target dimension k need only be quadratic in the logarithm of the\nsize of the point set to ensure the result holds with high probability. The\nlinear embeddings are random matrices composed of standard Cauchy random\nvariables, and the proofs rely on Chernoff bounds for sums of iid random\nvariables. The new metric is translation invariant, but is not induced by a\nnorm.\n