Some Results for Exact Support Recovery of Block Joint Sparse Matrix via Block Multiple Measurement Vectors Algorithm

Yingna Pan^*, Pingping Zhang

School of Science, Chongqing University of Posts and Telecommunications, Chongqing, China.

DOI: 10.4236/jamp.2023.114072                

Abstract

Block multiple measurement vectors (BMMV) is a reconstruction algorithm that can be used to recover the support of block K-joint sparse matrix X from Y = ΨX + V. In this paper, we propose a sufficient condition for accurate support recovery of the block K-joint sparse matrix via the BMMV algorithm in the noisy case. Furthermore, we show the optimality of the condition we proposed in the absence of noise when the problem reduces to single measurement vector case.

Keywords

Support Recovery, Compressed Sensing, Block Multiple Measurement Vectors Algorithm, Block Restricted Isometry Property

1. Introduction

Compressed sensing [1] [2] [3] theory is a theoretical method to solve sparse solutions of large underdetermined linear systems, which has received lots of attention in the last decades and it has been applied to many research domains, including signal processing [4] , radar system [5] , medical imaging [6] , image compression [7] and so on. Suppose a signal $x=\left\{x_1\mathrm{,}{x}_2\mathrm{,}\cdots \mathrm{,}{x}_N\right\}\in {ℝ}^N$ , we aim to reconstruct it from linear measurements

$y=\Psi x+v\mathrm{,}$ (1)

where $y\in {ℝ}^M$ is called measurement vector, $\Psi \in {ℝ}^{M\times N}$ denotes a measurement matrix with $M\ll N$ , and $v\in {ℝ}^M$ is the noise vector. Because the signal $x$ we need to reconstruct is a vector, (1) is named as single measurement vector (SMV) model. Since the solution of (1) is not unique, some additional constraints on $\Psi$ and $x$ are needed to reconstruct $x$ uniquely. What we are interested in is that $x$ is sparse. ${\Vert x\Vert }_0$ is the ${\mathcal{l}}_0$ norm. When ${\Vert x\Vert }_0\le K$ , we say signal $x$ is K-sparse. To reconstruct such a signal $x$ from noisy model (1), a intuitive idea is to find a solution of ${\mathcal{l}}_0$ minimization

$\min {\Vert x\Vert }_0\text{s}\text{.t}\mathrm{.}y=\Psi x+v\mathrm{,}$ (2)

where $\Psi$ and $y$ are known. The problem mentioned above is called the SMV problem, and it is also the most common problem model in the field of signal recovery. The optimization problem (2) has a lot of efficient and effective algorithms that use greed strategy to recover $x$ , such as orthogonal matching pursuit (OMP) [8] , stagewise OMP [9] , regularized OMP [10] , compressive sampling matching pursuit [11] , subspace pursuit [12] , generalized OMP (gOMP) [13] , optimized OMP [14] , backtracking-based adaptive OMP [15] , etc. And various researches see [16] [17] [18] .

If the signal we need to recover is not a vector but a matrix $X\in {ℝ}^{N\times H}$ , then model (1) is transformed to multiple measurement vector (MMV) model as follows.

$Y=\Psi X+V\mathrm{,}$ (3)

where $Y\in {ℝ}^{M\times H}$ and $V\in {ℝ}^{M\times H}$ .

In many applications, including reconstruction multiband signals [19] and face recognition [20] , the matrix X has a few nonzero rows with blocks, i.e., we call block joint sparse matrix. In terms of how to measure the block joint sparsity, we can use a series of row blocks to present X. As in [21] and [22] , we assume that each block has the same length and is $d$ . Therefore, for rewriting X, we firstly define

$X\left[j\right]={\left[X_{d\left(j-1\right)+1}^{\text{T}}\mathrm{,}{X}_{d\left(j-1\right)+2}^{\text{T}}\mathrm{,}\cdots \mathrm{,}{X}_{dj-1}^{\text{T}}\mathrm{,}{X}_{dj}^{\text{T}}\right]}^{\text{T}}\mathrm{,}$

for $1\le j\le P$ , where $X_i$ denotes the i-th row of X. Then, X is represented as:

$X={\left[X{\left[1\right]}^{\text{T}}\mathrm{,}X{\left[2\right]}^{\text{T}}\mathrm{,}\cdots \mathrm{,}X{\left[P-1\right]}^{\text{T}}\mathrm{,}X{\left[P\right]}^{\text{T}}\right]}^{\text{T}}\mathrm{.}$

If there are no more than K blocks $X\left[j\right]\ne 0$ in $X\in {ℝ}^{N\times H}$ , X is a block K-joint sparse matrix. The measurement matrix $\Psi$ can be rewritten as:

$\Psi =\left[\Psi \left[1\right]\mathrm{,}\Psi \left[2\right]\mathrm{,}\cdots \mathrm{,}\Psi \left[P-1\right]\mathrm{,}\Psi \left[P\right]\right]\mathrm{,}$

where

$\Psi \left[j\right]=\left[{\Psi }_{d\left(j-1\right)+1}\mathrm{,}{\Psi }_{d\left(j-1\right)+2}\mathrm{,}\cdots \mathrm{,}{\Psi }_{dj-1}\mathrm{,}{\Psi }_{dj}\right]\mathrm{,}$

for $1\le j\le P$ , and ${\Psi }_i$ denotes the i-th column of $\Psi$ .

Thus, to reconstruct X, we turn to solve the following optimization problem, which is called MMV problem.

$\min \left|supp\left(X\right)\right|\text{s}\text{.t}\mathrm{.}Y=\Psi X+V\mathrm{,}$ (4)

where the $supp\left(X\right)=\left\{j\mathrm{<mo>\; |\; </mo>}X\left[j\right]\ne 0\right\}$ represents the set of nonzero blocks.

To discuss the performance of the reconstruction algorithm for solving (2), restricted isometry property (RIP) [23] is very common. Then, to study (4), block RIP (bRIP) as a generalization of RIP was proposed in [24] . Particularly, we say that matrix $\Psi$ obeys the bRIP with parameter ${\delta }_{block}\in \left(\mathrm{0,1}\right)$ if

$\left(1-{\delta }_{block}\right){\Vert \theta \Vert }_2^2\le {\Vert \Psi \theta \Vert }_2^2\le \left(1+{\delta }_{block}\right){\Vert \theta \Vert }_2^2$ (5)

for any block K-sparse vectors $\theta$ . The smallest one among all ${\delta }_{block}$ meeting (5) is called the block restricted isometry constant (bRIC) of A with order K. For simplicity of writing, throughout this paper, we still use ${\delta }_K$ to represents the bRIC whenever there is no confusion.

Based on the MMV algorithm [25] , Fu et al. firstly proposed a new greedy algorithm in [22] , which is called block MMV (BMMV), to recover the block joint sparse matrices by thinking about block joint sparsity. Simply, the BMMV algorithm is a block multiple measurement vectors version of OMP. For $\Gamma \subset \left\{\mathrm{1,2,}\cdots \mathrm{,}P\right\}$ , we use $\left|\Gamma \right|$ to denote the cardinality of $\Gamma$ . Let $\Psi \left[\Gamma \right]\in {ℝ}^{M\times \left|\Gamma \right|}$ denote the submatrix of the vector X whose rows indices are restricted to $\Gamma$ and the submatrix of $\Psi$ that whose columns indices are only restricted to the set $\Gamma$ is denoted by $X\left[\Gamma \right]\in {ℝ}^{\left|\Gamma \right|\times H}$ . The BMMV algorithm selects the block index closest to the residual to add to the estimated support at each iteration. The estimated support is used to solve a least square problem to get the estimated original signal. We present the detailed framework of the BMMV algorithm which is described in Algorithm 1.

