A New Analysis for Support Performance with Block Generalized Orthogonal Matching Pursuit

Abstract

For recovering block-sparse signals with unknown block structures using compressive sensing, a block orthogonal matching pursuit- (BOMP-) like block generalized orthogonal matching pursuit (BgOMP) algorithm has been proposed recently. This paper focuses on support conditions of recovery of any $\mathbf{K}$-sparse block signals incorporating BgOMP under the framework of restricted isometry property (RIP). The proposed support conditions guarantee that BgOMP can achieve accurate recovery block-sparse signals within $\mathbf{k}$ iterations.

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

The block generalized orthogonal matching pursuit (BgOMP) [1] in compressive sensing (CS) theory has been proposed for recovering block-sparse signals$\mathbf{x}$, in which the signal vector $\mathbf{x}$ has at most $K$ nonzero block elements, and satisfies ${\mathbf{x}}_{\mathrm{2,0}}\le K$ [2–4]. In many practical applications, the signals usually exist in the form of block structure such as pattern recognition [5], aeronautical signal processing [6], and deoxyribonucleic acid (DNA) microarrays [7]. In other words, the nonzero coefficients of sparse signals appear in a few blocks inconsistently [8–10].

The BgOMP algorithm is mainly designated to restore nonzero indexes in the block, containing significant information, rather than restoring each entry in addition to having applications in block-objects detection, such as computer vision and pattern recognition [11]. Based on the previous literature, the main target of this paper is to explore support conditions for the high-accurate recovery of block-sparse signals through the BgOMP algorithm under the framework of restricted isometry property (RIP). The results can prove the bound of BgOMP signal recovery, which provides strong mathematical support for CS algorithm selection in sparse coding, pattern recognition, image reconstruction, and other fields.

2. Preliminaries

Consider the following linear model:$$\begin{array}{}\text{(1)}& \mathbf{Y}=\mathbf{A}\mathbf{x}+\mathbf{v},\end{array}$$where $\mathbf{A}\in {\mathrm{ℝ}}^{M_1\times M_2}$ ($M_1\ll M_2$) is a sensing matrix with normalized columns, $\mathbf{Y}\in {\mathrm{ℝ}}^{M_1\times 1}$ is a measurement vector, and the vector v represents a random noise. Specifically, $\mathbf{x}\in {\mathrm{ℝ}}^{M_2\times 1}$ is a concatenation of blocks $\mathbf{x}i\in {\mathrm{ℝ}}^d$, $1\le i\le L$

For any proper subset $S\subset \mathrm{1,2},\dots ,L$, we define that $\mathbf{A}S$ represents the submatrix of $\mathbf{A}$ which only includes the block index of $S$. Similarly, $\mathbf{x}S$ denotes the subvector of $\mathbf{x}$ which only includes the block index of $S$. A trivial summary of the BgOMP algorithm is described in Algorithm 1. For the sake of uniformity, $\Omega =\text{supp}\mathbf{x}=i|\mathbf{x}i\ne 0$. Signal $\mathbf{x}$ is assumed to be block K-sparse if $\Omega =\text{K}$, where K is a positive integer. In the $k^{\text{th}}$ greedy iterations, the BgOMP algorithm takes $\text{N}$ largest correlations between the residual ${\mathbf{r}}^{k-1}$ and columns of $\mathbf{A}$.

Algorithm 1: Block generalized orthogonal matching pursuit.

  Input: sensing matrix $\mathbf{A}$, measurement vector Y, select $N$ indexes in each iteration, number of blocks L, the number of iterations $t$, and the accuracy of recovery $\epsilon$.

  Initialization:${\mathbf{r}}^0=\mathbf{Y}$, ${\text{S}}_0=\varnothing$.

  Iterate the following steps until stopping criterion $\text{t}>k+1$ or ${\mathbf{r}}^t\le \epsilon$ is met.

  Step 1: $t=t+1$;

  Step 2: $s^t$= set of indices corresponding to the N largest block elements in ${\mathbf{A}}^{T}i{\mathbf{r}}^{t-1}i\in \text{supp}\mathbf{x}$;

  Step 3: $S_t=S_{t-1}\cup s^t$

  Step 4: $\widehat{x}{S}_t=\arg \min \mathbf{Y}-\mathbf{A}{S}_t{\mathbf{x}}_2$;

  Step 5: ${\mathbf{r}}^t=\mathbf{Y}-\mathbf{A}{S}_t\widehat{x}{S}_t$.

  Output: $k=t_{\max }$; $\widehat{x}=\arg {\min }_{\mathbf{x}:\text{supp}\mathbf{x}\subset {\mathbf{S}}_k}{\mathbf{Y}-\mathbf{A}\mathbf{X}}_2$.

3. Analysis of BgOMP

Signals with block property are frequently encountered in practical applications. Given that because of the above background, the purpose of this research is to explore a sufficient condition for the high-accurate recovery of the block-sparse signals by using the BgOMP algorithm in the framework of RIP.

Lemma 1.

If $S$ be a proper subset of $\Omega \ne 0$ and matrix A satisfies block RIP of order $Nk+N+\mathrm{\Omega }-\ell$, for some of $\upsilon \ge 1$ and $N\ge 1$, then$$\begin{array}{}\text{(2)}& {{\mathbf{A}}_{\Omega -S}^T\mathbf{q}S}_{2,\infty }-{{\mathbf{A}}_W^T\mathbf{q}S}_{2,\infty }\ge \frac{1-\sqrt{\nu +1}{\delta }_{Nk+N+\Omega -\ell }{{\mathbf{x}}_{\Omega -S}}_2}{\sqrt{N\nu }},\end{array}$$where $\mathbf{q}S={\mathbf{P}}_S^{†}{\mathbf{A}}_{\Omega -S}{\mathbf{x}}_{\Omega -S}$.

