Asymptotic Analysis of Complex LASSO via Complex Approximate Message Passing (CAMP)
Asymptotic Analysis of Complex LASSO via Complex Approximate Message Passing (CAMP)
复制标题
DOI：
10.1109/tit.2013.2252232
复制
发表时间：
2011-08
影响因子：
2.5
通讯作者：
A. Maleki;L. Anitori;Zai Yang;Richard Baraniuk
中科院分区：
文献类型：
--
作者：
A. Maleki;L. Anitori;Zai Yang;Richard Baraniuk
从一组欠采样的随机线性测量中恢复稀疏信号是压缩感知中的主要问题。在本文中，我们考虑的情况下，信号和测量都是复值。我们研究了流行的恢复方法l1-正则化最小二乘或LASSO。虽然一些研究表明，LASSO提供了理想的解决方案在某些条件下，该算法在复杂的设置精确的渐近性能还不知道。本文将近似消息传递（AMP）算法推广到求解复值LASSO问题，得到复近似消息传递算法（CAMP）。然后，我们推广的状态演化框架，最近推出的分析AMP的复杂设置。使用状态演化，我们推导出精确的LASSO和CAMP的相变和噪声灵敏度的公式。我们的理论结果与独立同分布的情况有关。高斯感知矩阵模拟证实，我们的结果持有一个更大的一类随机矩阵。
Recovering a sparse signal from an undersampled set of random linear measurements is the main problem of interest in compressed sensing. In this paper, we consider the case where both the signal and the measurements are complex-valued. We study the popular recovery method of l1-regularized least squares or LASSO. While several studies have shown that LASSO provides desirable solutions under certain conditions, the precise asymptotic performance of this algorithm in the complex setting is not yet known. In this paper, we extend the approximate message passing (AMP) algorithm to solve the complex-valued LASSO problem and obtain the complex approximate message passing algorithm (CAMP). We then generalize the state evolution framework recently introduced for the analysis of AMP to the complex setting. Using the state evolution, we derive accurate formulas for the phase transition and noise sensitivity of both LASSO and CAMP. Our theoretical results are concerned with the case of i.i.d. Gaussian sensing matrices. Simulations confirm that our results hold for a larger class of random matrices.