An Improved Variable Step SAMP Method Based on Correlation Principle

Abstract

The fixed step size in the sparse adaptive matching pursuit algorithm can result in limited accuracy and overestimation. To address this, this paper proposes a variable-step sparse adaptive matching pursuit algorithm based on the Spearman correlation coefficient. By measuring the Spearman correlation coefficient between the candidate set and the input signal, and introducing an adaptive step size adjustment method based on the parameter values of the correlation coefficient, the performance of the SAMP algorithm is optimized and its adaptability is enhanced. Extensive experiments demonstrate that the proposed method achieves good reconstruction results for one-dimensional sparse signals and two-dimensional images.

1. Introduction

In recent years, with the continuous development of artificial intelligence, smart devices have been continuously updated and applied across various industries, making a variety of sensors an important bridge connecting these smart devices. Sensors collect data information and perform calculations, extractions, reconstructions, and other processes to achieve control over smart devices. In light of the vast amounts of data that need to be stored and transmitted, efficient and high-quality storage and transmission have garnered the attention of researchers.

The Nyquist sampling theorem is one of the most important theoretical foundations of modern signal processing. To prevent distortion or aliasing in the reconstructed signal, the sampling rate must exceed twice the highest frequency of the sampled signal [1]. However, high sampling rates and the process of compressed transmission waste a significant amount of resources. The emergence of compressed sensing provides a new approach to effectively address this issue. Compressed sensing can capture all the information in the original signal effectively with a lower sampling rate, enabling the reconstruction of the original signal and significantly reducing the amount of data required for storage or transmission [2]. Therefore, it has been widely applied in fields such as image encryption [3], medical diagnosis [4], radar imaging [5], and superharmonic detection [6].

The key to reconstructing signals with compressed sensing technology lies in the choice of reconstruction algorithm [7]. Currently, common algorithms for compressed sensing reconstruction are divided into three categories: convex optimization algorithms [8,9], greedy algorithms [10], and combinatorial algorithms [11]. Convex optimization algorithms can accurately reconstruct the original signal under certain conditions; however, their high computational complexity makes them difficult to apply to large-scale or high-dimensional signals [12]. Combinatorial algorithms achieve the reconstruction of the original signal by combining different algorithms. However, compared to single algorithms, this approach requires more computational resources, making it challenging to implement in resource-constrained situations [13]. In contrast, greedy algorithms have garnered widespread attention due to their low computational complexity and short reconstruction time [14]. The Matching Pursuit (MP) algorithm has been the most widely used greedy algorithm for signal reconstruction in recent years, leading to the development of many improved algorithms based on MP, such as OMP, ROMP, and STOMP. However, these algorithms require the sparsity of the signal as prior information, which is often difficult to ascertain, thus reducing the applicability of many MP algorithms. The emergence of the SAMP algorithm has broken this deadlock, as it is widely used due to its characteristic of not requiring sparsity as prior information; researchers have also proposed many improved algorithms based on SAMP, such as CCSAMP and VSSAMP. Although the aforementioned methods yield good reconstruction results under certain conditions, they are somewhat limited by their need for prior information or fixed step sizes, often resulting in unsatisfactory reconstruction outcomes. To address this, this paper proposes a variable-step sparse adaptive matching pursuit algorithm based on the Spearman correlation coefficient, which introduces an adaptive step size adjustment method without requiring prior information, enabling the high-quality reconstruction of one-dimensional sparse signals and two-dimensional image signals.

The organization of the rest of this paper is as follows: Section 2 discusses related work on reconstruction algorithms, while Section 3 covers the theoretical background of compressed sensing and the process of the SAMP algorithm. Section 4 presents the algorithm proposed in this paper, Section 5 details the experimental results of the proposed method under different signals, and finally, Section 6 concludes the paper.

2. Related Work

Reliable reconstruction algorithms not only improve reconstruction accuracy but also exhibit good work efficiency, and greedy algorithms possess this characteristic; therefore, this subsection will focus on greedy algorithms.

The main idea of the greedy algorithm is to approximate the original signal during the iterative process, resulting in a reconstructed signal with high precision. The Matching Pursuit (MP) [15] and Orthogonal Matching Pursuit (OMP) [16] algorithms are among the earliest greedy algorithms; OMP effectively resolves the issue of atom redundancy in MP by ensuring the orthogonality between atoms selected in successive iterations, thus providing greater robustness. However, this orthogonality also introduces a series of problems, for instance, the OMP algorithm may become trapped in local optima and struggle to converge in certain cases [17]. To address this, Needell et al. proposed the Regularized Orthogonal Matching Pursuit (ROMP) algorithm [18], which introduces randomness in atom selection, thereby mitigating the issues arising from orthogonality and reducing computational complexity while ensuring algorithm performance. For the aforementioned algorithms, if the selected atoms do not contain information from the original signal, the reconstruction quality will also diminish. In response, Dileep et al. proposed the Compressed Sampling Matching Pursuit (CoSaMP) algorithm, which incorporates a backtracking approach to identify and reselect atoms that do not meet termination conditions, effectively enhancing algorithm performance by choosing columns most relevant to the current residual. Similarly, the Subspace Pursuit (SP) [19] algorithm also incorporates the backtracking concept.

