The generalized Lasso with non-linear observations
arXiv:1502.04071
Abstract
We study the problem of signal estimation from non-linear observations when the signal belongs to a low-dimensional set buried in a high-dimensional space. A rough heuristic often used in practice postulates that non-linear observations may be treated as noisy linear observations, and thus the signal may be estimated using the generalized Lasso. This is appealing because of the abundance of efficient, specialized solvers for this program. Just as noise may be diminished by projecting onto the lower dimensional space, the error from modeling non-linear observations with linear observations will be greatly reduced when using the signal structure in the reconstruction. We allow general signal structure, only assuming that the signal belongs to some set K in R^n. We consider the single-index model of non-linearity. Our theory allows the non-linearity to be discontinuous, not one-to-one and even unknown. We assume a random Gaussian model for the measurement matrix, but allow the rows to have an unknown covariance matrix. As special cases of our results, we recover near-optimal theory for noisy linear observations, and also give the first theoretical accuracy guarantee for 1-bit compressed sensing with unknown covariance matrix of the measurement vectors.
arXiv comment21 pages
References in corpus (10)
- Simultaneous analysis of Lasso and Dantzig selector
- On the conditions used to prove oracle results for the Lasso
- Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing
- A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
- Trace Lasso: a trace norm regularization for correlated designs
- Learning subgaussian classes : Upper and minimax bounds
- Sparse single-index model
- Manifold-Based Signal Recovery and Parameter Estimation from Compressive Measurements
- Simple Bounds for Noisy Linear Inverse Problems with Exact Side Information
- New Analysis of Manifold Embeddings and Signal Recovery from Compressive Measurements
Cited by in corpus (12)
- High-dimensional estimation with geometric constraints
- Sparse Nonlinear Regression: Parameter Estimation and Asymptotic Inference
- Channel Estimation in Broadband Millimeter Wave MIMO Systems with Few-Bit ADCs
- Precise Error Analysis of Regularized M-estimators in High-dimensions
- Fundamental Limits of Ridge-Regularized Empirical Risk Minimization in High Dimensions
- A Geometric View on Constrained M-Estimators
- Using the LASSO for gene selection in bladder cancer data
- Linear signal recovery from -bit-quantized linear measurements: precise analysis of the trade-off between bit depth and number of measurements
- BER Analysis of the box relaxation for BPSK Signal Recovery
- Scalable Approximations for Generalized Linear Problems
- Optimal Estimation of Slope Vector in High-dimensional Linear Transformation Model
- Vanilla Lasso for sparse classification under single index models