Matrix Computations and Scientific Computing Seminar: Sparse Recovery via Differential Inclusions

Seminar | March 1 | 11 a.m.-12 p.m. | 380 Soda Hall

 Yuan Yao, Hong Kong University of Science and Technology

 Department of Mathematics

Estimate or recovery of sparse parameters from their noisy measurements is a fundamental problem in compressed sensing and high dimensional statistics, etc. In the past two decades, convex regularization approach such as LASSO or BPDN has been made popular for its algorithmic tractability. However, a well-known shortcoming of LASSO and any convex regularizations lies in the bias of estimators, which motivates further investigation of nonconvex regularization yet suffering the computational hurdle. Here we bring an idea based on some dynamics developed in applied mathematics to address this challenge in statistics. Such dynamics can be shown to traverse a path passing through the oracle estimator, an unbiased estimate of the true parameter whose entries have the same signs as those of the true signs, while the LASSO regularization path always deviates from that due to its bias. A discretization of the dynamics leads to the Linearized Bregman iteration algorithm, which is a simple iterative thresholding rule and easy to parallelize in favor of big data analysis. This approach adapts to various sparse regularizations, such as logistic regression, fused lasso, matrix regression, and graphical models etc. Application examples will be demonstrated in robust ranking, social networks, and computational health, together with a new R package — Libra.