Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares
Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares
复制标题
DOI：
10.1137/19m1308116
复制
发表时间：
2019-12
期刊：
影响因子：
--
通讯作者：
M. Iwen;D. Needell;E. Rebrova;A. Zare
中科院分区：
文献类型：
--
作者：
M. Iwen;D. Needell;E. Rebrova;A. Zare
在本文中，新的一般模式的Johnson-Lindenstrauss（JL）子空间嵌入的建议，都是相当快的生成和更容易存储比传统的JL嵌入时，非常大的向量和/或张量。相应的嵌入结果，然后证明了两种不同类型的低维（张量）子空间。这些新的子空间嵌入结果的第一个产生改进的空间复杂度界嵌入的秩$r$张量的CP分解包含在一个固定的（但未知的）一组$r$秩一基础张量的跨度。在传统的向量设置这第一个结果产生新的和非常一般的近最优的不经意子空间嵌入结构，需要更少的随机位生成比标准的JL嵌入时，嵌入子空间的$\mathbb{C}^N$跨越的基向量具有特殊的克罗内克结构。本文证明的第二个结果提供了任意$r$维子空间$\mathcal{S} \subset \mathbb{C}^N$的新的快速JL嵌入，其也需要更少的随机位（并且因此更容易存储-即，需要更少的空间），以便实现小的失真。这些新的不经意子空间嵌入结果通过$（i）$有效地将$\mathcal{S}$中的任何给定向量折叠成一个（不一定是低秩的）张量，然后$（ii）$将得到的张量嵌入$\mathbb{C}^m$，其中$m \leq C r \log^c（N）/\epsilon^2 $。压缩和快速压缩最小二乘解方法相关的应用程序也被认为是，包括用于拟合低秩CP分解，和建议的JL嵌入结果示出在这两种设置中工作良好的数值。
In this paper new general modewise Johnson-Lindenstrauss (JL) subspace embeddings are proposed that are both considerably faster to generate and easier to store than traditional JL embeddings when working with extremely large vectors and/or tensors. Corresponding embedding results are then proven for two different types of low-dimensional (tensor) subspaces. The first of these new subspace embedding results produces improved space complexity bounds for embeddings of rank-$r$ tensors whose CP decompositions are contained in the span of a fixed (but unknown) set of $r$ rank-one basis tensors. In the traditional vector setting this first result yields new and very general near-optimal oblivious subspace embedding constructions that require fewer random bits to generate than standard JL embeddings when embedding subspaces of $\mathbb{C}^N$ spanned by basis vectors with special Kronecker structure. The second result proven herein provides new fast JL embeddings of arbitrary $r$-dimensional subspaces $\mathcal{S} \subset \mathbb{C}^N$ which also require fewer random bits (and so are easier to store - i.e., require less space) than standard fast JL embedding methods in order to achieve small $\epsilon$-distortions. These new oblivious subspace embedding results work by $(i)$ effectively folding any given vector in $\mathcal{S}$ into a (not necessarily low-rank) tensor, and then $(ii)$ embedding the resulting tensor into $\mathbb{C}^m$ for $m \leq C r \log^c(N) / \epsilon^2$. Applications related to compression and fast compressed least squares solution methods are also considered, including those used for fitting low-rank CP decompositions, and the proposed JL embedding results are shown to work well numerically in both settings.