Georgia Institute of Technology College of Sciences

Low-rank structures are common in modern data analysis and signal processing, and they usually play essential roles in various estimation and detection problems. It is challenging to recover the underlying low-rank structures reliably from corrupted or undersampled measurements. In this talk, we will introduce convex and nonconvex optimization methods for low-rank recovery by two examples. The first example is community detection in network data analysis. In the literature, it has been formulated as a low-rank recovery problem, and then SDP relaxation methods can be naturally applied. However, the statistical advantages of convex optimization approaches over other competitive methods, such as spectral clustering, were not clear. We show in this talk that the methodology of SDP is robust against arbitrary outlier nodes with strong theoretical guarantees, while standard spectral clustering may fail due to a small fraction of outliers. We also demonstrate that a degree-corrected version of SDP works well for a real-world network dataset with a heterogeneous distribution of degrees. Although SDP methods are provably effective and robust, the computational complexity is usually high and there is an issue of storage. For the problem of phase retrieval, which has various applications and can be formulated as a low-rank matrix recovery problem, we introduce an iterative algorithm induced by nonconvex optimization. We prove that our method converges reliably to the original signal. It requires far less storage and has much higher rate of convergence compared to convex methods.