Structured signal recovery from non-linear and heavy-tailed measurements

Abstract

We study high-dimensional signal recovery from non-linear measurements with design vectors having elliptically symmetric distribution. Special attention is devoted to the situation when the unknown signal belongs to a set of low statistical complexity, while both the measurements and the design vectors are heavy-tailed. We propose and analyze a new estimator that adapts to the structure of the problem, while being robust both to the possible model misspecification characterized by arbitrary non-linearity of the measurements as well as to data corruption modeled by the heavy-tailed distributions. Moreover, this estimator has low computational complexity. Our results are expressed in the form of exponential concentration inequalities for the error of the proposed estimator. On the technical side, our proofs rely on the generic chaining methods, and illustrate the power of this approach for statistical applications. Theory is supported by numerical experiments demonstrating that our estimator outperforms existing alternatives when data is heavy-tailed.

References in corpus (8)

• Simultaneous analysis of Lasso and Dantzig selector
• The LASSO with Non-linear Measurements is Equivalent to One With Linear Measurements
• High-dimensional estimation with geometric constraints
• Estimation with Norm Regularization
• A Shrinkage Principle for Heavy-Tailed Data: High-Dimensional Robust Low-Rank Matrix Recovery
• Optimal linear estimation under unknown nonlinear transform
• Tail bounds via generic chaining
• Upper bounds on product and multiplier empirical processes

Cited by in corpus (7)

• On Stein's Identity and Near-Optimal Estimation in High-dimensional Index Models
• Least squares estimation in the monotone single index model
• Structured Recovery with Heavy-tailed Measurements: A Thresholding Procedure and Optimal Rates
• High Dimensional M-Estimation with Missing Outcomes: A Semi-Parametric Framework
• Misspecified Nonconvex Statistical Optimization for Phase Retrieval
• Non-Gaussian Observations in Nonlinear Compressed Sensing via Stein Discrepancies
• Surrogate Aided Unsupervised Recovery of Sparse Signals in Single Index Models for Binary Outcomes