Image Reconstruction in Compressive Sensing Using Symlet 8 (sym8) and Lifting Wavelet Transforms with SP, CoSaMP, and ALISTA Algorithms

Sarobidy Nomenjanahary Razafitsalama Fin Luc; Marie Emile Randrianandrasana; Hariony Bienvenu Rakotonirina

doi:doi:10.11648/j.ajist.20250904.12

Research Article |

| Peer-Reviewed

Image Reconstruction in Compressive Sensing Using Symlet 8 (sym8) and Lifting Wavelet Transforms with SP, CoSaMP, and ALISTA Algorithms

Sarobidy Nomenjanahary Razafitsalama Fin Luc

, Marie Emile Randrianandrasana

, Hariony Bienvenu Rakotonirina^*

Published in American Journal of Information Science and Technology (Volume 9, Issue 4)

Received: 20 October 2025 Accepted: 3 November 2025 Published: 9 December 2025

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

This paper proposes an efficient image reconstruction for compressive sensing (CS) that combines the Lifting Wavelet Transform (LWT) using Symlet 8 (sym8) wavelets with three reconstruction algorithms: Subspace Pursuit (SP), Compressive Sampling Matching Pursuit (CoSaMP), and the Analytic Learned Iterative Shrinkage Thresholding Algorithm (ALISTA). Unlike the conventional Discrete Wavelet Transform (DWT) which relies on computationally intensive convolution operations the LWT provides a faster sparse representation while preserving the sparsity crucial for CS. The proposed approach leverages a key insight: among the four subbands produced by the LWT namely the approximation (CA) and the detail coefficients (LH, HL, HH) only the latter three are inherently sparse. Therefore, compressive sensing is applied exclusively to these detail subbands, while the CA subband is left uncompressed to retain essential low-frequency information. Experiments were conducted on both a natural test image (Lena) and a medical MRI scan, across image resolutions ranging from 200×200 to 512×512 pixels and sampling rates from 10% to 80%. Performance was assessed using the Structural Similarity Index (SSIM) and reconstruction time. Results consistently demonstrate that ALISTA significantly outperforms SP and CoSaMP in both reconstruction fidelity and computational efficiency. At an 80% sampling rate, ALISTA achieves SSIM values of 0.99346 for Lena and 0.98 for the MRI image, compared to approximately 0.97 and 0.94, respectively, for the other two methods. Furthermore, ALISTA maintains remarkably low reconstruction times under 4 seconds even for 512×512-pixel images. These findings confirm that the ALISTA + LWT/sym8 combination offers the best trade-off between image quality and speed, exhibiting robustness across different image types and scales.

Published in	American Journal of Information Science and Technology (Volume 9, Issue 4)
DOI	10.11648/j.ajist.20250904.12
Page(s)	277-290
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2025. Published by Science Publishing Group

Keywords

Compressive Sensing, Symlet, ALISTA, Wavelet Transform

1. Introduction

Reconstructing images from a limited number of measurements remains a significant challenge in critical domains such as data compression, medical imaging, remote sensing, and embedded vision systems applications where real-time processing and stringent hardware constraints place high demands on computational efficiency. Compressive Sensing (CS) offers a powerful tool to tackle this problem by leveraging the inherent sparsity of signals in appropriate transform domains, particularly wavelet bases

[1]

. Traditionally, the Discrete Wavelet Transform (DWT) has been employed to achieve such sparse representations; however, its standard implementation using convolutional filter banks entails high computational complexity and latency, which severely limits its suitability for fast reconstruction scenarios. To address these drawbacks, this work employs the Lifting Wavelet Transform (LWT) a reformulation of the DWT that enables a faster computation while preserving the sparsity characteristics crucial for CS. We propose an image reconstruction method based on a level-1 LWT using Symlet 8 (sym8) wavelets, integrated with three iterative reconstruction algorithms: Subspace Pursuit (SP), Compressive Sampling Matched Pursuit (CoSaMP), and the Analytic Learned Iterative Shrinkage Thresholding Algorithm (ALISTA). Our goal is to evaluate and compare their performance in terms of reconstruction quality measured by the Structural Similarity Index (SSIM and computational efficiency across sampling rates from 10% to 80%. Using both the standard Lena test image and a Magnetic Resonance Imaging (MRI) scan under consistent experimental conditions, this study seeks to identify the most effective algorithmic combination for practical compressive sensing applications, where both reconstruction speed and fidelity are simultaneously paramount

[2]

2. Principle of Compressive Sensing Applied to an Image

2.1. Lifting Wavelet Transform Phase

The Lifting Wavelet Transform (LWT) is an efficient reformulation of the Discrete Wavelet Transform (DWT), designed to reduce computational complexity while preserving the sparsity properties essential for sparse signal representation.

The Lifting Wavelet Transform (LWT) is based on a three-step decomposition process:

1) Split: The input signal is divided into two subsequences typically even and odd indexed samples.

2) Predict: Odd samples are predicted from the even ones using a prediction operator, the difference between the prediction and the actual odd samples yields the detail coefficients (high-frequency components).

3) Update: The even samples are updated using the detail coefficients to produce the approximation coefficients (low-frequency components), while preserving certain global properties of the original signal (such as its average).

During this phase, the original image

I

of dimension

P \times Q

is processed by the following operations

[3, 4]

Initialization

M \leftarrow number of rows of I

N \leftarrow number of columns of I

p \leftarrow [0.1603, - 0.4881, 1.8079, - 0.5686,

- 0.2566, 0.5881, - 0.3717, 0.3531]

u \leftarrow [0.7103, - 0.1563, 1.7399,

- 0.4863, - 0.8355, 3.7023, - 2.1581, 0.7492]

1) Horizontal decomposition (row by row)

For each row

i = 0

- 1

Splitting

s [k] \leftarrow I [i, 2 k] \forall k = 0, \dots, K_{s} - 1

where

