Various thresholds for ℓ1subscriptℓ1\ell_{1}-optimization in compressed sensing
Mihailo Stojnic School of Industrial Engineering Purdue University, West Lafayette, IN 47907 e-mail:
Abstract
Abstract
中文速览
压缩感知（compressed sensing）的核心难题之一是：当测量方程数目远少于未知量维度时，如何高效地恢复稀疏信号——即只有少数非零分量的向量。现有理论（Donoho、Candès等人的工作）已证明，用ℓ₁范数最小化（一种多项式时间可解的线性规划）可以做到这一点，并给出了测量数与稀疏度之间的比例关系，但已知的界并不总是最优。本文提出了一套基于"零空间刻画"与Gordon逃逸定理（escape through a mesh theorem）的新概率分析框架，针对零空间在Grassmann流形上均匀分布的随机测量矩阵，系统计算出强阈值、截面阈值和弱阈值（strong/sectional/weak threshold）这三类稀疏度比例常数的精确值。结果表明，本文得到的阈值在若干情形下与目前已知最佳值持平甚至有所改进，为理解ℓ₁优化的恢复能力提供了更紧的理论保证，对压缩感知系统的实际设计具有直接参考价值。
原文 arXiv:0907.3666;中英对照 + 大白话阅读 https://aha.fim.ai/paper/0907.3666v1