On fast Johnson-Lindenstrauss embeddings of compact submanifolds of R^N with boundary

DOI10.1007/S00454-022-00420-WMaRDI QIDQ6151027zbMATH OpenFDO

Authors

Publication date 9 February 2024

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2110.04193

zbMATH Keywords

manifolds with boundaryJohnson-Lindenstrauss lemmafast dimension reductionrandomized manifold embeddings

Mathematics Subject Classification ID

Global submanifolds (53C40) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Numerical approximation and computational geometry (primarily algorithms) (65D99) Applications of differential geometry to sciences and engineering (53Z99)

Abstract: Let $mathcalM$ be a smooth $d$-dimensional submanifold of $mathbb{R}^N$ with boundary that's equipped with the Euclidean (chordal) metric, and choose $mleqN$. In this paper we consider the probability that a random matrix $Ainmathbb{R}^{mimesN}$ will serve as a bi-Lipschitz function $A:mathcalMightarrowmathbb{R}^m$ with bi-Lipschitz constants close to one for three different types of distributions on the $mimesN$ matrices $A$, including two whose realizations are guaranteed to have fast matrix-vector multiplies. In doing so we generalize prior randomized metric space embedding results of this type for submanifolds of $mathbb{R}^N$ by allowing for the presence of boundary while also retaining, and in some cases improving, prior lower bounds on the achievable embedding dimensions $m$ for which one can expect small distortion with high probability. In particular, motivated by recent modewise embedding constructions for tensor data, herein we present a new class of highly structured distributions on matrices which outperform prior structured matrix distributions for embedding sufficiently low-dimensional submanifolds of $mathbb{R}^N$ (with $dlesssimsqrtN$) with respect to both achievable embedding dimension, and computationally efficient realizations. As a consequence we are able to present, for example, a general new class of Johnson-Lindenstrauss embedding matrices for $mathcalO(lo{g}^{c}N)$-dimensional submanifolds of $mathbb{R}^N$ which enjoy $mathcalO(Nlog(logN))$-time matrix vector multiplications.

Recommendations

• Lower bounds on the low-distortion embedding dimension of submanifolds of \(\mathbb{R}^n\)
• On outer bi-Lipschitz extensions of linear Johnson-Lindenstrauss embeddings of subsets of \(\mathbb{R}^N\)
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• Random projections of smooth manifolds
• On variants of the Johnson–Lindenstrauss lemma

Cites work

• scientific article; zbMATH DE number 3842680 (Why is no real title available?)
• scientific article; zbMATH DE number 3736560 (Why is no real title available?)
• scientific article; zbMATH DE number 2117213 (Why is no real title available?)
• scientific article; zbMATH DE number 3056613 (Why is no real title available?)
• 50 years sets with positive reach -- a survey
• A mathematical introduction to compressive sensing
• A simple proof of the restricted isometry property for random matrices
• An elementary proof of a theorem of Johnson and Lindenstrauss
• Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
• Approximation of points on low-dimensional manifolds via random linear projections
• Compressive Sensing on Manifolds Using a Nonparametric Mixture of Factor Analyzers: Algorithm and Performance Bounds
• Curvature Measures
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Dimensionality reduction with subgaussian matrices: a unified theory
• Estimating the reach of a manifold
• Extensions of Lipschitz mappings into a Hilbert space
• Fast dimension reduction using Rademacher series on dual BCH codes
• Finding the homology of submanifolds with high confidence from random samples
• High-dimensional probability. An introduction with applications in data science
• Isometric sketching of any set via the restricted isometry property
• Johnson–Lindenstrauss Embeddings with Kronecker Structure
• Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares
• Lower bounds on the low-distortion embedding dimension of submanifolds of \(\mathbb{R}^n\)
• New analysis of manifold embeddings and signal recovery from compressive measurements
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• On recovery guarantees for one-bit compressed sensing on manifolds
• On the differential geometry of closed space curves
• On the immersion of manifolds in Euclidean space
• Random projections of smooth manifolds
• Riemannian geometry.
• Self-Linking and the Gauss Integral in Higher Dimensions
• Self-linking and the directed secant span of a differentiable manifold
• Some Integral Formulas for Space Curves and Their Generalization
• Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs
• The Riemannian obstacle problem
• The reach, metric distortion, geodesic convexity and the variation of tangent spaces
• Tighter bounds for random projections of manifolds
• Totally skew embeddings of manifolds
• What happens to a manifold under a bi-Lipschitz map?

Cited in

(1)

• On outer bi-Lipschitz extensions of linear Johnson-Lindenstrauss embeddings of subsets of \(\mathbb{R}^N\)

This page was built for publication: On fast Johnson-Lindenstrauss embeddings of compact submanifolds of \(\mathbb{R}^N\) with boundary

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6151027)