### Low-Rank Recovery: From Convex to Nonconvex Methods

- Series
- Job Candidate Talk
- Time
- Monday, February 9, 2015 - 11:05 for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Xiaodong Li – University of Pennsylvania

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.