↑ 点击蓝字关注极市平台

作者丨杜伟、陈萍

来源丨机器之心

编辑丨极市平台

极市导读

一篇长达 2840 页的博士论文，都是关于矩阵理论的，可以当教材了。 >>加入极市CV技术交流群，走在计算机视觉的最前沿

一篇论文的篇幅竟然多达数千页，比很多教材都要厚，这简直无法想象。不过，学术界的「能人异士」层出不穷，德州大学奥斯汀分校的 CS 博士生 Zhao Song 就做到了。

这是一篇 2019 年 8 月提交的博士论文，总篇幅达到了 2840 页，其中目录就占了 31 页。此外在致谢部分，论文作者还以整整 5 页的篇幅感谢了合作者、提供宝贵意见以及读博期间帮助过他的人。

论文地址：https://repositories.lib.utexas.edu/bitstream/handle/2152/80715/SONG-DISSERTATION-2019.pdf?sequence=1&isAllowed=y

不过，作者在论文第 1 页做了免责声明，表示：「这篇论文不符合德州大学奥斯汀分校当前的写作格式指南，论文仅供参考使用。」

下面让我们简单了解下这篇巨长的博士论文到底讲了些什么。

2840 页，这篇博士论文讲了什么

矩阵（matrix）在很多理论计算机科学和机器学习问题中发挥着至关重要的作用。在这篇博士论文中，作者旨在提供对矩阵的更好理解，并且文中的很多见解对古老的、已经得到充分研究的算法问题带来了改进。

具体来讲，作者从三个层面对计算机科学和机器学习领域的矩阵展开了研究。

首先，他探究了矩阵在优化算法中的作用。作者研究了大量的矩阵优化问题，并针对线性规划、经验风险最小化、常微分方程和深度神经网络提供了新的求解方法和结果。其中，在线性规划优化问题中，作者提出了一种在当前矩阵乘法时间上运行的新算法，并表示 gaisuan「解决了停滞了三十年之久的研究障碍」。此外，该算法可以泛化至多种多样的凸优化问题，即经验风险最小化问题。具体算法如下所示：

然后，他探究了随机矩阵中的集中不等式问题。具体来讲，作者将大量的切尔诺夫（Chernoff）类型的标量集中不等式和斯宾塞（Spencer）类型的差异定理泛化到矩阵中。

标量随机变量集中的切尔诺夫边界是随机算法分析中的基本工具。过去十年，切尔诺夫边界的矩阵泛化得到广泛应用，但这种泛化存在着一定的限制，并且是否可以消除这些限制的问题也悬而未决。通过提供大量更宽松独立性假设条件下新的矩阵切尔诺夫边界，作者对这一问题给出了肯定的答案。

如下为定理 8.1.1：k 均匀强瑞利分布（Strongly Rayleigh Distribution）的矩阵切尔诺夫边界。

斯宾塞定理是差异理论中的一个著名结果，但如何将斯宾塞定理泛化至矩阵设置中这个重要问题却没有得到解决。作者在这方面取得了一些进展，并证明了在某些限制设置条件下斯宾塞定理可以实现矩阵泛化。并且，文中的结果可以泛化至著名的卡迪森 - 辛格猜想（Kadison-Singer conjecture）问题。

如下为定理 1.3.4：卡迪森 - 辛格问题。

最后，他提出了一系列求解矩阵问题的新算法。新算法大致可以分为两类：矩阵分解问题和结构化重建问题。在矩阵分解算法上，针对各种低秩矩阵分解，作者提出了新的算法，包括一些新的固定参数可处理的算法；在结构化重建算法上，针对一些具有结构矩阵的重建任务，给出了新的算法。

例如，作者重新考虑了 L2/L2 的压缩感知问题，提出了编码速度更快和列稀疏更小的算法。此外，作者还给出了针对傅里叶变换（Fourier transform）的快速算法等。

作者介绍

个人主页：https://simons.berkeley.edu/people/zhao-song

论文作者 Zhao Song 本科毕业于西蒙菲沙大学，获得了计算机科学学士学位，博士毕业于德克萨斯大学奥斯汀分校计算机科学系，由 Eric Price 教授指导。在进入德克萨斯大学之前，Zhao Song 曾是哈佛大学的访问学者，也在 IBM 研究中心实习过。

Zhao Song 的研究领域广泛，涉及机器学习、理论计算机科学和数学，如深度学习理论、对抗样本、强化学习、线性回归、矩阵 / 张量分解、线性规划、傅立叶变换等。论文被引用次数超过 2000 次：

参考链接：

https://scholar.google.com/citations?user=yDZct7UAAAAJ&hl=en

https://dblp.org/pid/76/4051-2.html

推荐阅读

2020年AI领域有哪些让人惊艳的研究？
不要再用arxiv链接了！为了让论文引用更规范，上交毕业生、南加州大学华人博士创建了一个小工具
图灵奖得主Yann LeCun的六十年

添加极市小助手微信（ID : cvmart2），备注：姓名-学校/公司-研究方向-城市（如：小极-北大-目标检测-深圳），即可申请加入极市目标检测/图像分割/工业检测/人脸/医学影像/3D/SLAM/自动驾驶/超分辨率/姿态估计/ReID/GAN/图像增强/OCR/视频理解等技术交流群：每月大咖直播分享、真实项目需求对接、求职内推、算法竞赛、干货资讯汇总、与 10000+来自港科大、北大、清华、中科院、CMU、腾讯、百度等名校名企视觉开发者互动交流~

△长按添加极市小助手

△长按关注极市平台，获取最新CV干货

觉得有用麻烦给个在看啦~

篇幅达2840页、目录就有31页，这位华人小哥的博士论文堪比教材

2840 页，这篇博士论文讲了什么

作者介绍

2020年AI领域有哪些让人惊艳的研究？

不要再用arxiv链接了！为了让论文引用更规范，上交毕业生、南加州大学华人博士创建了一个小工具

图灵奖得主Yann LeCun的六十年