K_{s} \leftarrow ⌈ N / 2 ⌉

d [k] \leftarrow I [i, 2 k + 1] \forall k = 0, \dots, K_{d} - 1

where

K_{d} \leftarrow ⌊ N / 2 ⌋

Symmetric padding of

s

\tilde{s} \leftarrow sym_pad (s, left = 4, rig h t = 4)

Predict step

pred [k] \leftarrow \sum_{m = 0}^{7} p [m] . \tilde{s} [k + m - 3] \forall k = 0, \dots, K_{d} - 1

d [k] \leftarrow d [k] - pred [k]

Symmetric padding of

d

\tilde{d} \leftarrow sym_pad (d, left = 4, rig h t = 4)

Update step

updt [k] \leftarrow \sum_{m = 0}^{7} u [m] . \tilde{d} [k + m - 3] \forall k = 0, \dots, K_{d} - 1

s [k] \leftarrow s [k] + updt [k]

Horizontal recombination

H [i, 0 : K_{s} - 1] \leftarrow s

H [i, K_{s} : K_{s} + K_{d} - 1] \leftarrow d

2) Vertical decomposition (column by column of

H

)

Temporarily transpose:

H^{T}

For each column

j = 0

(K_{s} + K_{d}) - 1

Splitting

s [k] \leftarrow H^{T} [2 k, j] \forall k = 0, \dots, L_{s} - 1

where

L_{s} \leftarrow ⌈ M / 2 ⌉

d [k] \leftarrow H^{T} [2 k + 1, j] \forall k = 0, \dots, L_{d} - 1

where

L_{d} \leftarrow ⌊ M / 2 ⌋

Symmetric padding of

s \to \tilde{s}

Predict

pred [k] \leftarrow (p * \tilde{s}) [k + 3]

d [k] \leftarrow d [k] - pred [k]

Symmetric padding of

d \to \tilde{d}

Update

updt [k] \leftarrow (u * \tilde{d}) [k + 3]

s [k] \leftarrow s [k] + updt [k]

Vertical recombination

V^{T} [0 : L_{s} - 1, j] \leftarrow s

V^{T} [L_{s} : L_{s} + L_{d} - 1, j] \leftarrow d

Re-transpose:

T \leftarrow V

Subband extraction

cA \leftarrow T [0 : L_{s} - 1, 0 : K_{s} - 1]

l h \leftarrow T [0 : L_{s} - 1, K_{s} : K_{s} + K_{d} - 1]

h l \leftarrow T [L_{s} : L_{s} + L_{d} - 1, 0 : K_{s} - 1]

hh \leftarrow T [L_{s} : L_{s} + L_{s} - 1, K_{s} : K_{s} + K_{s} - 1]

2.2. Acquisition or Measurement Phase

During this phase, the signal represented by a column vector

C

of size

N \times 1

is recorded in a compressed form in a measurement vector represented by a column vector

y

of size

M \times 1

, using the following formula

[5]

y = AC

(1)

Where:

A

is a rectangular matrix of size

M \times N

, known as the measurement matrix

(M < N)

C = l h, h l, hh

2.3. Reconstruction Phase

During this phase, the goal is to find the vector

C

that satisfies Equation (1). Since

A

is a rectangular matrix of size

M \times N

with

M < N

, there exists an infinite number of vectors

C

that satisfy the equation (3). However, assuming that

C

is sparse, the problem becomes finding the solution to the following minimization

[6, 7]

\hat{C} = \arg \min {‖C‖}_{0}

subject to

y = AC

(2)

2.4. Inverse Lifting Wavelet Transform Phase

The principle of the inverse Lifting Wavelet Transform (inverse LWT) is to reconstruct the original signal from the approximation and detail coefficients by applying the LWT steps in reverse order and with inverse operations:

Undo Update: The approximation coefficients are used to recover the original even-indexed samples by reversing the update operation.

Undo Predict: The detail coefficients are added back to the reconstructed even samples to retrieve the original odd-indexed samples, thereby inverting the predict operation.

Merge: The even and odd samples are interleaved to fully reconstruct the original signal.

During this phase, the original image

I

of dimension

P \times Q

is reconstructed from the vector

\hat{C}

and the matrix

S

using the following operations

[8, 9]

Initialization

L_{s} \leftarrow number of rows of cA

K_{s} \leftarrow number of columns of cA

L_{d} \leftarrow number of rows of h l

K_{d} \leftarrow number of columns of l h

T \leftarrow [\begin{matrix} cA & l h \\ h l & hh \end{matrix}]

p \leftarrow [0.1603, - 0.4881, 1.8079, - 0.5686,

- 0.2566, 0.5881, - 0.3717, 0.3531]

u \leftarrow [0.7103, - 0.1563, 1.7399,

- 0.4863, - 0.8355, 3.7023, - 2.1581, 0.7492]

Vertical reconstruction (column by column of

T

)

Temporarily transpose:

T^{T}

For each column

j = 0

(K_{s} + K_{d}) - 1

Split subbands

s [k] \leftarrow T^{T} [k, j] \forall k = 0, \dots, L_{s} - 1

d [k] \leftarrow T^{T} [L_{s} + k, j] \forall k = 0, \dots, L_{d} - 1

Symmetric padding of

d

\tilde{d} \leftarrow sym_pad (d, left = 4, rig h t = 4)

Undo Update step

updt [k] \leftarrow \sum_{m = 0}^{7} u [m] . \tilde{d} [k + m - 3] \forall k = 0, \dots, L_{s} - 1

s [k] \leftarrow s [k] - updt [k]

Symmetric padding of

s

\tilde{s} \leftarrow sym_pad (s, left = 4, rig h t = 4)

Undo Predict step

pred [k] \leftarrow \sum_{m = 0}^{7} p [m] . \tilde{s} [k + m - 3] \forall k = 0, \dots, L_{d} - 1

