Papers › On Outer Bi-Lipschitz Extensions of Linear Johnson-Lindenstrauss Embeddings of...
On Outer Bi-Lipschitz Extensions of Linear Johnson-Lindenstrauss Embeddings of Low-Dimensional Submanifolds of ℝᴺ
Mark A. Iwen, Mark Philip Roach
Let ℳ be a compact d-dimensional submanifold of ℝᴺ with reach τ and volume V_ℳ. Fix ϵ∈(0,1). In this paper we prove that a nonlinear function f: ℝᴺ →ℝᵐ exists with m ≤C (d / ϵ² ) log((√(V_ℳ))/τ ) such that (1 - ϵ) x - y ₂ ≤ f(x) - f(y) ₂ ≤(1 + ϵ) x - y ₂ holds for all x ∈ℳ and y ∈ℝᴺ. In effect, f not only serves as a bi-Lipschitz function from ℳ into ℝᵐ with bi-Lipschitz constants close to one, but also approximately preserves all distances from points not in ℳ to all points in ℳ in its image. Furthermore, the proof is constructive and yields an algorithm which works well in practice. In particular, it is empirically demonstrated herein that such nonlinear functions allow for more accurate compressive nearest neighbor classification than standard linear Johnson-Lindenstrauss embeddings do in practice.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections