The Squared-Error of Generalized LASSO: A Precise Analysis
Samet Oymak, Christos Thrampoulidis and Babak Hassibi Department of Electrical Engineering Caltech, Pasadena – 91125 This work was supported in part by the National Science Foundation under grants CCF-0729203, CNS-0932428 and CIF-1018927, by the Office of Naval Research under the MURI grant N00014-08-1-0747, and by a grant from Qualcomm Inc.
Abstract
We consider the problem of estimating an unknown signal $\mathbf{x}_{0}$ from noisy linear observations $\mathbf{y}=\mathbf{A}\mathbf{x}_{0}+\mathbf{z}\in\mathbb{R}^{m}$ . In many practical instances of this problem, $\mathbf{x}_{0}$ has a certain structure that can be captured by a structure inducing function $f(\cdot)$ . For example, $\ell_{1}$ norm can be used to encourage a sparse solution. To estimate $\mathbf{x}_{0}$ with the aid of a convex $f(\cdot)$ , we consider three variations of the widely used $LASSO$ estimator and provide sharp characterizations of their performances. Our study falls under a generic framework, where the entries of the measurement matrix $\mathbf{A}$ and the noise vector $\mathbf{z}$ have zero-mean normal distributions with variances $1$ and $\sigma^{2}$ , respectively. For the LASSO estimator $\mathbf{x}^{*}$ , we ask: “What is the precise estimation error as a function of the noise level $\sigma$ , the number of observations $m$ and the structure of the signal?". In particular, we attempt to calculate the Normalized Square Error (NSE) defined as $\frac{\|\mathbf{x}^{*}-\mathbf{x}_{0}\|_{2}^{2}}{\sigma^{2}}$ . We show that, the structure of the signa
中文速览
广义LASSO（Generalized LASSO）在压缩感知和结构化信号恢复中被广泛使用，但对于任意凸正则函数，其估计误差究竟精确是多少，一直缺乏统一的理论刻画。本文针对带噪线性观测模型，对三种常见的LASSO形式——约束型、ℓ₂惩罚型和ℓ₂²惩罚型——分别推导出归一化均方误差（NSE）的精确公式，核心发现是：无论信号结构多复杂、正则函数如何选取，误差最终都可以用一个"高斯平方距离"摘要参数来概括，其形式与普通最小二乘的误差公式高度相似，只需将信号维度替换为该摘要参数即可。基于此，论文还给出了最优惩罚参数的选取方案，并为稀疏信号、低秩矩阵、块稀疏信号等典型结构导出了可直接使用的闭合式误差上界。这一成果为理解结构化信号估计的基本极限提供了统一而精确的几何框架，对算法设计和参数调优均有直接指导意义。
原文 arXiv:1311.0830;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1311.0830v2