新晉菲爾茲獎得主王虹曾跨界涉足人工智能領域。有網友發現,王虹教授在NeurIPS 2019上發表了一篇論文,并且是共同一作。這引發了人們的好奇:一個純數學方向的頂尖學者為何會在人工智能頂會上發表論文?

這篇論文研究的是機器學習和數據分析中的低秩矩陣近似問題。實際數據通常可以整理成一個大矩陣,但直接存儲和處理成本極高。低秩近似通過用一個結構更簡單、秩更低的矩陣來盡可能準確地還原原始矩陣。常用的近似算法是列子集選擇(CSS),其思路是從原矩陣中挑出具有代表性的若干列,再用它們張成的空間去近似整個矩陣。這種方法不僅降低了存儲和計算成本,還使結果更容易解釋。

此前的研究表明,對于一般的低秩近似,CSS算法的近似比上界大約是O(k+1)。王虹等人的工作則進一步推進了這個界限,使得算法能夠被嚴格限制,最壞結果也只會比最優解差一點點。此外,他們還構造了p≥2情況下的下界,證明其結果精確到常數1。換句話說,這篇論文給出了近乎封頂的理論答案。

論文中最關鍵的部分是使用了調和分析的經典工具Riesz–Thorin插值定理。通常情況下,要證明一套算法在所有p值下都成立,需要針對不同的p分別展開復雜分析。而Riesz–Thorin插值定理可以在掌握某些端點結果后,把結論“插值”到中間的所有p值。具體來說,論文先證明p=1、2、∞三個特殊情況,再通過插值理論推出整個范圍內的近似界。這套工具在調和分析和算子理論中屬于經典方法,但在當時并不是理論計算機科學研究者最常用的技術。審稿人最終認可這篇論文最主要的技術創新就是引入Riesz–Thorin定理。




