任何用过电子表格的人都可以作证：将数据整理成表格往往很方便。但在大数据时代，这些表格可能极其庞大，包含数百万甚至数亿行。
让大数据分析在计算上切实可行的一种方法，是通过删去大量行来缩小数据表——用数学术语来说，就是矩阵。关键在于，保留下来的行必须在某种意义上能够代表被删去的行，这样对它们进行计算才能得出近似正确的结果。
在6月举行的ACM计算理论研讨会上，麻省理工学院（MIT）的研究人员将介绍一种新算法，它能找到原始矩阵的最小近似矩阵，并保证计算结果可靠。对于工程和机器学习中一类重要问题，这比以往技术有显著改进。对于所有类别的问题，该算法也能以尽可能快的速度找到近似矩阵。
为了确定压缩矩阵中的某一行在多大程度上代表原始矩阵中的一行，该算法需要测量两者之间的“距离”。但“距离”有不同的定义方式。
一种常见方式是所谓的“欧几里得距离”。计算欧几里得距离时，将两行中对应位置元素的差值平方后相加，再对所得总和开平方，便得到两行之间的距离。其直观依据是勾股定理：直角三角形两条直角边长度的平方和的平方根，就是斜边的长度。
另一种距离度量不太常见，但在解决机器学习及其他优化问题时尤其有用。它叫作“曼哈顿距离”，就是两行对应元素之差的绝对值之和。
深入范数
事实上，曼哈顿距离和欧几里得距离都是统计学家所称的“范数”的实例。曼哈顿距离，即1-范数，是差值之和的一次方根；欧几里得距离，即2-范数，是差值平方和的平方根。3-范数是差值立方和的立方根，依此类推直至无穷范数。
在论文中，麻省理工学院的研究人员——应用数学博士后Richard Peng和电气工程与计算机科学研究生Michael Cohen——证明，他们的算法在任何范数下压缩矩阵都是最优的。但据Peng称：“我们真正关心的是1-范数。”
在任意范数下压缩矩阵，第一步都是为原始矩阵的每一行指定一个“权重”。一行的权重表示它与多少其他行相似，并决定该行被纳入压缩矩阵的可能性。如果该行被纳入，其数值就会按权重进行乘算。例如，如果10行彼此可以很好地互相替代，但都无法替代矩阵中的其他行，那么每一行被纳入压缩矩阵的概率都是10%。如果其中一行被选中，它的所有元素都会乘以10，从而体现它所代表的另外九行的贡献。
尽管曼哈顿距离在某种意义上比欧几里得距离简单，但它使行权重的计算更困难。此前，在1-范数下压缩矩阵的最佳算法会生成一个矩阵，其行数与原始矩阵列数的2.5次方成正比。而在2-范数下压缩矩阵的最佳算法生成的矩阵，其行数则与原始矩阵的列数乘以其自身的对数成正比。
这意味着，如果矩阵有100列，那么在Peng和Cohen的研究之前，1-范数下可能达到的最佳压缩结果，是一个有数十万行的矩阵；而在2-范数下，结果是一个有两三百行的矩阵。随着列数增加，这种差距还会扩大。
驾驭递归
Peng和Cohen的算法在1-范数下压缩矩阵的效果与在2-范数下同样好；而在2-范数下，它的压缩效果与前代算法一样好。这是因为在2-范数下，它直接采用了现有的最佳算法。在1-范数下，它采用同一算法，但会重复使用五六次。
这篇论文的真正贡献，是从数学上证明2-范数算法在1-范数下也能得出可靠结果。Peng解释说，计算1-范数权重的方程早已为人所知。但“这个定义有个有趣之处：它是递归的，”他说。“所以正确的权重同时出现在等式左边和右边。”也就是说，某一矩阵行的权重——称为 w ——被设定为一个数学表达式的值，而该表达式本身也包含 w。
“人们知道这个定义存在，但统计学界的人不知道该如何处理它，”Peng说。“他们看到它就会想：‘我究竟怎么用这个来计算？’”
Peng和Cohen证明的是，如果一开始将等式右边的 w 设为1，然后计算该表达式并把结果代回等式右边的w，再重复这一过程，你很快就会收敛到 w正确值的良好近似。
“这是高度优雅的数学成果，与以往结果相比取得了重大进展，”加州大学伯克利分校计算机科学教授Richard Karp说。他曾获美国国家科学奖章和计算机科学领域最高荣誉图灵奖。“它把原始问题归结为一个非常容易理解的问题。我很欣赏其中的数学推演。”
本文由我们与 MIT News 合作发布。发表本文并不代表世界经济论坛认可其中观点。
如需持续关注议程， 请订阅我们的每周通讯。
作者：Larry Hardesty是MIT News撰稿人。
图片：一幅插图显示，一名男子手持笔记本电脑，身上投映着二进制代码。路透社/Kacper Pempel。
