The permutation-based block compressed sensing (CS) scheme is a new CS-based image compression method, in which permutation strategies are used prior to sampling with purpose of balancing the sparsity levels among the blocks. Although it has been shown to be an efficient method to improve sampling efficiency, there remain several fundamental questions on both the theoretical and practical side of this scheme. This paper primarily concerns about one of these theoretical issues revolving around the error performance of block CS (BCS). In this paper, we analyze the error performance bound of BCS and a new error performance bound is established. It is revealed that better recovery quality can be achieved if the permutated 2D signal has smaller maximum block sparsity level.
The set of all K -sparse vectors can be denoted by K = {x ∈ RN×1 | x 0 ≤ K} .
(
For a K -sparse signal x , the measurement vector can be obtained by
y = Φx . where Φ ∈ RM×（NM N）is a measurement matrix and y ∈ RM×1 is the measurement vector of x .
According to CS theory, x can be recovered from y if Φ ∈ RM×N satisfies restricted isometry property (RIP) [1, 2]. x can be recovered by solving xˆ = arg min x 1 s. t . y=Φx .
(3) 2.2.
For an image D ∈ R N × N , it can be represented by
X = ΨDΨ T , represented by where Ψ ∈ R N × N is a wavelet basis and X ∈R N× N is the wavelet coefficient matrix. In block-based CS scheme, X is split into a lot of blocks with dimension of n × n . It can be (2) (4) (6)
(5)
(
Let Ki = xi 0 , then, the block sparsity level vector of X can be denoted by K = [K1, K2,..., KL ] . Let Kmax = K ∞ be the maximum block sparsity level. If ΦB satisfies RIP with order Kmax , we can reconstruct all blocks of X , and then reconstruct the original image D .
For a signal s ∈ Rn , the best k -term approximation is defined by where Xi is i -th block of X and L = N n .
Let xi ∈ Rn×n be the vectorized signal of Xi , then we can be obtain the measurement vector by σ k (s)1 := min s − z 1 .
z∈k s − sˆ 2 ≤ c0 σ k (s)1 k
. X1 X L+1 X = X L− L+1
X2 X L+2 XL− L+2
X L
X2 L ,
X L yi = ΦB xi ,
For compressible signals, the CS reconstruction via solving (3) is nearly as good as that using the best k -term approximation of s .
Lemma 1 [19]: Suppose that ΦB is a measurement matrix obeying RIP with order 2k , and δ 2k ≤ 2 −1. Then, for a signal s , the solution sˆ to (3) obeys for some constant c0 .
Obviously, the above lemma can also be generalized to 2D signals, a representative result can be found in [15]. Lemma 1 and its generalized result for 2D signals show the fact that the CS reconstruction error via solving (3) is bound by the best k -term approximation error. But, what is the Obviously, the inequality (11) is equivalent to Because
n n u ≥ u(i) .
1 n−l +1 i=l u ≥ n n u(i) .
1 (n −1) i=2
n (n −1) u 1 − n i=2 u(i) ≥ 0 .
Proof of Lemma 2.1: When l=2 , the above inequality can be rewritten as
n (n −1) u 1 − n u(i)
i=2
n n
= (n −1) u(
n n
= (n −1) u(
In this section, we carefully research the reconstruction error bound of BCS for 2D signals. Before we give the main theorem of this paper, we provide two lemmas that will be used in the proof.
Lemma 2. Suppose that s ∈Rn is a k -sparse signal, and k is a positive integer, then we have 1 k σ k (s)1 := min s − z 1 ≤ z∈k k − k ⋅ s 1 .
(9) Proof: In order to prove Lemma 2, we will require the following lemma.
Lemma 2.1. Suppose that u∈Rn is a signal whose entries are arranged in amplitude descending
order, i.e., u(
Now, we generalize inequality (10) to l ≥ 2 , u 1 ≥ ≥ ≥
n n u(i) ≥ n −1 i=2 n n u(i) , n − l +1 i=l
n n u(i) n − 2 i=3 which complete the proof.
Proof of Lemma 2: Firstly, we prove inequality (9) in the case of k ≤ k .
We define the support set of s as F = supp(s) , i.e., the set of i for which si ≠ 0 . Let sF ∈Rk be a
signal vector which only reserve the entries of s in the support set. Let sF′ ∈Rk be a signal vector
obtained by rearranging sF in amplitude descending order, i.e., sF′ (
(15) where the first equality holds because s = s(i) + s(i) = s(i) +0 = sF 1 and the second 1 i∈F i∉F i∈F i∉F equality uses the fact that sF′ is just a signal vector obtained by rearranging the entries order of sF .
Let s′ be the best k -term approximation of s , then we have σ k (s)1 = s − s′ 1 =i=kk+1 sF′(i) ≤ k −k k sF′ 1 = k −k k s 1 , (16) where the inequality uses the result of Lemma 2.1.
Now we consider the case of k > k . We have σ k (s)1 := min s − z 1 = 0 ≤ z∈k k1 k − k ⋅ s 1 , (17) which gives (9) with k > k .
Lemma 3. Suppose that s ∈Rn is a k -sparse signal, then we have Proof: Firstly, we consider arbitrary signal vector v =[v1,v2,...,vn]∈Rn . For any signal v , we have
v 12 = i=n1 jn=1 vi ⋅ v j ≤ n n vi 2 + v j i=1 j=1 2 2
= n v 22 , where the equality condition holds if and only if v1 = v2 == vn .
Of course, sparse signal s ∈Rn also satisfies (19). However, we can derive a tighter bound for sparse signal by taking the sparse characteristic of s into consideration. Let sF ∈Rk be a signal vector which only reserves the nonzero entries of s , as used in Lemma 3.
According to (19), we have (18)
(19) (20) (21) Combining (15) with (20), we obtain sF 12 ≤ k sF 22 . which complete the proof.
Leveraging the above lemmas, we can establish the main result of this paper.
Theorem 1. Suppose that ΦB is a measurement matrix obeying RIP with order 2K , δ 2K ≤ 2 −1and K ≤ 2Kmax Kmin（Kmax + Kmin）, where Kmin is the minimum block sparsity level. Assume that each block of x = x1T , x2T ,..., xLT T ∈ RN×1 is sampled by ΦB via (6), where xi ∈ Rn×1 is i -th block of x . Let xˆi be the reconstruction signal of xi via solving (3), then for x , the CS recovery error μ = x − xˆ 2 x 2 obeys μ ≤ c Kmax − K ,
K (22) where xˆ = xˆ1T , xˆ2T ,..., xˆLT T ∈ RN×1 is the reconstruction signal of x and c is a finite constant. Proof: According Lemma 1 and Lemma 2, we have where ci is a finite constant and c = maxi ci .
We bound the square of reconstruction error term by xi − xˆi 2 ≤ ci σ K ( xi )1 ≤ c Ki − K where the first inequality uses the result of (23), the second inequality uses the inequality K ≤ 2Kmax Kmin（Kmax + Kmin）, the third inequality uses the result of Lemma 3, the fourth inequality uses the inequality Ki ≤ Kmax and the last inequality use the fact K ≤ Kmax .
Taking the square-root on both sides of (24) gives the inequality (22).
In conclusion, Theorem 1 shows that the reconstruction error bound of BCS depends on the maximum block sparsity level of the sparse signal. In the best case, when Kmax = K , which means that the nonzero elements of the 2D signal is distributed among the blocks evenly, the 2D sparse signal can be recovered perfectly by solving (3).
The main application of Theorem 1 is the permutation-based BCS scheme for CS-based image compression applications. According to Theorem 1, better recovery quality can be achieved if the signal has smaller maximum block sparsity level. Therefore, we can improve sampling efficiency by using permutation strategies prior to sampling. In practice, a lot of permutation strategies [11-18] have been proposed. The simulation results of [11-18] have shown that the reconstructed-images quality can be improved significantly if we can reduce the maximum block sparsity level by using permutation strategies prior to sampling. The successful application of permutation-based BCS scheme in CS-based image compression field can be regarded as a favorable evidence for Theorem 1.
In this paper, we analyze the error performance bound of BCS. It is revealed that better reconstruction performance can be achieved if the 2D signal has smaller maximum block sparsity level. We also show its potential applications in image compression field.