However, the aforementioned algorithms require the sparsity of the signal as prior information, limiting their applicability. In response, Dohono et al. proposed the Phase Orthogonal Matching Pursuit (StOMP) algorithm [20], which does not require signal sparsity as an input parameter and is advantageous when sparsity is unknown. Subsequently, to address the issue of slow convergence speed due to strong orthogonality, Blumensath et al. introduced the Phase-Controlled Weak Orthogonal Matching Pursuit (SWOMP) [21], which incorporates a weak selection process and sets a threshold for atom selection to ensure reconstruction accuracy, though the choice of threshold remains an unresolved issue. Similarly, the Sparsity Adaptive Matching Pursuit (SAMP) [22] algorithm also does not require sparsity as prior information; it is not constrained by preset thresholds and gradually approximates the original signal through continuous iteration with a fixed step size. However, the choice of an appropriate step size affects the reconstruction performance; a smaller step size may slow convergence, increasing iterations and time, while a larger step size may skip the optimal solution, reducing reconstruction accuracy [23]. In response, researchers improved the SAMP algorithm by introducing a variable step size strategy to reduce iteration counts and enhance reconstruction accuracy. Huang et al. proposed the Adaptive Regularized Matching Pursuit Algorithm for Compressed Sensing with Sparsity and Step Size [24], which uses a coefficient $\alpha$ to dynamically adjust the step size. Wang et al. introduced the Improved Sparsity Adaptive Matching Pursuit Algorithm based on Compressed Sensing [25], which dynamically adjusts the step size by incorporating a nonlinear function and a variable step size correction factor, enhancing reconstruction accuracy. The Variable Step Size Sparsity Adaptive Matching Pursuit (VSSAMP) algorithm estimates sparsity and determines the step size based on the energy difference between two residuals, optimizing reconstruction performance for one-dimensional signals and two-dimensional images while reducing reconstruction time [26]. The Correlation Coefficient Sparsity Adaptive Matching Pursuit (CCSAMP) Algorithm [27] identifies a linear relationship between the signal recovered from the support set and the candidate set. It uses the Pearson correlation coefficient (PCC) to measure the linear relationship between two vectors, enabling dynamic adjustment of the step size. However, the Pearson correlation coefficient requires variables to follow a normal distribution, which may limit its applicability to non-normally distributed data. Additionally, the Pearson correlation coefficient is highly sensitive to outliers, which may cause results to deviate from the true relationship.

To address the aforementioned issues, this paper proposes a variable step size sparsity adaptive Matching Pursuit Algorithm based on the Spearman correlation coefficient, which measures the similarity between the candidate set and the input signal, adapting the step size through correlation-based partitioning. This algorithm achieves high reconstruction accuracy for one-dimensional sparse signals and two-dimensional image signals.

3. Preliminaries

3.1. Compressed Perception Theory

Compressed sensing offers unique advantages in signal processing methods [28]; the premise for signal reconstruction is that the original signal is sparse, yet most signals do not meet the sparsity condition. Therefore, compressed sensing utilizes a sparse basis matrix $\mathit{\Psi }=\left\{{\mathit{\Psi }}_1,{\mathit{\Psi }}_2,\dots ,{\mathit{\Psi }}_N\right\}$, allowing the original signal x to be expressed as a sparse signal θ according to Formula (1) as follows:

$$x={\displaystyle \sum _{i=1}^N{\mathit{\Psi }}_i}{\mathit{\theta }}_i=\mathit{\Psi }\mathit{\theta }$$

(1)

where θ is a sparse signal under the sparse basis Ψ. The sparse basis is typically one of the discrete Fourier transform basis, discrete cosine transform basis, or wavelet transform basis. The essence of compressed sensing is to project high-dimensional signals into a low-dimensional space using a measurement matrix, expressed mathematically as follows:

$$\mathit{y}=\mathit{\Phi }\mathit{x}$$

(2)

The compressed signal y is obtained through Formula (2), where y is a column vector of size M × 1, x is a column vector of size N × 1, and M << N. Φ is the measurement matrix. The measurement matrix can generally be divided into deterministic measurement matrices and random measurement matrices. Since Gaussian random matrices and Bernoulli random matrices in random measurement matrices can generally satisfy the restricted isometry property (RIP), random measurement matrices are typically chosen. Combining (1) and (2), we can conclude that

$$\mathit{y}=\mathit{\Phi }\mathit{x}=\mathit{\Phi }\mathit{\Psi }\mathit{\theta }=\mathit{A}\mathit{\theta }$$

(3)

As shown in Formula (3), the product of the measurement matrix and the sparse basis yields the sensing matrix A, expressed as A = ΦΨ. Thus, given the compressed signal y, the measurement matrix Φ, and the sparse basis Ψ, the sparse signal θ, and the original signal x can be obtained from Formula (3). Generally, the accurate reconstruction of the sparse signal can be transformed into solving the following optimization problem:

$$\underset{\theta }{\min }{‖\mathit{\theta }‖}_0,\hspace{0.33em}\hspace{0.33em}\mathrm{subject} \mathrm{to} \mathit{y}=\mathit{\Phi }\mathit{x}$$

(4)

where ‖·‖₀ represents the L₀-norm, which counts the number of non-zero elements in a vector. However, the L₀-norm seeks the subset with the fewest non-zero elements, which requires combinatorial optimization across all subsets, complicating the problem; thus, the L₀-norm is NP-hard. Since the L₁-norm has been shown to be the optimal convex approximation of the L₀-norm, it is used to replace the L₀-norm to solve for sparse solutions [29]. The formula is as follows:

$$\underset{\theta }{\min }{‖\mathit{\theta }‖}_1,\hspace{0.33em}\hspace{0.33em}\mathrm{subject} \mathrm{to} \mathit{y}=\mathit{\Phi }\mathit{x}$$

(5)

From the above, it is clear that successfully reconstructing a signal involves three important components: the selection of the sparse basis, the choice of the measurement matrix, and the design of the reconstruction algorithm. These also represent three distinct research directions in the study of compressed sensing [30].

3.2. Introduction to SAMP Algorithm

The SAMP algorithm is widely used in compressed sensing due to its characteristic of not requiring sparsity as prior information. The pseudo-code for the SAMP algorithm is expressed as follows (Algorithm 1) [22]:

Algorithm 1: SAMP

