An improved algorithm of segmented orthogonal matching pursuit based on wireless sensor networks

Abstract

Aiming at the problems of low data reconstruction accuracy in wireless sensor networks and users unable to receive accurate original signals, improvements are made on the basis of the stagewise orthogonal matching pursuit algorithm, combined with sparseness adaptation and the pre-selection strategy, which proposes a sparsity adaptive pre-selected stagewise orthogonal matching pursuit algorithm. In the framework of the stagewise orthogonal matching pursuit algorithm, the algorithm in this article uses a combination of a fixed-value strategy and a threshold strategy to screen the candidate atom sets in two rounds to improve the accuracy of atom selection, and then according to the sparsity adaptive principle, the sparse approximation and accurate signal reconstruction are realized by the variable step size method. The simulation results show that the algorithm proposed in this article is compared with the orthogonal matching pursuit algorithm, regularized orthogonal matching pursuit algorithm, and stagewise orthogonal matching pursuit algorithm. When the sparsity is 35 < K < 45, regardless of the size of the perception matrix and the length of the signal, M = 128, N = 256 or M = 128, N = 512 are improved, and the reconstruction time is when the sparsity is 10, the fastest time between 25 and 25, that is, less than 4.5 s. It can be seen that the sparsity adaptive pre-selected stagewise orthogonal matching pursuit algorithm has better adaptive characteristics to the sparsity of the signal, which is beneficial for users to receive more accurate original signals.

Introduction

Data compression performed by sensor nodes in wireless sensor networks (WSNs) before data transmission can effectively save energy and extend battery life. ¹ In recent years, a large number of compression algorithms have been proposed and applied. They also have achieved remarkable results. After the signal is sent out, the space occupied by the signal is reduced by compression, and the original signal is restored through signal reconstruction after reaching the destination node.

In terms of signal reconstruction, the main algorithms include the minimum convex optimization algorithm, combination algorithm, and greedy algorithm. ² The main idea of the $l_1$ norm minimum convex optimization algorithm ³ is to minimize the $l_1$ norm of the solution vector under linear constraints. This type of method can accurately reconstruct all sparse signals under certain conditions. However, the computational complexity is high, the reconstruction time is long, it is difficult to solve the problem of large-scale signal reconstruction, and the practicability is poor. The combination algorithm ⁴ is structured sampling on the signal, and then uses the group measurement to obtain the support set of the signal, but this method is often based on a certain characteristic of the signal and lacks versatility. The greedy algorithm ⁵ is solved by minimizing the $l_0$ norm, which gradually approximates the original signal by selecting a local optimal solution at each iteration. Each iteration mainly includes two steps of atomic matching and updating, using the coefficient and support of the signal. The greedy algorithm is more widely used than the previous two algorithms because it allows a certain reconstruction error, is easy to implement, and has a fast reconstruction speed.

The greedy algorithm is the earliest proposed matching pursuit (MP) algorithm. ⁶ The atom selection strategy of the MP algorithm is to select the atom with the highest degree of matching with the residual from the observation matrix as the candidate atom. This atom selection strategy can be guaranteed to become high accuracy, but the orthogonality between the iterative residual and the selected atom set cannot be guaranteed. This makes the approximate solution obtained by MP suboptimal in the sense of the optimal K term approximation. The orthogonal matching pursuit (OMP) algorithm ⁷ improves the MP algorithm. The OMP algorithm uses the least squares method to update the linear combination coefficients of the selected atoms each time the set of selected atoms is updated. However, the MP and OMP algorithms are not ideal in reconstruction efficiency and accuracy. ⁸ Needell D and Vershynin R. proposed a regularized orthogonal matching pursuit (ROMP) algorithm on the basis of the OMP algorithm, ⁹ using the regularization method which finds the atom set with the largest energy in the candidate atom set to update the support set. Donoho D and Tanner J. proposed a stagewise orthogonal matching pursuit (StOMP) algorithm. ¹⁰ By setting a threshold, atoms are selected in batches instead of simply selecting the atom with the highest degree of matching with the signal. This can improve the efficiency of the algorithm, but the reconstruction accuracy is poor. At the same time, the above greedy algorithms all require that the sparsity of the signal is known. If the sparsity estimation is not accurate, many signals will not be accurately reconstructed, but this premise is difficult to meet in practical applications. ¹¹ Thong T et al. proposed the sparsity adaptive matching pursuit (SAMP) algorithm. ¹² This algorithm is not affected by signal sparsity. It is used in preseting the initial step size and adding a fixed value in each iteration. The step size gradually realizes the estimation of the signal sparsity, and at the same time updates the residual and the support set to approximate the original signal, but overall, the reconstruction efficiency of the algorithm is low. ¹³

Aiming at the problem of low reconstruction rate, this article proposes a pre-selection strategy to enhance the accuracy of the algorithm in the atom selection stage. The atom selection part is refined, it is carried out in two steps. First, the atoms are selected through a fixed-value strategy, the atoms after the primary selection are used as candidate atoms in the reselection stage. In the reselection stage, a threshold selection strategy is used to screen the candidate atoms a second time. After the reselection stage is completed, the atoms that pass the screening twice will be added to the support set to participate in the signal reconstruction. Finally, according to the principle of sparsity adaptation, the step size is used to achieve the staged selection of atoms in the candidate set. As the iterative process is carried out in segments, the step size and support set are continuously updated. And finally, the third screening of atoms is achieved. This approach enables the reconstructed signal to recover the original signal more accurately, and the reconstruction efficiency of the algorithm is also improved. Compared with the traditional algorithm, the atom is screened three times, so that the screened signal is closer to the original signal. After reconstruction, the original signal is recovered more accurately and the reconstruction efficiency of the algorithm is improved, the node storage cost and communication overhead are reduced, and the sampling efficiency is indirectly improved, which lays a solid foundation for the subsequent data transmission of the WSN.