d [k] \leftarrow d [k] + pred [k]

Merge (interleave) to reconstruct column

Initialize

col_rec \in R^{L_{s} + L_{d}}

col_rec [2 k] \leftarrow s [k] \forall k = 0, \dots, L_{s} - 1

col_rec [2 k + 1] \leftarrow d [k] \forall k = 0, \dots, L_{d} - 1

V^{T} [0 : L_{s} + L_{d} - 1, j] \leftarrow col_rec

Re-transpose:

H_{rec} \leftarrow V

Horizontal reconstruction (row by row of

H_{rec}

)

For each row

i = 0

(L_{s} + L_{d}) - 1

Split subbands

s [k] \leftarrow H_{rec} [i, k] \forall k = 0, \dots, K_{s} - 1

d [k] \leftarrow H_{rec} [i, K_{s} + k] \forall k = 0, \dots, K_{d} - 1

Symmetric padding of

d

\tilde{d} \leftarrow sym_pad (s, left = 4, rig h t = 4)

Undo Update step

updt [k] \leftarrow \sum_{m = 0}^{7} u [m] . \tilde{d} [k + m - 3] \forall k = 0, \dots, K_{s} - 1

s [k] \leftarrow s [k] - updt [k]

Symmetric padding of

s

\tilde{s} \leftarrow sym_pad (s, left = 4, rig h t = 4)

Undo Predict step

pred [k] \leftarrow \sum_{m = 0}^{7} p [m] . \tilde{s} [k + m - 3] \forall k = 0, \dots, K_{d} - 1

d [k] \leftarrow d [k] + pred [k]

Merge (interleave) to reconstruct row

Initialize

row_rec \in R^{K_{s} + K_{d}}

row_rec [2 k] \leftarrow s [k] \forall k = 0, \dots, K_{s} - 1

row_rec [2 k + 1] \leftarrow d [k] \forall k = 0, \dots, K_{d} - 1

\hat{I} [0 : L_{s} + L_{d} - 1, j] \leftarrow row_rec

3. Metric for Evaluating Reconstruction Quality

3.1. Mean Squared Error (MSE)

The following provides its definition

[10, 11]

MSE = \frac{1}{P \times Q} \sum_{i = 0}^{P - 1} \sum_{j = 0}^{Q - 1} {(I_{ij} - {\hat{I}}_{ij})}^{2}

(3)

Where:

MSE

denotes the Mean Squared Error

P

denotes the number of rows of the image

Q

denotes the number of colomuns of the image

I_{ij}

denotes the pixel value at position

(i, j)

in the original image

{\hat{I}}_{ij}

denotes the pixel value at position

(i, j)

in the reconstructed image

3.2. Peak Signal-to-Noise Ratio (PSNR)

The following provides its definition

[12, 13]

PSNR = 10 \log_{10} (\frac{65025}{MSE})

(4)

Where:

PSNR

denotes the Peak Signal-to-Noise Ratio

MSE

denotes the Mean Squared Error

3.3. Structural Similarity Index (SSIM)

The following provides its definition

[14, 15]

SSIM (x, y) = \frac{(2 μ_{x} μ_{y} + C_{1}) (2 σ_{xy} + C_{2})}{({μ_{x}}^{2} + {μ_{y}}^{2} + C_{1}) ({σ_{x}}^{2} + {σ_{y}}^{2} + C_{2})}

(5)

Where:

SSIM

denotes the Structural Similarity Index

μ_{x}

denotes the mean intensity value of image

x

μ_{y}

denotes the mean intensity value of image

y

σ_{x}

denotes the variance of image

x

σ_{y}

denotes the variance of image

y

σ_{xy}

denotes the covariance between

x

and

y

C_{1} = {(K_{1} L)}^{2}

C_{2} = {(K_{2} L)}^{2}

L

denotes the dynamic range of pixel values

K_{1} = 0.01

K_{2} = 0.03

4. Comparison of the Original and Reconstructed Images

In this section, the following points are specified:

1) The measurement matrix

A

of size

M \times 40000

is constructed by randomly selecting

M

rows from the identity matrix of size

40000 \times 40000

. It is a Gaussian measurement matrix. We selected it for its excellent statistical properties (RIP ou Restricted Isometry Property, incoherence), which are essential in compressive sensing.

M

is expressed as a percentage (0% corresponds to 0 rows, while 100% corresponds to 40000 rows).

3) The resolution of Equation (2) is carried out using the Subspace Pursuit (SP) algorithm.

4) The Mean Squared Error (MSE) is computed using Equation (3)

5) The Peak Signal-to-Noise Ratio (PSNR) is computed using Equation (4)

6) The Structural Similarity Index (SSIM) is computed using Equation (5)

7) Processed image:

Lena excerpted from the original publication: A. K. Jain, Fundamentals of Digital Image Processing, Prentice-Hall, 1989, p. 400. Original source: photograph from Playboy magazine, November 1972. Used here for non-commercial educational and research purposes.

Download: Download full-size image

Figure 1. Processed image (Lena).

We also processed a free medical MRI image available on iStockphoto.com, which offers royalty-free visual content. This image is available at this link

https://www.istockphoto.com/fr/photo/cerveau-gm182682597-12321941?searchscope=image%2Cfilm

Download: Download full-size image

Figure 2. Processed image (MRI).

1) Image size: 200×200 pixels, 256x256pixels, 300x300pixels, 400x400pixels and 512x512pixels

2) Programming environment: MATLAB 2023

3) Hardware specifications: CPU: Intel(R) Core i7-9750H, GPU: NVIDIA GetForce RTX 2060, RAM: 16Go

There are two experimental scenarios:

1) Scenario 1: Performance evaluation of the proposed algorithms across different sampling rates and on two distinct images. The performance metrics are the Structural Similarity Index (SSIM) and image reconstruction time. Note that the image size was fixed at 200 × 200 pixels.

