2023/07/15 by Casey, Michael P.
#60B20 (primary) 62G30 #68Q87 #68R12 #68T09 (secondary) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Metric Geometry (math.MG) #Probability (math.PR) #Statistics Theory (math.ST)
paper · doi:10.48550/arxiv.2307.07704
For a set X of N points in ℝD, the Johnson-Lindenstrauss lemma provides random linear maps that approximately preserve all pairwise distances in X -- up to multiplicative error (1± ε) with high probability -- using a target dimension of O(ε-2log(N)). Certain known point sets actually require a target dimension this large -- any smaller dimension forces at least one distance to be stretched or compressed too much. What happens to the remaining distances? If we only allow a fraction η of the distances to be distorted beyond tolerance (1± ε), we show a target dimension of O(ε-2log(4e/η)log(N)/R) is sufficient for the remaining distances. With the stable rank of a matrix A as ‖A‖F2/‖A‖2, the parameter R is the minimal stable rank over certain log(N) sized subsets of X-X or their unit normalized versions, involving each point of X exactly once. The linear maps may be taken as random matrices with i.i.d. zero-mean unit-variance sub-gaussian entries. When the data is sampled i.i.d. as a given random vector ξ, refined statements are provided; the most improvement happens when ξ or the unit normalized \widehatξ-ξ' is isotropic, with ξ' an independent copy of ξ, and includes the case of i.i.d. coordinates.