Block-Sparse Signals: Uncertainty Relations and Efficient Recovery
Block-Sparse Signals: Uncertainty Relations and Efficient Recovery
复制标题
DOI：
10.1109/tsp.2010.2044837
复制
发表时间：
2010-06-01
影响因子：
5.4
通讯作者：
Boelcskei, Helmut
中科院分区：
文献类型：
--
作者：
Eldar, Yonina C.;Kuppinger, Patrick;Boelcskei, Helmut
我们考虑了从欠定的线性方程组中恢复块稀疏信号的有效方法，即具有非零条目的稀疏信号以簇的形式出现。基于我们引入的块相干性度量，推导了块稀疏信号的不确定关系。然后，我们证明了块版本的正交匹配追踪算法在块相干足够小的情况下恢复块k-稀疏信号所需的时间不超过k步。通过L(2)/L(1)的混合优化方法，证明了块相干性的相同条件保证了成功的恢复。这补充了以前块稀疏情况下的恢复结果，该情况依赖于小的块限制等距常数。本文结果的意义在于，显式地利用块稀疏可以得到比传统意义上将信号视为稀疏的信号更好的重构性质，从而忽略了问题中的附加结构。
We consider efficient methods for the recovery of block-sparse signals-i.e., sparse signals that have nonzero entries occurring in clusters-from an underdetermined system of linear equations. An uncertainty relation for block-sparse signals is derived, based on a block-coherence measure, which we introduce. We then show that a block-version of the orthogonal matching pursuit algorithm recovers block k-sparse signals in no more than k steps if the block-coherence is sufficiently small. The same condition on block-coherence is shown to guarantee successful recovery through a mixed l(2)/l(1)-optimization approach. This complements previous recovery results for the block-sparse case which relied on small block-restricted isometry constants. The significance of the results presented in this paper lies in the fact that making explicit use of block-sparsity can provably yield better reconstruction properties than treating the signal as being sparse in the conventional sense, thereby ignoring the additional structure in the problem.