Seminars on Numerical algebra, Optimization and Data Sciences：Provable Sample-Efficient Sparse Phase Retrieval Initialized by Truncated Power Method

：蔡剑锋（香港科技大学）
：2022-10-21 16:00
：腾讯会议ID：869-197-552（无密码）

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

时  间：10月21日下午16:00

地  点：腾讯会议ID：869-197-552（无密码）

内容摘要:

We study the sparse phase retrieval problem, recovering an s-sparse length-n signal x from m magnitude-only measurements. Two-stage non-convex approaches have drawn much attention in recent studies for this problem. Despite non-convexity, most two-stage algorithms like projected gradient descent and its variants are guaranteed to achieve linear convergence when appropriately initialized. However, in terms of sample complexity, the bottleneck of most existing non-convex algorithms usually comes from the first stage, namely the initialization stage. The widely used spectral method requires m>=O(s^2 log n) measurements to produce a desired initial guess, which dominates non-convex algorithms. To reduce the number of measurements, we propose a simple truncated power method as an initialization strategy for non-convex algorithms in this work. Theoretically, we show that m>=O(s' s log n) measurements are sufficient to recover the signal, where s'=||x||_2^2/||x||_{\infty}^2 is the stable sparsity of x. When the underlying signal contains at least one significant component, s'=O(1), and our sample complexity m>=O(s log n) is nearly optimal. Numerical experiments illustrate that the proposed method is more sample-efficient than state-of-the-art algorithms.

个人简介：

蔡剑锋，2007年在香港中文大学获博士学位，曾先后在新加坡国立大学、美国加州大学洛杉矶分校和美国爱荷华大学工作；2015年加入香港科技大学数学系，并于2019年晋升正教授。蔡剑锋教授的研究兴趣是数据科学和成像技术中的算法设计和分析，在包括JAMS，ACHA，SIAM系列期刊，IEEE Trans.系列期刊，JMLR，CVPR，ICCV等发表论文70多篇，谷歌学术引用一万余次。2017年和2018年被评选为全球高被引学者。

 

联系人：杜魁