Input: compressed signal $\mathit{y}$, perception matrix $\mathit{A}$, step size $S$. Output: Signal sparse representation coefficient estimated ${\mathit{\theta }}_t$. 1: Initialization: 2: ${\mathit{r}}_0=\mathit{y}$; ${\mathit{\Lambda }}_t=\varnothing$; ${\mathit{A}}_t=\varnothing$; $L=S$; $stage=1$; $t=1$ 3: Repeat: 4: ${\mathit{S}}_t=Max(‖{\mathit{A}}^T{\mathit{r}}_{t-1}‖,L)$ 5: ${\mathit{C}}_{\mathrm{t}}={\mathit{\Lambda }}_{t-1}\cup {\mathit{S}}_t$ 6: ${\widehat{\mathit{\theta }}}_t=\arg \min ‖\mathit{y}-{\mathit{A}}_t{\mathit{\theta }}_t‖={({\mathit{A}}_t^T{\mathit{A}}_t)}^{-1}{\mathit{A}}_t^T\mathit{y}$ 7: ${\mathit{F}}_t=\max (‖{\mathit{A}}_t\mathit{y}‖,\mathit{L})$ 8: ${\mathit{r}}_{new}=\mathit{y}-{\mathit{A}}_{tL}{({\mathit{A}}_{tL}^T{\mathit{A}}_{tL})}^{-1}{\mathit{A}}_{tL}^T\mathit{y}$ 9: If ${‖{\mathit{r}}_{new}‖}_2<1e-6$ then 10: Output ${\mathit{\theta }}_t$ 11: else if ${‖{\mathit{r}}_{new}‖}_2\ge {‖{\mathit{r}}_{t-1}‖}_2$ 12: $stage=stage+1$ 13: $L=stage\times S$ 14: $t=t+1$ 15: else 16: ${\mathit{r}}_{new}={\mathit{r}}_{t-1}$ 17: ${\mathit{\Lambda }}_t=\mathit{F}$ 18: $t=t+1$ 19: end if 20: Until ${‖{\mathit{r}}_{new}‖}_2<1e-6$ 21: Output: 22: ${\widehat{\mathit{\theta }}}_t={({\mathit{A}}_t^T{\mathit{A}}_t)}^{-1}{\mathit{A}}_t^T\mathit{y}$

where Λ_t is the index of the t-th iteration, a_j represents the j-th column of the sensing matrix A, A_t represents the set of columns selected from the sensing matrix A under the index set C_k, and θ_t represents the estimated sparse representation coefficients of the signal.

From the steps of the algorithm, it can be seen that, during the step size update phase, in each iteration, the step size increases by a fixed S. This prevents the dynamic updating of the step size, affecting the reconstruction accuracy of the signal. When S is small, the accuracy of the sparse estimate is high, but the number of iterations increases, leading to inefficient reconstruction. Conversely, when S is large, the number of iterations decreases, but there is a risk of losing the optimal solution, resulting in reduced reconstruction accuracy.

4. Proposed Method

The SAMP algorithm estimates the sparsity of each iteration by comparing the residual value, gradually approaching the optimal sparse solution, and finally successfully reconstructing the original signal. However, due to the use of fixed step size during iteration, the accuracy of sparsity estimation is compromised. Therefore, the Spearman correlation coefficient SAMP (SCCSAMP) algorithm is proposed to dynamically change the step size according to the correlation between the compressed signal and the candidate set.

The initial parameters are expressed as follows:

