On fast Johnson-Lindenstrauss embeddings of compact submanifolds of \(\mathbb{R}^N\) with boundary

DOI10.1007/S00454-022-00420-WarXiv2110.04193MaRDI QIDQ6151027

No author found.

Publication date: 9 February 2024

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

Abstract: Let $mathcal{M}$ be a smooth $d$-dimensional submanifold of $mathbb{R}^N$ with boundary that's equipped with the Euclidean (chordal) metric, and choose $m leq N$. In this paper we consider the probability that a random matrix $A in mathbb{R}^{m imes N}$ will serve as a bi-Lipschitz function $A: mathcal{M} ightarrow mathbb{R}^m$ with bi-Lipschitz constants close to one for three different types of distributions on the $m imes N$ 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 $d lesssim sqrt{N}$) 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 $mathcal{O}(log^c N)$-dimensional submanifolds of $mathbb{R}^N$ which enjoy $mathcal{O}(N log (log N))$-time matrix vector multiplications.

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

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

Cites Work

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

Related Items (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