The proof of Lemma 1 has been included in Appendix A.

Theorem 1.

Given any ${\mathbf{v}}_2\le \epsilon$, matrix $\mathbf{A}$ satisfies block RIP with the order $Nk+N+\mathrm{\Omega }-k$. It implies that the successful recovery can be guaranteed, and the support condition of the BgOMP algorithm is satisfied. The following bound of RIP constant can be expressed as$$\begin{array}{}\text{(3)}& {\delta }_{Nk+N+\Omega -k}<\frac{1}{\sqrt{\Omega /N+1}}.\end{array}$$

Also, the minimum of nonzero block elements of $\mathbf{x}$ satisfies the following condition:$$\begin{array}{}\text{(4)}& \underset{i\in \Omega }{\min }{{\mathbf{x}}_i}_2>\frac{2\epsilon }{1-\sqrt{\Omega /N+1}{\delta }_{Nk+N+\Omega -k}}.\end{array}$$

Proof: .

First, we assume that BgOMP chooses the right block indices in $k$ iterations, i.e., $S_k$, which corresponds to ${\mathbf{A}}^{T}i{\mathbf{r}}^{k-1}$. Moreover, we have $S_k=kN$. The notation $\Omega -S_k$ indicates a set with elements belonging to $\Omega$ but not included in $S_k$. Let $\mathrm{\Omega }\cap S_k=\ell$, and we have $\mathrm{\Omega }\cap S_k=\mathrm{\Omega }-\mathrm{\Omega }-S_k\ge k$ and $0<k\le \ell \le \Omega$. In addition, let W be the set of $N$ incorrect indexes indices. Obviously, $W\subset \overline{\Omega \cup S_k}$ and $W=N$. Suppose ${\alpha }_j^k$ denotes the j-th largest correlation between ${\mathbf{r}}^k$ and the columns of $\mathbf{A}$ that belong to the set of incorrect indexes. Also, let ${\beta }_i^k$ denotes the i-th largest correlation between ${\mathbf{r}}^k$ and the columns of ${\mathbf{A}}_{\Omega -S_k}$. Obviously, to prove the support condition of BgOMP, it is equivalent to show that ${\beta }_1^k>{\alpha }_N^k$. Thus, based on Lemma 1 in [7], we can define ${\beta }_1^k$ and ${\alpha }_N^k$ as follows:$$\begin{array}{}\text{(5)}& {\beta }_1^k={{\mathbf{A}}_{\Omega -S_k}^T{\mathbf{r}}^k}_{2,\infty },\text{(6)}& {\alpha }_N^k=\min {\mathbf{A}}_i,r^k,i\in W\le \frac{{{\mathbf{A}}_W^T{\mathbf{r}}^k}_{\mathrm{2,2}}}{\sqrt{N}},\end{array}$$where $\cdot$ represents inner product operator. For the convenience of presentation, we write $\mathbf{A}i$as ${\mathbf{A}}_i$. From the above, it suffices to show that$$\begin{array}{}\text{(7)}& {{\mathbf{A}}_{\Omega -S_k}^T{\mathbf{r}}^k}_{2,\infty }>\frac{{{\mathbf{A}}_W^T{\mathbf{r}}^k}_{\mathrm{2,2}}}{\sqrt{N}}.\end{array}$$

Hence, we can obtain with a least square estimation as follows:$$\begin{array}{}\text{(8)}& {\widehat{x}}_{S_k}={{\mathbf{A}}_{S_k}^T{\mathbf{A}}_{S_k}}^{-1}{\mathbf{A}}_{S_k}^T\mathbf{Y}\end{array}$$

Then, by step 5 of Algorithm 1 and (8), we have$$\begin{array}{}\text{(9)}& {\mathbf{r}}^k=\mathbf{Y}-{\mathbf{A}}_{S_k}{\widehat{x}}_{S_k}=\mathbf{I}-{\mathbf{A}}_{S_k}{{\mathbf{A}}_{S_k}^T{\mathbf{A}}_{S_k}}^{-1}{\mathbf{A}}_{S_k}^T\mathbf{Y}\stackrel{a}{=}{\mathbf{P}}_{S_k}^{†}{\mathbf{A}}_{\Omega }{\mathbf{x}}_{\Omega }+\mathbf{v}\stackrel{b}{=}{\mathbf{P}}_{S_k}^{†}{\mathbf{A}}_{\Omega -S_k}{\mathbf{x}}_{\Omega -S_k}+{\mathbf{P}}_{S_k}^{†}\mathbf{v},\end{array}$$Where (a) is from the definition of ${\mathbf{P}}_{S_k}^{†}=\mathbf{I}-{\mathbf{A}}_{S_k}{{\mathbf{A}}_{S_k}^T{\mathbf{A}}_{S_k}}^{-1}{\mathbf{A}}_{S_k}^T$ and (b) follows from the fact that ${\mathbf{P}}_{S_k}^{†}{\mathbf{A}}_{S_k}=0$. Thus, on the left-hand side of (7), we obtain a lower bound as$$\begin{array}{}\text{(10)}& {{\mathbf{A}}_{\Omega -S_k}^T{\mathbf{r}}^k}_{2,\infty }\ge {{\mathbf{A}}_{\Omega -S_k}^T{\mathbf{P}}_{S_k}^{†}{\mathbf{A}}_{\Omega -S_k}{\mathbf{x}}_{\Omega -S_k}}_{2,\infty }-{{\mathbf{A}}_{\Omega -S_k}^T{\mathbf{P}}_{S_k}^{†}\mathbf{v}}_{2,\infty }.\end{array}$$

