静园5号院科研讲座 | 卡内基梅隆大学David Woodruff副教授谈子空间嵌入问题

关键词：Subspace Embedding, Oblivious

编者按

2019年8月8日，卡内基梅隆大学的 David Woodruff 副教授受邀访问北京大学前沿计算研究中心，并在静园五院做了题为“Tight Bounds For L1 Oblivious Subspace Embeddings”的主题报告，介绍了关于高维矩阵做子空间嵌入（Subspace Embedding）的工作。报告由中心讲席教授邓小铁老师主持，听众包括来自北京大学信息科学技术学院、数学学院等单位的师生。

David Woodruff 副教授报告现场

Woodruff 教授首先提到大家熟知的最小二乘回归问题：给定矩阵 A∈R^n×d，向量 b∈Rⁿ，找到向量 x∈R^d 使得 |Ax-b|₂ 尽可能小。这一问题可以推广至任意 p 范数上，用于对 d 维数据做线性拟合。在现实生活中，数据量 n 远远大于 d，这使得这一情况值得被研究。对于最小二乘回归问题，我们知道这一问题的解可以被 x^*=A^-b 表示，其中 A^- 是矩阵 A 的伪逆，这一问题的计算需要 O(nd²) 时间。这个时间量在现实生活中显得过高，一个处理办法是对这个问题做一些放缩，即允许求解近似最优，以及引入随机算法。这也引出了本次报告的核心问题：子空间嵌入。

一个矩阵 S 被称作 p 范数子空间嵌入，如果对所有 x∈R^d，|Ax|_p≤|SAx|_p≤κ|Ax|_p 以常数概率成立。而如果得到了这样一个子空间嵌入，解 p 范数回归问题的算法即可变为：对由 A 和 b 拼接得到的矩阵求子空间 [A b] 嵌入，再最小化 |SAx-Sb|_p。以 L2 子空间嵌入为例，令 r=O(d/ϵ²)，S 大小是 r×n，每个元素独立同分布于高斯分布 N(0,1/r) 的矩阵。可以通过网论证（Net Argument）和Johnson-Lindenstrauss (JL) 引理得知，S 是一个子空间嵌入，且是无依赖子空间嵌入（Oblivious Subspace Embedding， OSE），即和矩阵 A 的取值无关。然而这一方法的缺点是，矩阵 SA 的计算已经需要 O(nd²) 的时间，并没有从效率上得到提升。然而正是源于这样的想法，后续有研究成果对这一构造稍微做了一些改动：在 CountSketch 算法中，令 r=O(d²/ϵ²)，S 矩阵在每一列随机选一个位置，并随机赋值为±1，矩阵其他位置均为0。可以证明对任意 x，以常数概率 |SAx|₂=(1±ϵ)|Ax|₂ 会发生。注意到矩阵每列只有一个非0数的特点，我们知道 SA 的计算只需要 A 的 O(nnz(A)) 的时间，即和 A 的非零元素个数呈线性关系。同时，如果 S 每列只选一个非0值，即使想保证矩阵的秩，d² 的依赖也是紧的。而在 OSNAP 算法中，S 矩阵每列选 s=O(log_B d/ϵ) 个非0随机±1值，r=O(B d log d/ϵ²)，可以证明这样的矩阵 S 也是子空间嵌入，而且对应的下界 r=Ω(B d²/ϵ )。

而对于 L1 子空间嵌入问题，我们是否可以用类似的方法去做呢？Woodruff 教授这里回顾了 L2 子空间嵌入下用到的技术：JL引理（高斯分布引出的2-稳定（2-stable）版本），网论证。Woodruff 教授提到，这里可能我们需要1-稳定分布。无独有偶，柯西分布恰恰具有这一性质：a₁C₁+⋯+a_nC_n≈|a|₁C，其概率密度函数为 f(x)=1/(π(1+x²))。柯西分布的尾部可以被 Θ(1/x) 限定住，但这一尾部相对较大，对分析会带来一定困难。对于稠密柯西嵌入（Dense Cauchy Embedding），即嵌入中每个元素均为取自柯西分布的独立变量时，令 r=O(d log⁡d)，可以证明对所有 x，以常数概率 Ω(r)|Ax|₁≤|SAx|₁≤O(rd log⁡d)|Ax|₁ 会成立。下界的证明源自网论证和柯西下尾概率不等式，而上界的证明用到了 d 维子空间1范数下的一组基，先证明 |SU|₁=O(rd log⁡rd) 以常数概率发生，进而 |SUx|₁≤|SU|₁|x|_∞≤O(rd log⁡rd)|Ux|₁。其中第一个不等式是 Holder不等式的应用。对于稀疏柯西嵌入（Sparse Cauchy Embedding），即其中每列只有一个非零值，独立同分布于一个柯西分布，令 r=O(d⁵ log⁵⁡d)，可以证明对所有 x，以常数概率

会成立，同样的，矩阵 SA 的计算时间为 O(nnz(A))。

对于 L1无依赖子空间嵌入问题之前的结论，Woodruff 教授总结提炼出如下问题：

1. Ω(d log⁡d) 的拉伸（distortion）是不是最优？能不能提出 (1+ϵ) 的拉伸？（如果是有依赖的版本，(1+ϵ) 的拉伸是可以做到的）；

2. 是否能做到 r=O(d log⁡d)，拉伸为 O(d log⁡d) 的稀疏无依赖子空间嵌入？稀疏度和r的大小有没有什么权衡？

Woodruff 教授及其合作者的最新论文对这些问题给出了解答：对于 1≤p<2，任意 p 范数 r 行的 OSE 的拉伸度为

特别的，r=n 时，单位矩阵就是一个无拉伸的 OSE，p 趋向于2时，拉伸度趋向于 (1+ϵ)。而对于 p=1 的情况，r=poly(d)，n≫r 的时候，下界为 Ω(d log²⁡d)，而稠密柯西嵌入和最优只差 O(log³d) 的因子。证明的大概思路基于Yao的最小最大原理（Yao's Minimax Principle）：构造一组矩阵 A 的一个分布，并说明对任意嵌入 S，都有这样的下界。由于时间关系，Woodruff 教授没有仔细介绍这一构造和证明细节，具体内容可以参考他主页上的论文。

Woodruff 教授最后提到一些公开问题：是否可以构造 L1 的 OSE，使得：1）用到  O(d²) 行，稀疏度为1，拉伸度为 O(d log⁡d)？2）用到 O(d logd) 行，稀疏度为 O(1)，拉伸度为 O(d logd)？3）用到 O(2^O(d)) 行，拉伸度为 O(1)，或者证明更强的下界结论？而一个更有一般性的问题是，得到 1<p<2 的OSE的紧界。有听众问提问，为什么只关注 1<p<2？Woodruff 教授解释到，当然可以研究 p>2 的情况，但一般来说更高的 p 值意味着对离群的点更重视，在实际场景中不是那么适用。听众在报告中问了Woodruff 教授很多问题，Woodruff 教授均细心解答。报告结束后，Woodruff 教授继续和中心师生进行了深入交流。

邓小铁教授与David Woodruff副教授合影

图文 | 肖涛

EconCS@PKU

往 期 报 告

—   版权声明  —

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

点“阅读原文”看报告概要等信息