An Optimal Condition for the Block Orthogonal Matching Pursuit Algorithm
An Optimal Condition for the Block Orthogonal Matching Pursuit Algorithm
复制标题
DOI：
10.1109/access.2018.2853158
复制
发表时间：
2018-07
期刊：
影响因子：
3.9
通讯作者：
Jinming Wen;Huangke Chen;Zhengchun Zhou
中科院分区：
文献类型：
--
作者：
Jinming Wen;Huangke Chen;Zhengchun Zhou
从线性模型 ${{y}}= {A} {{x}} + {v}$ 恢复块 $K$ -稀疏信号 ${{x}}$ 的支持，其中 ${A}$ 是传感矩阵，${v}$ 是噪声向量，来自许多应用。块正交匹配追踪（BOMP）算法是一种流行的块稀疏恢复算法，近十年来备受关注。 Eldar等人证明了这一点。 BOMP 可以在噪声情况下（在 ${{x}}$ 和 ${v}$ 的特定条件下）恢复任何块 $K$ 的非零块的位置 $\Omega$ -稀疏向量 ${{x}}$ ，块长度为 $d$（在 ${{x}}$ 和 ${v}$ 的特定条件下），并且可以在无噪声情况下在 $K$ 迭代中精确恢复 ${{x}}$（如果块相互） ${A}$的相干性$\mu ({A})$和亚相干性$\nu ({A})$满足$(2K-1)d\mu ({A}) +(d-1) \nu ({A})。本文首先改进并发展了$\ell下的BOMP算法恢复$\Omega $的充分条件。 分别为 _{2}$ 有界和 $\ell _{\infty }$ 有界噪声。然后，我们证明，对于任何给定的正整数 $K$ 和 $d$ ，总是存在一个块 $K$ 稀疏向量 ${{x}}$ ，块长度为 $d$ ，以及一个传感矩阵 ${A}$ ，其中 $(2K-1)d\mu ({A}) + (d-1) \nu ({A})=1 $ ，使得 BOMP 无法恢复 ${{x}}$ 来自 ${{y}}= {A} {{x}} $，进行 $K$ 次迭代。这表明 Eldar 等人提出的条件。就 ${A}$ 的条件而言是尖锐的。
Recovery of the support of a block $K$ -sparse signal ${{x}}$ from a linear model ${{y}}= {A} {{x}} + {v}$ , where ${A}$ is a sensing matrix and ${v}$ is a noise vector, arises from many applications. The block orthogonal matching pursuit (BOMP) algorithm is a popular block sparse recovery algorithm and has received much attention in the recent decade. It was proved by Eldar et al. that the BOMP can recover the positions $\Omega $ of the nonzero blocks of any block $K$ -sparse vector ${{x}}$ with a block length $d$ in the noisy case (under certain condition on ${{x}}$ and ${v}$ ) and can exactly recover ${{x}}$ in the noiseless case in $K$ iterations if the block mutual coherence $\mu ({A})$ and sub-coherence $\nu ({A})$ of ${A}$ satisfy $(2K-1)d\mu ({A}) +(d-1) \nu ({A}) In this paper, we first improve and develop sufficient conditions of recovering $\Omega $ with the BOMP algorithm under the $\ell _{2}$ -bounded and $\ell _{\infty }$ -bounded noises, respectively. Then, we show that for any given positive integers $K$ and $d$ , there always exist a block $K$ -sparse vector ${{x}}$ with the block length $d$ , and a sensing matrix ${A}$ with $(2K-1)d\mu ({A}) + (d-1) \nu ({A})=1 $ such that the BOMP is not able to recover ${{x}}$ from ${{y}}= {A} {{x}} $ in $K$ iterations. This indicates that the condition proposed by Eldar et al. is sharp in terms of the condition on ${A}$ .