题目：Fast Non-convex Matrix Sensing with Optimal Sample Complexity

报告人：蔡剑锋教授 香港科技大学

时间：2025年3月22日（星期六）上午9:00-10:00

地点：兴庆校区数学楼2-1会议室

报告摘要：

We study the problem of recovering an unknown d1*d2 rank-r matrix from m random linear measurements. Convex methods achieve the optimal sample complexity O(r*(d1+d2)) but are computationally expensive. Non-convex approaches, while more computationally efficient, often require suboptimal sample complexity O(r^2*(d1+d2)). Recent advance achieves for a non-convex approach but relies on the restrictive assumption of positive semidefinite (PSD) matrices and suffers from slow convergence in ill-conditioned settings. Bridging this gap, we show that Riemannian gradient descent (RGD) achieves both optimal sample complexity and computational efficiency without requiring the PSD assumption. Specifically, for Gaussian measurements, RGD exactly recovers the low-rank matrix with O(r*(d1+d2)) samples, matching the information-theoretic lower bound, and converges linearly to the global minimum with an arbitrarily small convergence rate.

报告人简介：蔡剑锋现任香港科技大学数学系教授。主要研究兴趣为信号，图像和数据的理论和算法基础。他在矩阵恢复，图像重构和成像算法等领域，取得了一系列开创性的科研成果。他关于矩阵补全的SVT算法对学术研究和实际应用产生重要影响，被广泛引用。他在2017年和2018年被评为全球高被引学者，学术文章总被引超14000次。

邀请人：杨在 教授