北航数学论坛学术报告
Fast Non-convex Matrix Sensing with Optimal Sample Complexity
蔡剑锋
（香港科技大学）
报告时间：2025年4月25日
报告地点：沙河主E806，16:00-17:00
报告摘要：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年任美国爱荷华大学助理教授。作为计算调和分析、信号与图像处理、稀疏与低秩重构领域的权威专家，蔡教授取得多项突破性研究成果，发表在JAMS、SIAM系列、IEEE系列、ACHA、PRL、Ann. Stat.、JMLR等国际知名数学与工程期刊上。蔡剑锋教授予2017及2018年连续两年入选科睿唯安"全球高被引科学家"。
邀请人： 黄猛