Basic theory of compressed sensing

Compressed sensing includes three contents, which are the sparse representation of the signal, the measurement of the observation matrix, and the reconstruction algorithm. In the mathematical model of compressed sensing: ¹⁴

$$\mathrm{y}=\mathrm{Ax}$$

(1)

where x represents the original signal, A represents the sparse mapping matrix, and y represents the compressed measurement. The process of sparse representation is that the original signal can be reflected into a small vector space through the sparse mapping matrix A, and the number of rows in the vector space after the effect will be much less. This process is actually the core idea of sparse theory, which is to use low-dimensional signals to describe high-dimensional signals. ¹⁵ The specific compression process is as follows: first, sparsely represent the signal on an orthogonal basis Ψ, then determine an observation basis Φ, which needs to be uncorrelated with Ψ, then the observation value Y can be obtained by y = Φx, and finally, Y is optimized and reconstructed. The mathematical model of compressed sensing is shown in Figure 1.

Figure 1.

Mathematical model of compressed sensing.

Sparse representation of the signal

If the signal x ∈ R^N of length N has only K coefficients that are not 0 (or obviously larger than other coefficients) in a certain transform domain, and K << N, then the signal x is sparse in this transform domain, also called K-sparse. ¹⁶ If the signal on the sparse basis matrix $\Psi =[{\Psi }_1,{\Psi }_{2,\cdots ,}{\Psi }_N]$ is represented as S, then the sparse transformation process can be expressed as follows:

$$\mathrm{x}=\sum _{\mathrm{i}=1}^{\mathrm{N}}{\mathrm{S}}_{\mathrm{i}}{\mathrm{\Psi }}_{\mathrm{i}}=\mathrm{\Psi }\mathrm{S}$$

(2)

Observation matrix measurement

Obtain M(K << M << N) linear projections on the measurement basis $\mathrm{\Phi }=({\mathrm{\Phi }}_1^{\mathrm{T}},{\mathrm{\Phi }}_2^{\mathrm{T}},\cdots ,{\mathrm{\Phi }}_{\mathrm{M}}^{\mathrm{T}})$ . y(i)=<x, ${\mathrm{\Phi }}_{\mathrm{j}}^{\mathrm{T}}$ >, j = {1,2,…, M}, is used to accurately reconstruct the original signal ¹⁷ in the form of a matrix, which can be written as:

$$\mathrm{y}=\mathrm{\Phi }\mathrm{x}=\mathrm{\Phi }\mathrm{\Psi }\mathrm{S}$$

(3)

Compressed sensing algorithm reconstruction

Starting from the M measured values, the original signal x is reconstructed or approximated with the help of the observation matrix Φ and the reconstruction algorithm. In the case where x is K-sparse, the reconstruction of the signal can be equivalent to the problem of the optimal solution under the constraints, ¹⁸ which is expressed as follows:

$$\hat{x}=\mathrm{argmin}\Vert x{\Vert }_0$$

(4)

$$s.t.y=\mathrm{\Phi }x$$

(5)

Feasibility analysis based on threshold reconstruction

The sparsity adaptive pre-selected segmented OMP algorithm proposed in this article uses threshold indicators to select atoms when the signal sparsity is unknown. In this section, we will use the constraint isometric property to prove that the sparsity of the algorithm is unknown, but the threshold can still accurately reconstruct the original signal. The definition of constrained isometric properties is presented below.

Definition 3.1 ¹⁹

For any K-sparse signal x and the constant δ_K∈(0,1), if

$$(1-{\mathrm{\delta }}_{\mathrm{K}})\Vert \mathrm{x}{\Vert }_2^2\le \Vert {\mathrm{A}}_{\mathrm{I}}\mathrm{x}{\Vert }_2^2\le (1+{\mathrm{\delta }}_{\mathrm{K}})\Vert \mathrm{x}{\Vert }_2^2\forall \mathrm{x}\in {\mathrm{R}}^{\left|\mathrm{I}\right|}$$

(6)

then it is said that matrix A satisfies the K-order constrained equidistant property, and δ_K is called the K-order constrained equidistant constant, where the index I∈{1,2,…, N} and |I|≤ K, A_I is only corresponding to matrix A for the sub-matrix composed of the columns of the index set I, and |I| represents the number of elements contained in the index set I.

Lemma 3.1 ¹⁹

If matrix A satisfies the s-order constraint equidistance, then for any index that satisfies the condition s ≥|Γ| Set Γ and any x∈R^N, y∈R^|Γ,| the following formula holds:

$$(1-{\mathrm{\delta }}_{\mathrm{\Gamma }})\Vert \mathrm{x}(\mathrm{\Gamma }){\Vert }_2\le \Vert {\mathrm{A}}_{\mathrm{\Gamma }}^{*}{\mathrm{A}}_{\mathrm{\Gamma }}\mathrm{x}(\mathrm{\Gamma }){\Vert }_2\le (1+{\mathrm{\delta }}_{\left|\mathrm{\Gamma }\right|})\Vert \mathrm{x}(\mathrm{\Gamma }){\Vert }_2$$

(7)

$$\Vert {\mathrm{A}}_{\mathrm{\Gamma }}^{*}\mathrm{y}{\Vert }_2\le \sqrt{(1+{\mathrm{\delta }}_{\left|\mathrm{\Gamma }\right|})}\Vert \mathrm{y}{\Vert }_2$$

(8)

Lemma 3.2 ¹⁹

Assuming that Γ and Λ are two disjoint sets, if A satisfies the |Γ∪Λ| order constraint equidistance with constant δ_|Γ∪Λ,| then for any x∈R^|Λ| has the following formula:

