Support recovery from noisy random measurements via weighted ℓ1 minimization
Support recovery from noisy random measurements via weighted ℓ1 minimization
复制标题
DOI：
10.1109/isit.2016.7541534
复制
发表时间：
2016-07
期刊：
影响因子：
--
通讯作者：
Jun Zhang;U. Mitra;Kuan-Wen Huang;Nicolò Michelusi
中科院分区：
文献类型：
--
作者：
Jun Zhang;U. Mitra;Kuan-Wen Huang;Nicolò Michelusi
在这里，我们根据噪声欠定测量的支持恢复来分析一般加权 ℓ1 最小化的样本复杂性。该分析通过考虑加权效应，概括了标准 ℓ1 最小化的先前工作。我们陈述了权重和样本复杂度之间的明确关系，使得随着问题维度的增加，使用加权 ℓ1 最小化的 i.i.d 随机高斯测量矩阵以高概率恢复底层信号的支持。该结果提供了预测不同算法相对性能的衡量标准。在分析的推动下，提出了一种新的迭代加权策略。在重新加权部分支持 (RePS) 算法中，解决了一系列加权 ℓ1 最小化问题，其中使用部分支持恢复来修剪优化；此外，用于下一次迭代的权重由当前估计更新。通过所提出的测量和数值结果将 RePS 与其他加权算法进行比较，这证明了其在认知无线电驱动的频谱占用估计问题上的优越性能。
Herein, we analyze the sample complexity of general weighted ℓ1 minimization in terms of support recovery from noisy underdetermined measurements. This analysis generalizes prior work for standard ℓ1 minimization by considering the weighting effect. We state explicit relationship between the weights and the sample complexity such that i.i.d random Gaussian measurement matrices used with weighted ℓ1 minimization recovers the support of the underlying signal with high probability as the problem dimension increases. This result provides a measure that is predictive of relative performance of different algorithms. Motivated by the analysis, a new iterative weighted strategy is proposed. In the Reweighted Partial Support (RePS) algorithm, a sequence of weighted ℓ1 minimization problems are solved where partial support recovery is used to prune the optimization; furthermore, the weights used for the next iteration are updated by the current estimate. RePS is compared to other weighted algorithms through the proposed measure and numerical results, which demonstrate its superior performance for a spectrum occupancy estimation problem motivated by cognitive radio.