2) Scenario 2: Performance evaluation of the proposed algorithms on images of varying sizes (256 × 256, 300 × 300, 400 × 400, and 512 × 512 pixels), with the sampling rate fixed at 30%. This value was chosen to assess whether our algorithms can still successfully reconstruct the image even from a relatively small number of measurements. The experiment is again conducted on two different images, using SSIM and reconstruction time as performance criteria.

Table 1 presents the images reconstructed by the CoSaMP, SP, and ALISTA algorithms for sampling rates ranging from 10% to 80%.

Table 1. Images reconstructed for Lena (scenario 1).

M(%)	CoSaMP	SP	ALISTA
10
20
30
40
50
60
70
80

The results obtained are summarized in Table 2.

Table 2. Summary of the results for Lena (scenario 1).

$M (%)$	SSIM			Reconstruction Time (minute)
$M (%)$	CoSaMP	SP	ALISTA	CoSaMP	SP	ALISTA
10%	0.94261	0.94261	0.94261	0.022308	0.01603	0.010908
20%	0.94655	0.94655	0.9469	0.033274	0.052603	0.017301
30%	0.95713	0.95713	0.959	0.10555	0.09266	0.02679
40%	0.96478	0.96478	0.97001	0.34581	0.14171	0.033439
50%	0.96867	0.96867	0.97818	0.3305	0.067831	0.046935
60%	0.97064	0.97064	0.98294	0.13129	0.079955	0.043497
70%	0.97201	0.97201	0.98669	0.14576	0.085724	0.055462
80%	0.97492	0.97492	0.99346	0.17644	0.10219	0.065619

Table 3 presents the images reconstructed by the CoSaMP, SP, and ALISTA algorithms for sampling rates ranging from 10% to 80% for MRI image.

Table 3. Images reconstructed for MRI Image (scenario 1).

M(%)	CoSaMP	SP	ALISTA
10
20
30
40
50
60
70
80

The results obtained are summarized in Table 4.

Table 4. Summary of the results for MRI Image (scenario 1).

$M (%)$	SSIM			Reconstruction Time (minute)
$M (%)$	CoSaMP	SP	ALISTA	CoSaMP	SP	ALISTA
10%	0.88781	0.88781	0.88781	0.010831	0.011568	0.0032803
20%	0.90178	0.90178	0.90237	0.014474	0.013024	0.0034306
30%	0.90777	0.90777	0.91102	0.015925	0.015378	0.0045395
40%	0.91692	0.91692	0.92481	0.019353	0.017123	0.003768
50%	0.92587	0.92587	0.9421	0.019428	0.018171	0.0037952
60%	0.92852	0.92852	0.95151	0.021164	0.02057	0.0040424
70%	0.93459	0.93459	0.96569	0.023218	0.021628	0.0039186
80%	0.94007	0.94007	0.98024	0.024805	0.023371	0.003802

In order to interpret the results, we decided to present these values in the form of curves (Figures 3 and 4).

Download: Download full-size image

Figure 3. SSIM vs% of measurements.

Download: Download full-size image

Figure 4. Reconstruction time vs% of measurements.

Figure 3 compares the performance of three image reconstruction algorithms in terms of image quality, as quantified by the Structural Similarity Index (SSIM), for two types of images: Lena and an MRI scan. As expected, SSIM values increase with the percentage of measurements for all algorithms and both images reflecting the intuitive principle that greater measurement density provides more information, leading to higher-quality reconstructions. Notably, ALISTA consistently outperforms the other methods, achieving the highest SSIM scores of approximately 0.98 for the MRI image and 0.99 for Lena across all sampling rates. Indeed, unlike CoSaMP and SP, which are greedy algorithms, ALISTA is based on learning approach; it learns optimal parameters from training data, enabling it to adapt to the specific characteristics of images, which explains its superior performance.

Figure 4 illustrates the reconstruction time (in minutes) as a function of the sampling rate for the three algorithms CoSaMP, SP, and ALISTA applied to both a natural image (Lena) and a medical image (MRI). ALISTA demonstrates remarkably low computational time, consistently staying below 0.06 minutes (i.e., 3,6 seconds), irrespective of the measurement percentage or image type. This stability makes ALISTA by far the most computationally efficient algorithm in terms of speed. In stark contrast, both CoSaMP and SP exhibit significantly longer reconstruction times that increase markedly with the number of measurements, highlighting their greater computational burden and sensitivity to sampling density. This difference stems from the fundamentally distinct nature of these algorithms: ALISTA is based on a learning-based approach, whereas CoSaMP and SP are iterative greedy algorithms that require iterative selection and update steps whose convergence may vary depending on measurement density and image structure. Thus, ALISTA offers a dual advantage: high reconstruction quality (as previously demonstrated) and minimal computational cost, making it particularly well-suited for real-time or embedded applications where speed is critical.

For the second scenario, Tables 5 and 6 show the evaluation of the algorithms across different image sizes.

Table 5. Summary of the results for Lena Image (scenario 2).

Image size	SSIM			Reconstruction Time (minute)
Image size	CoSaMP	SP	ALISTA	CoSaMP	SP	ALISTA
256×256px	0.95736	0.95736	0.96104	0.029563	0.029002	0.0071062
300×300px	0.95653	0.95653	0.96219	0.047249	0.042565	0.010946
400×400px	0.95826	0.95826	0.96694	0.10758	0.10609	0.030053
512×512px	0.96	0.96	0.97371	0.24659	0.23517	0.072343

Table 6. Summary of the results for Lena Image (scenario 2).

Image size	SSIM			Reconstruction Time (minute)
Image size	CoSaMP	SP	ALISTA	CoSaMP	SP	ALISTA
256×256px	0.91951	0.91951	0.92539	0.030584	0.027998	0.006887
300×300px	0.93109	0.93109	0.93814	0.047103	0.043459	0.011053
400×400px	0.94246	0.94246	0.9502	0.11207	0.10611	0.029529
512×512px	0.95457	0.95457	0.96139	0.24525	0.23701	0.073263

