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

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

Author name not available (Why is that?)

Publication date: 9 February 2024

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

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.

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)

Cites Work

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

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)