Similarly, it is easy to obtain an upper bound with the right-hand side of (7):$$\begin{array}{}\text{(11)}& \frac{{{\mathbf{A}}_W^T{\mathbf{r}}^k}_{\mathrm{2,2}}}{\sqrt{N}}\le {{\mathbf{A}}_W^T{\mathbf{r}}^k}_{2,\infty }\le {{\mathbf{A}}_W^T{\mathbf{P}}_{S_k}^{†}{\mathbf{A}}_{\Omega -S_k}{\mathbf{x}}_{\Omega -S_k}}_{2,\infty }+{{\mathbf{A}}_W^T{\mathbf{P}}_{S_k}^{†}\mathbf{v}}_{2,\infty }\end{array}$$

Integrating (7), (10), and (11), we show that$$\begin{array}{c}\text{(12)}& {{\mathbf{A}}_{\Omega -S_k}^T{\mathbf{P}}_{S_k}^{†}{\mathbf{A}}_{\Omega -S_k}{\mathbf{x}}_{\Omega -S_k}}_{2,\infty }-{{\mathbf{A}}_{W_k}^T{\mathbf{P}}_{S_k}^{†}{\mathbf{A}}_{\Omega -S_k}{\mathbf{x}}_{\Omega -S_k}}_{2,\infty }>{{\mathbf{A}}_{\Omega -S_k}^T{\mathbf{P}}_{S_k}^{†}\mathbf{v}}_{2,\infty }+{{\mathbf{A}}_W^T{\mathbf{P}}_{S_k}^{†}\mathbf{v}}_{2,\infty }.\end{array}$$

In the following, with the aim of Lemma 1, we derive a lower bound of (12):$$\begin{array}{c}\text{(13)}& {{\mathbf{A}}_{\Omega -S_k}^T{\mathbf{P}}_{S_k}^{†}{\mathbf{A}}_{\Omega -S_k}{\mathbf{x}}_{\Omega -S_k}}_{2,\infty }-{{\mathbf{A}}_W^T{\mathbf{P}}_{S_k}^{†}{\mathbf{A}}_{\Omega -S_k}{\mathbf{x}}_{\Omega -S_k}}_{2,\infty }\ge \frac{1-\sqrt{\Omega -\ell /N+1}{\delta }_{Nk+N+\Omega -\ell }{{\mathbf{x}}_{\Omega -S_k}}_2}{\sqrt{\Omega -\ell }}.\end{array}$$

By assumption $\Omega \cap S_k=\ell$, we have$$\begin{array}{}\text{(14)}& {{\mathbf{x}}_{\Omega -S_k}}_2\ge \sqrt{\Omega -\ell }\underset{i\in \Omega -S_k}{\min }{{\mathbf{x}}_i}_2\ge \sqrt{\Omega -\ell }\underset{i\in \Omega }{\min }{{\mathbf{x}}_i}_2.\end{array}$$

Using (13) and (14), it is trivial to have$$\begin{array}{c}\text{(15)}& {{\mathbf{A}}_{\Omega -S_k}^T{\mathbf{P}}_{S_k}^{†}{\mathbf{A}}_{\Omega -S_k}{\mathbf{x}}_{\Omega -S_k}}_{2,\infty }-{{\mathbf{A}}_{W-S_k}^T{\mathbf{P}}_{S_k}^{†}{\mathbf{A}}_{\Omega -S_k}{\mathbf{x}}_{\Omega -S_k}}_{2,\infty }\ge 1-\sqrt{\Omega -\ell /N+1}{\delta }_{Nk+N+\Omega -\ell }\underset{i\in \Omega }{\min }{{\mathbf{x}}_i}_2\\ \stackrel{a}{\ge }1-\sqrt{\Omega -k/N+1}{\delta }_{Nk+N+\Omega -k}\underset{i\in \Omega }{\min }{{\mathbf{x}}_i}_2,\end{array}$$where (a) denotes the fact that $0<k\le \ell$ from Lemma 2 in [12, 13]. Then, we reach the following equivalence that$$\begin{array}{c}\text{(16)}& {{\mathbf{A}}_{\Omega -S_k}^T{\mathbf{P}}_{S_k}^{†}\mathbf{v}}_{2,\infty }+{{\mathbf{A}}_W^T{\mathbf{P}}_{S_k}^{†}\mathbf{v}}_{2,\infty }={{\mathbf{A}}_{i_0}^T{\mathbf{P}}_{S_k}^{†}\mathbf{v}}_2+{{\mathbf{A}}_{j_0}^T{\mathbf{P}}_{S_k}^{†}\mathbf{v}}_2={{\mathbf{A}}_{i_0\cup j_0}^T{\mathbf{P}}_{S_k}^{†}\mathbf{v}}_{\mathrm{2,1}}\\ \stackrel{a}{\le }\sqrt{2}{{\mathbf{A}}_{i_0\cup j_0}^T{\mathbf{P}}_{S_k}^{†}\mathbf{v}}_2\stackrel{b}{\le }\sqrt{21+{\delta }_{Nk+N+\Omega -\ell }}{{\mathbf{P}}_{S_k}^{†}\mathbf{v}}_2\\ \stackrel{c}{\le }\sqrt{21+{\delta }_{Nk+N+\Omega -\ell }}\epsilon ,\end{array}$$where $i_0\in \mathrm{\Omega }-S_k,j_0\in W$. (a) is because ${\mathbf{A}}_{i_0\cup j_0}^T{\mathbf{P}}_{S_k}^{†}\mathbf{v}$ is a $2\times 1$ block vector and the property of norm ${\mathbf{X}}_1\le \sqrt{n}{\mathbf{X}}_2$; (b) is reduced to (3) in [14]; and (c) follows from$$\begin{array}{}\text{(17)}& {{\mathbf{P}}_{S_k}^{†}\mathbf{v}}_2\le {{\mathbf{P}}_{S_k}^{†}}_2{\mathbf{v}}_2\le {\mathbf{v}}_2\le \epsilon .\end{array}$$With (15) and (16), we reach that$$\begin{array}{c}\text{(18)}& 1-\sqrt{\Omega -k/N+1}{\delta }_{Nk+N+\Omega -k}\underset{i\in \Omega }{\min }{{\mathbf{x}}_i}_2>\sqrt{21+{\delta }_{Nk+N+\Omega -\ell }}\epsilon \underset{i\in \Omega }{\min }{{\mathbf{x}}_i}_2>\frac{\sqrt{21+{\delta }_{Nk+N+\Omega -\ell }}\epsilon }{1-\sqrt{\Omega -k/N+1}{\delta }_{Nk+N+\Omega -k}}.\end{array}$$