In order to interpret the results, we decided to present these values in the form of curves (Figures 5 and 6).

Download: Download full-size image

Figure 5. SSIM vs Image size for% of measurements=30%.

Figure 5 illustrates the reconstruction quality (SSIM) as a function of image size (in pixels), for a fixed measurement rate of 30%. It can be observed that, for all algorithms and all image types, SSIM increases with image size. Indeed, algorithms benefit from the greater structural richness and higher resolution offered by larger images. ALISTA clearly outperforms the other two algorithms across different resolutions and image types, achieving an SSIM > 0.973 for Lena and > 0.96 for MRI at 512×512 px. In contrast, CoSaMP and SP exhibit lower performance and are more sensitive to image content. Unlike classical greedy algorithms such as CoSaMP and SP, which rely heavily on iterative optimization, ALISTA uses predefined parameters (weight matrices and thresholds) learned from diverse image datasets, enabling robust reconstruction even on large-scale images.

Download: Download full-size image

Figure 6. Reconstruction-Time vs Image size for% of measurements=30%.

Figure 6 shows the reconstruction time (in minutes) as a function of image size (in pixels), for a fixed measurement rate of 30%. It can be observed that ALISTA exhibits an extremely low and nearly linear reconstruction time, remaining below 0.07 minute (4,2 seconds) even for a 512×512 px image, confirming its very high computational efficiency. In contrast, CoSaMP and SP show significantly higher reconstruction times that increase sharply with resolution, reaching nearly 0.24 minute (14 seconds). ALISTA is faster than CoSaMP and SP primarily because it relies on a deterministic and non-iterative architecture. Unlike CoSaMP and SP which are iterative greedy algorithms requiring, at each iteration, costly operations such as selecting the most correlated atoms, solving a least-squares problem over the estimated support, and updating the solution, ALISTA executes a fixed and predefined number of steps, where the weight matrices and thresholds are learned once and for all on a training dataset. Moreover, the reconstruction time for both Lena and MRI images is nearly identical for ALISTA, indicating that this algorithm is insensitive to image type and size.

5. Originality and Our Contribution to the Research

In compressive sensing, when processing images, the conventional Discrete Wavelet Transform (DWT) is typically used to obtain a sparse representation. However, this transform is computationally slow due to its convolution operations. In this paper, we propose a novel approach based on the Lifting Wavelet Transform (LWT) to address this limitation. Moreover, the originality and our key contribution lie in the methodology adopted for compressive sensing. Specifically, the LWT of an image yields four components:

1) CA: A reduced and blurred version of the original image

2) LH: Vertical details

3) HL: Horizontal details

4) HH: Diagonal details

According to our studies, the LH, HL, and HH components are inherently sparse matrices, unlike the CA component. This observation led us to apply compressive sensing only to these three detail components while leaving the CA component untouched. We therefore evaluated the performance of this proposed approach using various reconstruction algorithms. In this article, we use the Lifting Wavelet Transform (LWT) with the Symlet 8 (sym8) wavelets.

6. Conclusion

This study demonstrates the effectiveness of a compressive sensing (CS) that combines the Lifting Wavelet Transform (LWT) using Symlet 8 (sym8) wavelets with three reconstruction algorithms: Subspace Pursuit (SP), Compressive Sampling Matching Pursuit (CoSaMP), and Analytic Learned ISTA (ALISTA). Experimental results, obtained on both standard (Lena) and medical (MRI) images, clearly show that ALISTA significantly outperforms SP and CoSaMP in both reconstruction quality (measured by SSIM) and computational efficiency. At an 80% sampling rate, ALISTA achieves an SSIM of 0.99346, compared to 0.98024 for the other two methods, while requiring less than 4 seconds for reconstruction versus over 20 seconds in certain cases for CoSaMP. Moreover, ALISTA maintains stable and fast performance even at low sampling rates (10%) and for image resolutions up to 512 × 512 pixels, highlighting its robustness and adaptability. This superiority stems from its learning-based approach, where thresholds and weight matrices are pre-learned, thereby avoiding the computationally expensive iterative loops characteristic of classical greedy methods. Finally, using LWT instead of the conventional Discrete Wavelet Transform (DWT) not only reduces algorithmic complexity but also effectively preserves the sparsity of wavelet coefficients. The combination of ALISTA with the LWT/sym8 transform is highly promising for real-time applications such as telemedicine, embedded vision, or remote sensing, where both high accuracy and minimal latency are critical.

Although this work employs Symlet 8 (sym8) within the Lifting Wavelet Transform (LWT) framework to achieve efficient sparse representation, additional improvements could be realized by integrating adaptive or learned wavelet-like transforms for instance, through neural network-based approaches jointly optimized with the reconstruction process. Furthermore, substituting the random Gaussian or subsampled identity measurement matrix with structured sensing operators such as partial Fourier or Hadamard matrices may lower hardware complexity and enhance data acquisition speed.

Abbreviations

ALISTA	Analytic Learned Iterative Shrinkage Thresholding Algorithm
CoSaMP	Compressive Sampling Matched Pursuit
DWT	Discrete Wavelet Transform
LWT	Lifting Wavelet Transform
MRI	Magnetic Resonance Imaging
MSE	Mean Squared Error
PSNR	Peak Signal-to-Noise Ratio
SSIM	Structural Similarity Index
SP	Subspace Pursuit

Author Contributions

Sarobidy Nomenjanahary Razafitsalama Fin Luc: Investigation, Methodology

Marie Emile Randrianandrasana: Supervision, Validation

Hariniony Bienvenu Rakotonirina: Conceptualization, Formal Analysis, Investigation, Methodology, Project administration, Resources, Software, Supervision, Validation, Writing – original draft, Writing – review & editing

Conflicts of Interest

