Dimension reduction techniques for ℓ_p, 1 ≤ p ≤ 2, with applications

2014/08/08 by Bartal, Yair, Gottlieb, Lee-Ad
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1408.1789

Abstract

For Euclidean space (ℓ₂), there exists the powerful dimension reduction transform of Johnson and Lindenstrauss, with a host of known applications. Here, we consider the problem of dimension reduction for all ℓ_p spaces 1 ≤ p ≤ 2. Although strong lower bounds are known for dimension reduction in ℓ₁, Ostrovsky and Rabani successfully circumvented these by presenting an ℓ₁ embedding that maintains fidelity in only a bounded distance range, with applications to clustering and nearest neighbor search. However, their embedding techniques are specific to ℓ₁ and do not naturally extend to other norms. In this paper, we apply a range of advanced techniques and produce bounded range dimension reduction embeddings for all of 1 ≤ p ≤ 2, thereby demonstrating that the approach initiated by Ostrovsky and Rabani for ℓ₁ can be extended to a much more general framework. We also obtain improved bounds in terms of the intrinsic dimensionality. As a result we achieve improved bounds for proximity problems including snowflake embeddings and clustering.

Related

• Fast Dimensionality Reduction from ℓ₂ to ℓ_p
• Dimension Reduction for Clustering: The Curious Case of Discrete Centers
• Entropy-based Bounds on Dimension Reduction in L₁
• The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction
• Approximate nearest neighbor search for ℓ_p-spaces (2 < p < ∞) via embeddings