We rearrange (18) as follows:$$\begin{array}{}\text{(19)}& \underset{i\in \Omega }{\min }{{\mathbf{x}}_i}_2>\frac{2\epsilon }{1-\sqrt{\Omega /N+1}{\delta }_{Nk+N+\Omega -k}}.\end{array}$$

Because of the constant ${\delta }_{Nk+N+\mathrm{\Omega }-\ell }\in \mathrm{0,1}$, the RIC bound of the BgOMP algorithm can be represented as$$\begin{array}{}\text{(20)}& {\delta }_{Nk+N+\Omega -k}<\frac{1}{\sqrt{\Omega /N+1}}.\end{array}$$

Thus, we complete the proof.

Theorem 2.

Let a matrix $\mathbf{A}$ satisfy the block RIP with the order $Nk+N+\mathrm{\Omega }-k$ and the RIC bound of BgOMP meet the condition in (20). Otherwise, the BgOMP algorithm fails to recover the block signals $\mathbf{x}$.

Proof.

For some $N\ge 1$ and $0<k\le \Omega$, we have$$\begin{array}{}\text{(21)}& {\delta }_{Nk+N+\Omega -k}<\frac{1}{\sqrt{Nk+N+\Omega -k}}\le \frac{1}{\sqrt{\Omega /N+1}}.\end{array}$$

Hence, let ${\delta }_{Nk+N+\mathrm{\Omega }-k}=\delta$ and Theorem 2 is equivalent to prove the following inequivalence:$$\begin{array}{}\text{(22)}& \frac{1}{\sqrt{Nk+N+\Omega -k}}\le \delta <1.\end{array}$$

The BgOMP algorithm fails to recover $\mathbf{x}$.

The preparatory work: for any $\lambda =Nk+N+\mathrm{\Omega }-k-1\ge 1$, $\lambda$ is a positive integer. Let us define a matrix function as$$\begin{array}{}\text{(23)}& \mathbf{B}d=\begin{array}{cc}\frac{\lambda }{\lambda +1}{\mathbf{I}}_{d\lambda }& \frac{{\mathbf{E}}_{d\lambda \times d}}{\lambda +1}\\ \frac{E_{d\times d\lambda }}{\lambda +1}& \frac{\lambda +2}{\lambda +1}{\mathbf{I}}_d\end{array},\end{array}$$where ${\mathbf{E}}_{d\lambda \times d}={\mathbf{I}}_d,\cdots {\mathbf{I}}_d\in {\mathrm{ℝ}}^{d\lambda \times d}$, with ${\mathbf{I}}_{\text{d}}$ being the $d\times d$ identity matrix. Meanwhile, we define a constant $s$ and matrix $\mathbf{C}d$ as$$\begin{array}{}\text{(24)}& s=\delta -\frac{1}{\sqrt{Nk+N+\Omega -k}},\mathbf{C}d=\mathbf{B}d-s{\mathbf{I}}_{\lambda +1d}.\end{array}$$

In the following, we divide the proof into two steps:

  Step 1. We plan to prove that $\mathbf{C}d$ is a symmetric positive matrix. Therefore, $\mathbf{C}d$ can be transformed into matrix ${\mathbf{A}}^{T}d\mathbf{A}d$ by Doolittle decomposition, and then, we can ensure that $\mathbf{A}d$ satisfies the block RIP of order $\text{N}k+\text{N}+\Omega -k$ with ${\delta }_{Nk+N+\mathrm{\Omega }-k}=\delta$. In order not to steal the attention of the main proof, we prove Step 1 in Appendix B.

  Step 2. Next, we show that BgOMP fails to recover $\mathbf{x}={1_d^T,1_d^T\cdots 1_d^T}^T\in {\mathrm{ℝ}}^{d\lambda }$ with all of its entries being 1. Without loss of generality,$\mathbf{x}$ can be extended to $\mathbf{x}d={1_d^T,\cdots 1_d^T,0_d^T}^T\in {\mathrm{ℝ}}^{d\lambda +1}$. Integrating (23),$\mathbf{Y}d=\mathbf{A}d\mathbf{x}d$ and $\mathbf{C}d={\mathbf{A}}^{T}d\mathbf{A}d$.

$$\begin{array}{c}\text{(25)}& {{\mathbf{A}d\lambda +1}^T\mathbf{Y}d}_2={{\mathbf{A}d\lambda +1}^T\mathbf{A}d\mathbf{x}d}_2={{0_{d\lambda \times d},{\mathbf{I}}_d}^T\mathbf{C}d\mathbf{x}d}_2\\ ={\frac{1}{\lambda +1}{\mathbf{E}}_{d\times d\lambda },\frac{\lambda +2}{\lambda +1}-s{\mathbf{I}}_d\mathbf{x}d}_2\\ =\frac{\lambda \sqrt{d}}{\lambda +1}.\end{array}$$