$$\Vert {\mathrm{A}}_{\mathrm{\Gamma }}^{*}{\mathrm{A}}_{\mathrm{\Lambda }}\mathrm{x}{\Vert }_2\mathrm{K}\le {\mathrm{\delta }}_{|\mathrm{\Gamma }\cup \mathrm{\Lambda }|}\Vert \mathrm{x}{\Vert }_2$$

(9)

Lemma 3.3 ¹⁹

For any two integers K₁ and K₂ satisfying the condition K₁ ≤ K₂, there are

$${\mathrm{\delta }}_{{\mathrm{K}}_1}\le {\mathrm{\delta }}_{{\mathrm{K}}_2}$$

(10)

Established

Let C be the support set of the signal obtained at the termination of the algorithm proposed in this section and satisfy q = |C.| The following proves that the algorithm estimates the signal x_j (1, 2,…, L) feasibility.

Corollary 2.3.1

Denote the index set Λ ={I₁, I₂,…, I_s}, let s∈N and s ≤ q, matrix A satisfies the q+s-order constraint equidistance with constant δ_q+s and ${\mathrm{\delta }}_{\mathrm{q}+\mathrm{s}}=\frac{\sqrt{\mathrm{s}}}{(1+\sqrt{2})\sqrt{\mathrm{q}}}$ , if each column of A in the measurement y_j = Ax_j satisfies:

$$\begin{array}{c}\multicolumn{1}{c}{\left|〈{\mathrm{A}}_{{\mathrm{i}}_1},{\mathrm{y}}_{\mathrm{j}}〉\right|\ge \left|〈{\mathrm{A}}_{{\mathrm{i}}_2},{\mathrm{y}}_{\mathrm{j}}〉\right|\ge \cdots \ge \left|〈{\mathrm{A}}_{{\mathrm{i}}_{\mathrm{s}}},{\mathrm{y}}_{\mathrm{j}}〉\right|}\\ \multicolumn{1}{c}{\ge \underset{\mathrm{m}\in \{1,2,\cdots ,\mathrm{N}\},\mathrm{m}\ne \mathrm{j},\mathrm{j}\in \mathrm{\Lambda }}{sup}\left|〈{\mathrm{A}}_{\mathrm{m}},{\mathrm{y}}_{\mathrm{j}}〉\right|}\end{array}$$

(11)

then there is

$$\mathrm{\Lambda }\cap \mathrm{C}\ne \varnothing$$

(12)

yes, where y_j =Ax_j = A_Cx_j(C).

Proof

Use the method of proof by contradiction. Suppose Λ∩ C ≠∅, then from equation (9):

$$\Vert {\mathrm{A}}_{\mathrm{\Lambda }}^{*}{\mathrm{y}}_{\mathrm{j}}{\Vert }_2=\Vert {\mathrm{A}}_{\mathrm{\Lambda }}^{*}{\mathrm{A}}_{\mathrm{C}}{\mathrm{x}}_{\mathrm{j}}(\mathrm{C}){\Vert }_2\le {\mathrm{\delta }}_{|\mathrm{\Lambda }\cup \mathrm{C}|}\Vert {\mathrm{x}}_{\mathrm{j}}(\mathrm{C}){\Vert }_2={\mathrm{\delta }}_{\mathrm{s}+\mathrm{q}}\Vert {\mathrm{x}}_{\mathrm{j}}{\Vert }_2$$

(13)

Note that $\tilde{\mathrm{C}}$  = {n₁, n₂,…, n_s}is the index set composed of the subscripts of the s largest components in|x_j| and satisfies

$$|{\mathrm{x}}_{\mathrm{j}}({\mathrm{n}}_1)|\ge |{\mathrm{x}}_{\mathrm{j}}({\mathrm{n}}_2)|\ge \cdots \ge |{\mathrm{x}}_{\mathrm{j}}({\mathrm{n}}_{\mathrm{s}})|\ge \underset{\mathrm{n}\in \{1,2,\cdots ,\mathrm{N}\},\mathrm{n}\notin \tilde{\mathrm{C}}}{sup}|{\mathrm{x}}_{\mathrm{j}}(\mathrm{n})|$$

(14)

where|x_j| is the vector composed of the absolute values of the components of vector x_j. Obviously $\tilde{\mathrm{C}}$ is a subset of C. Know from formula (12):

$$\begin{array}{c}\Vert {\mathrm{A}}_{\mathrm{\Lambda }}^{*}{\mathrm{y}}_{\mathrm{j}}{\Vert }_2\ge \Vert {\mathrm{A}}_{\tilde{\mathrm{C}}}^{*}{\mathrm{y}}_{\mathrm{j}}{\Vert }_2=\Vert {\mathrm{A}}_{\tilde{\mathrm{C}}}^{*}{\mathrm{A}}_{\mathrm{C}}{\mathrm{x}}_{\mathrm{j}}(\mathrm{C}){\Vert }_2\hfill \\ =\Vert {\mathrm{A}}_{\tilde{\mathrm{C}}}^{*}{\mathrm{A}}_{\tilde{\mathrm{C}}}{\mathrm{x}}_{\mathrm{j}}(\tilde{\mathrm{C}})+{\mathrm{A}}_{\tilde{\mathrm{C}}}^{*}{\mathrm{A}}_{\mathrm{C}\backslash \tilde{\mathrm{C}}}{\mathrm{x}}_{\mathrm{j}}(\mathrm{C}\backslash \tilde{\mathrm{C}}){\Vert }_2\hfill \\ \ge \Vert {\mathrm{A}}_{\tilde{\mathrm{C}}}^{*}{\mathrm{A}}_{\tilde{\mathrm{C}}}{\mathrm{x}}_{\mathrm{j}}(\tilde{\mathrm{C}}){\Vert }_2-\Vert {\mathrm{A}}_{\tilde{\mathrm{C}}}^{*}{\mathrm{A}}_{\mathrm{C}\backslash \tilde{\mathrm{C}}}{\mathrm{x}}_{\mathrm{j}}(\mathrm{C}\backslash \tilde{\mathrm{C}}){\Vert }_2\hfill \end{array}$$

