On Fast Johnson–Lindenstrauss Embeddings of Compact Submanifolds of $$\mathbbm {R}^N$$ with Boundary
On Fast Johnson–Lindenstrauss Embeddings of Compact Submanifolds of $$\mathbbm {R}^N$$ with Boundary
复制标题
关于带有边界的 $$mathbbm {R}^N$$ 紧致子流形的 Fast Johnson—Lindenstrauss 嵌入
DOI：
10.1007/s00454-022-00420-w
复制
发表时间：
2022
影响因子：
0.8
通讯作者：
Tavakoli, Arman
中科院分区：
文献类型：
--
作者：
Iwen, Mark A.;Schmidt, Benjamin;Tavakoli, Arman
设为的光滑维子流形，其边界满足欧几里德（弦）度量，选择。在本文中，我们考虑的概率，一个随机矩阵将作为bi-Lipschitz函数的bi-Lipschitz常数接近1的三种不同类型的分布的矩阵A，其中包括两个的实现是保证有快速矩阵向量乘法。在这样做时，我们推广了这种类型的子流形的先验随机度量空间嵌入结果，通过允许边界的存在，同时也保留，并在某些情况下提高，可实现的嵌入维数的先验下界，人们可以期望小失真的概率很高。特别是，最近的modewise嵌入构造张量数据的动机，在这里，我们提出了一类新的高度结构化的矩阵分布优于先前的结构化矩阵分布嵌入足够低维的子流形（与）相对于可实现的嵌入维数，计算效率的实现。因此，我们能够提出，例如，一个一般的新类的Johnson-Lindenstrauss嵌入矩阵的维子流形的享受时间矩阵向量乘法。
Letbe a smoothd-dimensional submanifold ofwith boundary that’s equipped with the Euclidean (chordal) metric, and choose. In this paper we consider the probability that a random matrixwill serve as a bi-Lipschitz functionwith bi-Lipschitz constants close to one for three different types of distributions on thematricesA, 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 ofby allowing for the presence of boundary while also retaining, and in some cases improving, prior lower bounds on the achievable embedding dimensionsmfor 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(with) 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-dimensional submanifolds ofwhich enjoy-time matrix vector multiplications.