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

报告时间：2025-03-14   10:00~11:00

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

报告地点：雷军科技楼八楼报告厅（806）

Abstract：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.