Improvement of Forward-Backward Pursuit Algorithm Based on Weak Selection ()
1. Introduction
Compressed Sensing (CS) [1] [2] [3] is a new kind of signal processing theory, which makes use of the sparsity of signal to combine sampling and compression together. CS theory broke through the traditional Nyquist sampling limitation and achieved an efficient acquisition of signal, therefore, CS theory makes high speed and quality of information transmission to be possible. Once CS theory was proposed, it aroused scholars’ wide research. Now it is widely used in signal processing, wireless communication and medical imaging, etc.
The main research of CS theory includes signal sparse transformation, design of measurement matrix and signal reconstruction algorithm. At present, the common algorithms used in CS theory are mainly divided into two categories: one is linear programming algorithm based on optimization norm
, which approximates the original signal by converting the non-convex problem into convex problem. It mainly includes Basis Pursuit (BP) [4] which uses norm
to substitute norm
with quite high computing complexity; Iterative Thresholding (IT) [5] and Iterative Hard Thresholding (IHT) [6] that are derived by an optimization problem which is similar to OMP algorithm; Two Stage Thresholding (TST) [7] that adopts Two Stage Threshold strategy to improve its reconstruction performance, etc. The other one is greedy pursuit algorithm based on norm
, which approximates the original signal by local optimization. It includes Matching Pursuit (MP) [8] and Orthogonal Matching Pursuit (OMP) [9] at the earliest. Later on, based on the idea of backward strategy, Compressive Sampling Matching Pursuit (CoSaMP) [10] , Subspace Pursuit (SP) [11] were proposed, etc.
On the basis of TST algorithm, N. B. Karahanoglu and H. N. Erdogan proposed Forward-Backward Pursuit (FBP) in reference [12] with the feature without prior information of the sparsity. FBP algorithm uses fixed forward step to select atoms and backward step to delete atoms, through this process to implement the support set expansion and reduction. Hence, FBP does not require K as a priori in contrast to SP and CoSaMP. Additionally, the backward step of FBP can remove some possibly misplaced atoms from the support set, which is an advantage over forward greedy algorithms such as OMP. But in practical application, the major issue of FBP algorithm is time complexity, as the forward and backward step is a fixed size in each iteration without considering the transformation of signal in the process of iteration. The execution efficiency is low, thus it leads to taking more time to reconstruct signals and affects the reconstruction accuracy.
To address the above issues of FBP, forward-backward pursuit algorithm based on weak selection (SWFBP) was proposed by introducing threshold strategy into FBP algorithm to calculate the forward step, by which can make the forward step flexible. And for the first few iterations, most of the atoms which are selected are right, and they don’t need backward strategy, so this part of atoms would be directly incorporated into support set. Through above two methods, SWFBP has flexible forward and backward steps which would bring down the computing complexity and improve the reconstruction performance. The simulation results show that SWFBP is a more efficient greedy pursuit algorithm without prior information of the sparsity compared with FBP.
2. Compressed Sensing Theory and Reconstruction Algorithm
2.1. Compressed Sensing Theory
The core of CS theory is choosing an appropriate measurement matrix, by which can project a high-dimensional sparse signal to a low dimensional space, then use reconstruction algorithm to reconstruct the original high-dimensional signal from low dimension projection value. Specifically, suppose that
is a K-sparse, N-dimensional digital signal, that is, only K of
are valid and nonzero. We are interested in the case when
. One can reconstruct signal
with the following equation:
(1)
where
is an M-dimensional vector indicating the measurement value.
represents an
matrix (M < N), which called measurement matrix as well. Reference [13] states that if the signal
is sparse, then it will be reconstructed from a small number of linear projections via some optimization algorithms. The original solution of sparse signal reconstruction is mathematically described as follow:
subject to
(2)
However,
minimization problem is NP-hard, while greedy pursuit algorithms provide a favorable tool to solve this problem for approximate solutions. Reference [14] point out that when the measurement matrix
satisfies the restricted isometry property (RIP), we can solve Equation (2) by
optimization problem, i.e.:
subject to
(3)
2.2. Forward-Backward Pursuit Algorithm
FBP algorithm is a greedy pursuit algorithm based on
norm minimization problem, which extends the signal support set by forward and backward step. It receives wide attention due to its high reconstruction accuracy and the feature without prior information of the sparsity. The first stage of FBP algorithm is the forward step which expands the support set by indices of
largest magnitude elements in
, where we call
the forward step size. The second step is removing
smallest magnitude projection coefficients in
. Similar to
,
is referred to as the backward step size. The forward step size is chosen larger than the backward step size, hence the support estimate is enlarged by
atoms at each iteration.
When the sparse degree of signal is relatively small, the residual will constantly decrease by the process of iteration until it meet the termination conditions
(
is the termination threshold of iteration). As well, when the sparse degree is a large one, then it will exit the iteration by the termination conditions
. A schematic diagram of the FBP algorithm is depicted in Figure 1 and the pseudo-code of FBP algorithm is given in Algorithm 1.
Algorithm 1: FBP Algorithm
Input: Measurement matrix
, measurement vector
Define: Forward step
, backward step
, largest number of iterations
, termination threshold of iteration
Initialize:
,
,
while true do
Figure 1. Description of FBP algorithms.
Forward update:
Backward update:
Projection:
if
or
then
break
end if
end while
Output:
2.3. Forward-Backward Pursuit Algorithm Based on Weak Selection
The basic framework of SWFBP algorithm is similar to FBP algorithm. In the first few iterations, we select atoms by weak selection strategy. As most of these atoms are right, so join these atoms into support set directly. For the following iterations, first of all, through threshold strategy to expand the forward support set, and the forward step
is equal to the length of this set. Then calculate the orthogonal projection of the measurement vector
on this support set. Next, use
to calculate the backward step
and delete the indexes of
smallest orthogonal projection coefficients. Last, calculate the new projection coefficients and update the residuals. Terminal condition of iteration is the same as FBP algorithm. A schematic diagram of the SWFBP algorithm is depicted in
Figure 2. Description of SWFBP algorithms.
Figure 2 and the pseudo-code of SWFBP algorithm is given in Algorithm 2.
Algorithm 2: SWFBP Algorithm
Input: Measurement matrix
, measurement vector
Define: Threshold parameter
, value of step difference
, largest number of iterations
, threshold of iteration numbers
, termination threshold of iteration
Initialize:
,
,
while true do
Forward update:
the forward step
if
then
else
Backward update:
the backward step
end if
Projection:
if
or
then
break
end if
end while
Output:
3. Simulations and Analysis
Simulation environment was MATLAB R2015b. We experiment with one- dimensional sparse signal (Gaussian sparse signal and 0 - 1 sparse signal) and two-dimensional international standard test image lena.bmp by using FBP and SWFBP algorithm. Measurement matrix
obeys Gaussian distribution.
3.1. Reconstruction of One-Dimensional Sparse Signal
Experimental parameters are setting as follows: length of the sparse signal N = 256, sampling numbers M = 102, sparsity level K = 20, largest number of iterations
, termination threshold of iteration
, threshold parameter
, value of step difference
. For FBP algorithm, the forward step
, 10, 20 separately, and corresponding to
, the backward step
, 8, 18. Simultaneously, for SWFBP algorithm, the relationship between
and
is
. For each combination of (K, M), do 500 times independent experiments to compare the frequency of exact reconstruction, average recovery time and average normalized mean-squared error (ANMSE). The condition of exact reconstruction is described as follow:
(4)
And ANMSE was calculated by Equation (5).
(5)
Among (5),
represents the reconstruction signal for
.
Figure 3 shows the reconstruction results of SWFBP
and FBP
, under Gaussian sparse signal. From Figure 3, we can see that the exact reconstruction frequency of SWFBP algorithm is higher than FBP algorithm whether under different sparsity or sampling numbers. For example, when the sparsity level K = 40, the exact reconstruction frequency of SWFBP is 90% and FBP’s is 85%. For recovery time, compared with FBP algorithm, SWFBP algorithm has improved largely, and with the increasing of K, the effect is more obviously. Specifically, when
, recovery time of SWFBP is 50% to 60% of FBP’s. For ANMSE, there is not much difference between SWFBP and FBP with
increasing, but in general, SWFBP’s is lower than FBP’s.
Figure 4 shows the reconstruction results of SWFBP
and FBP
, under 0 - 1 sparse signal. Similar to the above test, on the exact reconstruction frequency, SWFBP is not lower than FBP. And for ANMSE, there is also not much difference between SWFBP and FBP. These are because that there is no difference between non-zero element in 0 - 1 sparse signal, also this will lead the algorithms’ reconstruction performance reduce greatly for which selecting the atoms according to the correlation of residual. In spite of this, the recovery time of SWFBP has improved significantly.
3.2. Threshold Parameter
In SWFBP algorithm, parameters involved are
,
,
and
. Among them,
and
are mainly decided by
. In this part, we experiment with different
under the condition of
and
for SWFBP algorithm.
Figure 3. Reconstruction results for Gaussian sparse signal. (a) Comparison of the exact reconstruction frequency under different K; (b) Comparison of the exact reconstruction frequency under different M; (c) Comparison of average recovery time; (d) Comparison of ANMSE.
Figure 4. Reconstruction results for 0 - 1 sparse signal. (a) Comparison of the exact reconstruction frequency under different K; (b) Comparison of the exact reconstruction frequency under different M; (c) Comparison of average recovery time; (d) Comparison of ANMSE.
Figure 5 shows the reconstruction results of SWFBP algorithm while
is equal to 0.65, 0.75, 0.85 and 0.95. From Figure 5, we know that with the increase of
, the exact reconstruction frequency and average recovery time are increased in the same space. In other words, the influence of parameter
to this algorithm is that with
increase, the exact reconstruction frequency also increase, but at the cost of more recovery time.
3.3. Reconstruction of Two-Dimensional Image
In order to further illustrate the reconstruction performance of SWFBP algorithm, in this part, we experiment with two-dimensional standard image 256 × 256 Lena. The parameters are setting the same as part 3.1. We choose two indicators to judge the reconstruction performance of algorithm: Recovery time, Peak Signal to Noise Ratio (PSNR), through the following two formulas to calculate PSNE.
(6)
(7)
Figure 6 shows the curve of recovery time and PSNR under different sampling numbers respectively. It can be seen that compared with FBP, performance of SWFBP are all have certain improved. By introducing the threshold strategy in SWFBP algorithm, the iteration times decreased, thus the recovery time is shorten greatly, all are maintained under 3 seconds. When sampling number is 70, SWFBP algorithm has 1 dB gain in the PSNR over FBP algorithm, and the recovery time is only 40% of FBP algorithm.
Figure 5. (a) Comparison of exact reconstruction frequency under different threshold
; (b) Comparison of average recovery time under different threshold
.
Figure 6. (a) Comparison of recovery time for two-dimensional image; (b) Comparison of PSNR for two-dimensional image.
Figure 7. Reconstruction images for Lena by FBP and SWFBP at M/N = 0.4.(a) Original image; (b) SWFBP
; (c)FBP
; (d) FBP
; (e)FBP
.
Table 1. Comparison of recovery time and PSNR under different sampling rate.
Figure 7 shows the reconstruction images of Lena under sampling rate M/N = 0.4. As shown in Figure 7, the reconstruction image of SWFBP is clearer than FBP’s visually, i.e. the improved algorithm has higher accuracy in image sparse approximation.
Table 1 shows the recovery time and PSNR under different sampling rate for FBP and SWFBP algorithm. From the date in Table 1, we can draw a conclusion that SWFBP has advantages in no matter recovery time or PSNR.
4. Conclusion
On the basis of FBP algorithm, in this paper, SWFBP algorithm was proposed. By adapting a simple threshold strategy to FBP algorithm, the proposed algorithm SWFBP can be flexibly the forward and backward steps, and thus to combine the high reconstruction accuracy and flexible atom selecting mechanism of weak selection together. The simulation results demonstrate that SWFBP algorithm provides a better performance and lower computation cost compared to FBP algorithm. In particular, while the sparse signal obeys Gaussian distribution, the exact reconstruction frequency and accuracy are better than FBP, and while the sparse signal obeys 0 - 1 distribution, the exact reconstruction frequency and precise are approximate to FBP’s. Reconstruction results of two-dimensional images show that the reconstruction performances of SWFBP have certainly improved while its recovery time is decreased obviously. Despite of this, the atom selecting method is still not match enough so far, and we hope to find a solution to perfect the atom selecting mechanism in the future.
Acknowledgements
This work was supported by the Specialized Research Fund for the Doctoral Program of Higher Education (No. 20130031110032 and No. 20130031110033).