Like other signal reconstruction algorithms, many results about performance of recovering block MMV problem via BMMV are studied. It is represented in [22] that if $\Psi$ obeys ${\delta }_{K+1}<\frac{1}{\sqrt{K}+1}$ , then the block K-joint sparse matrices can be accurately reconstructed in K iterations from noiseless model $Y=\Psi X$ by BMMV. In [21] , the condition in [22] was improved to ${\delta }_{K+1}<\frac{1}{\sqrt{K+1}}$ which also is proved to be sharp. As far as we know, there are no researches on support recovery under noisy model (3) with block structure. We complete this part of content that has not yet been studied. It is necessary to study the recovery performance of the BMMV algorithm in noisy case because it is inevitably contaminated by noise in practical applications. Specifically, we firstly prove that if ${\delta }_{K+1}<\frac{1}{\sqrt{K+1}}$ and $\underset{i\in \Omega }{\min }{\Vert X\left[i\right]\Vert }_F>\frac{2\epsilon }{1-\sqrt{K+1}{\delta }_{K+1}}$ , then the BMMV algorithm can perfectly recover $supp\left(X\right)$ with stopping criteria ${\Vert R^k\Vert }_F\le \epsilon$ under ${\Vert V\Vert }_F\le \epsilon$ . Moreover, our sufficient condition is optimal if noisy model degenerates to noiseless model. Besides, when $d=1$ and $H=1$ , the BMMV algorithm turns to the OMP algorithm, and the sufficient condition we mentioned above degenerates to ( [17] , Theorem 1).

2. Preliminaries

2.1. Notation

Let ${\Vert \cdot \Vert }_2$ and ${\Vert \cdot \Vert }_F$ denote the ${\mathcal{l}}_2$ and Frobenius norm of a vector and matrix, respectively. The zero and identity matrix are denoted by $0$ and I, respectively. The j-th element of vector $x$ is denoted by $x_j$ . Let $\Omega =supp\left(X\right)=\left\{j\mathrm{<mo>\; |\; </mo>}{X}^{\text{T}}\left[j\right]\ne 0\right\}$ denotes the support of a matrix X with block structure, then $\left|\Omega \right|\le K$ for any matrix X which is block K-joint sparse, where $X^{\text{T}}\left[j\right]$ denote the transpose of $X\left[j\right]$ . P as the number of blocks of X is assumed for simplity. Let $S_1\backslash S_2$ represents a set which elements are indexed by $S_1$ and are not contained in set $S_2$ for any set $S_1\mathrm{,}{S}_2\subset \left\{\mathrm{1,2,}\cdots \mathrm{,}P\right\}$ . Similarly, we use ${\Omega }^c=\left\{\mathrm{1,2,}\cdots \mathrm{,}P\right\}\backslash \Omega$ and ${\Gamma }^c=\left\{\mathrm{1,2,}\cdots \mathrm{,}P\right\}\backslash \Gamma$ represent the complementary of set $\Omega$ and $\Gamma$ , respectively. Let $\Psi {\left[\Gamma \right]}^{†}={\left(\Psi {\left[\Gamma \right]}^{\text{T}}\Psi \left[\Gamma \right]\right)}^{-1}\Psi {\left[\Gamma \right]}^{\text{T}}$ denotes the pseudoinverse of $\Psi \left[\Gamma \right]$ if the rank of the columns of $\Psi \left[\Gamma \right]$ is full, where the inverse of a square matrix is represented by ${(\cdot )}^{-1}$ . Therefore, the projector and its orthogonal complement on the columns space of $\Psi \left[\Gamma \right]$ can be denoted by $P\left[\Gamma \right]=\Psi \left[\Gamma \right]\Psi {\left[\Gamma \right]}^{†}$ and $P^{\perp }\left[\Gamma \right]=I-P\left[\Gamma \right]$ , respectively.

2.2. Some Useful Lemmas

For proving our subsequent theoretical studies, we first present some useful lemmas for our theoretical analysis.

Lemma 1 ( [26] , Lemma 1) Suppose $\Psi$ obeys both the bRIP of orders $K_1$ and $K_2$ , then ${\delta }_{K_1}\le {\delta }_{K_2}$ with $K_1<K_2$ .

Lemma 2 ( [11] , Proposition 3.1) Suppose $\Gamma$ is a set with $\left|\Gamma \right|\le K$ and $\Psi$ obeys the bRIP of order K. Then

${\Vert {\Psi }^{\text{T}}\left[\Gamma \right]x\Vert }_2\le \left(1+{\delta }_K\right){\Vert x\Vert }_2\mathrm{,}$

where $x\in {ℝ}^M$ .

Lemma 3 ( [26] , Lemma 2) Let $S_1$ and $S_2$ satisfy $\left|S_1\backslash S_2\right|\ge 1$ . Suppose $\Psi$ obeys $\left|S_1\cup S_2\right|$ -order bRIP, then

$\left(1-{\delta }_{\left|S_1\cup S_2\right|}\right){\Vert x\Vert }_2^2\le {\Vert P^{\perp }\left[S_1\right]\Psi \left[S_2\backslash S_1\right]x\Vert }_2^2\le \left(1+{\delta }_{\left|S_1\cup S_2\right|}\right){\Vert x\Vert }_2^2\mathrm{,}$

where $x\in {ℝ}^{\left|S_2\cup S_1\right|}$ .

Lemma 4 ( [27] , Lemma 1) Let $B\in {ℝ}^{m\times n}$ and $D\in {ℝ}^{n\times p}$ . Then

${\Vert BD\Vert }_F^2\le {\Vert D\Vert }_F{\Vert B^{\text{T}}BD\Vert }_F\mathrm{.}$

3. Main Results

Lemma 5 is proposed and plays a very important role in the subsequent theoretical proof.

Lemma 5 Let $\Gamma \subseteq \Omega$ with $\left|\Gamma \right|<\left|\Omega \right|$ , then

