Mean field analysis of sparse reconstruction with correlated variables
Mean field analysis of sparse reconstruction with correlated variables
复制标题
相关变量稀疏重建的平均场分析
DOI：
10.1109/eusipco.2016.7760452
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Anirvan M. Sengupta
中科院分区：
文献类型：
--
作者：
M. Ramezanali;P. Mitra;Anirvan M. Sengupta
稀疏重建算法旨在从有限数量的测量中检索高维稀疏信号。一个常见的例子是 LASSO 或 Basis Pursuit，其中使用 ℓ<sub>1</sub>-惩罚和成本函数 ||y - Hx||<sup>2</sup><sub>2</sub> 来强制执行稀疏性。对于随机设计矩阵 H，尖锐的相变边界将“好”参数区域与“坏”参数区分开，其中“好”参数区域可以无差错地恢复足够稀疏的信号，而“坏”参数区域则恢复失败。然而，相关变量情况下相变边界的理论分析滞后于不相关变量情况。这里我们使用统计物理学中的复制技巧来表明，当 N 维信号 x 是 K 稀疏且 H 是 M × N 维且协方差 E[H<sub>ia</sub>H<sub>jb</sub>] = 1/MC<sub>ij</sub>D<sub>ab</sub> 时，并且所有 D<sub>aa</sub> = 1，完美恢复发生在 M ~ ψ<sub>K</sub> (D) K log(N/M) 处于非常稀疏的极限，其中 ψ<sub>K</sub> (D) ≥ 1，表明对于相同程度的稀疏性需要更多观测。
Sparse reconstruction algorithms aim to retrieve high-dimensional sparse signals from a limited number of measurements. A common example is LASSO or Basis Pursuit where sparsity is enforced using an ℓ<sub>1</sub>-penalty together with a cost function ||y - Hx||<sup>2</sup><sub>2</sub>. For random design matrices H, a sharp phase transition boundary separates the `good' parameter region where error-free recovery of a sufficiently sparse signal is possible and a `bad' regime where the recovery fails. However, theoretical analysis of phase transition boundary of the correlated variables case lags behind that of uncorrelated variables. Here we use replica trick from statistical physics to show that when an N-dimensional signal x is K-sparse and H is M × N dimensional with the covariance E[H<sub>ia</sub>H<sub>jb</sub>] = 1/M C<sub>ij</sub>D<sub>ab</sub>, with all D<sub>aa</sub> = 1, the perfect recovery occurs at M ~ ψ<sub>K</sub> (D) K log(N/M) in the very sparse limit, where ψ<sub>K</sub> (D) ≥ 1, indicating need for more observations for the same degree of sparsity.