Similarly,$$\begin{array}{c}\text{(26)}& {{\mathbf{A}di}^T\mathbf{Y}d}_2={{\mathbf{A}di}^T\mathbf{A}d\mathbf{x}d}_2={{0_{i-1\lambda \times d},{\mathbf{I}}_d,0_{d+1-i\lambda \times d}}^T\mathbf{C}d\mathbf{x}d}_2\\ =\frac{\lambda \sqrt{d}}{\lambda +1}-s\sqrt{d},\end{array}$$where $1\le i\le \lambda$. By (25) and (26), since$s\ge 0$, we notice that$$\begin{array}{}\text{(27)}& {{\mathbf{A}d\lambda +1}^T\mathbf{Y}d}_2\ge {{\mathbf{A}di}^T\mathbf{Y}d}_2.\end{array}$$

Therefore, in the first iteration, BgOMP will choose the position of $0_d^T$ in which $\mathbf{x}d$ is selected as the indexes; this goes against our hypothesis. By (25) and (26), to guarantee successful recovery, $\mathbf{x}$must satisfy $s<0$; that is, $\delta <1/\sqrt{Nk+N+\Omega -k}\le 1/\sqrt{\Omega /N+1}$.

Theorem 3 can give sufficient condition of BOMP under the framework of RIP. Interestingly, by the established result, one can easily see that the support condition of BOMP is as restrictive as BgOMP when N equals 1; at this point, BgOMP degenerates into BOMP. But as N increases, the support condition given by (4) slacks gradually. Figure 1 compares the RIC of two algorithms. We observe that the RIC of BgOMP is significantly less restrictive than BOMP. Therefore, by suitable exploitation of RIP, a successful signal recovery scheme for BgOMP was obtained.

[figure omitted; refer to PDF]

4. Conclusion

In this paper, the support conditions of recovery block-sparse signals by using BgOMP are proposed; the bound of RIP constant must satisfy $1/\sqrt{\Omega /N+1}$, otherwise it may cause recovery failure. And, we have presented a sufficient condition, which is weaker than BOMP, for the exact support recovery of block K-sparse signals with K iterations of BgOMP.

Acknowledgments

The authors thank 2-nd Research Institute, Civil Aviation Administration of China. Furthermore, this work was supported by the Science and Technology Bureau of Sichuan Province, under Grant no. 2020YFG0414.

Appendix

Appendix

A

Proof.

To prove Lemma 1, it is equivalent to the following two steps. In the first step, for some of $v\ge 1$, we denote$$\begin{array}{}\text{(A.1)}& \sqrt{v}{{\mathbf{x}}_{\Omega -S_k}}_2{{\mathbf{A}}_{\Omega -S_k}^T\mathbf{q}{s}_k}_{2,\infty }\ge {\mathbf{q}{s}_k}_2^2.\end{array}$$

We have each $j\in W$, in the second step, to prove$$\begin{array}{c}\text{(A.2)}& {\mathbf{q}{s}_k}_2^2-\sqrt{v}{{\mathbf{x}}_{\Omega -S_k}}_2{{\mathbf{A}}^{T}j\mathbf{q}{s}_k}_2\ge 1-\sqrt{v+1}{\delta }_{Nk+N+\Omega -k}{{\mathbf{x}}_{\Omega -S_k}}_2^2.\end{array}$$

By (A.1), it suffices to show$$\begin{array}{c}\text{(A.3)}& \sqrt{v}{{\mathbf{x}}_{\Omega -S_k}}_2{{\mathbf{A}}_{\Omega -S_k}^T\mathbf{q}{s}_k}_{2,\infty }\ge {{\mathbf{x}}_{\Omega -S_k}}_2{{\mathbf{A}}_{\Omega -S_k}^T\mathbf{q}{s}_k}_{2,\infty }\stackrel{a}{=}{\displaystyle \sum _{f\in \Omega -S_k}{{\mathbf{x}}_f}_2}{{\mathbf{A}}_{\Omega -S_k}^T\mathbf{q}{s}_k}_{2,\infty }\stackrel{b}{\le }{\displaystyle \sum _{f\in \Omega -S_k}{{\mathbf{x}}_f}_2}{{\mathbf{A}}_f^T\mathbf{q}{s}_k}_{2,\infty }\\ \stackrel{c}{\ge }{\displaystyle \sum _{f\in \Omega -S_k}{\mathbf{x}}_f^T{\mathbf{A}}_f^T\mathbf{q}{s}_k}={{\mathbf{A}}_{\Omega -S_k}{\mathbf{x}}_{\Omega -S_k}}^T\mathbf{q}{s}_k\\ \stackrel{d}{=}{{\mathbf{P}}_{S_k}^{†}{\mathbf{A}}_{\Omega -S_k}{\mathbf{x}}_{\Omega -S_k}}^T{\mathbf{P}}_{S_k}^{†}{\mathbf{A}}_{\Omega -S_k}{\mathbf{x}}_{\Omega -S_k}={{\mathbf{P}}_{S_k}^{†}{\mathbf{A}}_{\Omega -S_k}{\mathbf{x}}_{\Omega -S_k}}_2^2={\mathbf{q}{s}_k}_2^2,\end{array}$$where (a) follows from Lemma 1 in [7]; (b) is according to the fact that ${\mathbf{A}}_{\Omega -S_k}^T\mathbf{q}{s}_{2,\infty }\ge {\mathbf{A}}_f^T\mathbf{q}{s}_2$; (c) is from Cauchy–Schwarz inequality; and (d) follows from the definition of $\mathbf{q}\text{s}$ in Lemma 1. Next, we shall prove the second step, might as well set $v=\Omega -\ell /N$, it is not difficult to see that satisfaction $v\ge 1$. Let $\eta =-\sqrt{v+1}-1/v$, and by a simple calculation, we obtain$$\begin{array}{}\text{(A.4)}& \frac{2\eta }{1-{\eta }^2}=-\sqrt{v},\frac{1+{\eta }^2}{1-{\eta }^2}=\sqrt{v+1}.\end{array}$$

To simplify the expression, let us define$$\begin{array}{}\text{(A.5)}& h_i=\frac{{\mathbf{A}j}_i^T\mathbf{q}{s}_k}{{{\mathbf{A}}^{T}j\mathbf{q}{s}_k}_2},\hspace{1em}1\le i\le d.\end{array}$$