(15)

Among them, C\ $\tilde{\mathrm{C}}$ is a set of elements that belong to C but do not belong to $\tilde{\mathrm{C}}$ . From Lemma 3.1:

$$\Vert {\mathrm{A}}_{\tilde{\mathrm{C}}}^{*}{\mathrm{A}}_{\tilde{\mathrm{C}}}{\mathrm{x}}_{\mathrm{j}}(\tilde{\mathrm{C}}){\Vert }_2\ge (1-{\mathrm{\delta }}_{\mathrm{s}})\Vert {\mathrm{x}}_{\mathrm{j}}(\tilde{\mathrm{C}}){\Vert }_2$$

(16)

However, according to formula (9), we have

$$\Vert {\mathrm{A}}_{\tilde{\mathrm{C}}}^{*}{\mathrm{A}}_{\mathrm{C}\backslash \tilde{\mathrm{C}}}{\mathrm{x}}_{\mathrm{j}}(\mathrm{C}\backslash \tilde{\mathrm{C}}){\Vert }_2\le {\mathrm{\delta }}_{\mathrm{q}}\Vert {\mathrm{x}}_{\mathrm{j}}(\mathrm{C}\backslash \tilde{\mathrm{C}}){\Vert }_2$$

(17)

So there is

$$\Vert {\mathrm{A}}_{\mathrm{\Lambda }}^{*}{\mathrm{y}}_{\mathrm{j}}{\Vert }_2\ge (1-{\mathrm{\delta }}_{\mathrm{s}})\Vert {\mathrm{x}}_{\mathrm{j}}(\tilde{\mathrm{C}}){\Vert }_2-{\mathrm{\delta }}_{\mathrm{q}}\Vert {\mathrm{x}}_{\mathrm{j}}(\mathrm{C}\backslash \tilde{\mathrm{C}}){\Vert }_2$$

(18)

According to formulas (13) and (18), there are

$${\mathrm{\delta }}_{\mathrm{s}+\mathrm{q}}\Vert {\mathrm{x}}_{\mathrm{j}}{\Vert }_2\ge (1-{\mathrm{\delta }}_{\mathrm{s}})\Vert {\mathrm{x}}_{\mathrm{j}}(\tilde{\mathrm{C}}){\Vert }_2-{\mathrm{\delta }}_{\mathrm{s}}\Vert {\mathrm{x}}_{\mathrm{j}}(\mathrm{C}\backslash \tilde{\mathrm{C}}){\Vert }_2$$

(19)

From equations (10) and (19), there are

$${\mathrm{\delta }}_{\mathrm{s}+\mathrm{q}}\Vert {\mathrm{x}}_{\mathrm{j}}{\Vert }_2\ge (1-{\mathrm{\delta }}_{\mathrm{s}+\mathrm{q}})\Vert {\mathrm{x}}_{\mathrm{j}}(\tilde{\mathrm{C}}){\Vert }_2-{\mathrm{\delta }}_{\mathrm{s}+\mathrm{q}}\Vert {\mathrm{x}}_{\mathrm{j}}(\mathrm{C}\backslash \tilde{\mathrm{C}}){\Vert }_2$$

(20)

If the elements of |xj| are arranged in descending order, that is

$$\begin{array}{c}\multicolumn{1}{c}{|{\mathrm{x}}_{\mathrm{j}}({\mathrm{n}}_1)|\ge |{\mathrm{x}}_{\mathrm{j}}({\mathrm{n}}_2)|\ge \cdots \ge |{\mathrm{x}}_{\mathrm{j}}({\mathrm{n}}_{\mathrm{s}})|\ge |{\mathrm{x}}_{\mathrm{j}}({\mathrm{n}}_{\mathrm{s}+1})|}\\ \multicolumn{1}{c}{\ge \cdots \ge |{\mathrm{x}}_{\mathrm{j}}({\mathrm{n}}_{\mathrm{q}})|}\end{array}$$

(21)

Then

$$\begin{array}{c}\multicolumn{1}{c}{(\mathrm{q}-\mathrm{s})({\mathrm{x}}_{\mathrm{j}}^2({\mathrm{n}}_1)+{\mathrm{x}}_{\mathrm{j}}^2({\mathrm{n}}_2)+\cdots +{\mathrm{x}}_{\mathrm{j}}^2({\mathrm{n}}_{\mathrm{s}}))}\\ \multicolumn{1}{c}{\ge \mathrm{s}({\mathrm{x}}_{\mathrm{j}}^2({\mathrm{n}}_{\mathrm{s}+1})+{\mathrm{x}}_{\mathrm{j}}^2({\mathrm{n}}_{\mathrm{s}+2})+\cdots +{\mathrm{x}}_{\mathrm{j}}^2({\mathrm{n}}_{\mathrm{q}}))}\end{array}$$

(22)

In fact, there are s(q – s) terms on both sides of equation (22) but the terms on the left are greater than or equal to the terms on the right. Based on formula (22), we have

