The generalized Lasso with non-linear observations
Yaniv Plan and Roman Vershynin Y. Plan is with the Department of Mathematics, University of British Columbia 1984 Mathematics Rd., Vancouver, BC V6T 1Z2, Canada R. Vershynin is with the Department of Mathematics, University of Michigan, 530 Church St., Ann Arbor, MI 48109, U.S.A.
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\subset\mathbb{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 f
中文速览
从高维信号的非线性观测中准确恢复信号，是压缩感知和统计学习中长期悬而未决的难题。这篇论文证明了一个"懒人友好"的结论：即便观测是非线性的（比如1-bit量化，只保留符号信息），只要把这些观测直接塞进标准的广义Lasso（K-Lasso）求解器中，就能得到精度接近最优的重建结果——无需知道非线性函数的具体形式，也无需知道测量向量的协方差矩阵。论文的核心思路是把非线性观测分解为"有效线性项加噪声"，用高斯均值宽度（Gaussian mean width）来刻画信号集合的有效维度，再借助Gordon逃逸定理给出严格的误差上界。理论上，这是首个在测量向量协方差未知情形下给出1-bit压缩感知精确保证的结果，不仅统一了稀疏向量、低秩矩阵等多种信号结构，也为工程中"把非线性当线性处理"这一经验做法提供了坚实的数学支撑。
原文 arXiv:1502.04071;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1502.04071v2