今年KDD的这篇Best Paper来自雅虎实验室。研究大数据背景下的matrix sketching问题。文章所描述的算法我认为是比较practical的，是近似精度和计算量的很好的折中。另外证明简洁有效，矩阵不等式的缩放技巧是一大看点。

##优化目标和算法

这篇文章的目标是找到一个矩阵\(B_{(l\times m)}\)近似原始矩阵\(A_{(n\times m)}\)，其中\(l \ll n\)。这个问题有一个经典解法，就是SVD低秩近似，通过找矩阵\(A \in \mathcal{R}^{n\times m}\)的最大\(l\)个奇异值，得到的近似矩阵\(\hat{A} \in \mathcal{R}^{l\times m}\)是如下问题的最优解：

\[minimize \quad \|A - B\|_F \quad s.t. \quad rank(B) \leq l\]

但这个方法需要计算一个\(n\times m\)矩阵的SVD分解，当\(n\)很大的时候（比如有1亿个cookie组成的矩阵）计算量是难以忍受的。和low-rank approximation不同，这篇文章退而求其次，试图找到\(A^T A\)的近似，即寻找矩阵\(B_{(l\times m)}\)近似矩阵\(A_{(n\times m)}\)，使得

\[\begin{align*} B^T B &\prec A^TA \\ \|A^T A - B^T B\| &\leq 2 \| A \|_f^2 / l \end{align*}\]

这里我沿用了文章中的记号，其中\(\| \cdot \|\)表示矩阵的2-范数，\(\| \cdot \|_f\)表示矩阵的F-范数。

事实上这和low-rank approximation要解决的问题已经不是同一回事了，而和一个名叫frequent-items的方法有更多的共同点。这个方法试图使用\(O(l)\)空间对\(m \gg l\)个独立元素执行在线计数。很显然，这必须丢弃一些出现次数过少的元素。具体方法建议参考原文引用19所描述的算法。

而这篇文章使用了与之类似的shrinkage策略，算法步骤如下：

##实验和性能 Frequent-directions有以下计算上的优势：

  • 可以online计算;
  • 只对小矩阵\(B_{(l\times m)}\)执行SVD;
  • 可以应用于分块矩阵：\(A=[A_1;A_2]\)，\(B=[B_1;B_2]\)。可将矩阵分块到多台机器上并行计算，完事后拼起来即可.

实验对比了多种方法，包括sampling, hashing, brute-force(即svd-low-rank)等，可以看到新方法在计算速度上显著好于brute-force，在近似效果上显著好于sampling, hashing等。

##部分证明注解

这一节我对证明部分做一些简单的注解，方便大家阅读原文：

###记号 上述算法中，\(A_i\)表示矩阵\(A\)中的一行，而\(B^{i}\), \(C^i\)分别代表某一轮迭代后的矩阵\(B\)和\(C\)

如果没有进入到if条件，那么这一轮的\(\delta = 0\)

###Isometric Left Rotation 算法中\(C\)被称为\(B\)的『isometric left rotation』，我们看看它们的范数有什么关系:

\[\begin{align*} \|B\|_f^2 &= \|U \Sigma V^T \|_f^2 \\ &= tr(V\Sigma U^T U \Sigma V^T) \\ &= tr(V\Sigma^2 V^T) \\ &= \|\Sigma V^T\|_f^2 \\ &= \|C\|_f^2 \\ &(= tr(\Sigma^2) = \sum_{j=1}^l \sigma_j^2) \end{align*}\]

而对任意向量\(\mathbf{x}\)，有

\[\begin{align*} \|B\mathbf{x}\|^2 &= \mathbf{x}^T V\Sigma U^T U \Sigma V^T \mathbf{x} \\ &= \mathbf{x}^TV\Sigma^2 V^T\mathbf{x} \\ &= \|C\mathbf{x}\|^2 \end{align*}\]

可见两者拥有相等的F-范数和点乘后的向量范数。

###范数不等式 对任意单位向量\(\|\mathbf{x}\|=1\)，有：

\[\begin{align*} \mathbf{x}^T D \mathbf{x} = \|\mathbf{x}^T D \mathbf{x}\| &\leq \|\mathbf{x}\| \|D\mathbf{x}\| = \| D\mathbf{x} \| \\ &\leq \max\limits_{\|\mathbf{y}\|=1} \| D \mathbf{y} \| = \| D \| \end{align*}\]