$$\begin{array}{c}\multicolumn{1}{c}{\mathrm{q}({\mathrm{x}}_{\mathrm{j}}^2({\mathrm{n}}_1)+{\mathrm{x}}_{\mathrm{j}}^2({\mathrm{n}}_2)+\cdots +{\mathrm{x}}_{\mathrm{j}}^2({\mathrm{n}}_{\mathrm{s}}))\ge \mathrm{s}({\mathrm{x}}_{\mathrm{j}}^2({\mathrm{n}}_1)}\\ \multicolumn{1}{c}{+\cdots +{\mathrm{x}}_{\mathrm{j}}^2({\mathrm{n}}_{\mathrm{s}})+\cdots +{\mathrm{x}}_{\mathrm{j}}^2({\mathrm{n}}_{\mathrm{q}}))}\end{array}$$

(23)

From the definition of the index set $\tilde{\mathrm{C}}$ and then combined with formula (23), there is

$$\Vert {\mathrm{x}}_{\mathrm{j}}(\tilde{\mathrm{C}}){\Vert }_2\ge \sqrt{\frac{\mathrm{s}}{\mathrm{q}}}\Vert {\mathrm{x}}_{\mathrm{j}}{\Vert }_2$$

(24)

Noticed

$$\Vert {\mathrm{x}}_{\mathrm{j}}(\tilde{\mathrm{C}}){\Vert }_2^2+\Vert {\mathrm{x}}_{\mathrm{j}}(\mathrm{C}\setminus \tilde{\mathrm{C}}){\Vert }_2^2=\Vert {\mathrm{x}}_{\mathrm{j}}(\mathrm{C}){\Vert }_2^2=\Vert {\mathrm{x}}_{\mathrm{j}}{\Vert }_2^2$$

(25)

Then

$$\Vert {\mathrm{x}}_{\mathrm{j}}(\mathrm{C}\backslash \tilde{\mathrm{C}}){\Vert }_2\le \sqrt{1-\frac{\mathrm{s}}{\mathrm{q}}}\Vert {\mathrm{x}}_{\mathrm{j}}{\Vert }_2$$

(26)

Because of equation (20), equations (24) and (26) have

$${\mathrm{\delta }}_{\mathrm{s}+\mathrm{q}}\Vert {\mathbf{x}}_{\mathrm{j}}{\Vert }_2\ge (1-{\mathrm{\delta }}_{\mathrm{s}+\mathrm{q}})\sqrt{\frac{\mathrm{s}}{\mathrm{q}}}\Vert {\mathbf{x}}_{\mathrm{j}}{\Vert }_2-{\mathrm{\delta }}_{\mathrm{s}+\mathrm{q}}\sqrt{1-\frac{\mathrm{s}}{\mathrm{q}}}\Vert {\mathbf{x}}_{\mathrm{j}}{\Vert }_2$$

(27)

In other words

$$\sqrt{\frac{\mathrm{s}}{\mathrm{q}}}\le {\mathrm{\delta }}_{\mathrm{s}+\mathrm{q}}+{\mathrm{\delta }}_{\mathrm{s}+\mathrm{q}}\sqrt{\frac{\mathrm{s}}{\mathrm{q}}}+{\mathrm{\delta }}_{\mathrm{s}+\mathrm{q}}\sqrt{1-\frac{\mathrm{s}}{\mathrm{q}}}$$

(28)

considering

$$\sqrt{\frac{\mathrm{s}}{\mathrm{q}}}+\sqrt{1-\frac{\mathrm{s}}{\mathrm{q}}}\le \sqrt{2}$$

(29)

then

$$\sqrt{\frac{\mathrm{s}}{\mathrm{q}}}\le (1+\sqrt{2}){\mathrm{\delta }}_{\mathrm{s}+\mathrm{q}}$$

(30)

which is

$${\mathrm{\delta }}_{\mathrm{s}+\mathrm{q}}\ge \frac{\sqrt{\mathrm{s}}}{(1+\sqrt{2})\sqrt{\mathrm{q}}}$$

(31)

Obviously, formula (31) is contradictory to the assumption of Corollary 3.1. Therefore, Λ∩ C ≠∅. The certificate is complete.

Corollary 3.1

This shows that although there is no signal sparsity as a priori information, the threshold mechanism proposed in this article can still ensure that at least one correct index for the signal x_j can be found by the algorithm in the first iteration, which is an accurate reconstruction of the original signals that lay the foundation.

Segment OMP algorithm improvement

Piecewise OMP algorithm

The StOMP algorithm is a greedy algorithm improved from the OMP algorithm. ²⁰ The greedy algorithm selects the 2K or K atoms, whose inner product is the largest in the iterative process. The StOMP algorithm determines the atoms through a threshold, and the input parameters do not include the signal sparsity K. Compared with the ROMP algorithm, the StOMP algorithm has higher computational efficiency and reconstructed signal accuracy. ²¹ However, the StOMP algorithm still has a problem, which is the setting of the threshold. The threshold cannot be too large or too small. If the value is too large, the calculation efficiency will be reduced; if the value is too small, it will increase the possibility of wrong atom selection. Although a threshold selection range is given as 2≤α≤3, because the selection of the threshold has a great influence on the effect of the algorithm, this range still appears to be very broad and needs to be precise again. ²² In order to reduce the low signal reconstruction efficiency caused by improper selection of the threshold, this article proposes a combination of pre-selection strategy and adaptive sparsity, which is used to enhance the accuracy of the algorithm in the atomic selection phase. Thus, while improving the reconstruction efficiency, the accuracy of signal reconstruction is ensured. In this article, the SAPStOMP algorithm, StOMP algorithm, OMP algorithm, and ROMP algorithm are further simulated. The comparison between several algorithms verifies that the SAPStOMP algorithm has obvious advantages compared with other algorithms.

Principles of algorithm improvement

