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

Authors: C. Y. Xia; Z. L. Zhou; Chun-Bo Guo; Y. S. Hao; C. B. Hou
Journal: Mathematical Problems in Engineering
 (2021)

---

## 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 anyK-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 k iterations.


---

## Body

## 1. Introduction

The block generalized orthogonal matching pursuit (BgOMP) [1] in compressive sensing (CS) theory has been proposed for recovering block-sparse signalsx, in which the signal vector x has at most K nonzero block elements, and satisfies x2,0≤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:(1)Y=Ax+v,where A∈ℝM1×M2 (M1≪M2) is a sensing matrix with normalized columns, Y∈ℝM1×1 is a measurement vector, and the vector v represents a random noise. Specifically, x∈ℝM2×1 is a concatenation of blocks xi∈ℝd, 1≤i≤LFor any proper subsetS⊂1,2,…,L, we define that AS represents the submatrix of A which only includes the block index of S. Similarly, xS denotes the subvector of 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, Ω=suppx=i|xi≠0. Signal x is assumed to be block K-sparse if Ω=K, where K is a positive integer. In the kth greedy iterations, the BgOMP algorithm takes N largest correlations between the residual rk−1 and columns of A.Algorithm 1:Block generalized orthogonal matching pursuit.
Input: sensing matrix A, measurement vector Y, select N indexes in each iteration, number of blocks L, the number of iterations t, and the accuracy of recovery ε.Initialization:r0=Y, S0=∅.Iterate the following steps until stopping criteriont>k+1 or rt≤ε is met.Step 1: t=t+1;Step 2: st= set of indices corresponding to the N largest block elements in ATirt−1i∈suppx;Step 3: St=St−1∪stStep 4: x^St=argminY−AStx2;Step 5: rt=Y−AStx^St.Output: k=tmax; x^=argminx:suppx⊂SkY−AX2.


