Convergence and Stability of a Class of Iteratively Re-weighted Least Squares Algorithms for Sparse Signal Recovery in the Presence of Noise.
Convergence and Stability of a Class of Iteratively Re-weighted Least Squares Algorithms for Sparse Signal Recovery in the Presence of Noise.
复制标题
DOI：
10.1109/tsp.2013.2287685
复制
发表时间：
2013-10-30
期刊：
影响因子：
--
通讯作者：
Brown EN
中科院分区：
文献类型：
--
作者：
Babadi B;Ba D;Purdon PL;Brown EN
在本文中，我们研究了一类迭代重加权最小二乘（IRLS）算法的理论特性，用于在存在噪声的情况下恢复稀疏信号。我们演示了此类算法与一类用于高斯尺度混合 (GSM) 分布下约束最大似然估计的期望最大化 (EM) 算法之间的一一对应关系。我们考虑的 IRLS 算法通过 0 < ν ≤ 1 和 ε > 0 进行参数化。EM 形式以及与 GSM 的联系使我们能够确定 IRLS(ν, ε) 算法最小化 ℓν “范数”的 ε 平滑版本。我们利用 EM 理论证明，对于每个 0 < ν ≤ 1，IRLS(ν, ε) 迭代序列的极限点是约束集上 ε-平滑 ℓν ‘范数’最小化问题的驻点。最后，我们采用压缩采样 (CS) 理论中的技术来证明，如果迭代的极限点与全局极小值重合，则 IRLS(ν, ε) 算法类对于每个 0 < ν ≤ 1 都是稳定的。对于 ν = 1 的情况，我们表明该算法以指数方式快速收敛到驻点的邻域，并概述了其对 ν < 1 的超指数收敛的推广。我们通过模拟实验证明了我们的主张。 IRLS 的简单性以及本贡献中提供的理论保证为其采用作为稀疏信号恢复的标准工具提供了令人信服的理由。
In this paper, we study the theoretical properties of a class of iteratively re-weighted least squares (IRLS) algorithms for sparse signal recovery in the presence of noise. We demonstrate a one-to-one correspondence between this class of algorithms and a class of Expectation-Maximization (EM) algorithms for constrained maximum likelihood estimation under a Gaussian scale mixture (GSM) distribution. The IRLS algorithms we consider are parametrized by 0 < ν ≤ 1 and ε > 0. The EM formalism, as well as the connection to GSMs, allow us to establish that the IRLS(ν, ε) algorithms minimize ε-smooth versions of the ℓν ‘norms’. We leverage EM theory to show that, for each 0 < ν ≤ 1, the limit points of the sequence of IRLS(ν, ε) iterates are stationary point of the ε-smooth ℓν ‘norm’ minimization problem on the constraint set. Finally, we employ techniques from Compressive sampling (CS) theory to show that the class of IRLS(ν, ε) algorithms is stable for each 0 < ν ≤ 1, if the limit point of the iterates coincides the global minimizer. For the case ν = 1, we show that the algorithm converges exponentially fast to a neighborhood of the stationary point, and outline its generalization to super-exponential convergence for ν < 1. We demonstrate our claims via simulation experiments. The simplicity of IRLS, along with the theoretical guarantees provided in this contribution, make a compelling case for its adoption as a standard tool for sparse signal recovery.