Greedy algorithms generally use an atomic selection strategy to complete the selection of atoms, in which the atom screening part will indirectly affect the signal reconstruction efficiency. In this article, the atom screening part is refined and the atom is screened in two rounds using the pre-selection strategy. The pre-selection strategy will use a combination of two strategies, namely, a fixed-value selection strategy and a threshold selection strategy. Among them, the fixed-value strategy is a simple improvement strategy to the serial atom selection strategy. Different from the serial atom selection strategy, only the atom with the largest inner product of the residual is selected to be added to the support set. The fixed-value selection strategy selects L matching atoms in each iteration, where L is less than sparsity K; the threshold strategy is to judge whether the candidate atoms meet a predetermined threshold condition. Since the number of atoms meeting the threshold condition in each iteration is uncertain, the number of atoms selected in each iteration is also uncertain. These atoms that meet the threshold conditions will be put into the support set and participate in the subsequent signal reconstruction.

The algorithm in this article performs the third screening in the support set. The sparsity adaptive process is used this time. This process is to find a suitable estimated sparsity to approximate the true sparsity of the signal. If this article defines an ideal support set Λ^T as a support set that contains all the correct atoms and only the correct atoms, the sparsity K of the signal is actually the potential of the ideal support set, namely, |Λ^T| = K. When the signal sparsity K is unknown, the sparsity adaptive sets the initial step size to form an atom candidate set, determines the number of atoms in the candidate set and the current step size, and completes the support set update according to the judgment result. The long update completes the approximate estimation of the sparsity and makes the signal reconstruction more accurate.

In the pre-selection strategy section, there will be two choices of atomic pre-selection and atomic reselection. If the atomic selection is regarded as the interview of the reconstruction algorithm on the atoms in the observation matrix, then the atomic pre-selection and the atomic reselection are similar to the initial and retests in the interview. First, the primary selection of atoms is performed through a fixed-value strategy, and then the primary selected atoms are regarded as candidate atoms in the reselection stage. In the multi-selection stage, the threshold selection strategy is adopted. The atoms selected in the multiple selection phase will be screened for the third time. The third screening process is related to the step length. When the number of candidate sets is small, the next iteration takes a large step. The support set can be effectively expanded to achieve the goal of approaching sparsity. When the number of candidate sets is large, in order to prevent the overestimation of sparsity, this article adopts a small step size to filter atoms and approximate sparsity. By changing the step size by identifying the parameters, the support set can be expanded more effectively and the sparsity of self-adaptive estimation can be achieved, so as to achieve the purpose of improving signal reconstruction performance.

The SAPStOMP algorithm uses the pre-selection strategy as the atomic selection strategy, and effectively expands the support set in combination with sparsity adaptation. It is worth noting that the number of atoms selected in each iteration as the threshold strategy of the primary selection is not fixed. Therefore, it is possible that the number of atoms passing the pre-selection is less than the number of atoms to be “admitted” for the double selection. In this case, the SAPStOMP algorithm treats all atoms that have passed the primary selection as automatic check-selection, and put them directly into the support set. The sparseness adaptive part after that is equal to the third selection, which improves the accuracy of reconstruction. The algorithm flow of the sparsity adaptive pre-selected segmented OMP algorithm is shown in Figure 2.

Figure 2.

Sparsity adaptive pre-selected segmented orthogonal matching pursuit algorithm flow.

Improved algorithm steps

The symbol description is as follows: y is the observed vector, the size is M×1, y = Φx; x is the original signal, which is generally not sparse, but in a certain transform domain Ψ is sparse, and the size is N×1 (M << N); θ is K-sparse, which is the sparse representation of the signal in x in a certain transform domain; Φ is the measurement matrix, the size is M×N; Ψ is the sparse matrix, the size is N×N; A is the sensing matrix, the size is M×N, generally K << M << N. The sparse representation model in compressed sensing is x = Ψθ, so the sensing matrix A = ΦΨ.

In the following process, r_t represents the residual, t represents the number of iterations, Ø represents the empty set, Λ_t represents the index (column number) set of t iterations (the number of elements is L, L is equal to the integer multiple of the step size ST), a_j represents the jth column of matrix A, A ={a_j}(for all j∈C_K) represents the column set of matrix A selected by index set C_K (let the number of columns be L_t), θt is the column vector of L_t×1, the symbol ∪ represents the set union operation, <·,·> represents the inner product of vectors, and abs[.] represents the modulus value (absolute value).

Input: M×N sensing matrix A = ΦΨ; N×1 dimensional observation vector y; total number of iterations S, default is 10; threshold parameter α, default is 2.5; step size ST; step size multiple stage. Output: signal sparse representation coefficient estimation $\hat{\theta }$ , N×1 dimensional residual r_t = y-A_t $\hat{\theta }$ _t.process:

• Step 1. Initialization: r₀ = y, Λ₀ =∅, A₀ =∅, Lt = ST, t = 1, Stage = 1.

• Step 2. Calculate the correlation degree: ${\mathrm{u}}_{\mathrm{t}}=\mathrm{abs}\left[{\mathrm{A}}^{\mathrm{T}}{\mathrm{r}}_{\mathrm{t}-1}\right]$ (i.e. calculate $r_{t-1},a_j$ , 1<<j<< N).

• Step 3. Primary selection: select the maximum value of Lt in u_t, and form a set J_t (column sequence number set) corresponding to the column number j of A to generate a temporary set J_t.

• Step 4. Check:

• 1. If J_t ≥ L_t, generate set $U_t=\{u_t(i)|i\in \{1,2,\cdots ,N\}\}$ , and ${\mathrm{V}}_{\mathrm{t}}=\{|{\mathrm{u}}_{\mathrm{k}}(\mathrm{i})|\mathrm{i}\in {\mathrm{J}}_{\mathrm{t}}\}$ , and select L_t largest, find the index of the element in U_t and add it to A_t, so that the atomic index selected twice is added to the support set that ${\Lambda }_{\mathrm{t}}={\Lambda }_{\mathrm{t}-1}\stackrel{}{\cup }{\mathrm{A}}_{\mathrm{t}}$ ;

