学术报告

题      目：Provable sample-efficient sparse phase retrieval initialized by truncated power method

报  告  人：蔡剑锋  教授  (邀请人：陈艳南 )

                                    香港科技大学

时      间：12月18日  14：30-15：30

地     点：数科院西楼二楼会议室

报告人简介:

        蔡剑锋教授现任香港科技大学数学系教授，主要研究兴趣为信号，图像和数据的理论和算法基础。蔡剑锋教授在矩阵恢复，图像恢复算法等领域，取得了一系列开创性的科研成果。其关于矩阵恢复的SVT算法对学术研究和实际应用产生重要影响，该文章谷歌被引次数超6000次。蔡剑锋教授关于图像恢复的工作发表于被誉为数学四大期刊之一的Journal of the AMS。蔡剑锋教授在2017年和2018年被评为全球高被引学者，学术文章总被引超13000次。蔡剑锋教授在 Journal of the American Mathematical Society, Journal of the American Statistical Association, SIAM Journal on Optimization, Applied and Computational Harmonic Analysis等国际期刊发表论文70余篇，以及在CVPR,  ICCV，NeuRIPS等计算机顶会发表文章10余篇。

摘      要：

        We study the sparse phase retrieval problem, recovering an s-sparse length-n signal from m magnitude-only measurements. Two-stage non-convex approaches have drawn much attention in recent studies. Despite non-convexity, many two-stage algorithms provably converge to the underlying solution linearly when appropriately initialized. However, in terms of sample complexity, the bottleneck of those algorithms with Gaussian random measurements often comes from the initialization stage. Although the refinement stage usually needs only m=O(s logn) measurements, the widely used spectral initialization in the initialization stage requires m=O(s^2 logn) measurements to produce a desired initial guess, which causes the total sample complexity order-wisely more than necessary. To reduce the number of measurements, we propose a truncated power method to replace the spectral initialization for non-convex sparse phase retrieval algorithms. We prove that m=O(ss logn)  measurements, where   is the stable sparsity of the underlying signal, are sufficient to produce a desired initial guess. When the underlying signal contains only very few significant components, the sample complexity of the proposed algorithm is m=O(s logn) and optimal.

        欢迎老师、同学们参加、交流！