Convex Community Detection and Nonconvex Blind Deconvolution
主 题: Convex Community Detection and Nonconvex Blind Deconvolution
报告人: Prof. Xiaodong Li(UC Davis)
时 间: 2016-06-17 10:00 - 2016-06-17 11:00
地 点: Room 29, Quan Zhai, BICMR
For community detection in network data analysis, we propose a convex relaxation for the widelyusedmodularity maximization method, followed by a doubly-weighted `1-norm k-median procedure whichyields an explicit clustering. More importantly, strong non-asymptotic results of misclassification rates areestablished under the degree-corrected stochastic block model (DCSBM), with minimum assumptions on thesparsity and density gap. Experiment results show that our method enjoys better empirical performancecompared to some state-of-the-art spectral methods in the literature.In the second half of the talk, I will introduce a non-convex optimization method for blind deconvolution,which is an important problem in many areas including astronomy, medical imaging, optics, and wirelesscommunications. We present an efficient regularized gradient descent algorithm. When the number of measurementsis slightly larger than the information theoretical minimum, we show that the algorithm convergesat a geometric rate and is provably robust in the presence of noise. To the best of our knowledge, our algorithmis the first blind deconvolution algorithm that is numerically efficient, robust against noise, and comeswith rigorous recovery guarantees under certain subspace conditions. Numerical experiments demonstratethat our method yields excellent performance even in situations beyond our theoretical framework.
