A framework to characterize performance of LASSO algorithms
Mihailo Stojnic School of Industrial Engineering Purdue University, West Lafayette, IN 47907 e-mail:
Abstract
Abstract
中文速览
在压缩感知（compressed sensing）领域，从带噪声的欠定线性方程组中恢复稀疏信号是一个核心难题，此前的工作虽然证明了 LASSO 和 SOCP 等算法能将恢复误差控制在噪声水平的常数倍以内，却无法给出误差的精确值。本文构建了一套严格的统计分析框架，专门用来精确刻画 LASSO 算法在高维随机设定下的最坏情形 ℓ₂ 误差，即在给定稀疏度比例 β 和测量比例 α 的条件下，算法输出与真实稀疏向量之间距离的确切上界。分析结果与 Bayati、Montanari 等人通过状态演化（state evolution）方法独立得到的精确结论完全吻合，同时作为副产品，论文还发现了一种 SOCP 算法可以达到与 LASSO 完全相同的恢复性能。这项工作的意义在于，它为实际应用中广泛使用的 LASSO 类算法提供了可靠的数学保证，使人们能够在部署前就精确预测算法在各种噪声和稀疏度条件下的表现。
原文 arXiv:1303.7291;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1303.7291v1