2021/05/28 by Mark Iwen, Iwen, Mark, Arman Tavakoli +3
Engineering · Mathematics · #Advanced Numerical Analysis Techniques #FOS: Computer and information sciences #FOS: Mathematics #Geometric Analysis and Curvature Flows #Information Theory (cs.IT) #Numerical Analysis (math.NA) #Point processes and geometric inequalities
paper · pdf · doi:10.48550/arxiv.2105.13512
openalex publication_date 2021/05/28 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28
Let M be a smooth submanifold of ℝn equipped with the Euclidean (chordal) metric. This note considers the smallest dimension m for which there exists a bi-Lipschitz function f: M ↦ ℝm with bi-Lipschitz constants close to one. The main result bounds the embedding dimension m below in terms of the bi-Lipschitz constants of f and the reach, volume, diameter, and dimension of M. This new lower bound is applied to show that prior upper bounds by Eftekhari and Wakin (arXiv:1306.4748) on the minimal low-distortion embedding dimension of such manifolds using random matrices achieve near-optimal dependence on both reach and volume. This supports random linear maps as being nearly as efficient as the best possible nonlinear maps at reducing the ambient dimension for manifold data. In the process of proving our main result, we also prove similar results concerning the impossibility of achieving better nonlinear measurement maps with the Restricted Isometry Property (RIP) in compressive sensing applications.