Low-rank structures are common in modern data analysis, and they play essential roles in various applications. It is challenging to recover low-rank structures reliably and efficiently from corrupted or under-sampled measurements. In this talk, we discuss convex and nonconvex optimization methods for low-rank recovery by two examples.
The first example is robust community detection in networks. We look for a community detection method, which is not only statistically powerful and computationally efficient, but also robust against adversarial outlier nodes, which is very important in statistical practices. By introducing the generalized stochastic block model, we prove that convex optimization methods proposed in the literature are robust against the influence of outliers. As a byproduct, we also demonstrate numerically that convex methods perform well in a challenging real-world network dataset.
Although convex methods are provably effective and robust, the computational complexity is still relatively high. Moreover, there is often an issue of memory. For the problem of phase retrieval in imaging, which is a special model of low-rank recovery, we introduce a nonconvex optimization with theoretically guaranteed performance. It is much more efficient than convex methods in terms of computation and memory.
- Tags
-