## 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.
IfS be a proper subset of Ω≠0 and matrix A satisfies block RIP of order Nk+N+Ω−ℓ, for some of υ≥1 and N≥1, then(2)AΩ−STqS2,∞−AWTqS2,∞≥1−ν+1δNk+N+Ω−ℓxΩ−S2Nν,where qS=PS†AΩ−SxΩ−S.The proof of Lemma1 has been included in Appendix A.Theorem 1.
Given anyv2≤ε, matrix A satisfies block RIP with the order Nk+N+Ω−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(3)δNk+N+Ω−k<1Ω/N+1.
Also, the minimum of nonzero block elements ofx satisfies the following condition:(4)mini∈Ωxi2>2ε1−Ω/N+1δNk+N+Ω−k.Proof: .
First, we assume that BgOMP chooses the right block indices ink iterations, i.e., Sk, which corresponds to ATirk−1. Moreover, we have Sk=kN. The notation Ω−Sk indicates a set with elements belonging to Ω but not included in Sk. Let Ω∩Sk=ℓ, and we have Ω∩Sk=Ω−Ω−Sk≥k and 0<k≤ℓ≤Ω. In addition, let W be the set of N incorrect indexes indices. Obviously, W⊂Ω∪Sk¯ and W=N. Suppose αjk denotes the j-th largest correlation between rk and the columns of A that belong to the set of incorrect indexes. Also, let βik denotes the i-th largest correlation between rk and the columns of AΩ−Sk. Obviously, to prove the support condition of BgOMP, it is equivalent to show that β1k>αNk. Thus, based on Lemma 1 in [7], we can define β1k and αNk as follows:(5)β1k=AΩ−SkTrk2,∞,(6)αNk=minAi,rk,i∈W≤AWTrk2,2N,where ⋅ represents inner product operator. For the convenience of presentation, we write Aias Ai. From the above, it suffices to show that(7)AΩ−SkTrk2,∞>AWTrk2,2N.
Hence, we can obtain with a least square estimation as follows:(8)x^Sk=ASkTASk−1ASkTY
Then, by step 5 of Algorithm1 and (8), we have(9)rk=Y−ASkx^Sk=I−ASkASkTASk−1ASkTY=aPSk†AΩxΩ+v=bPSk†AΩ−SkxΩ−Sk+PSk†v,Where (a) is from the definition of PSk†=I−ASkASkTASk−1ASkT and (b) follows from the fact that PSk†ASk=0. Thus, on the left-hand side of (7), we obtain a lower bound as(10)AΩ−SkTrk2,∞≥AΩ−SkTPSk†AΩ−SkxΩ−Sk2,∞−AΩ−SkTPSk†v2,∞.
Similarly, it is easy to obtain an upper bound with the right-hand side of (7):(11)AWTrk2,2N≤AWTrk2,∞≤AWTPSk†AΩ−SkxΩ−Sk2,∞+AWTPSk†v2,∞
Integrating (7), (10), and (11), we show that(12)AΩ−SkTPSk†AΩ−SkxΩ−Sk2,∞−AWkTPSk†AΩ−SkxΩ−Sk2,∞>AΩ−SkTPSk†v2,∞+AWTPSk†v2,∞.
In the following, with the aim of Lemma1, we derive a lower bound of (12):(13)AΩ−SkTPSk†AΩ−SkxΩ−Sk2,∞−AWTPSk†AΩ−SkxΩ−Sk2,∞≥1−Ω−ℓ/N+1δNk+N+Ω−ℓxΩ−Sk2Ω−ℓ.
By assumptionΩ∩Sk=ℓ, we have(14)xΩ−Sk2≥Ω−ℓmini∈Ω−Skxi2≥Ω−ℓmini∈Ωxi2.
Using (13) and (14), it is trivial to have(15)AΩ−SkTPSk†AΩ−SkxΩ−Sk2,∞−AW−SkTPSk†AΩ−SkxΩ−Sk2,∞≥1−Ω−ℓ/N+1δNk+N+Ω−ℓmini∈Ωxi2≥a1−Ω−k/N+1δNk+N+Ω−kmini∈Ωxi2,where (a) denotes the fact that 0<k≤ℓ from Lemma 2 in [12, 13]. Then, we reach the following equivalence that(16)AΩ−SkTPSk†v2,∞+AWTPSk†v2,∞=Ai0TPSk†v2+Aj0TPSk†v2=Ai0∪j0TPSk†v2,1≤a2Ai0∪j0TPSk†v2≤b21+δNk+N+Ω−ℓPSk†v2≤c21+δNk+N+Ω−ℓε,where i0∈Ω−Sk,j0∈W. (a) is because Ai0∪j0TPSk†v is a 2×1 block vector and the property of norm X1≤nX2; (b) is reduced to (3) in [14]; and (c) follows from(17)PSk†v2≤PSk†2v2≤v2≤ε.With (15) and (16), we reach that(18)1−Ω−k/N+1δNk+N+Ω−kmini∈Ωxi2>21+δNk+N+Ω−ℓεmini∈Ωxi2>21+δNk+N+Ω−ℓε1−Ω−k/N+1δNk+N+Ω−k.
We rearrange (18) as follows:(19)mini∈Ωxi2>2ε1−Ω/N+1δNk+N+Ω−k.
Because of the constantδNk+N+Ω−ℓ∈0,1, the RIC bound of the BgOMP algorithm can be represented as(20)δNk+N+Ω−k<1Ω/N+1.
Thus, we complete the proof.Theorem 2.
Let a matrixA satisfy the block RIP with the order Nk+N+Ω−k and the RIC bound of BgOMP meet the condition in (20). Otherwise, the BgOMP algorithm fails to recover the block signals x.Proof.
For someN≥1 and 0<k≤Ω, we have(21)δNk+N+Ω−k<1Nk+N+Ω−k≤1Ω/N+1.
Hence, letδNk+N+Ω−k=δ and Theorem 2 is equivalent to prove the following inequivalence:(22)1Nk+N+Ω−k≤δ<1.
The BgOMP algorithm fails to recoverx.
The preparatory work: for anyλ=Nk+N+Ω−k−1≥1, λ is a positive integer. Let us define a matrix function as(23)Bd=λλ+1IdλEdλ×dλ+1Ed×dλλ+1λ+2λ+1Id,where Edλ×d=Id,⋯Id∈ℝdλ×d, with Id being the d×d identity matrix. Meanwhile, we define a constant s and matrix Cd as(24)s=δ−1Nk+N+Ω−k,Cd=Bd−sIλ+1d.
In the following, we divide the proof into two steps:Step 1. We plan to prove that Cd is a symmetric positive matrix. Therefore, Cd can be transformed into matrix ATdAd by Doolittle decomposition, and then, we can ensure that Ad satisfies the block RIP of order Nk+N+Ω−k with δNk+N+Ω−k=δ. 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 x=1dT,1dT⋯1dTT∈ℝdλ with all of its entries being 1. Without loss of generality,x can be extended to xd=1dT,⋯1dT,0dTT∈ℝdλ+1. Integrating (23),Yd=Adxd and Cd=ATdAd.(25)Adλ+1TYd2=Adλ+1TAdxd2=0dλ×d,IdTCdxd2=1λ+1Ed×dλ,λ+2λ+1−sIdxd2=λdλ+1.
Similarly,(26)AdiTYd2=AdiTAdxd2=0i−1λ×d,Id,0d+1−iλ×dTCdxd2=λdλ+1−sd,where 1≤i≤λ. By (25) and (26), sinces≥0, we notice that(27)Adλ+1TYd2≥AdiTYd2.
Therefore, in the first iteration, BgOMP will choose the position of0dT in which xd is selected as the indexes; this goes against our hypothesis. By (25) and (26), to guarantee successful recovery, xmust satisfy s<0; that is, δ<1/Nk+N+Ω−k≤1/Ω/N+1.
Theorem3 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 1
The changes of bound with sparsity level K.


## 4. Conclusion

In this paper, the support conditions of recovery block-sparse signals by using BgOMP are proposed; the bound of RIP constant must satisfy1/Ω/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.



---

*Source: 9438793-2021-01-30.xml*