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

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

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

报告地点：雷军科技楼A806报告厅

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.

蔡剑锋，现任香港科技大学教授。他于2000年获复旦大学计算数学学士学位，2004年同校获硕士学位，2007年获香港中文大学数学哲学博士学位。蔡剑锋教授于2007-2009年任新加坡国立大学研究员，2009-2011年担任美国加州大学洛杉矶分校CAM兼职助理教授，2011-2015年任美国爱荷华大学助理教授，2015-2019香港科技大学数学系副教授，2019至今数学系教授。作为计算调和分析、信号与图像处理、稀疏与低秩重构领域的权威专家，蔡教授取得多项突破性研究成果；其中在计算调和分析方向的一项原创性工作发表在了国际数学期刊四大之一JAMS上，而为低秩矩阵重构设计的SVT算法是该方向最具代表性的算法之一。蔡剑锋教授的其他重要工作也都发表在SIAM系列、IEEE系列、ACHA、JASA、JMLR等国际知名应用数学与工程期刊上。另外，蔡剑锋教授于2017及2018年连续两年入选科睿唯安"全球高被引科学家"。