• 2. If J_t < L_t, add all the atomic indexes that passed the primary selection to the support set that ${\Lambda }_t={\Lambda }_{t-1}\stackrel{}{\cup }{J}_t$ ;

• 3. If no new column is selected that ${\Lambda }_t={\Lambda }_{t-1}$ , stop the iteration and proceed to step 11.

• Step 5. Find the least squares solution of $\mathrm{y}={\mathrm{A}}_{\mathrm{t}}{\mathrm{\theta }}_{\mathrm{t}}$ : ${\hat{\theta }}_t=\arg \underset{{\theta }_t}{min}\Vert y-A_t{\theta }_t\Vert =(A_t^T{A}_t{)}^{-1}{A}_t^{T}y$ .

• Step 6. Generate a new support set: select the L_t item with the largest absolute value from ${\hat{\theta }}_t$ and mark it as ${\hat{\theta }}_{\mathrm{tL}}$ , the corresponding L_t column in A_t is marked as A_tL, the corresponding column number of A is marked as Λ_tL, and the set F = Λ_tL .

• Step 7. Update the support set: ${\Lambda }_{tL}={\Lambda }_{tL-1}\stackrel{}{\cup }{J}_t$ ;

• Step 8. Update the residual: $r_t=y-A_t{\hat{\theta }}_t=y-A_t(A_t^{T}A{)}^{-1}{A}_t^{T}y$ .

• Step 9. Determine the stop condition:

• 1. If r_t = 0, stop the iteration and proceed to step 11; if $\Vert r_t{\Vert }_2\ge \Vert r_{t-1}{\Vert }_2$ , update the step length multiple S_tage = S_tage + 1, and the updated step length is L_t = S_tage×L_(t-1). Return to step 2 to continue iterating, otherwise go to step 10;

• 2. If Λ_tL ≥ L, stop the iteration and go to step 11, otherwise go to step 10;

• 3. If t = S, stop the iteration and proceed to step 11, otherwise return to step 2 to continue the iteration.

• Step 10. Update the number of iterations: t=t+1.

• Step 11. The reconstructed $\hat{\theta }$ has a non-zero term at Λt, and its value is the ${\hat{\theta }}_t$ obtained in the last iteration.

• Note 1. After obtaining $\hat{\theta },$ the reconstructed signal $\hat{x}$  = Ψ $\hat{\theta }$ can be obtained by using the sparse matrix;

• Note 2. It can be known from the input parameters that this algorithm does not need to know the signal sparsity K;

• Note 3. When the measurement matrix is a random Gaussian matrix, the threshold Tn = ασt, where the value range of α is generally 2 ≤ α ≤ 3, and the noise level σ_t = ||r_t||₂/ $\sqrt{\mathrm{M}}$ represents the last iteration calculated residuals;

• Note 4. The variance is 1/M, in other words, the standard deviation is 1/ $\sqrt{\mathrm{M}}$ . The code for generating the random Gaussian measurement matrix in MATLAB is randn(M, N)/sqrt(M); the atomic selection in step 2 is to change the sensor matrix the inner product vector elements of the column vector and the residual are compared with a certain multiple of the 2 norm of the residual vector. In order to maintain consistency, try to generate the measurement matrix with randn(M, N)/sqrt(M).

• Step 1 of the algorithm is initialized, where the initial step size ST cannot be too large or too small. Too large will reduce the reconstruction quality, and too small will increase the reconstruction time. In practice, it is necessary to select a suitable value according to different goals. In order to obtain a higher reconstruction quality, this article chooses s = 1; step 2 selects the atom closest to the residual through the inner product of the atom and the residual; step 3 uses a fixed-value strategy to perform the primary selection of the atom, and selects L matches in each iteration step 4, check the atoms, get the atom candidate set J_t of the current iteration by setting the threshold αt, then put it into the support set, and use the support set Λ_t for signal estimation; step 5 Find the least squares solution, and use the orthogonalization idea to calculate the reconstructed signal to make the result more accurate; step 6 uses the least square method to obtain a more effective support set F, and through the third selection of atoms in the candidate set, some irrelevant atoms are removed, and finally formed really support set to achieve better reconstruction performance; step 7 calculate the residual r based on the support set of step 6; step 8 determine whether the stopping condition is satisfied. If satisfied, the output signal is sparse and express the coefficient estimate $\hat{\theta }$ , otherwise, go to step 9; step 8 compares with the 2 norm of the previous iteration. The update of the step size, the update of the final support set and the residual of this iteration are different from the StOMP algorithm. Because the StOMP algorithm does not involve step operations, it only selects atoms through threshold parameters. However, the algorithm proposed in this article re-selects the atoms after the primary selection of atoms, and the third selection process after that is related to the step size, and the step size is updated in step 8. When Λ_tL = 0, the number of candidate sets is small, so the next iteration takes a large step to effectively expand the support set to approximate the sparsity; when Λ_tL = 1, the number of candidate sets is large, in order to prevent overestimation of sparsity, so a small step size is used to filter the atoms and approximate the sparsity. In this way, the step size can be changed by identifying the parameters, which can more effectively expand the support set and adaptively estimate the sparsity, and achieve better signal reconstruction performance.

Experimental simulation

In order to verify the effectiveness of the pre-selected segmented OMP algorithm, a simulation experiment was carried out on the improved algorithm. Because the Gaussian matrix can satisfy the constraint equidistance with extremely high probability, the randomly generated Gaussian sparse signal x∈R^N and the Gaussian matrix Φ∈R^M×N with variable sparsity K are used as the original signal and for the observation matrix, the value range of K is [1, 80]. When the observation matrix is a Gaussian random matrix, the threshold parameter of StOMP and the algorithm in this article is set to 2.5.