$$\left\{\begin{array}{l}{\mathit{r}}_0=\mathit{y}\\ {\mathit{F}}_0=\varnothing \\ L=S\end{array}\right.$$

(6)

After parameters initialization, u is defined as the dot product of sensing matrix A and residual r. Then, L maximum values are selected from u to form S_t, which corresponds to column set. Then, the inner product of the sensing matrix A and the residual r is calculated, the largest L values are selected, and the relevant column sequence number in S_t is stored:

$${\mathit{S}}_t=Max(‖{\mathit{A}}^T{\mathit{r}}_{t-1}‖,L)$$

(7)

The index set Λ_t−1 of the previous iteration was merged with the S_t of the current iteration to construct the candidate set C_t of the t-th iteration: ${\mathit{C}}_t={\mathit{\Lambda }}_{t-1}\cup {\mathit{S}}_t$. The sparse signal of the t-th iteration is calculated using the least squares method as follows:

$${\widehat{\mathit{\theta }}}_t=\arg \min ‖\mathit{y}-{\mathit{A}}_t{\mathit{\theta }}_t‖={({\mathit{A}}_t^T{\mathit{A}}_t)}^{-1}{\mathit{A}}_t^T\mathit{y}$$

(8)

The L-th term with the largest absolute value from θ_t is selected and labeled as θ_tL, while the L-th column corresponding to A_t is selected and denoted as A_tL, and the set of sequence numbers of A_tL is reserved in the support set F_t, The residuals are obtained as follows:

$${\mathit{r}}_{new}=\mathit{y}-{\mathit{A}}_{tL}{({\mathit{A}}_{tL}^T{\mathit{A}}_{tL})}^{-1}{\mathit{A}}_{tL}^T\mathit{y}$$

(9)

The residual r is used to judge whether the stop iteration condition is satisfied; the iteration is terminated if it is satisfied, and the iteration is continued if it is not satisfied.

In the SAMP algorithm, we construct the vector y_tL, y_tL that was generated by the candidate set F_t.

$${\mathit{y}}_{tL}=\mathit{y}-{\mathit{r}}_{new}={\mathit{A}}_{tL}{({\mathit{A}}_{tL}^T{\mathit{A}}_{tL})}^{-1}{\mathit{A}}_{tL}^T\mathit{y}$$

(10)

As the number of iterations increases, the r_new tends to zero; therefore, the vectors y and y_tL are gradually close to each other. Compressed sensing theory states that the sparse signal x can be recovered from the small number of linear measurements $\mathit{y}=\mathit{A}\mathit{x}$, requiring the perception matrix A to satisfy the restricted isometry property (RIP).

During the recovery of sparse signals, the selection of atoms most relevant to vector y is achieved by maximizing $‖{\mathit{A}}_{\mathrm{t}}^T\mathit{y}‖$, in other words, the projection of the vector y onto the column space of the sensing matrix A is actually calculated. Therefore, selecting the set of atoms F_t corresponding to the L component with the largest absolute value means selecting the atoms that contribute the most to vector y. This selection strategy ensures that the atoms selected in each iteration will contribute the most to signal y, so that the vector y_tL contains more useful atoms and minimizes the reconstruction error at each step. This theoretically increases the representativeness and information content of the selected atoms, and better preserves the geometric properties of the signal, making the selected atoms more orthogonal and independent, thus increasing the likelihood that the sensing matrix A satisfies the RIP.

Therefore, the algorithm proposed in this paper deals with the step size in segments by measuring the similarity between the vectors y and y_tL. A higher similarity means that atoms closer to the sparse solution are selected. By judging the similarity, different step sizes can be selected to effectively approximate the sparse solution.

Common correlation analysis methods include covariance, the Pearson correlation coefficient, and the Spearman correlation coefficient. The calculation result of covariance is only used to judge whether the two variables are correlated, and its value is not easy to define the degree of correlation. The Pearson coefficient can be used to analyze the degree of correlation, but it is only suitable for data that conform to the normal distribution. The Spearman correlation coefficient can be used for the correlation analysis of any two groups of data with the same length. Spearman’s correlation coefficient reflects the correlation between variables by using monotone function, which is not affected by data dimension and is not sensitive to outliers [31]. Therefore, the Spearman correlation coefficient is selected for correlation analysis in this paper, and its calculation method is as follows:

$$\mathit{\rho }={\displaystyle \frac{{\displaystyle \sum _i^N({\mathit{y}}_i-\overline{\mathit{y}})({({\mathit{y}}_{tL})}_{\mathrm{i}}-{\overline{\mathit{y}}}_{tL})}}{\sqrt{{\displaystyle \sum _i^N{({\mathit{y}}_i-\overline{\mathit{y}})}^2{\displaystyle \sum _i^N{({({\mathit{y}}_{tL})}_{\mathrm{i}}-{\overline{\mathit{y}}}_{tL})}^2}}}}}$$

(11)

where y_i and (y_tL)_i are the observed rank of two well-ordered variables, $\overline{\mathit{y}}$ and ${\overline{\mathit{y}}}_{tL}$ are the average rank of two variables, and N is the total number of each variable.

The range of the Spearman’s correlation coefficient ρ is [–1, 1]. A negative value indicates a negative correlation between two variables, while a positive value indicates a positive correlation between two variables. The absolute value of the calculated results can be used to characterize the degree of correlation between the two variables. The usual judgment criteria are as follows: 0.8~1.0 indicates a very strong correlation, 0.6~0.8 indicates a strong correlation, 0.4~0.6 indicates a moderate correlation, 0.2~0.4 indicates a weak correlation, and 0.0~0.2 indicates a very weak correlation or no correlation.

Assuming that ρ represents the Spearman correlation between y and y_tL, the formula is as follows:

$$\mathit{\rho }=Spearman(\mathit{y},{\mathit{y}}_{tL})$$

(12)

According to Spearman’s criterion, we can process step size in different steps. When 0 < ρ < 0.4, it is considered that the correlation between the two is weak and the step length should be taken. If 0.4 < ρ < 0.8, it is considered that the correlation between the two is above medium, and a small length is taken; if ρ > 0.8, it is considered that the correlation between the two vectors is very strong, and the sparse solution can be gradually approached with step size 1.

We calculate the complexity of the method in this paper according to the steps of the pseudocode. The pseudocode of the method proposed in this article is as follows (Algorithm 2, based on Algorithm 1):

Algorithm 2: SCCSAMP

Input: Compressed signal $\mathit{y}$, sensing matrix $\mathit{A}$, step size $S$. Output: Sparse coefficient of the estimated signal ${\mathit{\theta }}_t$.     1: Initialization:     2: ${\mathit{r}}_0=\mathit{y}$; ${\mathit{\Lambda }}_t=\varnothing$; ${\mathit{A}}_t=\varnothing$; $L=S$; $stage=1$; $t=1$     3: Repeat:     4: ${\mathit{S}}_t=Max(‖{\mathit{A}}^T{\mathit{r}}_{t-1}‖,L)$     5: ${\mathit{C}}_t={\mathit{\Lambda }}_{t-1}\cup {\mathit{S}}_t$     6: ${\widehat{\mathit{\theta }}}_t=\arg \min ‖\mathit{y}-{\mathit{A}}_t{\mathit{\theta }}_t‖={({\mathit{A}}_t^T{\mathit{A}}_t)}^{-1}{\mathit{A}}_t^T\mathit{y}$     7: ${\mathit{F}}_t=\max (‖{\mathit{A}}_t\mathit{y}‖,L)$     8: ${\mathit{r}}_{new}=\mathit{y}-{\mathit{A}}_{tL}{({\mathit{A}}_{tL}^T{\mathit{A}}_{tL})}^{-1}{\mathit{A}}_{tL}^T\mathit{y}$     9: ${\mathit{y}}_{tL}=\mathit{y}-{\mathit{r}}_{new}={\mathit{A}}_{tL}{\left({\mathit{A}}_{tL}^T{\mathit{A}}_{tL}\right)}^{-1}{\mathit{A}}_{tL}^T\mathit{y}$     10: $\mathit{\rho }=Spearman(\mathit{y},{\mathit{y}}_{tL})$     11: If $0.4<\mathit{\rho }<0.8$ then     12: $S=S+round({\mathit{\rho }}^{(-0.4)})$     13: else if $0<\mathit{\rho }<0.4$ then     14: $S=round({\mathit{\rho }}^{(-0.8)})$     15: else     16: $S=1$     17: end if     18: If ${‖{\mathit{r}}_{new}‖}_2<1e-6$ then     19: Output ${\mathit{\theta }}_t$     20: else if ${‖{\mathit{r}}_{new}‖}_2\ge {‖{\mathit{r}}_{t-1}‖}_2$     21: $stage=stage+1$     22: $L=stage\times S$     23: $t=t+1$     24: else     25: ${\mathit{r}}_{new}={\mathit{r}}_{t-1}$     26: ${\mathit{\Lambda }}_t=\mathit{F}$     27: $t=t+1$     28: end if     29: Until ${‖{\mathit{r}}_{new}‖}_2<1e-6$     30: Output:     31: ${\mathit{\theta }}_t={({\mathit{A}}_t^T{\mathit{A}}_t)}^{-1}{\mathit{A}}_t^T\mathit{y}$

In the code above, Step 4 computes the inner product and sorts to extract the top L values. The complexity of the inner product is O(MN), and the complexity of the descending sort is O(NlogN). Therefore, the overall complexity is (MN + NlogN).

In Step 5, the process of establishing the candidate set C_t requires the most N operations, resulting in a complexity of O(N).

In Step 6, the calculation of the least squares solution involves matrix–matrix multiplication, with a complexity of O(L²). The complexity for matrix inversion is O(L³), leading to a total complexity of O(ML² + L³).

In Step 7, the complexity of constructing F is O(L).

In Steps 8 and 9, the calculation of the residual involves a matrix–vector multiplication with a time complexity of O(ML).

In Step 10, calculating the Spearman correlation coefficient has a complexity of O(MlogM).

Based on the above analysis, after k iterations, the overall complexity can be summarized as O(K(MN + NlogN + N + L²M + L³ + L + ML + MlogM)). Since L is significantly smaller than both M and N, the total complexity for the SCCSAMP algorithm can be approximated as O(k(MN + NlogN)).

5. Experimental Results and Discussion

To verify the performance of the method proposed in this paper, we conducted the following work:

(1)

Reconstructed one-dimensional signals and compared them with the OMP, SP, STOMP, ROMP, CoSaMP, SAMP, VSSAMP, and CCSAMP algorithms.

(2)

Utilized the proposed method along with some SAMP-based algorithms and their improvements to reconstruct a set of commonly used two-dimensional images and present the visual results.

5.1. Performance Metrics

To evaluate the performance of the algorithm proposed in this paper, we selected the reconstruction success rate, relative error, and peak signal-to-noise ratio as performance metrics. The calculation methods are as follows:

$${\mathit{P}}_{sr}={\displaystyle \frac{{\mathit{n}}_s}{{\mathit{n}}_i}}\times 100\%$$

(13)

$$ERROR={\displaystyle \frac{{‖\mathit{x}-{\mathit{x}}_r‖}_2}{{‖\mathit{x}‖}_2}}\times 100\%$$

(14)

$$MSE={\displaystyle \frac{1}{MN}}{\displaystyle \sum _{i=0}^{M-1}{\displaystyle \sum _{j=0}^{N-1}{\left|\mathit{x}(i,j)-{\mathit{x}}_r(i,j)\right|}^2}}$$

(15)

$$PSNR(\mathit{x},{\mathit{x}}_r)=10\log ({\displaystyle \frac{MAX}{MSE}})$$

(16)

where the reconstruction success rate P_sr represents the ratio of successful reconstructions n_s to the total number of experiments n_i; a higher success rate indicates better reconstruction performance of the algorithm. The relative error ERROR indicates the percentage deviation between the reconstructed signal and the original signal, used to measure the error of the reconstructed signal; smaller errors suggest that the reconstructed signal is closer to the original, reflecting superior algorithm performance. The quality of the restored image is assessed using the peak signal-to-noise ratio (PSNR, in dB) between the original and restored images, and MAX is the maximum pixel value.

5.2. Experimental Results of One-Dimensional Signal

In this section, two types of signals are selected as the original signals for reconstruction: a one-dimensional Gaussian random sparse signal and a multicomponent cosine signal representing a complex signal with multiple frequency components. Both signals have a length of 256 and use a Gaussian matrix as the measurement matrix. The one-dimensional Gaussian random sparse signal utilizes an identity matrix as the sparse basis, and the OMP, SP, STOMP, ROMP, CoSaMP, SAMP, VSSAMP, and CCSAMP algorithms are chosen as the comparison group. For the multicomponent cosine signal, a discrete wavelet transform matrix serves as the sparse basis, and the SAMP, VSSAMP, and CCSAMP algorithms are used for comparison. The multicomponent cosine signal model is as follows:

$$\mathit{x}(n)=0.3\cos (2\pi f_{1}n{t}_s)+0.6\cos (2\pi f_{2}n{t}_s)+0.1\cos (2\pi f_{3}n{t}_s)+0.9\cos (2\pi f_{4}n{t}_s)$$

(17)

where n is 0, 1, 2……N − 1.

The relevant parameters are set as follows: f₁ = 50 Hz, f₂ = 100 Hz, f₃ = 200 Hz, and f₄ = 400 Hz, with f_s = 800 Hz as the sampling frequency and t_s = 1/f_s, The frequencies f₁, f₂, f₃, and f₄ correspond to four cosine signals.

5.2.1. The Reconstruction Success Rate of Sparse Signal Under Different Sparsity

To evaluate the algorithm’s performance at different sparsity levels, we set the parameter M = 128 and repeated measurements 5000 times at each sparsity level. A reconstruction is considered successful when the reconstruction error is less than 10⁻⁶, with the reconstruction success rate used as the evaluation metric. The experimental results are shown in Figure 1. As the sparsity level K increases, the reconstruction success rates of various algorithms decline to different extents. Among the algorithms that use sparsity as prior information, the ROMP algorithm, which treats sparsity as the strongest prior, exhibits the fastest decline in the reconstruction success rate across different sparsity levels, while the SP algorithm shows the slowest decline. Notably, when K = 45, the reconstruction success rate of the SP algorithm is 91%, while the success rates of other algorithms, which do not rely on sparsity as prior information, approach 100%. When the sparsity level is between 50 < K < 60, the proposed algorithm continues to demonstrate good performance, with a reconstruction success rate significantly higher than that of SAMP and VSSAMP.

5.2.2. Success Rate of Reconstruction of One-Dimensional Signal Under Different

To evaluate whether the reconstruction algorithms consistently maintain high performance under various measurement conditions and to ensure the accuracy and reliability of simulated measurements, this study assesses reconstruction success rates across different measurement values. Through multiple measurements and detailed analysis of the results, the credibility of the measurement outcomes is effectively enhanced.

At different measurement values M, we observed the reconstruction success rates for one-dimensional sparse signals and multi-component cosine signals, each reconstructed 5000 times. The experimental results are shown in Figure 2. As seen in Figure 2a, when the measurement values are within 75 < M < 95, the SCCSAMP algorithm exhibits a significantly higher reconstruction success rate for sparse signals compared to other algorithms. For M > 90, SCCSAMP consistently maintains a superior success rate relative to other algorithms, demonstrating the method’s robust reconstruction capability for sparse signals across various measurement values. Figure 2b further illustrates that with fewer measurements (e.g., $M$ between 10 and 25), SCCSAMP achieves higher reconstruction success rates than other algorithms, indicating that it provides stable reconstruction even with limited measurement data. This suggests that SCCSAMP is more effective in utilizing restricted measurement resources. When the measurement count increases to 30 or above, SCCSAMP’s reconstruction success rate consistently remains close to 100%, outperforming all comparison algorithms, particularly at higher measurement counts where its exceptional accuracy becomes evident.

5.2.3. Success Rate of Sparse Signal Reconstruction Under Asynchronous Length

To assess the performance of the proposed algorithm under different step sizes, we compared the reconstruction success rates of various algorithms across different step sizes. The experimental results are shown in Figure 3. As shown in Figure 3a–c, SCCSAMP demonstrates a marked advantage under various synchronization lengths. For instance, with synchronization lengths of S = 3 and S = 4, SCCSAMP achieves a reconstruction success rate approaching 80% with as few as 90 measurements, whereas other algorithms generally perform less effectively. This performance indicates that SCCSAMP can more accurately reconstruct signals with fewer measurements, showcasing superior robustness and precision. At low measurement counts, SCCSAMP’s success rate notably surpasses that of CCSAMP, VSSAMP, and SAMP, especially when the synchronization length is short (e.g., S = 3), where this gap is even more pronounced. This characteristic allows SCCSAMP to maintain high-quality signal reconstruction in data-constrained environments, highlighting one of its core strengths. These findings suggest that SCCSAMP exhibits robust reconstruction capabilities across different synchronization lengths, with its improvement strategy enhancing reconstruction accuracy while minimizing required measurements.

5.2.4. The Measurement Error of Sparse Signal Under Different Sparsity Level

Sparsity refers to the number of non-zero elements in a signal; higher sparsity indicates greater signal complexity, which increases reconstruction difficulty and leads to higher errors. Comparing the measurement errors of each algorithm at different sparsity levels can reflect their performance advantages, to some extent. As shown in

Table 1. Measurement errors of different algorithms under different sparsity levels.

Num.	SAMP	VSSAMP	CCSAMP	SCCSAMP
20	5.88 × 10−16	5.89 × 10−16	6.03 × 10−16	5.86 × 10−16
25	6.98 × 10−16	6.64 × 10−16	6.70 × 10−16	6.45 × 10−16
30	7.54 × 10−16	7.10 × 10−16	7.43 × 10−16	6.99 × 10−16
35	8.16 × 10−16	8.14 × 10−16	8.44 × 10−16	7.90 × 10−16
40	8.01 × 10−16	8.17 × 10−16	8.95 × 10−16	7.99 × 10−16
45	1.01 × 10−15	9.28 × 10−16	9.85 × 10−16	9.63 × 10−16
50	1.13 × 10−15	1.06 × 10−15	1.12 × 10−15	1.06 × 10−15
55	1.07 × 10−15	1.08 × 10−15	1.17 × 10−15	1.14 × 10−15
60	1.07 × 10−15	1.05 × 10−15	1.10 × 10−15	1.11 × 10−15

In the table, the minimum measurement error is highlighted in bold.

, the measurement errors of all algorithms increase with higher sparsity levels. When the sparsity level is between [20, 40], the SCCSAMP algorithm achieves lower measurement errors compared to other algorithms. When sparsity exceeds 40, the increased difficulty in atom selection for reconstruction algorithms results in SCCSAMP’s reconstruction error not being the smallest. Its performance is comparable to that of other algorithms and remains within the same order of magnitude.

5.2.5. The Reconstruction Success Rate of Noisy Signal

According to the findings in [27], the CCSAMP algorithm demonstrates superior noise resistance compared to the SAMP algorithm and its improved versions. Therefore, this study uses CCSAMP as a benchmark to verify the noise resistance of SCCSAMP. As shown in Figure 4a, the reconstruction success rate of SCCSAMP for sparse signals significantly surpasses that of CCSAMP as SNR increases, particularly within the 30 dB–50 dB range. This indicates that SCCSAMP achieves superior reconstruction performance at higher SNRs, providing more effective sparse signal recovery. Figure 4b shows that, for multicomponent cosine signals, SCCSAMP also slightly outperforms CCSAMP under high SNR conditions, especially at 40 dB and above, where SCCSAMP’s success rate approaches 100%, slightly exceeding CCSAMP under the same conditions. This further confirms SCCSAMP’s enhanced reconstruction performance for multicomponent cosine signals at higher SNRs.

5.3. Experimental Results for Two-Dimensional Images

5.3.1. Experiment A

In this section, we used 512 × 512 grayscale images—Barbara, Boat, Couple, Lake, Lena, Pirate, Walkbridge, and Woman—as source signals. Under different compression ratios, we evaluated the reconstruction performance of the proposed algorithm and compared it with the SAMP, VSSAMP, and CCSAMP algorithms based on the visual results and performance metrics obtained from reconstructing these eight images. In practical applications, when two-dimensional images are stacked into one-dimensional long vectors, the sparsity basis level in the transform domain is often much greater than 1. Therefore, a larger step size is typically used for image processing applications; in this study, we set the step size to 64. During the experiments, the images were processed in blocks, using discrete wavelet transform as the sparsity basis for sparse representation, with a Gaussian matrix used as the observation matrix.

To provide a more intuitive comparison of the proposed algorithm with the competing algorithms, the visual results for Woman and Pirate at different compression ratios are shown in Figure 5. From the figure, it is evident that under the same initial step size, the SCCSAMP algorithm outperforms the other algorithms, demonstrating the best reconstruction performance. The SCCSAMP algorithm exhibits stable reconstruction performance as the compression ratio varies. To provide a more precise comparison of the performance of different algorithms, we used reconstruction error and peak signal-to-noise ratio (PSNR) to measure image reconstruction quality. The experimental results under different compression ratios are presented in Table 1,

Table 2. Experimental results of different algorithms at a compression ratio of 0.4.

Image	ERROR				PSNR
	SAMP	VSSAMP	CCSAMP	SCCSAMP	SAMP	VSSAMP	CCSAMP	SCCSAMP
Barbara	0.0955	0.0978	0.1060	0.0925	26.21	26.00	25.31	26.48
Boat	0.0909	0.0901	0.0955	0.0892	26.17	26.24	25.75	26.34
Couple	0.1050	0.1002	0.1084	0.0975	25.46	25.86	25.23	26.15
Lake	0.0430	0.0452	0.0491	0.0421	29.19	28.75	28.03	29.37
Lena	0.0730	0.0753	0.0817	0.0691	28.05	27.77	27.07	28.52
Pirate	0.1034	0.1024	0.1094	0.0953	25.67	25.75	25.18	26.38
Walkbridge	0.0566	0.0549	0.0601	0.0526	27.01	27.27	26.47	27.64
Woman	0.0611	0.0613	0.0643	0.0586	30.53	30.5	30.09	30.89

and

Table 3. Experimental results of different algorithms at a compression ratio of 0.6.

Image	ERROR				PSNR
	SAMP	VSSAMP	CCSAMP	SCCSAMP	SAMP	VSSAMP	CCSAMP	SCCSAMP
Barbara	0.0752	0.0709	0.0741	0.0645	28.28	28.80	28.41	29.60
Boat	0.0830	0.0747	0.0785	0.0712	27.55	28.46	28.03	28.88
Couple	0.0852	0.0779	0.0813	0.0764	27.27	28.06	27.69	28.22
Lake	0.0348	0.0333	0.0332	0.0303	31.02	31.41	31.44	32.24
Lena	0.0609	0.0567	0.0567	0.0519	29.61	30.23	30.24	31.01
Pirate	0.0867	0.0793	0.0813	0.0739	27.2	27.98	27.76	28.59
Walkbridge	0.0462	0.0427	0.0431	0.0396	28.77	29.44	29.36	30.09
Woman	0.0516	0.0475	0.0493	0.0447	31.99	32.72	32.38	33.24

, with the best experimental data highlighted in bold.

As shown in Table 2, Table 3 and

Table 4. Experimental results of different algorithms at a compression ratio of 0.8.

Image	ERROR				PSNR
	SAMP	VSSAMP	CCSAMP	SCCSAMP	SAMP	VSSAMP	CCSAMP	SCCSAMP
Barbara	0.0643	0.0560	0.0561	0.0523	29.65	26.69	30.83	31.44
Boat	0.0656	0.0590	0.0579	0.0571	29.00	29.92	30.08	30.21
Couple	0.0716	0.0627	0.0624	0.0588	28.84	29.99	30.03	30.54
Lake	0.0300	0.0273	0.0267	0.0250	32.31	33.15	33.34	33.9
Lena	0.0537	0.0478	0.0467	0.0445	30.72	31.73	31.92	32.35
Pirate	0.0758	0.0668	0.0667	0.0618	28.36	29.47	29.47	30.14
Walkbridge	0.0393	0.0355	0.0352	0.0334	30.17	31.05	31.14	31.59
Woman	0.0466	0.0404	0.0405	0.0381	32.89	34.12	34.09	34.64

, for performance indicator error, SCCSAMP consistently outperforms the other three algorithms, particularly on images such as Barbara, Couple, and Lake. Specifically, at a compression ratio of 0.4, SCCSAMP achieves an error of only 0.0925 on the Barbara image, while the other algorithms exhibit error values ranging from 0.0955 to 0.1060, highlighting SCCSAMP’s high precision at lower compression ratios. Similarly, at compression ratios of 0.6 and 0.8, SCCSAMP’s error values remain significantly lower across multiple images. For instance, at a compression ratio of 0.8, the error on the Lake image for SCCSAMP is 0.0200, while SAMP, VSSAMP, and CCSAMP yield errors of 0.0374, 0.0267, and 0.0252, respectively. This indicates that SCCSAMP is able to maintain lower errors even at higher compression rates. Overall, while all algorithms exhibit an increase in error with higher compression ratios, SCCSAMP demonstrates a relatively modest increase, underscoring its stability and robustness in preserving the essential characteristics of the reconstructed images. Higher PSNR values indicate that the reconstructed image is closer in quality to the original. SCCSAMP also shows superior performance in PSNR across most conditions. At a compression ratio of 0.4, SCCSAMP achieves PSNR values of 29.37 and 28.88 on the Lake and Couple images, respectively, surpassing the PSNR values of SAMP, VSSAMP, and CCSAMP and indicating SCCSAMP’s ability to reconstruct images with greater clarity under identical compression conditions. At a compression ratio of 0.6, SCCSAMP maintains a distinct advantage in PSNR on images such as Barbara, Lena, and Walkbridge, reaching values of 29.60, 31.01, and 29.44, respectively, which are the highest among the four algorithms. This suggests that SCCSAMP is more effective at reconstructing high-quality images. Even at the high compression ratio of 0.8, SCCSAMP continues to outperform, achieving a PSNR of 34.64 on the Woman image, which is significantly higher than the values for SAMP (32.82), VSSAMP (33.08), and CCSAMP (34.12). Taken together, SCCSAMP achieves superior PSNR across all compression ratios, underscoring its effectiveness in maintaining visual quality.

5.3.2. Experiment B

To validate the stability and generalizability of the proposed algorithm, we selected various types of images from the CVG-UGR dataset and the Linnaeus 5 dataset for experimentation. The detailed information of the selected images is shown in Figure 6, where images (a) and (b) are sized 256 × 256, and images (c) and (d) are sized 128 × 128. In this experiment, we took into account the impact of both image type and image size on the experimental results. The performance metrics error and PSNR were used for evaluation, and the experimental results of different methods at various compression ratios are presented in

Table 5. The experimental results on different types of images with compression ratio of 0.4.

Image	ERROR				PSNR
	SAMP	VSSAMP	CCSAMP	SCCSAMP	SAMP	VSSAMP	CCSAMP	SCCSAMP
220005	0.1281	0.1266	0.1340	0.1061	24.03	24.14	23.64	25.67
220015	0.1757	0.1859	0.1967	0.0818	29.75	31.15	31.08	32.41
310011	0.1105	0.1092	0.1220	0.1052	25.85	25.95	24.99	26.28
310008	0.2070	0.2163	0.2418	0.1990	23.58	23.20	22.23	23.92

,

Table 6. The experimental results on different types of images with compression ratio of 0.6.

Image	ERROR				PSNR
	SAMP	VSSAMP	CCSAMP	SCCSAMP	SAMP	VSSAMP	CCSAMP	SCCSAMP
220005	0.1041	0.0911	0.0994	0.0828	25.84	26.99	26.23	27.83
220015	0.0755	0.0700	0.0711	0.0596	28.72	29.38	29.25	30.78
310011	0.0892	0.0822	0.0836	0.0753	27.70	28.42	28.27	29.18
310008	0.1605	0.1545	0.1586	0.1313	25.79	26.12	25.90	27.54

and

Table 7. The experimental results on different types of images with compression ratio of 0.8.

Image	ERROR				PSNR
	SAMP	VSSAMP	CCSAMP	SCCSAMP	SAMP	VSSAMP	CCSAMP	SCCSAMP
220005	0.0897	0.0700	0.0750	0.0642	27.12	29.27	28.68	30.03
220015	0.0670	0.0571	0.0576	0.0494	29.75	31.15	31.08	32.41
310011	0.0762	0.0674	0.0674	0.0630	29.07	30.14	30.13	30.73
310008	0.1331	0.1202	0.1228	0.1042	27.42	28.30	28.12	29.54

.

As shown in Table 5, Table 6 and Table 7, for performance indicator error, at different compression ratios, SCCSAMP consistently achieves the lowest error values in all images, indicating superior detail preservation after compression. For example, at a compression ratio of 0.4, SCCSAMP achieves an error of 0.0818 on image 220015, which is substantially lower than the errors of 0.1757, 0.1859, and 0.1967 for SAMP, VSSAMP, and CCSAMP, respectively. This trend persists across higher compression ratios; at a ratio of 0.8, SCCSAMP’s error on image 220005 is only 0.0642, compared to 0.0897 for SAMP, 0.0700 for VSSAMP, and 0.0750 for CCSAMP. These results indicate that SCCSAMP provides more accurate compression performance across all compression levels; for performance indicator PSNR, SCCSAMP also achieves the highest PSNR values in most cases, suggesting superior image quality retention post-compression. For instance, at a compression ratio of 0.8 on image 220015, SCCSAMP achieves a PSNR of 32.41, outperforming SAMP (29.75), VSSAMP (31.15), and CCSAMP (29.38). At lower compression ratios, SCCSAMP maintains this advantage, as seen with image 220005 at a 0.4 compression ratio, where SCCSAMP’s PSNR reaches 25.67, exceeding the values obtained by the other algorithms. This further demonstrates that SCCSAMP not only minimizes error but also provides enhanced perceptual image quality.

6. Conclusions

To address the limitations of the SAMP algorithm, this paper proposes a variable step-size sparse adaptive matching pursuit algorithm based on the Spearman correlation coefficient. The algorithm adjusts the step size by calculating the similarity coefficient between the compressed signal and the signals in the candidate set using the Spearman coefficient. Experimental simulations on one-dimensional sparse signals and two-dimensional image signals demonstrate that, compared to traditional methods, the proposed algorithm not only improves the reconstruction success rate but also maintains good reconstruction accuracy.