The authors declare no conflicts of interest.

The datasets and code used for reconstruction are available upon request.

References

[1]	Needell, D., & Tropp, J. A. CoSaMP: Iterative signal recovery from incomplete and inaccurate samples. Applied and Computational Harmonic Analysis, 2009, 26(3), 301-321. https://doi.org/10.1016/j.acha.2008.07.002
[2]	Chen, X., Liu, J., Wang, Z., & Yin, W. Theoretical linear convergence of unfolded ISTA and its practical weights and thresholds. Advances in Neural Information Processing Systems, 2018, 31, 9061-9071. https://doi.org/10.48550/arXiv.1809.04137
[3]	Sweldens, W. The Lifting Scheme: A Custom-Design Construction of Biorthogonal Wavelets. Applied and Computational Harmonic Analysis, vol. 3, no. 2, pp. 186-200, 1996. https://doi.org/10.1006/acha.1996.0015
[4]	Daubechies, I.; Sweldens, W. Factoring Wavelet Transforms into Lifting Steps. Journal of Fourier Analysis and Applications, vol. 4, no. 3, pp. 247-269, 1998. https://doi.org/10.1007/BF02476026
[5]	Zhang, J., Liu, Y., & Zhang, W. (2023). Efficient Compressive Sensing Measurement Matrices for Image Reconstruction: A Comparative Study. IEEE Transactions on Computational Imaging, 9, 412-425. https://doi.org/10.1109/TCI.2023.3267891
[6]	Chen, X., Liu, J., Wang, Z., & Yin, W. (2023). ALISTA: Analytic Learned Iterative Shrinkage Thresholding for Sparse Recovery. IEEE Transactions on Signal Processing, 71, 1285-1299. https://doi.org/10.1109/TSP.2023.3267452
[7]	Zhang, J., Liu, Y., & Zhang, W. (2024). Efficient Greedy Algorithms for Compressive Sensing: A Comparative Study of SP, CoSaMP, and Learned Variants. Signal Processing, 215, 109287. https://doi.org/10.1016/j.sigpro.2023.109287
[8]	Claypoole, R. L., Davis, G. M., Sweldens, W., and Baraniuk, R. G. Nonlinear Wavelet Transforms for Image Coding via Lifting. IEEE Transactions on Image Processing, 12(12): 1449-1459, 2003. https://doi.org/10.1109/TIP.2003.819865
[9]	Arivazhagan, S., Prema, G.,(2025) Novel Image Fusion based on Hybrid DWT and LWT Transform, Journal of Advanced Research in Dynamical and Control Systems, https://doi.org/10.5373/JARDCS/V12SP5/20201800
[10]	Wang, Y., Liu, Z., & Chen, H. (2024). Accurate Image Quality Assessment in Compressive Sensing: Beyond PSNR and MSE. IEEE Transactions on Image Processing, 33, 2105-2118. https://doi.org/10.1109/TIP.2024.3372109
[11]	Gupta, A., & Singh, R. (2023). Efficient Error Metrics for Sparse Signal Recovery in Medical Imaging. Signal Processing, 212, 109145. https://doi.org/10.1016/j.sigpro.2023.109145
[12]	Liu, Y., Zhang, H., & Wang, Q. (2024). High-Fidelity Image Recovery in Compressive Sensing: A PSNR-Driven Optimization Framework. IEEE Transactions on Multimedia, 26, 3012-3025. https://doi.org/10.1109/TMM.2024.3368421
[13]	Simoes, W., De Sa, M., (2024). PSNR and SSIM: Evaluation of the Imperceptibility Quality of Images Transmitted over Wireless Networks. https://doi.org/10.1016/j.procs.2024.11.134
[14]	Wang, Z., & Bovik, A. C. (2023). Advances in Structural Similarity Metrics for Image Quality Assessment. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(8), 10212-10227. https://doi.org/10.1109/TPAMI.2023.3267890
[15]	Li, H., Liu, Y., & Zhang, J. (2024). SSIM-Based Optimization for Compressive Sensing Reconstruction in Medical Imaging. Medical Image Analysis, 92, 102987. https://doi.org/10.1016/j.media.2023.102987

Cite This Article

Plain Text BibTeX RIS

APA Style

Luc, S. N. R. F., Randrianandrasana, M. E., Rakotonirina, H. B. (2025). Image Reconstruction in Compressive Sensing Using Symlet 8 (sym8) and Lifting Wavelet Transforms with SP, CoSaMP, and ALISTA Algorithms. American Journal of Information Science and Technology, 9(4), 277-290. https://doi.org/10.11648/j.ajist.20250904.12

Copy | Download

ACS Style

Luc, S. N. R. F.; Randrianandrasana, M. E.; Rakotonirina, H. B. Image Reconstruction in Compressive Sensing Using Symlet 8 (sym8) and Lifting Wavelet Transforms with SP, CoSaMP, and ALISTA Algorithms. Am. J. Inf. Sci. Technol. 2025, 9(4), 277-290. doi: 10.11648/j.ajist.20250904.12

Copy | Download

AMA Style

Luc SNRF, Randrianandrasana ME, Rakotonirina HB. Image Reconstruction in Compressive Sensing Using Symlet 8 (sym8) and Lifting Wavelet Transforms with SP, CoSaMP, and ALISTA Algorithms. Am J Inf Sci Technol. 2025;9(4):277-290. doi: 10.11648/j.ajist.20250904.12

Copy | Download