The above equation satisfies ${\mathbf{h}}_2=1$ and ${\mathbf{h}}^T{\mathbf{A}}^{T}j\mathbf{q}{\text{s}}_k={\mathbf{A}}^{T}j\mathbf{q}{{\text{s}}_k}_2$. Moreover, we define$$\begin{array}{}\text{(A.6)}& \mathbf{u}=\begin{array}{c}{\mathbf{x}}_{\Omega -S_k}\\ 0\end{array}\in {\mathrm{ℝ}}^{\Omega -S_{k}d+Nd},\mathbf{F}=\begin{array}{c}0\\ \eta {{\mathbf{x}}_{\Omega -S_k}}_2\mathbf{h}\end{array}\in {\mathrm{ℝ}}^{\Omega -S_{k}d+Nd},\text{(A.7)}& \mathbf{B}={\mathbf{P}}_{S_k}^{†}\begin{array}{cc}{\mathbf{A}}_{\Omega -S_k}& \mathbf{q}{s}_k\end{array}.\end{array}$$

Then, it is not hard to see that$$\begin{array}{}\text{(A.8)}& \mathbf{q}{s}_k={\mathbf{P}}_{S_k}^{†}{\mathbf{A}}_{\Omega -S_k}{\mathbf{x}}_{\Omega -S_k}=\mathbf{B}\mathbf{u}\end{array}$$and$$\begin{array}{}\text{(A.9)}& {\mathbf{u}+\mathbf{F}}_2^2=1+{\eta }^2{{\mathbf{x}}_{\Omega -S_k}}_2^2,\text{(A.10)}& {{\eta }^2\mathbf{u}-\mathbf{F}}_2^2=1+{\eta }^2{\eta }^2{{\mathbf{x}}_{\Omega -S_k}}_2^2.\end{array}$$

Furthermore, we have$$\begin{array}{c}\text{(A.11)}& {\mathbf{F}}^T{\mathbf{B}}^T\mathbf{B}\mathbf{u}=\eta {{\mathbf{x}}_{\Omega -S_k}}_2{\mathbf{h}}^T{\mathbf{A}}^{T}j{{\mathbf{P}}_{S_k}^{†}}^T\mathbf{q}{s}_k\stackrel{a}{=}\eta {{\mathbf{x}}_{\Omega -S_k}}_2{\mathbf{h}}^T{\mathbf{A}}^{T}j\mathbf{q}{s}_k\\ \stackrel{b}{=}{{\mathbf{x}}_{\Omega -S_k}}_2{{\mathbf{A}}^{T}j\mathbf{q}{s}_k}_2,\end{array}$$where (a) follows from Lemma 3 in [14] and (b) is because ${\mathbf{h}}^T{\mathbf{A}}^{T}j\mathbf{q}{\text{s}}_k={\mathbf{A}}^{T}j\mathbf{q}{{\text{s}}_k}_2$. On the one hand,$$\begin{array}{c}\text{(A.12)}& {\mathbf{B}\mathbf{u}+\mathbf{F}}_2^2-{\mathbf{B}{\eta }^2\mathbf{u}-\mathbf{F}}_2^2\stackrel{a}{\ge }1-{\delta }_{Nk+N+\Omega -\ell }{\mathbf{u}+\mathbf{F}}_2^2-1+{\delta }_{Nk+N+\Omega -\ell }{{\eta }^2\mathbf{u}-\mathbf{F}}_2^2\\ \stackrel{b}{=}1-{\delta }_{Nk+N+\Omega -\ell }1+{\eta }^2{{\mathbf{x}}_{\Omega -S_k}}_2^2-1+{\delta }_{Nk+N+\Omega -\ell }{\eta }^4+{\eta }^2{{\mathbf{x}}_{\Omega -S_k}}_2^2\\ =1-{\eta }^4{{\mathbf{x}}_{\Omega -S_k}}_2^{2}1-\frac{1+{\eta }^2}{1-{\eta }^2}{\delta }_{Nk+N+\Omega -\ell }\\ \stackrel{c}{=}1-{\eta }^4{{\mathbf{x}}_{\Omega -S_k}}_2^{2}1-\sqrt{v+1}{\delta }_{Nk+N+\Omega -\ell },\end{array}$$where steps (a) and (b) are derived from equations (36) and (37), respectively; and (c) is because of (A.4). On the other hand, we have$$\begin{array}{c}\text{(A.13)}& {\mathbf{B}\mathbf{u}+\mathbf{F}}_2^2-{\mathbf{B}{\eta }^2\mathbf{u}-\mathbf{F}}_2^2\stackrel{a}{\le }{{\mathbf{B}\mathbf{u}}_2+{\mathbf{B}\mathbf{F}}_2}^2-{{\eta }^2{\mathbf{B}\mathbf{u}}_2-{\mathbf{B}\mathbf{F}}_2}^2\\ =1-{\eta }^4{\mathbf{B}\mathbf{u}}_2+21+{\eta }^2{\mathbf{F}}^T{\mathbf{B}}^T\mathbf{B}\mathbf{u}\\ \stackrel{b}{=}1-{\eta }^4{\mathbf{B}\mathbf{u}}_2+2\eta 1+{\eta }^2{{\mathbf{x}}_{\Omega -S_k}}_2{{\mathbf{A}}^{T}j\mathbf{q}{s}_k}_2\\ =1-{\eta }^4{\mathbf{B}\mathbf{u}}_2+\frac{2\eta }{1-{\eta }^2}{{\mathbf{x}}_{\Omega -S_k}}_2{{\mathbf{A}}^{T}j\mathbf{q}{s}_k}_2\\ \stackrel{c}{=}1-{\eta }^4{\mathbf{B}\mathbf{u}}_2-\sqrt{v}{{\mathbf{x}}_{\Omega -S_k}}_2{{\mathbf{A}}^{T}j\mathbf{q}{s}_k}_2,\end{array}$$where (a) follows from trigonometric inequality; (b) is from (A.11); and (c) is because of (A.4). Integrating (A.12) and (A.13), we can obtain$$\begin{array}{}\text{(A.14)}& {\mathbf{B}\mathbf{u}}_2-\sqrt{v}{{\mathbf{x}}_{\Omega -S_k}}_2{{\mathbf{A}}^{T}j\mathbf{q}{s}_k}_2\ge {{\mathbf{x}}_{\Omega -S_k}}_2^{2}1-\sqrt{v+1}{\delta }_{Nk+N+\Omega -\ell }.\end{array}$$