The simulation experiment was carried out with MATLAB 7.0 software under Microsoft 64-bit Win 10 system, and it took 4937.843,156 s to run. In the simulation experiment, the probability and time of accurate signal reconstruction by each algorithm are the main evaluation criteria. The unit of time is second (s), and the probability of accurate signal reconstruction is expressed in percentage (%). In the simulation experiment, each experiment is conducted for 1000 times, and the average probability and time of accurate signal reconstruction of 1000 times of experiment are taken as the final probability and time of accurate signal reconstruction.

In this experiment, compare the correct reconstruction probability and reconstruction time of OMP, ROMP, StOMP, and SAPStOMP algorithms under different sparsity conditions. In order to compare the reconstruction effects of various algorithms under different sparsity, the size of the perception matrix and the length of the signal are respectively taken as M = 128, N = 256 and M = 128, N = 512.

The size of the perception matrix and the length of the signal taken in Figure 3 are M = 128 and N = 256, respectively. It can be seen from the figure that ROMP is suitable for a lower sparsity environment; when K = 40, the OMP algorithm’s reconstruction performance is significantly lower than that of the StOMP algorithm and the SAPStOMP algorithm; for the signal with sparsity K = 45, the improved algorithm, StOMP algorithm, OMP algorithm, and ROMP algorithm have respectively 98.89%, 49.82%, 24.11%, and 24.11%. The SAPStOMP algorithm can accurately recover the original signal for all signals with a sparsity less than 45. In a higher sparsity environment, the SAPStOMP algorithm also has an advantage over other algorithms in terms of reconstruction accuracy. In general, the SAPStOMP algorithm has the best reconstruction performance under different sparsity.

Figure 3.

Reconstruction performance of each algorithm under different sparsity (N = 256).

The size of the perception matrix and the length of the signal taken in Figure 4 are M = 128 and N = 512. Compared with Figure 3, the signal length is changed and the simulation is performed again. It can be seen that the ROMP algorithm has a signal length of N = 512. In this case, it is also applicable to environments with lower sparsity; under the same sparsity K, the probability of accurate signal reconstruction of the SAPStOMP algorithm is higher than the other algorithms in all algorithms. For the convenience of comparison, the probability of accurate reconstruction of each algorithm is compared with K = 40 as an example. At this time, the accurate reconstruction probability of each algorithm is 60.81% of SAPStOMP algorithm, 51.64% of StOMP algorithm, SAPStOMP algorithm is 9.17% better than StOMP algorithm, 26.14% of OMP algorithm, and 0% of ROMP algorithm from high to low. When the sparsity is 35 < K < 45, the SAPStOMP algorithm has advantages over other algorithms, but in other sparsity situations, the effect of the SAPStOMP and StOMP algorithms is not much different, and both are in the first echelon, which is better than other algorithms. In general, the SAPStOMP algorithm is more suitable for the 35 < K < 45 environment when the signal length is 512, and it still needs to be improved in other sparsity environments.

Figure 4.

Reconstruction performance of each algorithm under different sparsity (N = 512).

Through the above two groups of simulation experiments, it can be seen that for short signals (N = 256), the SAPStOMP algorithm has a better probability of accurate signal reconstruction than other algorithms. For signals with long length (N = 512), under the same sparsity K, the SAPStOMP and StOMP algorithms have little difference in probability of accurate signal reconstruction. Therefore, when the sparsity is 10 to 25, the reconstruction time of each algorithm is compared and analyzed.

Figure 5 compares the reconstruction time of each algorithm under different sparsity, and finds that the SAPStOMP algorithm takes the shortest reconstruction time under the same sparsity. For example, when K = 20, the OMP algorithm takes the longest time and the SAPStOMP algorithm takes the shortest time; when K = 25, the SAMP algorithm takes longer to reconstruct than the OMP algorithm. The improved algorithm in this article still takes longer and is the shortest. The lesser the time required for reconstruction, the faster the user can obtain the original signal.

Figure 5.

Reconstruction time of each algorithm under different sparsity.

It can be seen from the above simulation results that the SAPStOMP algorithm is significantly better than the OMP algorithm, ROMP algorithm, and StOMP algorithm in terms of the accuracy of the reconstructed signal and the signal reconstruction time.

Conclusion

In view of the short reconstruction time of the StOMP algorithm but low reconstruction accuracy, this article improves on the original StOMP algorithm and proposes the SAPStOMP algorithm. The SAPStOMP algorithm uses the combination of a threshold strategy and a fixed-value strategy to improve the accuracy of atomic screening, and uses step conversion to improve the reconstruction efficiency. The initial stage uses a large step to increase the reconstruction speed, and the subsequent stage uses a small step and long approximation to the true sparsity of the signal, and finally realizes the accurate reconstruction of the signal. At the same time, a simulation comparison experiment was carried out to compare the reconstruction efficiency and the time of the improved algorithm, OMP algorithm, ROMP algorithm, and StOMP algorithm. Experiments show that the SAPStOMP algorithm has higher reconstruction efficiency and shorter reconstruction time than the OMP algorithm, ROMP algorithm, and StOMP algorithm. Therefore, the algorithm in this article not only has high reconstruction quality, but also has certain advantages in reconstruction time. It is a better reconstruction algorithm. But there are still shortcomings in this article: the proposed algorithm needs further improvement; this article applies it directly to the default parameters in atom selection phase 2.5; this can be a further refined study with more appropriate threshold parameters; the algorithm has a signal length of 512 cases, only in the sparse degree of 35 < K < 45, whereas in other parts, the sparse degree of refactoring rate still needs to be improved.