$\begin{array}{l}\underset{i\in \Omega \backslash \Gamma }{\max }{\Vert {\Psi }^{\text{T}}\left[i\right]P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X\left[\Omega \backslash \Gamma \right]\Vert }_F\\ -\underset{j\in {\Omega }^c}{\max }{\Vert {\Psi }^{\text{T}}\left[j\right]P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X\left[\Omega \backslash \Gamma \right]\Vert }_F\\ \ge \frac{{\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_F}{\sqrt{\left|\Omega \backslash \Gamma \right|}}\left(1-\sqrt{\left|\Omega \backslash \Gamma \right|+1}{\delta }_{\left|\Omega \right|+1}\right)\mathrm{.}\end{array}$

Proof 1 The skill of proof is similar to the results in ([21, Lemma 4, Lemma 5). To prove Lemma 5, we first show that

$\underset{i\in \Omega \backslash \Gamma }{\max }{\Vert {\Psi }^{\text{T}}\left[i\right]P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X\left[\Omega \backslash \Gamma \right]\Vert }_F\ge \frac{{\Vert P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X\left[\Omega \backslash \Gamma \right]\Vert }_F^2}{\sqrt{\left|\Omega \backslash \Gamma \right|}{\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_F}\mathrm{.}$ (6)

By assumption, it is easy to get $\Gamma \subseteq \Omega$ , $\left|\Gamma \right|<\left|\Omega \right|$ , and ${\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_F\ne 0$ , then

$\begin{array}{l}\underset{i\in \Omega \backslash \Gamma }{\max }{\Vert {\Psi }^{\text{T}}\left[i\right]P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X\left[\Omega \backslash \Gamma \right]\Vert }_F\\ \ge \frac{{\Vert {\Psi }^{\text{T}}\left[\Omega \backslash \Gamma \right]P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X\left[\Omega \backslash \Gamma \right]\Vert }_F}{\sqrt{\left|\Omega \backslash \Gamma \right|}}\\ \stackrel{\text{(i)}}{=}\frac{{\Vert \left(P^{\perp }\left[\Gamma \right]{\Psi }^{\text{T}}\left[\Omega \backslash \Gamma \right]\right)P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X\left[\Omega \backslash \Gamma \right]\Vert }_F}{\sqrt{\left|\Omega \backslash \Gamma \right|}}\\ \stackrel{\text{(ii)}}{\ge }\frac{{\Vert {\mathcal{P}}^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X\left[\Omega \backslash \Gamma \right]\Vert }_F^2}{\sqrt{\left|\Omega \backslash \Gamma \right|}{\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_F}\mathrm{,}\end{array}$

(i) is because

${\left(P^{\perp }\left[\Gamma \right]\right)}^{\text{T}}{P}^{\perp }\left[\Gamma \right]=P^{\perp }\left[\Gamma \right]P^{\perp }\left[\Gamma \right]=P^{\perp }\left[\Gamma \right]\mathrm{,}$ (7)

and (ii) is from Lemma 4 with $B=P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]$ , and $D=X\left[\Omega \backslash \Gamma \right]$ . Thus, (6) holds. So, by (6), we can easily get that

$\begin{array}{l}{\Vert P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X\left[\Omega \backslash \Gamma \right]\Vert }_F^2\\ \le \sqrt{\left|\Omega \backslash \Gamma \right|}{\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_F\underset{i\in \Omega \backslash \Gamma }{\max }{\Vert {\Psi }^{\text{T}}\left[i\right]P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X\left[\Omega \backslash \Gamma \right]\Vert }_F\mathrm{.}\end{array}$ (8)

Let

$\alpha =-\frac{\sqrt{\left|\Omega \backslash \Gamma \right|+1}-1}{\sqrt{\left|\Omega \backslash \Gamma \right|}}\mathrm{,}$

then, by some sample calculations, we obtain

$\frac{2\alpha }{1-{\alpha }^2}=-\sqrt{\left|\Omega \backslash \Gamma \right|}\mathrm{,}$ (9)

$\frac{1+{\alpha }^2}{1-{\alpha }^2}=\sqrt{\left|\Omega \backslash \Gamma \right|+1}\mathrm{.}$ (10)

To simplify the notation, for given $j\in {\Omega }^c$ , it is necessary to introduce a new matrix $Z\in {ℝ}^{d\times P}$ , and the p-th column of Z is defined as

$\begin{array}{l}{Z}_p=\frac{{\Psi }^{\text{T}}\left[j\right]P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X_p\left[\Omega \backslash \Gamma \right]}{{\Vert {\Psi }^{\text{T}}\left[j\right]P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X_p\left[\Omega \backslash \Gamma \right]\Vert }_F}\mathrm{,}\\ 1\le p\le P\mathrm{,}\end{array}$ (11)

where $X_p\left[\Omega \backslash \Gamma \right]$ is the p-th column of $X\left[\Omega \backslash \Gamma \right]\in {ℝ}^{\left|\Omega \backslash \Gamma \right|\times P}$ . Furthermore, we define

$Q=P^{\perp }\left[\Gamma \right]\left[\Psi \left[\Omega \backslash \Gamma \right]\Psi \left[j\right]\right]\in {ℝ}^{M\times \left(\left|\Omega \backslash \Gamma \right|+1\right)}\mathrm{,}$ (12)

$U=\left[\begin{array}{c}X\left[\Omega \backslash \Gamma \right]\\ 0\end{array}\right]\in {ℝ}^{\left(\left|\Omega \backslash \Gamma \right|+1\right)\times P}\mathrm{,}$ (13)

$W=\left[\begin{array}{c}0\\ \alpha {\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_{F}Z\end{array}\right]\in {ℝ}^{\left(\left|\Omega \backslash \Gamma \right|+1\right)\times P}\mathrm{.}$ (14)

Then

$QU=P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X\left[\Omega \backslash \Gamma \right]$ (15)

and

${\Vert U+W\Vert }_F^2=\left(1+{\alpha }^2\right){\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_F^2\mathrm{,}$ (16)

${\Vert {\alpha }^{2}U-W\Vert }_F^2={\alpha }^2\left(1+{\alpha }^2\right){\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_F^2\mathrm{.}$ (17)

Moreover,

$\begin{array}{l}{\displaystyle \underset{p=1}{\overset{P}{\sum }}}{W}_i^{\text{T}}{Q}^{\text{T}}Q{U}_i\\ \stackrel{\text{(iii)}}{=}\alpha {\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_F{\displaystyle \underset{p=1}{\overset{P}{\sum }}}{Z}_p^{\text{T}}{\Psi }^{\text{T}}\left[j\right]P^{\perp }\left[\Gamma \right]P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X_p\left[\Omega \backslash \Gamma \right]\\ \stackrel{\text{(iv)}}{=}\alpha {\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_F{\displaystyle \underset{p=1}{\overset{P}{\sum }}}{Z}_p^{\text{T}}{\Psi }^{\text{T}}\left[j\right]P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X_p\left[\Omega \backslash \Gamma \right]\\ \stackrel{\text{(v)}}{=}\alpha {\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_F{\Vert {\Psi }^{\text{T}}\left[j\right]P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X_p\left[\Omega \backslash \Gamma \right]\Vert }_F\mathrm{,}\end{array}$ (18)

where (iii) is because (12)-(15), (iv) follows from (7), and (v) is from (11). Therefore, for any $j\in {\Omega }^c$ , by applying (18), we can get

$\begin{array}{l}{\Vert Q\left(U+W\right)\Vert }_F^2\\ ={\displaystyle \underset{p=1}{\overset{P}{\sum }}}{\Vert Q\left(U_p+W_p\right)\Vert }_2^2\\ ={\displaystyle \underset{p=1}{\overset{P}{\sum }}}\left({\Vert Q{U}_p\Vert }_2^2+{\Vert Q{W}_p\Vert }_2^2\right)+2{\displaystyle \underset{p=1}{\overset{P}{\sum }}}{W}_p^{\text{T}}{Q}^{\text{T}}Q{U}_p\\ ={\Vert QU\Vert }_F^2+{\Vert QW\Vert }_F^2+2\alpha {\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_F{\Vert {\Psi }^{\text{T}}\left[j\right]P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X\left[\Omega \backslash \Gamma \right]\Vert }_F\end{array}$ (19)

and

$\begin{array}{l}{\Vert Q\left({\alpha }^{2}U-W\right)\Vert }_F^2\\ ={\displaystyle \underset{p=1}{\overset{P}{\sum }}}{\Vert Q\left({\alpha }^2{U}_p-W_p\right)\Vert }_2^2\\ ={\displaystyle \underset{p=1}{\overset{P}{\sum }}}\left({\alpha }^4{\Vert Q{U}_p\Vert }_2^2+{\Vert Q{W}_p\Vert }_2^2\right)-2{\alpha }^2{\displaystyle \underset{p=1}{\overset{P}{\sum }}}{W}_p^{\text{T}}{Q}^{\text{T}}Q{U}_p\\ ={\alpha }^4{\Vert QU\Vert }_F^2+{\Vert QW\Vert }_F^2-2{\alpha }^3{\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_F{\Vert {\Psi }^{\text{T}}\left[j\right]P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X\left[\Omega \backslash \Gamma \right]\Vert }_F\mathrm{.}\end{array}$ (20)

By the (19) and (20) are mentioned before, we can have

$\begin{array}{l}{\Vert Q\left(U+W\right)\Vert }_F^2-{\Vert Q\left({\alpha }^{2}U-W\right)\Vert }_F^2\\ =\left(1-{\alpha }^4\right){\Vert QU\Vert }_F^2+2\alpha \left(1+{\alpha }^2\right){\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_F{\Vert {\Psi }^{\text{T}}\left[j\right]P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X\left[\Omega \backslash \Gamma \right]\Vert }_F\\ =\left(1-{\alpha }^4\right)\left({\Vert QU\Vert }_F+\frac{2\alpha }{1-{\alpha }^2}\times {\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_F{\Vert {\Psi }^{\text{T}}\left[j\right]P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X\left[\Omega \backslash \Gamma \right]\Vert }_F\right)\\ =\left(1-{\alpha }^4\right)\left({\Vert QU\Vert }_F-\sqrt{\mathrm{<mo>\; |\; </mo>}\Omega \backslash \Gamma \mathrm{<mo>\; |\; </mo>}}\times {\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_F{\Vert {\Psi }^{\text{T}}\left[j\right]P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X\left[\Omega \backslash \Gamma \right]\Vert }_F\right)\mathrm{,}\end{array}$ (21)

where the last equality because of (9). It is not hard to check that

$\begin{array}{l}{\Vert Q\left(U+W\right)\Vert }_F^2-{\Vert Q\left({\alpha }^{2}U-W\right)\Vert }_F^2\\ \stackrel{\mathrm{<mo\; stretchy="false">\; (\; </mo>}\text{vi}\mathrm{<mo\; stretchy="false">\; )\; </mo>}}{\ge }\left(1-{\delta }_{\left|\Omega \right|+1}\right){\Vert U+W\Vert }_F^2-\left(1+{\delta }_{\left|\Omega \right|+1}\right){\Vert {\alpha }^{2}U-W\Vert }_F^2\\ \stackrel{\mathrm{<mo\; stretchy="false">\; (\; </mo>}\text{vii}\mathrm{<mo\; stretchy="false">\; )\; </mo>}}{=}\left(1-{\delta }_{\left|\Omega \right|+1}\right)\left(1+{\alpha }^2\right){\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_F^2-\left(1+{\delta }_{\left|\Omega \right|+1}\right){\alpha }^2\left(1+{\alpha }^2\right){\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_F^2\\ =\left(1+{\alpha }^2\right){\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_F^2\left(\left(1-{\delta }_{\left|\Omega \right|+1}\right)-\left(1+{\delta }_{\left|\Omega \right|+1}\right){\alpha }^2\right)\end{array}$

$\begin{array}{l}=\left(1+{\alpha }^2\right){\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_F^2\left(\left(1-{\alpha }^2\right)-{\delta }_{\left|\Omega \right|+1}\left(1+{\alpha }^2\right)\right)\\ =\left(1-{\alpha }^4\right){\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_F^2\left(1-\frac{1+{\alpha }^2}{1-{\alpha }^2}{\delta }_{\left|\Omega \right|+1}\right)\\ \stackrel{\mathrm{<mo\; stretchy="false">\; (\; </mo>}\text{viii}\mathrm{<mo\; stretchy="false">\; )\; </mo>}}{=}\left(1-{\alpha }^4\right){\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_F^2\left(1-\sqrt{\left|\Omega \backslash \Gamma \right|+1}{\delta }_{\left|\Omega \right|+1}\right)\mathrm{,}\end{array}$ (22)

where (vi) follows Lemma 3 and (12), (vii) is due to (16) and (17), and (viii) is from (10). By (15), (21), (22), and the fact that $1-{\alpha }^4>0$ , we have

$\begin{array}{l}{\Vert P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X\left[\Omega \backslash \Gamma \right]\Vert }_F^2\\ -\sqrt{\left|\Omega \backslash \Gamma \right|}{\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_F{\Vert {\Psi }^{\text{T}}\left[j\right]P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X\left[\Omega \backslash \Gamma \right]\Vert }_F\\ ={\Vert QU\Vert }_F^2-\sqrt{\left|\Omega \backslash \Gamma \right|}{\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_F{\Vert {\Psi }^{\text{T}}\left[j\right]P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X\left[\Omega \backslash \Gamma \right]\Vert }_F\\ \ge {\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_F^2\left(1-\sqrt{\left|\Omega \backslash \Gamma \right|+1}{\delta }_{\left|\Omega \right|+1}\right)\mathrm{.}\end{array}$

Combining the aforementioned Equation with (8), we obtain

$\begin{array}{l}\sqrt{\left|\Omega \backslash \Gamma \right|}{\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_F\times (\underset{i\in \Omega \backslash \Gamma }{\max }{\Vert {\Psi }^{\text{T}}\left[i\right]P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X\left[\Omega \backslash \Gamma \right]\Vert }_F\\ -{\Vert {\Psi }^{\text{T}}\left[j\right]P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X\left[\Omega \backslash \Gamma \right]\Vert }_F)\\ \ge \sqrt{\left|\Omega \backslash \Gamma \right|}{\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_F\times (\underset{i\in \Omega \backslash \Gamma }{\max }{\Vert {\Psi }^{\text{T}}\left[i\right]P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X\left[\Omega \backslash \Gamma \right]\Vert }_F\end{array}$

$\begin{array}{l}-\underset{j\in {\Omega }^c}{\max }{\Vert {\Psi }^{\text{T}}\left[j\right]P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X\left[\Omega \backslash \Gamma \right]\Vert }_F)\\ \ge {\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_F^2\left(1-\sqrt{\left|\Omega \backslash \Gamma \right|+1}{\delta }_{\left|\Omega \right|+1}\right)\mathrm{,}\end{array}$

which implies that

$\begin{array}{l}\underset{i\in \Omega \backslash \Gamma }{\max }{\Vert {\Psi }^{\text{T}}\left[i\right]P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X\left[\Omega \backslash \Gamma \right]\Vert }_F\\ -\underset{j\in {\Omega }^c}{\max }{\Vert {\Psi }^{\text{T}}\left[j\right]P^{\perp }\left[\Gamma \right]\Psi \left[\Omega \backslash \Gamma \right]X\left[\Omega \backslash \Gamma \right]\Vert }_F\\ \ge \frac{\left(1-\sqrt{\left|\Omega \backslash \Gamma \right|+1}{\delta }_{\left|\Omega \right|+1}\right){\Vert X\left[\Omega \backslash \Gamma \right]\Vert }_F}{\sqrt{\left|\Omega \backslash \Gamma \right|}}\mathrm{.}\end{array}$

Thus, we complete the proof. $■$

Remark 6 Specially, Lemma 5 is a general block version of ( [28] , Theorem 3.2). The main difference between our Lemma 5 and ( [28] , Theorem 3.2) exist in two aspects. First, our model is block version of multiple measurement vectors. Second, the ways of calculating $supp\left(X\right)$ are different.

Based on the Algorithm 1 and lemmas we presented above, we show our main results in this section. We provide a sufficient guarantee for the exact support recovery of block joint sparse matrices with the BMMV algorithm under the ${\Vert V\Vert }_F\le \epsilon$ bounded noise from noisy model (3).

Theorem 7 Consider (3). Assume that ${\Vert V\Vert }_F\le \epsilon$ and matrix X is block K-joint sparse. Provided that measurement matrix $\Psi$ obeys the bRIP of order $K+1$ with

${\delta }_{K+1}<\frac{1}{\sqrt{K+1}},$ (23)

and X satisfies

$\underset{i\in \Omega }{\min }{\Vert X\left[i\right]\Vert }_F>\frac{2\epsilon }{1-\sqrt{K+1}{\delta }_{K+1}}\mathrm{.}$ (24)

Then based on the stopping criteria ${\Vert R^k\Vert }_F\le \epsilon$ , the BMMV algorithm can accurately recover the $supp\left(X\right)$ in K iterations.

Proof 2 For proving Theorem 7, there are two points that need to be shown, namely, one is to prove that the BMMV algorithm selects a correct block index from $\Omega =supp\left(X\right)$ in each iteration, and the second is that the BMMV algorithm will select all the indices in $\Omega$ in all K iterations. The proof consists of two parts. First, we illustrate that all correct indices are identified in all iteration via BMMV. Second, we show that the process of identifying terminates after it is executed just $K=\left|\Omega \right|$ iterations. In the first step the mathematical induction method is used. Suppose that in the first $k-1$ iterations, the BMMV algorithm has selected the correct indices, which means that ${\Omega }_{k-1}=\left\{{\omega }^1\mathrm{,}{\omega }^2\mathrm{,}\cdots \mathrm{,}{\omega }^{k-1}\right\}\subseteq \Omega$ and $1\le k\le \left|\Omega \right|=K$ . Since ${\Omega }_0=\varnothing$ , it obviously holds when $k=1$ . Therefore, we only have to prove that a correct index is selected by the BMMV algorithm at the k-th iteration, i.e., ${\omega }^k\in \Omega \backslash {\Omega }_{k-1}$ .

By the Step 3 and 4 in Algorithm 1, we can obtain that the orthogonal relationship between $R^{k-1}$ and the columns space of $\Psi \left[i\right]$ , then we have

${\Vert {\Psi }^{\text{T}}\left[i\right]R^{k-1}\Vert }_F=\mathrm{0,}$

for any $i\in {\Omega }_{k-1}$ , so we get that ${\omega }^k\notin {\Omega }_{k-1}$ . For proving ${\omega }^k\in \Omega \backslash {\Omega }_{k-1}$ , by the Step 1 of BMMV, we turn to proof

$\underset{i\in \Omega \backslash {\Omega }_{k-1}}{\max }{\Vert {\Psi }^{\text{T}}\left[i\right]R^{k-1}\Vert }_F>\underset{j\in {\Omega }^c}{\max }{\Vert {\Psi }^{\text{T}}\left[j\right]R^{k-1}\Vert }_F\mathrm{.}$ (25)

By the estimating step of the BMMV algorithm, we obtain

$\hat{X}\left[{\Omega }_{k-1}\right]={\left({\Psi }^{\text{T}}\left[{\Omega }_{k-1}\right]\Psi \left[{\Omega }_{k-1}\right]\right)}^{-1}{\Psi }^{\text{T}}\left[{\Omega }_{k-1}\right]Y\mathrm{.}$ (26)

Then, from Step 4 of the BMMV algorithm and (26),

$\begin{array}{l}{R}^{k-1}=Y-\Psi \left[{\Omega }_{k-1}\right]\hat{X}\left[{\Omega }_{k-1}\right]\stackrel{\text{(}\tau \text{1)}}{=}{P}^{\perp }\left[{\Omega }_{k-1}\right]\left(\Psi X+V\right)\\ \stackrel{\text{(}\tau \text{2)}}{=}{P}^{\perp }\left[{\Omega }_{k-1}\right]\left(\Psi \left[{\Omega }_{k-1}\right]X\left[{\Omega }_{k-1}\right]+\Psi \left[\Omega \backslash {\Omega }_{k-1}\right]X\left[\Omega \backslash {\Omega }_{k-1}\right]+V\right)\\ \stackrel{\text{(}\tau \text{3)}}{=}{P}^{\perp }\left[{\Omega }_{k-1}\right]\Psi \left[\Omega \backslash {\Omega }_{k-1}\right]X\left[\Omega \backslash {\Omega }_{k-1}\right]+P^{\perp }\left[{\Omega }_{k-1}\right]V\mathrm{,}\end{array}$ (27)

where (τ1) is because the definition of $P^{\perp }\left[{\Omega }_{k-1}\right]$ is used, (τ2) is based on $\Omega =supp\left(X\right)$ and ${\Omega }_{k-1}\subseteq \Omega$ , and (τ3) is due to $P^{\perp }\left[{\Omega }_{k-1}\right]\Psi \left[{\Omega }_{k-1}\right]=0$ . Consequently, to show (25), we try to use (27) to obtain the lower and upper bound on the left and right side of (25), separately. For any $i\in \Omega \backslash {\Omega }_{k-1}$ and $j\in {\Omega }^c$ , by the triangle inequality, it is obtained that

$\begin{array}{l}\underset{i\in \Omega \backslash {\Omega }_{k-1}}{\max }{\Vert {\Psi }^{\text{T}}\left[i\right]R^{k-1}\Vert }_F\\ =\underset{i\in \Omega \backslash {\Omega }_{k-1}}{\max }{\Vert {\Psi }^{\text{T}}\left[i\right]P^{\perp }\left[{\Omega }_{k-1}\right]\Psi \left[\Omega \backslash {\Omega }_{k-1}\right]X\left[\Omega \backslash {\Omega }_{k-1}\right]+{\Psi }^{\text{T}}\left[i\right]P^{\perp }\left[{\Omega }_{k-1}\right]V\Vert }_F\\ \ge \underset{i\in \Omega \backslash {\Omega }_{k-1}}{\max }{\Vert {\Psi }^{\text{T}}\left[i\right]P^{\perp }\left[{\Omega }_{k-1}\right]\Psi \left[\Omega \backslash {\Omega }_{k-1}\right]X\left[\Omega \backslash {\Omega }_{k-1}\right]\Vert }_F\\ -\underset{i\in \Omega \backslash {\Omega }_{k-1}}{\max }{\Vert {\Psi }^{\text{T}}\left[i\right]P^{\perp }\left[{\Omega }_{k-1}\right]V\Vert }_F\end{array}$ (28)

and

$\begin{array}{l}\underset{j\in {\Omega }^c}{\max }{\Vert {\Psi }^{\text{T}}\left[j\right]R^{k-1}\Vert }_F\\ =\underset{j\in {\Omega }^c}{\max }{\Vert {\Psi }^{\text{T}}\left[j\right]P^{\perp }\left[{\Omega }_{k-1}\right]\Psi \left[\Omega \backslash {\Omega }_{k-1}\right]X\left[\Omega \backslash {\Omega }_{k-1}\right]+{\Psi }^{\text{T}}\left[j\right]P^{\perp }\left[{\Omega }_{k-1}\right]V\Vert }_F\\ \le \underset{j\in {\Omega }^c}{\max }{\Vert {\Psi }^{\text{T}}\left[j\right]P^{\perp }\left[{\Omega }_{k-1}\right]\Psi \left[\Omega \backslash {\Omega }_{k-1}\right]X\left[\Omega \backslash {\Omega }_{k-1}\right]\Vert }_F\underset{j\in {\Omega }^c}{\max }{\Vert {\Psi }^{\text{T}}\left[j\right]P^{\perp }\left[{\Omega }_{k-1}\right]V\Vert }_F\mathrm{.}\end{array}$ (29)

Therefore, by (28) and (29), to show (25), we only need to prove

$\begin{array}{l}\underset{i\in \Omega \backslash {\Omega }_{k-1}}{\max }{\Vert {\Psi }^{\text{T}}\left[i\right]P^{\perp }\left[{\Omega }_{k-1}\right]\Psi \left[\Omega \backslash {\Omega }_{k-1}\right]X\left[\Omega \backslash {\Omega }_{k-1}\right]\Vert }_F\\ -\underset{j\in {\Omega }^c}{\max }{\Vert {\Psi }^{\text{T}}\left[j\right]P^{\perp }\left[{\Omega }_{k-1}\right]\Psi \left[\Omega \backslash {\Omega }_{k-1}\right]X\left[\Omega \backslash {\Omega }_{k-1}\right]\Vert }_F\\ >\underset{i\in \Omega \backslash {\Omega }_{k-1}}{\max }{\Vert {\Psi }^{\text{T}}\left[i\right]P^{\perp }\left[{\Omega }_{k-1}\right]V\Vert }_F+\underset{j\in {\Omega }^c}{\max }{\Vert {\Psi }^{\text{T}}\left[j\right]P^{\perp }\left[{\Omega }_{k-1}\right]V\Vert }_F\mathrm{.}\end{array}$ (30)

Next, we try to find a lower bound on the left side of (30). Using the inductive assumption ${\Omega }_{k-1}\subseteq \Omega$ and $\left|supp\left(X\left[\Omega \backslash {\Omega }_{k-1}\right]\right)\right|=\left|\Omega \right|+1-k$ . Hence, we obtain

${\Vert X\left[\Omega \backslash {\Omega }_{k-1}\right]\Vert }_F\ge \sqrt{\left|\Omega \right|+1-k}\underset{i\in \Omega }{\min }{\Vert X\left[i\right]\Vert }_F\mathrm{.}$ (31)

Since $\left|{\Omega }_{k-1}\right|=k-1$ and ${\Omega }_{k-1}\subseteq \Omega$ , according to Lemma 5, we obtain

$\begin{array}{l}\underset{i\in \Omega \backslash {\Omega }_{k-1}}{\max }{\Vert {\Psi }^{\text{T}}\left[i\right]P^{\perp }\left[{\Omega }_{k-1}\right]\Psi \left[\Omega \backslash {\Omega }_{k-1}\right]X\left[\Omega \backslash {\Omega }_{k-1}\right]\Vert }_F\\ -\underset{j\in {\Omega }^c}{\max }{\Vert {\Psi }^{\text{T}}\left[j\right]P^{\perp }\left[{\Omega }_{k-1}\right]\Psi \left[\Omega \backslash {\Omega }_{k-1}\right]X\left[\Omega \backslash {\Omega }_{k-1}\right]\Vert }_F\\ \ge \frac{{\Vert X\left[\Omega \backslash {\Omega }_{k-1}\right]\Vert }_F}{\sqrt{\left|\Omega \right|+1-k}}\left(1-\sqrt{\left|\Omega \right|+2-k}{\delta }_{\left|\Omega \right|+1}\right)\\ \stackrel{\text{(}\tau \text{4)}}{\ge }\frac{{\Vert X\left[\Omega \backslash {\Omega }_{k-1}\right]\Vert }_F}{\sqrt{\left|\Omega \right|+1-k}}\left(1-\sqrt{K+1}{\delta }_{\left|\Omega \right|+1}\right)\\ \stackrel{\text{(}\tau \text{5)}}{\ge }\underset{i\in \Omega }{\min }{\Vert X\left[i\right]\Vert }_F\left(1-\sqrt{K+1}{\delta }_{K+1}\right)\mathrm{,}\end{array}$ (32)

where (τ4) is due to the assumption of X in this paper and the fact that $k>1$ and (τ5) is from Lemma 1, (23) and (31). Then, we deduce a upper bound on the right side of (30). There are $\alpha \in \Omega \backslash {\Omega }_{k-1}$ and $\beta \in {\Omega }^c$ that make

$\underset{i\in \Omega \backslash {\Omega }_{k-1}}{\max }{\Vert {\Psi }^{\text{T}}\left[i\right]P^{\perp }\left[{\Omega }_{k-1}\right]V\Vert }_F={\Vert {\Psi }^{\text{T}}\left[\alpha \right]P^{\perp }\left[{\Omega }_{k-1}\right]V\Vert }_F\mathrm{,}$

$\underset{j\in {\Omega }^c}{\max }{\Vert {\Psi }^{\text{T}}\left[j\right]P^{\perp }\left[{\Omega }_{k-1}\right]V\Vert }_F={\Vert {\Psi }^{\text{T}}\left[\beta \right]P^{\perp }\left[{\Omega }_{k-1}\right]V\Vert }_F\mathrm{.}$

Hence, we obtain

$\begin{array}{l}\underset{i\in \Omega \backslash {\Omega }_{k-1}}{\max }{\Vert {\Psi }^{\text{T}}\left[i\right]P^{\perp }\left[{\Omega }_{k-1}\right]V\Vert }_F{}_F+\underset{j\in {\Omega }^c}{\max }{\Vert {\Psi }^{\text{T}}\left[j\right]P^{\perp }\left[{\Omega }_{k-1}\right]V\Vert }_F\\ ={\Vert {\Psi }^{\text{T}}\left[\alpha \right]P^{\perp }\left[{\Omega }_{k-1}\right]V\Vert }_F+{\Vert {\Psi }^{\text{T}}\left[\beta \right]P^{\perp }\left[{\Omega }_{k-1}\right]V\Vert }_F\\ \stackrel{\text{(}\tau \text{6)}}{\le }\sqrt{2}{\Vert {\left[\Psi \left[\alpha \right]\mathrm{,}\Psi \left[\beta \right]\right]}^{\text{T}}{P}^{\perp }\left[{\Omega }_{k-1}\right]V\Vert }_F\\ \stackrel{\text{(}\tau \text{7)}}{\le }\sqrt{2\left(1+{\delta }_{K+1}\right)}\epsilon \mathrm{,}\end{array}$ (33)

where (τ6) is because ${\left[\Psi \left[\alpha \right]\mathrm{,}\Psi \left[\beta \right]\right]}^{\text{T}}{P}^{\perp }\left[{\Omega }_{k-1}\right]V$ is a matrix with two $d\times H$ subvectors and (τ7) are due to Lemma 2 and

${\Vert P^{\perp }\left[{\Omega }_{k-1}\right]V\Vert }_F\le {\Vert V\Vert }_F\le \epsilon \mathrm{,}$ (34)

respectively. Based on (32) and (33), (30) holds when

$\sqrt{2\left(1+{\delta }_{K+1}\right)}\epsilon <\left(1-\sqrt{K+1}{\delta }_{K+1}\right)\underset{i\in \Omega }{\min }{\Vert X\left[i\right]\Vert }_F\mathrm{,}$

that is,

$\underset{i\in \Omega }{\min }{\Vert X\left[i\right]\Vert }_F>\frac{\sqrt{2\left(1+{\delta }_{K+1}\right)}\epsilon }{1-\sqrt{K+1}{\delta }_{K+1}}\mathrm{.}$

In addition, by (23), we obtain ${\delta }_{K+1}<1$ . Hence, once (24) is satisfied, a correct index is identified by the BMMV algorithm in each iteration.

Next, the BMMV algorithm needs to be specified to be performed exact $\left|\Omega \right|=K$ iterations, that equals to prove that we always have ${\Vert R^k\Vert }_F>\epsilon$ for all $k\in \left[\mathrm{1,}K\right)$ and ${\Vert R^K\Vert }_F\le \epsilon$ . Since only one correct index is selected by the BMMV algorithm at a iteration under (24), by (27) and triangle inequality, for all $k\in \left[\mathrm{1,}K\right)$ , we obtain

$\begin{array}{c}{\Vert R^k\Vert }_F={\Vert P^{\perp }\left[{\Omega }_k\right]\Psi \left[\Omega \backslash {\Omega }_k\right]X\left[\Omega \backslash {\Omega }_k\right]+P^{\perp }\left[{\Omega }_k\right]V\Vert }_F\\ \ge {\Vert P^{\perp }\left[{\Omega }_k\right]\Psi \left[\Omega \backslash {\Omega }_k\right]X\left[\Omega \backslash {\Omega }_k\right]\Vert }_F-{\Vert P^{\perp }\left[{\Omega }_k\right]V\Vert }_F\\ \stackrel{\text{(}\tau \text{8)}}{\ge }\sqrt{1-{\delta }_K}{\Vert X\left[\Omega \backslash {\Omega }_k\right]\Vert }_F-\epsilon \\ \stackrel{\text{(}\tau \text{9)}}{\ge }\sqrt{\left(1-{\delta }_{K+1}\right)\left(K-k\right)}\underset{i\in \Omega }{\min }{\Vert X\left[i\right]\Vert }_F-\epsilon \\ \ge \sqrt{1-{\delta }_{K+1}}-\epsilon \mathrm{,}\end{array}$

where (τ8) is from (34) and Lemma 3, and (τ9) is because of Lemma 1 and (31). Hence, if

$\underset{i\in \Omega }{\min }{\Vert X\left[i\right]\Vert }_F>\frac{2\epsilon }{\sqrt{1-{\delta }_{K+1}}}\mathrm{,}$ (35)

then ${\Vert R^k\Vert }_F>\epsilon$ for each $k\in \left[\mathrm{1,}K\right)$ . After some transformations, it is easily get

$\frac{2\epsilon }{1-\sqrt{K+1}{\delta }_{K+1}}\ge \frac{2\epsilon }{\sqrt{1-{\delta }_{K+1}}}\mathrm{,}$ (36)

which is from $1-{\delta }_{K+1}\in \left(\mathrm{0,1}\right)$ and $1-\sqrt{K+1}{\delta }_{K+1}\le \sqrt{1-{\delta }_{K+1}}$ . Therefore, from (35) and (36), if (24) holds, ${\Vert R^k\Vert }_F>\epsilon$ for each $1\le k<K$ , i.e., it does not terminate until the K-th iteration is completed. Likewise, from (27), we have

$\begin{array}{l}{\Vert R^K\Vert }_F={\Vert P^{\perp }\left[{\Omega }_K\right]\Psi \left[\Omega \backslash {\Omega }_K\right]X\left[\Omega \backslash {\Omega }_K\right]+P^{\perp }\left[{\Omega }_K\right]V\Vert }_F\\ \stackrel{\text{(}\tau \text{10)}}{=}{\Vert P^{\perp }\left[{\Omega }_K\right]V\Vert }_F\le \epsilon \mathrm{,}\end{array}$

where (τ10) is due to $\left|{\Omega }_K\right|=\left|\Omega \right|=K$ . Due to the termination criteria, the BMMV algorithm stops after the K-th iteration. Hence, the BMMV algorithm just executes K iterations. Our proof is complete. $■$

When $H=1$ , the X turns to a block K-sparse vector $x$ and V turns to a vector $v$ . For block K-sparse vector, there are already many researches on recovery performance of block reconstruction algorithms, for example, block OMP (BOMP) ( [26] [29] ) and block gOMP (BgOMP) ( [30] [31] ).

Corollary 8 Taking $H=1$ in (3) and Theorem 7. Assume that ${\Vert v\Vert }_2\le \epsilon$ and vector $x$ is block K sparse. Provided that measurement matrix $\Psi$ obeys the bRIP of order $K+1$ with ${\delta }_{K+1}<\frac{1}{\sqrt{K+1}}$ , and $x$ satisfies

$\underset{i\in \Omega }{\min }{\Vert x[i]\Vert }_2>\frac{2\epsilon }{1-\sqrt{K+1}{\delta }_{K+1}}\mathrm{.}$

Then based on the stopping criteria ${\Vert r^k\Vert }_2\le \epsilon$ ( $r$ is a residual vector), the BMMV algorithm can accurately recover $supp\left(x\right)$ in K iterations.

Remark 9 The results in the Corollary 8 are consistent with the results of [26] , which is a sharp sufficient condition. However, [29] gives a new analysis for support recovery that is less restrictive for ${\min }_{i\in \Omega }{\Vert x\left[i\right]\Vert }_2$ . For more details, please refer to [29] .

If the length of blocks $d=1$ , the block K-joint sparse is equivalent to K-row sparse. In [32] gives two theorems to show the bound ${\delta }_{K+1}<\frac{1}{\sqrt{K+1}}$ is optimal in noiseless case. More details are in [32] , which means the bound based on bRIP we proposed is optimal in the noiseless case.

Corollary 10 Taking $H=1$ and $d=1$ in (3) and Theorem 7, X reduces to $x$ , V reduces to $v$ . Assume that ${\Vert v\Vert }_2\le \epsilon$ and vector $x$ is K sparse. Provided that measurement matrix $\Psi$ obeys the bRIP of order $K+1$ with ${\delta }_{K+1}<\frac{1}{K+1}$ , and $x$ satisfies

$\underset{i\in \Omega }{\min }\left|x_i\right|>\frac{2\epsilon }{1-\sqrt{K+1}{\delta }_{K+1}}\mathrm{.}$

Then based on the stopping criteria ${\Vert r^k\Vert }_2\le \epsilon$ , the BMMV algorithm can accurately recover $supp\left(x\right)$ in K iterations.

Remark 11 The Corollary 10 is same as ( [17] , Theorem 1), which is a sharp condition. [33] gives a less restrictive bound on ${\min }_{i\in \Omega }\left|x_i\right|$ . This means that our result have room for improvement.

4. Conclusions and Future Works

In this paper, studies on the performance of support recovery of block K-joint sparse matrix via the BMMV algorithm from $Y=\Psi X+V$ are analyzed. We obtained that if $\Psi$ satisfies bRIP with ${\delta }_{K+1}<\frac{1}{\sqrt{K+1}}$ and ${\min }_{i\in \Omega }{\Vert X\left[i\right]\Vert }_F\le \frac{2\epsilon }{1-\sqrt{K+1}{\delta }_{K+1}}$ , then BMMV can accurately reconstruct the $supp\left(X\right)$ in K iterations. With the help of ( [32] , Theorem 2), we also show the RIP-based condition is optimal when the problem reduces to SMV problem under the noiseless case.

Because our result about ${\min }_{i\in \Omega }{\Vert X\left[i\right]\Vert }_F$ is not yet optimal. Thus, one of future directions is to continue to refine this result and continue to study theoretical improvement of the related algorithms. Because the block length considered in this paper is a fixed value for simplicity, it is also worth considering that the block length is a variable. Then, the support recovery conditions are theoretical, and how it applies to practical applications is also a question. The BMMV algorithm selects only one index for each iteration, which means that the recovery program will directly fail once a wrong index is added to the estimation support. It is interesting to propose an improved algorithm to solve the problem.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Candes, E.J., Romberg, J. and Tao, T. (2006) Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information. IEEE Transactions on Information Theory, 5, 489-509. https://doi.org/10.1109/TIT.2005.862083
[2]	Donoho, D.L. (2006) Compressed Sensing. IEEE Transactions on Information Theory, 52, 1289-1306. https://doi.org/10.1109/TIT.2006.871582
[3]	Duarte, M.F. and Eldar, Y.C. (2011) Structured Compressed Sensing: From Theory to Applications. IEEE Transactions on Information Theory, 59, 4053-4085. https://doi.org/10.1109/TSP.2011.2161982
[4]	Donoho, D.L., Elad, M. and Temlyakov V. (2006) Stable Recovery of Sparse Overcomplete Repesentations in the Presence of Noise. IEEE Transactions on Information Theory, 52, 6-18. https://doi.org/10.1109/TIT.2005.860430
[5]	Herman, M. and Strohmer, T. (2009) High-Resolution Radar via Compressed Sensing. IEEE Transactions Signal Processing, 57, 2275-2284. https://doi.org/10.1109/TSP.2009.2014277
[6]	Lustig, M., Donoho, D.L. and Pauly, J.M. (2008) Compressed Sensing MRI. IEEE Signal Processing Magazine, 25, 72-82. https://doi.org/10.1109/MSP.2007.914728
[7]	Wakin, M., Laska, J., Duarte, M., et al. (2006) An Architecture for Compressive Imaging. 2006 International Conference on Image Processing, Atlanta, 8-11 October 2006, 1273-1276. https://doi.org/10.1109/ICIP.2006.312577
[8]	Tropp, J.A. and Gilbert, A.C. (2007) Signal Recovery from Random Measurements via Orthogonal Matching Pursuit. IEEE Transactions on Information Theory, 53, 4655-4666. https://doi.org/10.1109/TIT.2007.909108
[9]	Donoho, D.L., Tsaig, Y., Drori, I. and Starck, J.L. (2012) Sparse Solution of Underdetermined Systems of Linear Equations by Stagewise Orthogonal Matching Pursuit. IEEE Transactions on Information Theory, 58, 1094-1121. https://doi.org/10.1109/TIT.2011.2173241
[10]	Needell, D. and Vershynin, R. (2009) Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching Pursuit. Foundations of Computational Mathematics, 9, 317-334. https://doi.org/10.1007/s10208-008-9031-3
[11]	Needell, D. and Tropp, J.A. (2009) CoSaMP: Iterative Signal Recovery from Incomplete and Inaccurate Samples. Applied and Computational Harmonic Analysis, 26, 301-321. https://doi.org/10.1016/j.acha.2008.07.002
[12]	Dai, W. and Milenkovic, O. (2009) Subspace Pursuit for Compressive Sensing Signal Reconstruction. IEEE Transactions on Information Theory, 55, 2230-2249. https://doi.org/10.1109/TIT.2009.2016006
[13]	Wang, J., Kwon, S. and Shim, B. (2012) Generalized Orthogonal Matching Pursuit. IEEE Transactions Signal Processing, 60, 6202-6216. https://doi.org/10.1109/TSP.2012.2218810
[14]	Rebollo-Neira, L. and Lowe, D. (2002) Optimized Orthogonal Matching Pursuit Approach. IEEE Signal Processing Letters, 9, 137-140. https://doi.org/10.1109/LSP.2002.1001652
[15]	Huang, H. and Makur, A. (2011) Backtracking-Based Matching Pursuit Method for Sparse Signal Reconstruction. IEEE Signal Processing Letters, 18, 391-394. https://doi.org/10.1109/LSP.2011.2147313
[16]	Mo, Q. and Shen, Y. (2012) A Remark on the Restricted Isometry Property in Orthogonal Matching Pursuit. IEEE Transactions on Information Theory, 58, 3654-3656. https://doi.org/10.1109/TIT.2012.2185923
[17]	Wen, J.M., Zhou, Z.C., Wang, J., Tang, X.H. and Mo, Q. (2017) A Sharp Condition for Exact Support Recovery with Orthogonal Matching Pursuit. IEEE Transactions Signal Processing, 65, 1370-1382. https://doi.org/10.1109/TSP.2016.2634550
[18]	Wang, J., Zhou, Z., Li, D. and Tang, X. (2016) A Novel Sufficient Condition for Generalized Orthogonal Matching Pursuit. IEEE Communications Letters, 21, 805-808. https://doi.org/10.1109/LCOMM.2016.2642922
[19]	Mishali, M. and Eldar, Y.C. (2009) Blind Multiband Signal Reconstruction: Compressed Sensing for Analog Signals. IEEE Transactions Signal Processing, 57, 993-1009. https://doi.org/10.1109/TSP.2009.2012791
[20]	Wright, J., Yang, A.Y., Granesh, A., Sastry, S.S. and Ma, Y. (2009) Robust Face Recognition via Sparse Representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31, 210-227. https://doi.org/10.1109/TPAMI.2008.79
[21]	Shi, Y.L., Wang, L.B. and Luo, R. (2019) Sparse Recovery with Block Multiple Measurement Vectors Algorithm. IEEE Access, 7, 9470-9475. https://doi.org/10.1109/ACCESS.2019.2891568
[22]	Fu, Y., Li, H., Zhang, Q. and Zhou, J. (2014) Block-Sparse Recovery via Redundant Block OMP. Signal Precessing, 97, 162-171. https://doi.org/10.1016/j.sigpro.2013.10.030
[23]	Candes, E.J. and Tao, T. (2005) Denoding by Linear Programming. IEEE Transactions on Information Theory, 51, 4203-4215. https://doi.org/10.1109/TIT.2005.858979
[24]	Robust, Y.C. and Mishali, M. (2009) Robust Recovery of Signals from a Structured Union of Subspaces. IEEE Transactions on Information Theory, 55, 5302-5316. https://doi.org/10.1109/TIT.2009.2030471
[25]	Majumdar, A. and Ward, R.K. (2012) Face Recognition from Video: An MMV Recovery Approach. 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Kyoto, 25-30 March 2012, 2221-2224. https://doi.org/10.1109/ICASSP.2012.6288355
[26]	Wen, J.M., Zhou, Z.C., Liu, Z.L., Lai, M.J. and Tang, X.H. (2019) Sharp Sufficient Conditions for Stable Recovery of Block Sparse Signals by Block Orthogonal Matching Pursuit. Applied and Computational Harmonic Analysis, 47, 948-974. https://doi.org/10.1016/j.acha.2018.02.002
[27]	Wen, J.M., Tang, J. and Zhou, F.M. (2017) Greedy Block Coordinate Descent under Restricted Isometry Property. Mobile Networks and Applications, 22, 371-376. https://doi.org/10.1007/s11036-016-0774-9
[28]	Zhang, X.W., Xie, L.J. and Wang, J.P. (2022) Some Results on OMP Algorithm for MMV Problem. Mathematical Methods in the Applied Sciences, 45, 5402-5411. https://doi.org/10.1002/mma.8114
[29]	Li, H.F. and Wen, J.M. (2018) A New Analysis for Support Recovery with Block Orthogonal Matching Pursuit. IEEE Signal Processing, 26, 247-251. https://doi.org/10.1109/LSP.2018.2885919
[30]	Qi, R., Yang, D.W., Zhang, Y.J. and Li, H.W. (2018) On Recovery of Block Sparse Signals via Block Generalized Orthogonal Matching Pursuit. Signal Progressing, 153, 34-46. https://doi.org/10.1016/j.sigpro.2018.06.023
[31]	Xia, C.Y., Zhou, Z.L., Guo, C.B., Hao, Y.S. and Hou, C.B. (2021) A New Analysis for Support Performance with Block Generalized Orthogonal Matching Pursuit. Mathematical Problems in Engineering, 2021, Article ID: 9438793. https://doi.org/10.1155/2021/9438793
[32]	Li, H.F., Wang, L.B., Zhan, X.Q. and Jain, D.K. (2019) On the Fundamental Limit of Orthogonal Matching Pursuit for Multiple Measurement Vector. IEEE Access, 7, 48860-48866. https://doi.org/10.1109/ACCESS.2019.2907684
[33]	Liu, C., Fang, Y. and Liu, J.Z. (2017) Some New Results about Sufficient Conditions for Exact Support Recovery of Sparse Signals via Orthogonal Matching Pursuit. IEEE Transactions Signal Processing, 65, 4511-4524. https://doi.org/10.1109/TSP.2017.2711543