Since (A.3) and (A.8), it is easy to see that$$\begin{array}{c}\text{(A.15)}& \sqrt{v}{{\mathbf{x}}_{\Omega -S_k}}_2{{\mathbf{A}}_{\Omega -S_k}^T\mathbf{q}{s}_k}_{2,\infty }-\sqrt{v}{{\mathbf{x}}_{\Omega -S_k}}_2{{\mathbf{A}}^{T}j\mathbf{q}{s}_k}_2\ge {{\mathbf{x}}_{\Omega -S_k}}_2^{2}1-\sqrt{v+1}{\delta }_{Nk+N+\Omega -\ell }.\end{array}$$

For given $j\in W$ and $\text{N}\ge 1$, we have$$\begin{array}{c}\text{(A.16)}& {{\mathbf{A}}_{\Omega -S_k}^T\mathbf{q}{s}_k}_{2,\infty }-{{\mathbf{A}}_W^T\mathbf{q}{s}_k}_{2,\infty }\ge \frac{1-\sqrt{v+1}{\delta }_{Nk+N+\Omega -\ell }{{\mathbf{x}}_{\Omega -S_k}}_2}{\sqrt{v}}\\ \ge \frac{1-\sqrt{v+1}{\delta }_{Nk+N+\Omega -\ell }{{\mathbf{x}}_{\Omega -S_k}}_2}{\sqrt{Nv}},\end{array}$$which is Lemma 1. Hence, we complete the proof.

B

It is quite straightforward that $\mathbf{B}d$ is a symmetric matrix. To calculate the range of eigenvalue, let ${\text{u}}_i=v_i=\mathbf{x}{i}_2$ for $1\le i\le \lambda$ and $u_{\lambda +1}=-v_{\lambda +1}=\mathbf{x}{\lambda +1}_2$; then,$$\begin{array}{c}\text{(B.1)}& {\mathbf{x}}^T\mathbf{B}d\mathbf{x}=\frac{\lambda }{\lambda +1}{\displaystyle \sum _{i=1}^{\lambda }{\mathbf{x}}^{T}i\mathbf{x}i+\frac{\lambda +2}{\lambda +1}{\mathbf{x}}^T\lambda +1\mathbf{x}\lambda +1}+\frac{2}{\lambda +1}{\displaystyle \sum _{i=1}^{\lambda }{\mathbf{x}}^{T}i\mathbf{x}\lambda +1}\\ \le \frac{\lambda }{\lambda +1}{\displaystyle \sum _{i=1}^{\lambda }{{\mathbf{x}}^{T}i}_2^2+\frac{\lambda +2}{\lambda +1}{{\mathbf{x}}^T\lambda +1}_2^2}\\ +\frac{2}{\lambda +1}{\displaystyle \sum _{i=1}^{\lambda }{{\mathbf{x}}^{T}i}_2{{\mathbf{x}}^T\lambda +1}_2}\\ ={\mathbf{u}}^T\mathbf{B}1\mathbf{u}\le 1+\frac{1}{\sqrt{\lambda +1}}{\mathbf{u}}_2^2=1+\frac{1}{\sqrt{\lambda +1}}{\mathbf{x}}_2^2.\end{array}$$

Similarly, we have$$\begin{array}{}\text{(B.2)}& {\mathbf{x}}^T\mathbf{B}d\mathbf{x}={\mathbf{v}}^T\mathbf{B}1\mathbf{v}\ge 1-\sqrt{\frac{1}{\lambda +1}}{\mathbf{x}}_2^2.\end{array}$$

Integrating (24), (B.1), and (B.2), for any $\mathbf{x}$,$$\begin{array}{}\text{(B.3)}& 1-\frac{1}{\sqrt{\lambda +1}}{\mathbf{x}}_2^2\le {\mathbf{x}}^T\mathbf{B}d\mathbf{x}\le 1+\frac{1}{\sqrt{\lambda +1}}{\mathbf{x}}_2^2,\text{(B.4)}& 1-\delta {\mathbf{x}}_2^2\le {\mathbf{x}}^T\mathbf{C}d\mathbf{x}\le 1+\frac{2}{\sqrt{\lambda +1}}-\delta {\mathbf{x}}_2^2.\end{array}$$

It is not hard to see that ${\mathbf{x}}^T\mathbf{C}d\mathbf{x}>0$ from (B.4). Thus, we prove $\mathbf{C}d$ is the symmetric positive matrix. Also, $\mathbf{C}d$ can transform matrix ${\mathbf{A}}^{T}d\mathbf{A}d$ by Doolittle decomposition; that is, $\mathbf{C}d={\mathbf{A}}^{T}d\mathbf{A}d$. By (24), we will have$$\begin{array}{}\text{(B.5)}& {\mathbf{A}d\mathbf{x}}_2^2={\mathbf{x}}^T\mathbf{C}d\mathbf{x}={\mathbf{x}}^T\mathbf{B}\text{d}-s{\mathbf{I}}_{\lambda +1\text{d}}\mathbf{x}.\end{array}$$

