Support Recovery From Noisy Random Measurements via Weighted $\ell _1$ Minimization
Support Recovery From Noisy Random Measurements via Weighted $\ell _1$ Minimization
复制标题
DOI：
10.1109/tsp.2018.2838553
复制
发表时间：
2018-09
影响因子：
5.4
通讯作者：
Jun Zhang;U. Mitra;Kuan-Wen Huang;Nicolò Michelusi
中科院分区：
文献类型：
--
作者：
Jun Zhang;U. Mitra;Kuan-Wen Huang;Nicolò Michelusi
本文从噪声欠定测量的支持恢复角度，分析了一般加权最小化的样本复杂度。该分析通过考虑任意加权，推广了先前关于$\ well _1$最小化的工作。给出了权值与样本复杂度之间的显式关系，即对于具有i.d.高斯项的随机矩阵，随着问题维数的增加，加权的$\ well _1$最小化以高概率恢复底层信号的支持。该结果提供了一种预测不同算法相对性能的度量。在此基础上，提出了一种新的二值信号恢复迭代重加权策略。在二元稀疏性促进的重加权$\ well $最小化（bPRL1）算法中，利用部分支持恢复对优化进行删减，求解了一系列加权$\ well $最小化问题；此外，下一次迭代使用的权重由当前估计更新。通过所提出的度量将bPRL1与其他加权算法进行了比较，数值结果表明bPRL1在由认知无线电驱动的频谱占用估计问题上提供了优越的性能。
Herein, the sample complexity of general weighted $\ell _1$ minimization in terms of support recovery from noisy underdetermined measurements is analyzed. This analysis generalizes prior work on $\ell _1$ minimization by considering arbitrary weighting. The explicit relationship between the weights and the sample complexity is stated such that for random matrices with i.i.d. Gaussian entries, the weighted $\ell _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 reweighted strategy is proposed for binary signal recovery. In the binary sparsity-Promoting Reweighted $\ell _1$ minimization (bPRL1) algorithm, a sequence of weighted $\ell _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. bPRL1 is compared to other weighted algorithms through the proposed measure and numerical results are shown to provide superior performance for a spectrum occupancy estimation problem motivated by cognitive radio.