II. High Dimensional Estimation under Weak Moment Assumptions: Structured Recovery and Matrix Estimation

Abstract

The purpose of this thesis is to develop new theories on high-dimensional structured signal recovery under a rather weak assumption on the measurements that only a finite number of moments exists. High-dimensional recovery has been one of the emerging topics in the last decade partly due to the celebrated work of Candes, Romberg and Tao (e.g. [CRT06, CRT04]). The original analysis there (and the works thereafter) necessitates a strong concentration argument (namely, the restricted isometry property), which only holds for a rather restricted class of measurements with light-tailed distributions. It had long been conjectured that high-dimensional recovery is possible even if restricted isometry type conditions do not hold, but the general theory was beyond the grasp until very recently, when the works [Men14a, KM15] propose a new small-ball method. In these two papers, the authors initiated a new analysis framework for general empirical risk minimization (ERM) problems with respect to the square loss, which is robust and can potentially allow heavy-tailed loss functions. The materials in this thesis are partly inspired by [Men14a], but are of a different mindset: rather than directly analyzing the existing ERMs for signal recovery for which it is difficult to avoid strong moment assumptions, we show that, in many circumstances, by carefully re-designing the ERMs to start with, one can still achieve the minimax optimal statistical rate of signal recovery with very high probability under much weaker assumptions than existing works.

PhD thesis, USC

References in corpus (11)

• Simultaneous analysis of Lasso and Dantzig selector
• Nonlinear shrinkage estimation of large-dimensional covariance matrices
• The LASSO with Non-linear Measurements is Equivalent to One With Linear Measurements
• The lower tail of random quadratic forms, with applications to ordinary least squares and restricted eigenvalue properties
• Estimation with Norm Regularization
• A Shrinkage Principle for Heavy-Tailed Data: High-Dimensional Robust Low-Rank Matrix Recovery
• Learning without Concentration
• PAC-Bayesian bounds for the Gram matrix and least squares regression with a random design
• On Stein's Identity and Near-Optimal Estimation in High-dimensional Index Models
• Structured Recovery with Heavy-tailed Measurements: A Thresholding Procedure and Optimal Rates
• PAC-Bayesian bounds for Principal Component Analysis in Hilbert spaces