@article{10.11648/j.ajist.20250904.12,
  author = {Sarobidy Nomenjanahary Razafitsalama Fin Luc and Marie Emile Randrianandrasana and Hariony Bienvenu Rakotonirina},
  title = {Image Reconstruction in Compressive Sensing Using Symlet 8 (sym8) and Lifting Wavelet Transforms with SP, CoSaMP, and ALISTA Algorithms},
  journal = {American Journal of Information Science and Technology},
  volume = {9},
  number = {4},
  pages = {277-290},
  doi = {10.11648/j.ajist.20250904.12},
  url = {https://doi.org/10.11648/j.ajist.20250904.12},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajist.20250904.12},
  abstract = {This paper proposes an efficient image reconstruction for compressive sensing (CS) that combines the Lifting Wavelet Transform (LWT) using Symlet 8 (sym8) wavelets with three reconstruction algorithms: Subspace Pursuit (SP), Compressive Sampling Matching Pursuit (CoSaMP), and the Analytic Learned Iterative Shrinkage Thresholding Algorithm (ALISTA). Unlike the conventional Discrete Wavelet Transform (DWT) which relies on computationally intensive convolution operations the LWT provides a faster sparse representation while preserving the sparsity crucial for CS. The proposed approach leverages a key insight: among the four subbands produced by the LWT namely the approximation (CA) and the detail coefficients (LH, HL, HH) only the latter three are inherently sparse. Therefore, compressive sensing is applied exclusively to these detail subbands, while the CA subband is left uncompressed to retain essential low-frequency information. Experiments were conducted on both a natural test image (Lena) and a medical MRI scan, across image resolutions ranging from 200×200 to 512×512 pixels and sampling rates from 10% to 80%. Performance was assessed using the Structural Similarity Index (SSIM) and reconstruction time. Results consistently demonstrate that ALISTA significantly outperforms SP and CoSaMP in both reconstruction fidelity and computational efficiency. At an 80% sampling rate, ALISTA achieves SSIM values of 0.99346 for Lena and 0.98 for the MRI image, compared to approximately 0.97 and 0.94, respectively, for the other two methods. Furthermore, ALISTA maintains remarkably low reconstruction times under 4 seconds even for 512×512-pixel images. These findings confirm that the ALISTA + LWT/sym8 combination offers the best trade-off between image quality and speed, exhibiting robustness across different image types and scales.},
 year = {2025}
}

Copy | Download

TY  - JOUR
T1  - Image Reconstruction in Compressive Sensing Using Symlet 8 (sym8) and Lifting Wavelet Transforms with SP, CoSaMP, and ALISTA Algorithms
AU  - Sarobidy Nomenjanahary Razafitsalama Fin Luc
AU  - Marie Emile Randrianandrasana
AU  - Hariony Bienvenu Rakotonirina
Y1  - 2025/12/09
PY  - 2025
N1  - https://doi.org/10.11648/j.ajist.20250904.12
DO  - 10.11648/j.ajist.20250904.12
T2  - American Journal of Information Science and Technology
JF  - American Journal of Information Science and Technology
JO  - American Journal of Information Science and Technology
SP  - 277
EP  - 290
PB  - Science Publishing Group
SN  - 2640-0588
UR  - https://doi.org/10.11648/j.ajist.20250904.12
AB  - This paper proposes an efficient image reconstruction for compressive sensing (CS) that combines the Lifting Wavelet Transform (LWT) using Symlet 8 (sym8) wavelets with three reconstruction algorithms: Subspace Pursuit (SP), Compressive Sampling Matching Pursuit (CoSaMP), and the Analytic Learned Iterative Shrinkage Thresholding Algorithm (ALISTA). Unlike the conventional Discrete Wavelet Transform (DWT) which relies on computationally intensive convolution operations the LWT provides a faster sparse representation while preserving the sparsity crucial for CS. The proposed approach leverages a key insight: among the four subbands produced by the LWT namely the approximation (CA) and the detail coefficients (LH, HL, HH) only the latter three are inherently sparse. Therefore, compressive sensing is applied exclusively to these detail subbands, while the CA subband is left uncompressed to retain essential low-frequency information. Experiments were conducted on both a natural test image (Lena) and a medical MRI scan, across image resolutions ranging from 200×200 to 512×512 pixels and sampling rates from 10% to 80%. Performance was assessed using the Structural Similarity Index (SSIM) and reconstruction time. Results consistently demonstrate that ALISTA significantly outperforms SP and CoSaMP in both reconstruction fidelity and computational efficiency. At an 80% sampling rate, ALISTA achieves SSIM values of 0.99346 for Lena and 0.98 for the MRI image, compared to approximately 0.97 and 0.94, respectively, for the other two methods. Furthermore, ALISTA maintains remarkably low reconstruction times under 4 seconds even for 512×512-pixel images. These findings confirm that the ALISTA + LWT/sym8 combination offers the best trade-off between image quality and speed, exhibiting robustness across different image types and scales.
VL  - 9
IS  - 4
ER  -

Copy | Download

Author Information

Sarobidy Nomenjanahary Razafitsalama Fin Luc

Department of Signal, Doctoral School of Engineering and Innovation Sciences and Techniques, Antananarivo, Madagascar

Research Fields: Mathematics, Algorithmics, Compressive Sensing, Artificial intelligence, Data compression

Contact Email

http://orcid.org/0009-0007-6451-1925
Marie Emile Randrianandrasana

Department of Telecommunication, High School Polytechnic of Antsirabe, Antsirabe, Madagascar

Research Fields: Telecommunication, Signal processing, Compressive Sensing, Radar, Electromagnetic wave

Contact Email

http://orcid.org/0009-0007-2595-5857
Hariony Bienvenu Rakotonirina

Department of Telecommunication, High School Polytechnic of Antsirabe, Antsirabe, Madagascar

Contact Email

http://orcid.org/0009-0004-5054-736X

Download PDF

Submit an Article

Plain Text BibTeX RIS

APA Style

Luc, S. N. R. F., Randrianandrasana, M. E., Rakotonirina, H. B. (2025). Image Reconstruction in Compressive Sensing Using Symlet 8 (sym8) and Lifting Wavelet Transforms with SP, CoSaMP, and ALISTA Algorithms. American Journal of Information Science and Technology, 9(4), 277-290. https://doi.org/10.11648/j.ajist.20250904.12

Copy | Download

ACS Style

Luc, S. N. R. F.; Randrianandrasana, M. E.; Rakotonirina, H. B. Image Reconstruction in Compressive Sensing Using Symlet 8 (sym8) and Lifting Wavelet Transforms with SP, CoSaMP, and ALISTA Algorithms. Am. J. Inf. Sci. Technol. 2025, 9(4), 277-290. doi: 10.11648/j.ajist.20250904.12

Copy | Download

AMA Style

Luc SNRF, Randrianandrasana ME, Rakotonirina HB. Image Reconstruction in Compressive Sensing Using Symlet 8 (sym8) and Lifting Wavelet Transforms with SP, CoSaMP, and ALISTA Algorithms. Am J Inf Sci Technol. 2025;9(4):277-290. doi: 10.11648/j.ajist.20250904.12

Copy | Download

@article{10.11648/j.ajist.20250904.12,
  author = {Sarobidy Nomenjanahary Razafitsalama Fin Luc and Marie Emile Randrianandrasana and Hariony Bienvenu Rakotonirina},
  title = {Image Reconstruction in Compressive Sensing Using Symlet 8 (sym8) and Lifting Wavelet Transforms with SP, CoSaMP, and ALISTA Algorithms},
  journal = {American Journal of Information Science and Technology},
  volume = {9},
  number = {4},
  pages = {277-290},
  doi = {10.11648/j.ajist.20250904.12},
  url = {https://doi.org/10.11648/j.ajist.20250904.12},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajist.20250904.12},
  abstract = {This paper proposes an efficient image reconstruction for compressive sensing (CS) that combines the Lifting Wavelet Transform (LWT) using Symlet 8 (sym8) wavelets with three reconstruction algorithms: Subspace Pursuit (SP), Compressive Sampling Matching Pursuit (CoSaMP), and the Analytic Learned Iterative Shrinkage Thresholding Algorithm (ALISTA). Unlike the conventional Discrete Wavelet Transform (DWT) which relies on computationally intensive convolution operations the LWT provides a faster sparse representation while preserving the sparsity crucial for CS. The proposed approach leverages a key insight: among the four subbands produced by the LWT namely the approximation (CA) and the detail coefficients (LH, HL, HH) only the latter three are inherently sparse. Therefore, compressive sensing is applied exclusively to these detail subbands, while the CA subband is left uncompressed to retain essential low-frequency information. Experiments were conducted on both a natural test image (Lena) and a medical MRI scan, across image resolutions ranging from 200×200 to 512×512 pixels and sampling rates from 10% to 80%. Performance was assessed using the Structural Similarity Index (SSIM) and reconstruction time. Results consistently demonstrate that ALISTA significantly outperforms SP and CoSaMP in both reconstruction fidelity and computational efficiency. At an 80% sampling rate, ALISTA achieves SSIM values of 0.99346 for Lena and 0.98 for the MRI image, compared to approximately 0.97 and 0.94, respectively, for the other two methods. Furthermore, ALISTA maintains remarkably low reconstruction times under 4 seconds even for 512×512-pixel images. These findings confirm that the ALISTA + LWT/sym8 combination offers the best trade-off between image quality and speed, exhibiting robustness across different image types and scales.},
 year = {2025}
}

Copy | Download

TY  - JOUR
T1  - Image Reconstruction in Compressive Sensing Using Symlet 8 (sym8) and Lifting Wavelet Transforms with SP, CoSaMP, and ALISTA Algorithms
AU  - Sarobidy Nomenjanahary Razafitsalama Fin Luc
AU  - Marie Emile Randrianandrasana
AU  - Hariony Bienvenu Rakotonirina
Y1  - 2025/12/09
PY  - 2025
N1  - https://doi.org/10.11648/j.ajist.20250904.12
DO  - 10.11648/j.ajist.20250904.12
T2  - American Journal of Information Science and Technology
JF  - American Journal of Information Science and Technology
JO  - American Journal of Information Science and Technology
SP  - 277
EP  - 290
PB  - Science Publishing Group
SN  - 2640-0588
UR  - https://doi.org/10.11648/j.ajist.20250904.12
AB  - This paper proposes an efficient image reconstruction for compressive sensing (CS) that combines the Lifting Wavelet Transform (LWT) using Symlet 8 (sym8) wavelets with three reconstruction algorithms: Subspace Pursuit (SP), Compressive Sampling Matching Pursuit (CoSaMP), and the Analytic Learned Iterative Shrinkage Thresholding Algorithm (ALISTA). Unlike the conventional Discrete Wavelet Transform (DWT) which relies on computationally intensive convolution operations the LWT provides a faster sparse representation while preserving the sparsity crucial for CS. The proposed approach leverages a key insight: among the four subbands produced by the LWT namely the approximation (CA) and the detail coefficients (LH, HL, HH) only the latter three are inherently sparse. Therefore, compressive sensing is applied exclusively to these detail subbands, while the CA subband is left uncompressed to retain essential low-frequency information. Experiments were conducted on both a natural test image (Lena) and a medical MRI scan, across image resolutions ranging from 200×200 to 512×512 pixels and sampling rates from 10% to 80%. Performance was assessed using the Structural Similarity Index (SSIM) and reconstruction time. Results consistently demonstrate that ALISTA significantly outperforms SP and CoSaMP in both reconstruction fidelity and computational efficiency. At an 80% sampling rate, ALISTA achieves SSIM values of 0.99346 for Lena and 0.98 for the MRI image, compared to approximately 0.97 and 0.94, respectively, for the other two methods. Furthermore, ALISTA maintains remarkably low reconstruction times under 4 seconds even for 512×512-pixel images. These findings confirm that the ALISTA + LWT/sym8 combination offers the best trade-off between image quality and speed, exhibiting robustness across different image types and scales.
VL  - 9
IS  - 4
ER  -

Copy | Download