Integrating (22) and (B.3), by some simple calculations, we can show that$$\begin{array}{}\text{(B.6)}& 1-\delta {\mathbf{x}}_2^2\le {\mathbf{A}d\mathbf{x}}_2^2\le 1+\frac{2}{\sqrt{\lambda +1}}-\delta {\mathbf{x}}_2^2\le 1+\delta {\mathbf{x}}_2^2.\end{array}$$

From Definition 2 in [7], we can ensure that $\mathbf{A}d$ satisfies the block RIP of order $Nk+N+\mathrm{\Omega }-k$ with ${\delta }_{Nk+N+\mathrm{\Omega }-k}=\delta$.

This completes the proof.

C

This mainly researches the satisfactory performance of support reconstructs of $\mathbf{x}$ by using the BgOMP. To be specific, we compare Theorem 1 with BOMP sufficient condition (Theorem 3), which is expressed as follows.

Theorem 3.

(see [7, 9]). Suppose that in (1), ${\mathbf{v}}_2\le \epsilon$. Then, the BOMP algorithm can accurately reconstruct the support $\Omega$ and when the number of iterations is $k$, the iteration stop condition is satisfied:$$\begin{array}{}\text{(C.1)}& \underset{i\in \Omega }{\min }{{\mathbf{x}}_i}_2>\frac{2\epsilon }{1-\sqrt{\Omega +1}{\delta }_{k+1}}.\end{array}$$

The matrix A satisfies the block RIP of order $\Omega +1$, if there is a smallest constant ${\delta }_{k+1}\in \mathrm{0,1}$ which is defined as the restricted isometry constant (RIC). Therefore, the RIC bound of block-sparse vector $\mathbf{x}$ of BOMP is$$\begin{array}{}\text{(C.2)}& {\delta }_{k+1}<\frac{1}{\sqrt{\Omega +1}}.\end{array}$$

References

[1] A. Manoj, A. P. Kannu, "Sinusoid signal estimation using generalized block orthogonal matching pursuit algorithm," Proceedings of the 2018 International Conference on Signal Processing and Communications (SPCOM), pp. 60-64, .

[2] C. Y. Xia, Y. X. Gao, J. Yu, "Block-sparse signal recovery based on orthogonal matching pursuit via stage-wise weak selection," Signal, Image and Video Processing, vol. 14 no. 12, 2020.

[3] C. Ye, G. Gui, L. Xu, T. Ohtsuki, "Recovery of block-structured sparse signal using block-sparse adaptive algorithms via dynamic grouping," IEEE Access, vol. 6, pp. 56069-56083, DOI: 10.1109/access.2018.2872671, 2018.

[4] E. Crespo Marques, N. Maciel, L. Naviner, H. Cai, J. Yang, "A review of sparse recovery algorithms," IEEE Access, vol. 7, pp. 1300-1322, DOI: 10.1109/access.2018.2886471, 2019.

[5] J. Fang, Y. Shen, H. Li, P. Wang, "Pattern-coupled sparse Bayesian learning for recovery of block-sparse signals," IEEE Transactions on Signal Processing, vol. 63 no. 2, pp. 360-372, DOI: 10.1109/tsp.2014.2375133, 2015.

[6] C. Ye, G. Gui, S.-Y. Matsushita, L. Xu, "Block sparse signal reconstruction using block-sparse adaptive filtering algorithms," Journal of Advanced Computational Intelligence and Intelligent Informatics, vol. 20 no. 7, pp. 1119-1126, DOI: 10.20965/jaciii.2016.p1119, 2016.

[7] H. Li, J. Wen, "A new analysis for support recovery with block orthogonal matching pursuit," IEEE Signal Processing Letters, vol. 26 no. 2, pp. 247-251, DOI: 10.1109/lsp.2018.2885919, 2019.

[8] J. Wen, H. Chen, Z. Zhou, "An optimal condition for the block orthogonal matching pursuit algorithm," IEEE Access, vol. 6, pp. 38179-38185, DOI: 10.1109/access.2018.2853158, 2018.

[9] J. Wen, Z. Zhou, Z. Liu, M.-J. Lai, X. Tang, "Sharp sufficient conditions for stable recovery of block sparse signals by block orthogonal matching pursuit," Applied and Computational Harmonic Analysis, vol. 47 no. 3, pp. 948-974, DOI: 10.1016/j.acha.2018.02.002, 2019.

[10] H. Ge, L. Wang, J. Wen, J. Xian, "An RIP condition for exact support recovery with covariance-assisted matching pursuit," IEEE Signal Processing Letters, vol. 26 no. 3, pp. 520-524, DOI: 10.1109/lsp.2019.2896543, 2019.

[11] I. A. Kougioumtzoglou, I. Petromichelakis, A. F. Psaros, "Sparse representations and compressive sampling approaches in engineering mechanics: a review of theoretical concepts and diverse applications," Probabilistic Engineering Mechanics, vol. 61,DOI: 10.1016/j.probengmech.2020.103082, 2020.

[12] S. Satpathi, R. L. Das, M. Chakraborty, "Improving the bound on the RIP constant in generalized orthogonal matching pursuit," IEEE Signal Processing Letters, vol. 20 no. 11, pp. 1074-1077, DOI: 10.1109/lsp.2013.2279977, 2013.

[13] R. Wu, W. Huang, D.-R. Chen, "The exact support recovery of sparse signals with noise via orthogonal matching pursuit," IEEE Signal Processing Letters, vol. 20 no. 4, pp. 403-406, DOI: 10.1109/lsp.2012.2233734, 2013.

[14] D. Park, "Improved sufficient condition for performance guarantee in generalized orthogonal matching pursuit," IEEE Signal Processing Letters, vol. 24 no. 9, pp. 1308-1312, DOI: 10.1109/lsp.2017.2723724, 2017.