Ali Karah Bash*
| Husham Y. A. Alameen | Mohammed Madi
© 2026 The authors. This article is published by IIETA and is licensed under the CC BY 4.0 license (http://creativecommons.org/licenses/by/4.0/).
OPEN ACCESS
Compressive sensing (CS) is a reliable framework that enables efficient and reliable acquisition and reconstruction of sparse signals using a relatively small number of measurements. Further, CS can reduce the sampling rates required by the Nyquist criterion. In this study, the watermarking image is embedded in the Compressive Measurement Vectors (CMV) to provide additional data security during its acquisition and transmission. Using $\ell$1-norm minimization, orthogonal matching pursuit (OMP), and OMP with partially known support (OMP-PKS), the watermarked measurement vectors are reconstructed. The evaluation of each algorithm for reconstruction accuracy is conducted under two decoding strategies to assess reconstruction quality and computational efficiency. The experimental results demonstrate that the OMP-PKS algorithm achieves the best overall performance, producing high-quality reconstructions with improved peak signal-to-noise ratio (PSNR) values, while also reducing computation time compared with other reconstruction methods. The results demonstrate that the application of digital watermarking in CS reconstruction can facilitate secure and reliable image transmission across various communication and sensing systems.
digital watermarking, compressive sensing, ℓ1-norm minimization, orthogonal matching pursuit, OMP with partially known support, image reconstruction, signal processing
According to the Shannon-Nyquist sampling Theorem, a signal is completely reconstructed if it is sampled at a rate twice that of the maximum frequency present in the signal. Although this principle provides reliable signal recovery, sampling at such rates can result in substantial data volumes, particularly for redundant or high-dimensional signals, thereby increasing the computational, storage, and transmission requirements [1-5].
The methodology leveraged in compressive sensing (CS) is that it is possible to reconstruct any signal that holds a sparse representation in a certain basis using a limited number of observations. In CS, a signal is called sparse when the number of nonzero coefficients in an appropriate representation domain is relatively small, with the remaining coefficients being zero or negligible values. Natural images are not sparse in the original spatial domain. However, other suitable transforms like the discrete cosine transform (DCT), discrete Fourier transform (DFT), and discrete wavelet transform (DWT) may be used to obtain sparse/compressible representations [6].
Many algorithms have been developed to reconstruct sparse signals from compressive measurements, including total variation minimization, $\ell$1-based optimization, Bayesian approaches, and greedy iterative algorithms. Among these approaches, greedy reconstruction algorithms have attracted considerable attention because they can provide a favorable balance between reconstruction accuracy and computational complexity. Such algorithms iteratively identify the most relevant components of a sparse signal based on their correlation with the sensing measurements or the current residual, and progressively refine the reconstructed solution. Representative greedy reconstruction methods include orthogonal matching pursuit (OMP), compressive sampling matching pursuit (CoSaMP), and subspace matching pursuit (SAMP) [7].
OMP with partially known support (OMP-PKS) extends the conventional OMP framework by incorporating prior information about a portion of the signal support, thereby reducing the uncertainty associated with support identification during reconstruction [8]. On this basis, this study investigates three representative CS reconstruction approaches—$\ell$1-norm minimization, OMP, and OMP-PKS—to evaluate their reconstruction performance and computational behavior for sparse image recovery.
The $\ell$1-norm approach formulates sparse reconstruction as an optimization problem that promotes sparsity in the recovered signal [9]. In contrast, OMP iteratively selects the sensing matrix column that most strongly correlates with the current residual, updating the estimated support and reconstruction at each iteration [10]. By incorporating partially known support information, OMP-PKS can reduce the support-search burden compared with conventional OMP and can consequently improve reconstruction performance under suitable measurement conditions [11].
Research Gaps and Contributions:
Although research in signal processing and analysis has advanced CS and watermarking technologies, little existing research has embedded the watermark during the compressive measurement process. Furthermore, research comparing the performance of multiple reconstruction algorithms in this watermarking embedding remains limited. Many previous works have attempted to optimize either signal reconstruction accuracy or computational efficiency, but to date, few studies have combined both high reconstruction quality and fast execution within a unified compressed sensing framework. To address these gaps, this study makes the following contributions:
(1) It proposes a hybrid watermarking CS framework in which watermark information is embedded into the Compressive Measurement Vectors (CMV) to enhance data security during signal acquisition.
(2) It presents a systematic comparative performance evaluation of three reconstruction algorithms—ℓ1-norm minimization, OMP, and OMP-PKS—under consistent experimental conditions.
(3) It demonstrates that the OMP-PKS algorithm achieves superior reconstruction accuracy and computational efficiency, highlighting its suitability for real-time and secure image processing applications.
The rest of this paper is structured as follows. Section II presents the theoretical background of CS and the reconstruction algorithms. Section III talks about the materials and methodology. Section IV discusses the experimental results. Lastly, Section V is the conclusion of the paper.
This section provides a review of notable developments in CS and its applications in digital watermarking. CS has made impressive strides. New algorithms, a revised sensing model, and inconsistencies in the CS literature have motivated the study reported here. CS leverages the sparse or compressible nature of natural signals. It allows reconstruction from far fewer samples than that required by the Shannon–Nyquist theorem. This is useful in high-resolution image acquisition [1, 2]. Because natural images are unlikely to be sparse in the native pixel domain, the transformations of DCT, DFT, and DWT are commonly used to compact energy and exhibit sparse structures, thus permitting stable recovery from limited measurements [3-6]. Among the algorithms widely used are convex optimization methods and greedy pursuit algorithms. Theoretical guarantees for underdetermined linear systems are firm for convex approaches based on $\ell$1-norm minimization, namely Basis Pursuit Denoising (BPD) and the Least Absolute Shrinkage and Selection Operator (LASSO).
Therefore, they remain a method of choice if robustness and reproducibility are essential [7-9]. In contrast, greedy algorithms, such as OMP, iteratively select values most highly correlated with the residual. This attractive behavior provides them with low latency and low computational complexity, making them suitable for both real-time and resource-constrained systems [10]. An extension of OMP, namely OMP-PKS, assumes partial-support knowledge to guide the value selection. This helps improve the stability of the reconstruction at low sampling ratios—for example, by seeding indices of the dominant sub-bands in a wavelet pyramid [11]. Many improvements have been made to greedy frameworks. For example, the Constrained Backtracking Matching Pursuit (CBMP) algorithm adaptively adjusts the estimated sparsity level, enhancing the accuracy of support recovery in image reconstruction [12].
The Adaptive Iterative Forward-Backward (AIFB) method is proposed to improve the reconstruction error. In AIFB, a least-squares problem is solved in the forward phase, and this column selection improves over classical greedy methods [13]. Other studies showcase better accuracy and efficiency compared to OMP and CoSaMP under realistic noise and sampling scenarios. Initially, seek blind sparsity estimation based on a dichotomous search and greedy selection. At the same time, the second approach introduces a hybrid architecture that effectively combines conventional CS and one-bit CS support detection with noise-performance guarantees [14-16]. Surveys on dictionary learning, block-based CS, and chaotic CS [17, 18] show that these developments are not standalone. These developments are interconnected.
The increasing integration of computer science with applications in digital watermarking, which is widely used in image applications, provides a good opportunity to achieve acquisition and protection in a single measurement. Adaptive measurement selection and dynamic sampling strategies have been employed in conjunction with watermark embedding and recovery to enhance reconstruction fidelity while protecting the transmitted data [19].
Decoder design plays a pivotal role in such systems. First, the path restores the host image without any projections. It then retrieves the hidden watermark, which is easy to implement but is susceptible to interference between the host and the watermark. An alternative approach is to use null-space projection, where Q is a projection matrix constructed such that the watermark components are suppressed during reconstruction, thereby improving separability and robustness, albeit at the cost of higher computational complexity. The design of the sensing matrix has further implications on reconstruction stability, noise robustness, and achievable sampling ratios. Structured binary matrices with Fourier-domain sparsity are demonstrated to be highly noise-resilient compared to similar ensembles. In addition, classical theoretical results concerning random circulant or Toeplitz ensembles under $\ell$1-minimization continue to hold. Assuming certain conditions, OMP can also recover sparse supports with high probability [20]. Several practical schemes have been explored in the past that utilize single-iteration reconstruction schemes for missing-data and noise conditions [21]. These schemes include using Principal Component Analysis (PCA) to create CS frameworks that learn observation matrices from natural image libraries, followed by block-wise reconstruction. Thus, matrix design and data modelling will impact both reconstruction performance and computational efficiency [22, 23].
Across this literature, evaluation practices vary widely. Many studies emphasize peak signal-to-noise ratio (PSNR) as the primary measure of reconstruction quality, while underreporting complementary perceptual and watermark-related metrics. Similarly, computational performance and reconstruction quality are not consistently evaluated across different reconstruction algorithms, while runtime performance is inconsistently documented despite its importance for real-time or embedded applications [18, 19].
As a result, there remains a shortage of comprehensive, measurement-domain benchmarks that simultaneously:
A. Compare multiple reconstruction algorithms ($\ell$1, OMP, OMP-PKS).
B. Examine a different decoder architecture (projection-free and null-space QB = 0).
C. Systematically vary the sampling ratio (M/N); and
D. Assess comprehensive performance measures: PSNR, Mean Squared Error (MSE), reconstruction error, and computational time [9-11, 12-17, 18-22].
This paper takes the first step towards bridging this gap by performing a measurement-domain benchmark that assesses three reconstruction algorithms and two decoders in a single standard experimental setup. To summarize some of these developments, Table 1 outlines representative studies related to CS and measurement-domain watermarking. The methodological focus, evaluation metrics, and key findings are described. The limitations of the prior studies are noted, as are the gaps addressed by the present one. This comparative synthesis illuminates that while many studies have improved either reconstruction quality or sensing efficiency, very few scrutinize multiple recovery algorithms and decoder architectures under identical experimental conditions. This research intends to fill this gap.
Table 1. Comparative summary of representative studies on compressive sensing (CS) and measurement-domain watermarking
|
Study |
Domain |
Method |
Key Metrics |
Main Contributions |
Limitations / Gaps |
|
CBMP [12] |
CS recovery |
Constrained backtracking; dynamic sparsity |
PSNR, support accuracy |
Improves support estimation when K is unknown |
Sensitive to tuning; no watermarking context |
|
AIFB [13] |
CS recovery |
Adaptive forward–backward LS |
PSNR, residual norm |
Low error vs. classical greedy methods |
Added LS cost; lacks BER/NC & robustness |
|
Greedy frameworks [14] |
CS recovery |
Enhanced greedy vs. OMP/CoSaMP |
PSNR, runtime |
Better accuracy/efficiency under noise |
Focused on algorithms only; no security layer |
|
Blind sparsity [15] |
CS recovery |
Dichotomous + greedy |
Support accuracy |
Estimates sparsity & channel jointly |
Fragile to noise; no watermarking |
|
Hybrid one-bit CS [16] |
CS + support detection |
Conventional + one-bit cues |
Recovery error |
Robust to noise theoretically |
Limited imaging tests; no watermark metrics |
|
Survey [17] |
CS overview |
Dictionary, block, chaotic CS |
— |
Synthesizes models & methods |
No experimental or protection analysis |
|
Lee [18] |
Acoustics |
OMP for cavitation localization |
Latency |
Real-time feasibility shown |
Domain-specific; no imaging watermarking |
|
Imaging + watermarking [19] |
Imaging |
Adaptive sampling + watermark embedding |
PSNR |
Integrates acquisition & protection |
PSNR-only; lacks BER/NC & robustness |
|
Matrix pairings [20] |
Sensing matrices |
Binary + Fourier, circulant/Toeplitz |
PSNR, robustness |
Noise-resilient structured pairs |
Focused on matrices; no extraction reliability |
|
Single-iteration [21] |
Noisy data |
One-pass tailored recovery |
PSNR |
Efficient for missing data |
Narrow scope; no watermarking or attacks |
|
PCA-based CS [22] |
Imaging CS |
Blockwise PCA learning |
PSNR, efficiency |
Fast high-quality recovery |
Domain-dependent; lacks watermark layer |
|
This study |
Measurement-domain CS watermarking |
Embedding in CMV; two decoder strategies (AB and AF); ℓ1, OMP, OMP-PKS |
PSNR, MSE, reconstruction error, computational time |
Comparative benchmark across three reconstruction algorithms and two decoder strategies |
Limited to image reconstruction and watermark extraction under the evaluated experimental conditions |
This section presents the proposed framework for embedding a digital watermark into the CS measurement process and subsequently extracting it from the reconstructed image. The approach integrates watermarking into the CS acquisition pipeline. It employs three reconstruction algorithms—$\ell$1-minimization, OMP, and OMP-PKS—to evaluate reconstruction quality, MSE, and runtime efficiency across varying M/N.
3.1 Compressive sensing
Let $x \in R^N$ denote the vectorized image. Assume $x=\Psi \theta$, where $\Psi \in R^{N \times N}$ is an orthonormal transform (e.g., a wavelet basis) and $\theta$ is sparse or compressible (i.e., only $K$ << $N$ entries carry most energy). The acquisition uses a sensing matrix $\Phi \in R^{\mathrm{M} \times \mathrm{N}}$ with $M \ll N$, producing measurements.
$\begin{gathered}y=\Phi x+\eta=\Phi \Psi \theta+\eta=A \theta+\eta \\ A=\Phi \Psi\end{gathered}$ (1)
Throughout, M/N denotes the sampling ratio. Practical CS designs seek low mutual coherence between $\Phi$ and $\Psi$, or equivalently, a well-conditioned A; when rows/columns are $\ell$2-normalized, a common coherence surrogate satisfies $0 \leq$ $\mu(\Phi, \Psi) \leq 1$. For many random constructions, accurate recovery is observed once M scales on the order of
$M \gtrsim C K \log (N / K)$ (2)
where, C > 0 is problem-dependent [24].
3.2 Sparse representation via wavelets and prior support
To expose sparsity, an octave-tree DWT is applied to the image (Figure 1(A)), yielding sub-bands {LL, LH, HL, HH} across levels. Coefficients are reordered into a vector (Figure 1(B)) and arranged into row-wise blocks (Figure 1(C)). A hard wavelet shrinkage is used to suppress small-magnitude detail coefficients while retaining salient components. Because the LL sub-band concentrates low-frequency, high-energy content, its level-3 indices (LL3) form a partially known support set $T 0$ that can seed greedy pursuit in OMP-PKS. This prior reduces mis-selections at low M/N and accelerates convergence; caveats for highly textured scenes are examined empirically. The complete DWT-based sparsification and coefficient-reordering workflow is illustrated in Figure 1.
3.3 Watermark embedding in the measurement domain
Let $w \in\{-\alpha,+\alpha\}^L$ be a bipolar watermark of length L (with $\alpha>0$ the embedding strength). After forming $A=\Phi \Psi$, watermarking takes place in the measurement space as
$y_w=A \theta+B w$ (3)
where, $B \in R^{M \times L}$ is a known embedding matrix shared by the encoder and decoder. In transmission, the receiver observes.
$y_v=y_w+n=A \theta+B w+n$ (4)
where, channel perturbation $n$. For compact notation, define the stacked vector $z:=\left[{ }_w^\theta\right]$ and block matrix $H:=[A \mid B] \in$ $R^{M \times(N+L)}$; then from the Eq. (4), the output will be:
$y_v=H_z+n$ (5)
3.4 Reconstruction algorithms
3.4.1 $\ell$1-norm minimization
Sparse recovery proceeds via either the equality-constrained Basis Pursuit (BP),
$\widehat{\theta}=\arg \min _\theta\|\theta\|_1$ s.t. $y=A \theta$ (6)
or its Lagrangian form (BPD/LASSO),
$\hat{\theta}=\arg \min _\theta \frac{1}{2}\|y-\mathrm{A} \theta\|_2^2+\lambda\|\theta\|_1$ (7)
where, $\lambda>0$ and standard stopping criteria (tolerance, max iterations). In our pipeline, BP/BPD is applied either to $y_v$ (Decoder-1) or to transformed measurements $Q y_v$ (Decoder-2).
3.4.2 Orthogonal matching pursuit
OMP is a greedy algorithm derived from matching pursuit [25]. OMP iteratively selects columns of $A$ most correlated with the residual and solves a least-squares problem on the active set. A generic template is:
3.4.3 Orthogonal matching pursuit with partially known support
OMP-PKS extends OMP by seeding the active set with a partially known support $\mathcal{J}_0$—indices that are likely to contain significant coefficients—before the greedy iterations begin [26]. In this work, the prior support is drawn from the LL3 approximation band of a multi-level wavelet pyramid (see Figure 1), whose low-frequency content concentrates much of the image energy. To expose sparsity and make the prior operational, the image is first transformed using an octave-tree DWT (Figure 1(A)); the resulting coefficients are then reordered into a sensing-compatible vector layout (Figure 1(B)), and—when beneficial for streaming/cache locality—blocked row-wise so that each row acts as a sparse vector (Figure 1(C)). A wavelet shrinkage rule (hard/soft) is applied to suppress small-magnitude detail coefficients while retaining salient components; threshold selection follows a fixed per-level or universal policy [27-29]. The indices corresponding to LL3 extracted in Figure 1(A) define $\mathcal{J}_0$ [29].
Given measurements $y_v$ and sensing matrix A, OMP-PKS proceeds as follows: initialize $\mathcal{J} \leftarrow \mathcal{J}_0$; compute the leastsquares estimate on $A_{\mathcal{J}}$ and set the residual $r \leftarrow y_v-A_{\mathcal{J}} \theta_{\mathcal{J}}$. Then iterate the standard OMP steps-(i) select $j=\arg \max _i\left|\left\langle a_i, r\right\rangle\right|$, (ii) update $\mathcal{J} \leftarrow \mathcal{J} \cup\{j\}$, (iii) recompute the restricted least-squares solution, and (iv) refresh the residual until the stopping rule is met (target sparsity $k$, residual threshold $\tau$, or iteration cap). Anchoring the search with $\mathcal{J}_0$ reduces mis-selections, stabilizes recovery at low sampling ratios M/N, and typically cuts runtime by lowering the number of greedy iterations. Highly textured or nonstationary scenes may temper these gains; this behavior is quantified in the experimental section.
3.5 Digital watermarking
To protect content at the acquisition stage, a binary watermark is embedded directly in the CS measurement vector prior to transmission [30]. The pipeline proceeds in three coordinated stages that match the rest of the framework:
$y_w=A \theta+B w$ (8)
where, $\theta$ is the sparse representation of the image, $B \in$ $R^{\mathrm{M} \times \mathrm{L}}$ is a known embedding matrix shared by encoder and decoder, and $w$ is the binary mark.
Figure 2 shows the measurement-domain watermarking model. The watermarked measurements are formed as $y_w= A \theta+B w$. Dimensions are indicated under each block: $y_{\mathrm{w}} \in \mathrm{R}^{\mathrm{M}}, A \in R^{M \times N}, \theta \in R^N, B \in R^{M \times L}, w \in R^L$. Here $A=$ $\Phi \Psi$ (or $A=\Phi$ in the image domain), $\theta$ is sparse in $\Psi$, and $w$ is bipolar with magnitude $\alpha$.
3.6 The proposed methods
The proposed framework embeds a binary watermark in the measurement domain and then reconstructs the host image while enabling reliable watermark extraction. Embedding is performed once at the encoder; extraction is carried out after reconstruction via two complementary decoders. Throughout, $A \in R^{\mathrm{M} \times \mathrm{N}}$ denotes the sensing operator, $x \in R^{\mathrm{N}}$ the (sparse or compressible) image vector, $B \in R^{\mathrm{M} \times \mathrm{L}}$ a known embedding matrix, and $w \in\{-\alpha,+\alpha\}^{\mathrm{L}}$ the bipolar watermark.
3.6.1 Encoder (watermark insertion procedure)
For a given acquisition, the encoder forms the watermarked measurements:
$y_w=A x+B w$ (9)
where, transmits them. At the receiver, channel perturbations may be present; thus, the decoder observes:
$y_v=y_w+n=A x+B w+n$ (10)
For compact notation, define $H:=\left[\begin{array}{ll}A & B\end{array}\right] \in R^{M \times(N+L)}$ and $z:=\left[\frac{x}{w}\right]$. Then
$y_v=H z+n$ (11)
3.6.2 Decoder (Extraction procedure after reconstruction)
Two extraction strategies are considered, as illustrated in Algorithms 1 and 2. The first strategy is denoted as AB (projection-free reconstruction), whereas the second strategy is denoted as AF (null-space reconstruction).
Method 1 (AB)—Projection-free reconstruction (Algorithm 1)
This decoder works directly with $y_v$. A practical scheme is a joint sparse estimation followed by a refinement step:
A. Joint estimate: Solve a coupled problem to estimate $x$ (sparse) and $w$ (binary but modeled as sparse during optimization), e.g.
$(\tilde{x}, \widetilde{w})=\arg \min _{x, w} \frac{1}{2}\left\|y_v-A x-B w\right\|_2^2+\lambda_x\|x\|_1+\lambda_w\|w\|_1$ (12)
B. Watermark decision: Quantize the soft estimate to bipolar symbols.
$\widehat{w}=\alpha \operatorname{sign}(\widetilde{w})$ (13)
C. Signal refinement: Re-estimate $x$ after compensating for the detected watermark.
$\hat{x}=\arg \min _x \frac{1}{2}\left\|y_v-B \widehat{w}-A x\right\|_2^2+\lambda_x\|x\|_1$ (14)
When greedy recovery is desired, the optimization in Eqs. (12)-(14) is replaced by OMP or OMP-PKS steps applied to the corresponding residuals. In OMP-PKS, the active set is warm-started with a partially known support $\mathcal{J}_0$ obtained from the LL3 wavelet sub-band (indices $\mathcal{J}_0=\left\{\gamma_1, \gamma_2, \ldots, \gamma\left|\mathcal{J}_0\right|\right\}$), which stabilizes selection at low sampling ratios. Algorithm 1 summarizes the flow for both OMP-PKS (Part 1) and OMP (Part 2) within Method 1.
|
Algorithm 1. OMP-PKS and OMP procedures for Method 1 (AB) |
|
Inputs: $H$: measurement (sensing) matrix $y_v$: watermarked measurement vector of size $M \times 1$ $\lambda_0$: { } index set of support of $x$ $w$: watermarked image, $w \in\{-\alpha,+\alpha\} L, L$ is the number of bits $T$: known support part $K$: Sparsity rate Procedure: Part 1: Initialize: $t^k=|T|$, iteration $T=$ index of known part, $T=\left\{\gamma_1, \gamma_1, \ldots, \gamma_{|T|}\right\}$ $\Lambda=T$ $Z=\left[\begin{array}{l}x \\ w\end{array}\right]$ $H=\left[\varphi_{\gamma_1}, \varphi_{\gamma_2}, \varphi_{\gamma_3}, \ldots, \varphi_{\gamma_t k}\right]$ $Z_{t^k}=\left(H^{\prime} H\right)^{-1} H^{\prime} y_v$ $a_{t^k}=\langle H Z\rangle$ $r=y_v-H_T\left(H_T^{\dagger} y\right)$, or $r=y_v-a_{t^k}$ Part 2: While: $t \ll K$ $t=t+1$ $G_t=\operatorname{argmax}_{j=[1 N], j \in \Lambda_{t-1}}\left|<r_{t-1} H_j>\right|$ $\Lambda_t=\Lambda_{t-1} \cup G_t$ $H_t=\left\{H_{t-1} \cup G_t\right\}$ $Z_t=\arg \min _x\left\|y-H_{\lambda_t} Z\right\|_2$ $a_t=<H_t Z_t>$ $r_t=y-a_t$ End Outputs: $\hat{Z}=\operatorname{argmin}_x\left\|y_v-H Z\right\|_2$ $\left[\begin{array}{c}\hat{x} \\ \widetilde{w}\end{array}\right]=\hat{Z}$ $\widehat{w}=\alpha^* \operatorname{sgn}\left(\widetilde{w}_i\right)$ $\hat{x}=\operatorname{argmin}_x\left\|\left(y_v-B \hat{w}\right)-A x\right\|_2$ $\Lambda_k=\left\{\lambda_n\right\}, n=1,2, \ldots, k$ |
Method 2 (AF)—Null-space projection (Algorithm 2)
This decoder suppresses the watermark in measurement space prior to recovery. Construct a projection $Q \in R^{(\mathrm{M}-\mathrm{L}) \times \mathrm{M}}$ such that $Q B=0$, for example, by taking an orthonormal basis of the null $\left(B^{\top}\right)$. Applying $Q$ yields transformed measurements $y=Q y_v=Q A x+Q n=: A x+n$, after which $x$ is recovered using the chosen algorithm ($\ell$1, OMP, or OMP-PKS). The watermark can then be re-estimated from the residual in the original measurement space, $w=\alpha \operatorname{sign}\left(B^{\top}\left(y_v-A \hat{x}\right)\right)$ or, equivalently, one may pose the $\ell 1$ refinement on the projected system,
$\hat{x}=\arg \min _x \frac{1}{2}\|\tilde{y}-\tilde{A} x\|_2^2+\lambda_x\|x\|_1$ (15)
Algorithm 2 details the OMP-PKS/OMP procedures under the null-space projection. In both methods, identical stopping rules (target sparsity $k$, residual threshold $\mathcal{J}$, maximum iterations) and matched solver tolerances are used across algorithms to enable fair comparisons of reconstruction quality, watermark reliability, and runtime.
|
Algorithm 2. The OMP with OMP-PKS and OMP algorithms in the second extraction method |
|
Inputs: $A$: measurement (sensing) matrix by $M \times N$ $y_v$: watermarked measurement vector by $M \times 1$ $\tilde{y}$: measurement vector by $M \times 1$ $\lambda_0$: { } index set of support of $x$ $w$: watermarked image, $w \in\{-\alpha,+\alpha\}^L, L$ is the number of bits $T$: known support part $K$: Sparsity rate Procedure: Part 1: Initialize: $t^k=|\mathrm{T}|$, iteration $T=$ index of known part $T=\left\{\gamma_1, \gamma_1, \ldots, \gamma_{|\tau|}\right\}$ $\Lambda=T$ $A=\left[\varphi_{\gamma_1}, \varphi_{\gamma_2}, \varphi_{\gamma_3}, \ldots, \varphi_{\gamma_t k}\right]$ $x_{t^k}=\left(A^{\prime} A\right)^{-1} A^{\prime} \tilde{y}$ $a_{t^k}=\langle A x\rangle$ $r=y-A_\tau\left(A_\tau^{\dagger} \tilde{y}\right)$ $r=\tilde{y}-a_{t^k}$ Part 2: While: $t \ll K$ $t=t+1$ $G_t=\operatorname{argmax}_{j=[1 N], j \notin \Lambda_{t-1}}\left|<r_{t-1} A_j>\right|$ $\Lambda_t=\Lambda_{t-1} \cup G_t$ $A_t=\left\{A_{t-1} \cup G_t\right\}$ $x_{\mathrm{t}}=\arg \min _x\left\|\mathrm{y}-\mathrm{A}_{\lambda_t} x\right\|_2$ $a_t=<A_t x_t>$ $r_t=y-a_t$ End Outputs: $\hat{x}=\operatorname{argmin}_x\|y-A x\|_2$ $\widehat{w}=\left(B^{\prime} B\right)^{-1} B^{\prime}\left(y_v-A \hat{x}\right)$ $\widehat{w}=\alpha^* \operatorname{sgn}\left(\widehat{w_t}\right)$ $\Lambda_k=\left\{\lambda_n\right\}, n=1,2, \ldots, k$ |
This section presents the experimental findings and performance analysis of the proposed watermarking CS framework. Two decoder strategies were examined—projection-free reconstruction (Method 1 (AB)) and null-space projection (Method 2 (AF))—combined with three sparse-recovery algorithms: $\ell$1-norm minimization, OMP, and OMP-PKS. Performance metrics include PSNR, MSE, reconstruction error, and runtime, which are used to assess the performance of the methods.
4.1 Experimental setup
All experiments were conducted on a curated set of grayscale images that span smooth, textured, and edge-rich content (e.g., Lena, Barbara, Cameraman) at 256 × 256 (Figure 3). Watermarks are bipolar and binary, with sizes 16 × 16, 32 × 32, and 64 × 64; the embedding strength $\alpha$ is selected from a predefined grid to explore the fidelity-detectability trade-off. Unless otherwise specified, the sensing operator is $A \in R^{\mathrm{M} \times \mathrm{N}}$ (row-normalized, randomly generated), and the embedding matrix is $B \in R^{\mathrm{M} \times \mathrm{L}}$ (Gaussian with appropriate normalization).
For the second decoder, the projection $Q$ is constructed so that $Q B=0$ using an orthonormal basis of the null $\left(B^{\top}\right)$. Reconstruction is performed with three algorithms—$\ell$1 minimization, OMP, and OMP-PKS (warm-started from LL3 indices)—under two extraction paths: (i) projection-free and (ii) null-space projection. Performance is reported as a function of the sampling ratio M/N, which was varied from 0.156 to 0.839 using the discrete sampling ratios listed in Table 2.
Table 2. Data, signals, and watermark configuration
|
Category |
Parameter |
Setting |
|
Dataset |
Host image |
Lena, Barbara, and Cameraman (256 × 256) |
|
Dataset |
Sparsifying basis ($\Psi$) |
3-level wavelet; LL3 used for prior support |
|
Watermark |
Type/alphabet |
Binary bipolar (w ∈ {-$\alpha$, +$\alpha$}L) |
|
Watermark |
Size (L) |
16 × 16, 32 × 32, and 64 × 64 |
|
Watermark |
Embedding strength ($\alpha$) |
(final $\alpha$ range (-5.0,+5.0)) |
|
Sampling |
Ratio (M/N) |
0.156–0.839 (discrete sampling ratios) |
To facilitate rigorous appraisal and reproducibility, the study summarizes all key experimental variables and protocol details in Tables 2 and 3. Table 2 specifies the data domain (image set and resolutions), the sparsifying basis, the watermark design (alphabet and size L), the embedding strength $\alpha$, and the standard sampling grid M/N used across all methods. Table 3 details the sensing and embedding operators (A, B), the null-space projector Q for the second decoder; the following aspects are considered: reconstruction algorithms, evaluation metrics, and hardware configuration. Unless otherwise stated, results reported later are obtained using these settings uniformly. The benchmark images and watermark samples used in this study are illustrated in Figure 3. The selected images represent different levels of texture, contrast, and structural complexity, providing a consistent basis for evaluating the reconstruction performance of the methods under consideration.
Table 3. Measurement, algorithms, decoders, and evaluation metrics
|
Category |
Parameter |
Setting |
|
Measurement |
Sensing matrix (A) |
Random Gaussian matrix |
|
Measurement |
Embedding matrix (B) |
Gaussian random matrix |
|
Measurement |
Null-space projector (Q) |
Constructed to satisfy QB = 0 for the null-space decoder |
|
Reconstruction |
Algorithms |
$\ell$1-norm minimization, OMP, and OMP-PKS |
|
Reconstruction |
OMP-PKS prior support |
Partially known support obtained from the LL3 wavelet sub-band |
|
Decoders |
Extraction strategies |
Projection-free (AB) and null-space projection (AF) |
|
Evaluation |
Reconstruction quality |
PSNR (dB) |
|
Evaluation |
Reconstruction error |
MSE and reconstruction error |
|
Evaluation |
Computational efficiency |
Runtime (s) |
|
Sampling |
Sampling ratio (M/N) |
0.15625–0.83984375 (discrete sampling ratios) |
Note: orthogonal matching pursuit (OMP); OMP with partially known support (OMP-PKS); peak signal-to-noise ratio (PSNR); Mean Squared Error (MSE).
Table 4. Hardware configuration
|
Parameter |
Specification |
|
CPU |
11th Gen Intel(R) Core(TM) i7-11850H @ 2.50GHz (2.50 GHz) |
|
RAM |
32 GB |
|
GPU |
NVIDIA GeForce RTX, 16 GB |
|
Storage |
512 GB HDD |
|
Operating System |
Windows 11 Pro |
For each configuration, reconstruction performance was assessed by PSNR, MSE, reconstruction error, and runtime. Computational efficiency was evaluated based on the recorded runtime of each method. All experiments were performed using the hardware and software configuration reported in Table 4.
4.2 Quantitative assessment of reconstruction quality under different sampling levels
The performance in reconstruction of the three sparse recovery algorithms—$\ell$1-norm minimization, OMP and OMP-PKS—is taken into account over the investigated sampling-ratio interval for the 256 × 256 gray images. Three typical images (Barbara, Cameraman and Lena). Every host image includes consideration of three watermark sizes (16 × 16, 32 × 32, 64 × 64). The PSNR, MSE, reconstruction error and runtime results are presented in Figures 4-12. This setting is capable of examining the reconstruction behavior of the three algorithms on different characteristics of images and sizes of the watermark under the same experimental framework.
The outcomes of experiments conducted with watermark sizes of 16 × 16, 32 × 32, and 64 × 64 on the Barbara image are shown in Figures 4, 5, and 6, respectively. As the sampling ratio M/N increases, the reconstruction quality increases, followed by a relatively flat region, as seen in the PSNR curves. Across the configurations we have studied, OMP-PKS enters the high-quality reconstruction region at lower M/N ratios than OMP and $\ell$1-norm minimization. As the M/N increases, the corresponding MSE and reconstruction error curves decrease, which is consistent with the earlier increase in PSNR. The runtime graphs also show an increase in computational cost with M/N, but the rate of increase is different for the reconstruction algorithms.
The same evaluation was performed for the Cameraman image, with the results for watermark sizes of 16 × 16, 32 × 32, and 64 × 64 shown in Figures 7, 8, and 9, respectively. The PSNR results again demonstrate a clear dependence of reconstruction quality on M/N. OMP-PKS generally reaches its stable reconstruction region earlier than the other methods, whereas $\ell$1-norm minimization requires a higher M/N to reach its corresponding stable region. The MSE and error curves provide complementary evidence, showing a reduction in reconstruction error as additional measurements become available. The runtime plots further demonstrate that increasing M/N increases the computational requirements of the reconstruction process.
The results of watermarks of sizes 16 × 16, 32 × 32, and 64 × 64 for the Lena image are shown in Figures 10, 11, and 12, respectively. The findings show a similar general association between M/N and reconstruction quality, while providing the clearest numerical evidence of the advantage obtained by OMP-PKS. The PSNR attained by OMP-PKS when the Lena 256 × 256 image has a 64 × 64 watermark is 36.855 dB at M/N = 0.313 for both decoding methods. This PSNR value at M/N = 0.352 and 0.450 indicates that a stable, high-fidelity reconstruction region is achieved at such a low M/N. The PKS obtained from the LL3 wavelet sub-band helps in finding the dominant sparse coefficients, thus reducing the number of measurements required for high-quality reconstruction.
OMP needs a larger M/N to achieve the equivalent degree of stability. The PSNR value for the Lena 256 × 256 image, which is being watermarked with a 64 × 64 image by the OMP decoding strategy, is observed to be 29.885 dB. At M/N = 0.684, PSNRs of 29.682 dB and 29.885 dB are obtained, respectively. The PSNR improvement will not be a linear function of the M/N as the sampling ratio increases within the convergence region.
The $\ell$1-norm minimization technique does result in a smoother improvement in the quality of the reconstruction. The values show that the MSE of the Lena image increases with an increase in the size of the watermarked image. As a result, $\ell$1-norm minimization compared with OMP-PKS and OMP demands a significantly larger number of measurements to achieve a comparable reconstruction-quality level. These differences can be seen in the PSNR, MSE and error curves shown in Figures 4-12.
The numerical results for the representative Lena 256 × 256 image with a 64 × 64 watermark further illustrate the relationship between reconstruction quality and computational cost. OMP-PKS achieves 36.855 dB at M/N = 0.313, with runtimes of 1.537 × 10² s and 2.452 × 10² s for the two decoding strategies, respectively. OMP reaches approximately 29.885 dB at M/N = 0.528, with runtimes of 2.119 × 10² s and 2.115 × 10² s, whereas $\ell$1-norm minimization reaches 29.885 dB at M/N = 0.801, with runtimes of 7.622 × 10² s and 7.576 × 10² s. These results demonstrate that the higher reconstruction fidelity achieved by OMP-PKS is obtained at a considerably lower M/N than that required by the other two methods.
Across the nine experimental configurations shown in Figures 4-12, the detailed curves vary according to the texture, edge content, and watermark size of the host image. Nevertheless, the overall behavior remains consistent: increasing M/N generally improves reconstruction quality and reduces MSE and reconstruction error until a stable region is reached. The watermark size also affects the detailed reconstruction behavior, while the host-image content influences the convergence characteristics of the algorithms. Among the investigated methods, OMP-PKS provides the most favorable reconstruction behavior at relatively low M/N ratios, while OMP offers an intermediate solution and $\ell$1-norm minimization generally requires a higher M/N to achieve comparable reconstruction quality. These results demonstrate the effectiveness of incorporating partial support information into compressive-sensing reconstruction for watermarking applications.
The performance of the $\ell$1-norm minimization, OMP, and OMP-PKS reconstruction was tested on Barbara, Cameraman, and Lena images of size 256 × 256 with watermark sizes of 16 × 16, 32 × 32, and 64 × 64. The shifts in PSNR, MSE, reconstruction error, and runtime (for one frame) are shown in Figures 4-12, using the PSNR curve over the investigated range of M/N. As the ratio of M/N is increased, the overall quality of reconstruction improves, although the algorithm convergence patterns differ.
By utilizing the PKS of the LL3 wavelet sub-band, OMP-PKS achieves a high-fidelity reconstruction region at lower M/N. The 36.855 dB level reached by OMP-PKS at M/N = 0.313, in the representative Lena 256 × 256 with a 64 × 64 watermark, is significantly higher than the level of 29.885 dB reached by OMP at M/N = 0.528 and $\ell$1-norm minimization at M/N = 0.801. Table 5 summarizes the PSNR results, as obtained consequently.
The results demonstrate that OMP-PKS provides the highest reconstruction quality at a substantially lower M/N than $\ell$1-norm minimization and OMP, confirming its effectiveness under undersampling conditions.
Figure 4. Reconstruction performance of the three algorithms for Barbara 256 × 256 with a 16 × 16 watermark: (A) peak signal-to-noise ratio (PSNR), (B) Mean Squared Error (MSE), (C) reconstruction error, and (D) runtime versus M/N
Figure 5. Reconstruction performance of the three algorithms for Barbara 256 × 256 with a 32 × 32 watermark: (A) peak signal-to-noise ratio (PSNR), (B) Mean Squared Error (MSE), (C) reconstruction error, and (D) runtime versus M/N
This study presented a compressive-sensing-based digital watermarking framework in which watermark information is embedded in the compressed measurement domain and recovered using two decoding strategies: AB and AF. Three sparse reconstruction algorithms—$\ell$1-norm minimization, OMP, and OMP-PKS—were evaluated under the same experimental conditions.
The results show that OMP-PKS achieves better reconstruction performance under undersampling. It achieved a PSNR of 36.855 dB at (M/N = 0.313), while OMP and $\ell$1-norm minimization achieved about 29.885 dB at (M/N = 0.528) and (M/N = 0.801). OMP-PKS further exhibited stable reconstruction quality across the evaluated M/N range due to the advantage presented by the utilization of Partially Known Support (PKS) derived from the LL3 wavelet sub-band.
According to the computational results, OMP-PKS achieves high reconstruction fidelity with fewer measurements and at a competitive execution time relative to the rest of the considered reconstruction methods. The observed balance among reconstruction quality, sampling efficiency, and computational cost is primarily attributed to the use of PKS information in OMP-PKS, while the two decoding strategies provide complementary reconstruction paths. In conclusion, OMP-PKS provides an efficient sparse reconstruction scheme for compressive-sensing-based watermarking, especially under limited-measurement conditions where high reconstruction fidelity is required.
Future work will leverage a wider variety of images, adaptive watermark embedding, and robustness assessment against common signal-processing and geometric attacks, such as JPEG compression, additive white Gaussian noise (AWGN), blur, cropping, and rotation.
The project's objectives will also include studying reconstruction approaches based on adaptive support selection and hybrid learning to improve the generalization and robustness of the proposed framework.
The authors acknowledge the academic support provided by Hasan Kalyoncu University and the University of Mosul during the preparation of this research.
[1] Baraniuk, R.G. (2007). Compressive sensing [lecture notes]. IEEE Signal Processing Magazine, 24(4): 118-121. https://doi.org/10.1109/MSP.2007.4286571
[2] Jacques, L. (2010). A short note on compressed sensing with partially known signal support. Signal Processing, 90(12): 3308-3312. https://doi.org/10.1016/j.sigpro.2010.05.025
[3] Karah Bash, A.A.H., Kayhan, S.K. (2015). Watermarked compressive sensing measurements reconstructed by the greedy algorithms. International Journal of Computer Theory and Engineering, 7(3): 219-222. https://doi.org/10.7763/IJCTE.2015.V7.960
[4] Yamaç, M., Dikici, Ç., Sankur, B. (2013). Robust watermarking of compressive sensed measurements under impulsive and Gaussian attacks. In 21st European Signal Processing Conference (EUSIPCO), Marrakech, Morocco, pp. 1-5. https://ieeexplore.ieee.org/abstract/document/6811772.
[5] Lin, J., Dong, L., Fan, T., et al. (2020). Compressive sensing method for EUV source optimization using different bases. In Extreme Ultraviolet (EUV) Lithography XI, 11323: 551-557. https://doi.org/10.1117/12.2551897
[6] Wang, Z., Jiang, Y., Chen, S. (2023). Image parallel block compressive sensing scheme using DFT measurement matrix. Multimedia Tools and Applications, 82(14): 21561-21583. https://doi.org/10.1007/s11042-022-14176-1
[7] Shaik, C., RajaA, R., Kalapala, S.S., Nrusimhi, C.S.L., Kolusu, S.N.D.D., Polasi, P.K. (2022). A comprehensive review on compressive sensing. In 2022 International Conference on Applied Artificial Intelligence and Computing (ICAAIC), Salem, India, pp. 1723-1727. https://doi.org/10.1109/ICAAIC53929.2022.9792767
[8] Sinha, M.K., Kannu, A.P. (2024). Generalized sparse regression codes for short block lengths. IEEE Transactions on Communications, 72(5): 2536-2551. https://doi.org/10.1109/TCOMM.2024.3354205
[9] Wang, W., Brugiapaglia, S. (2024). Compressive Fourier collocation methods for high-dimensional diffusion equations with periodic boundary conditions. IMA Journal of Numerical Analysis, 44(6): 3780-3814. https://doi.org/10.1093/imanum/drad102
[10] Li, F., Triggs, C.M., Giurcăneanu, C.D. (2023). On the selection of predictors by using greedy algorithms and information-theoretic criteria. Australian & New Zealand Journal of Statistics, 65(2): 77-100. https://doi.org/10.1111/anzs.12387
[11] El Mahdaoui, A., Ouahabi, A., Moulay, M.S. (2022). Image denoising using a compressive sensing approach based on regularization constraints. Sensors, 22(6): 2199. https://doi.org/10.3390/s22062199
[12] Bi, X., Leng, L., Kim, C., Liu, X., Du, Y., Liu, F. (2021). Constrained backtracking matching pursuit algorithm for image reconstruction in compressed sensing. Applied Sciences, 11(4): 1-14. https://doi.org/10.3390/app11041435
[13] Aziz, A., Osamy, W., Khedr, A.M., Salim, A. (2022). Iterative selection and correction-based adaptive greedy algorithm for compressive sensing reconstruction. Journal of King Saud University - Computer and Information Sciences, 34(3): 892-900. https://doi.org/10.1016/j.jksuci.2020.03.010
[14] Jia, L. (2020). Joint Bayesian and greedy recovery for compressive sensing. Chinese Journal of Electronics, 29(5): 952-958. https://doi.org/10.1049/cje.2020.08.010
[15] Si, W.J., Liu, Q., Deng, Z.A. (2021). Adaptive reconstruction algorithm based on compressed sensing broadband receiver. Wireless Communications and Mobile Computing, 2021(1): 6673235. https://doi.org/10.1155/2021/6673235
[16] Tai, C.L., Hsieh, S.H., Lu, C.S. (2020). Greedy algorithms for hybrid compressed sensing. IEEE Signal Processing Letters, 27: 2059-2063. https://doi.org/10.1109/LSP.2020.3037732
[17] Li, L., Fang, Y., Liu, L., Peng, H., Kurths, J., Yang, Y. (2020). Overview of compressed sensing: Sensing model, reconstruction algorithm, and its applications. Applied Sciences, 10(17): 1-19. https://doi.org/10.3390/app10175909
[18] Lee, J.H. (2020). Acoustic localization of incipient cavitation in marine propeller using greedy-type compressive sensing. Ocean Engineering, 197: 106894. https://doi.org/10.1016/j.oceaneng.2019.106894
[19] Tian, P., Xu, D., Xu, W. (2021). Digital watermarking algorithm for multi-sampling compressed sensing in measurement domain. Journal of Physics: Conference Series, 1744(3): 032001. https://doi.org/10.1088/1742-6596/1744/3/032001
[20] Markarian, H., Ghofrani, S. (2020). Randomness, coherence and noise robustness in compressive sensing. Signal Processing and Renewable Energy, 4(1): 63-76.
[21] Shen, Y., Hu, R. (2019). Sparsity and incoherence in orthogonal matching pursuit. Multidimensional Systems and Signal Processing, 30(1): 257-274. https://doi.org/10.1007/s11045-018-0554-8
[22] Andráš, I., Dolinský, P., Michaeli, L., Šaliga, J. (2018). Sparse signal acquisition via compressed sensing and principal component analysis. Measurement Science Review, 18(5): 175-182. https://doi.org/10.1515/msr-2018-0025
[23] Kumar, S.S., Ramachandran, P. (2022). Review on compressive sensing algorithms for ECG signal for IoT based deep learning framework. Applied Sciences, 12(16): 8368. https://doi.org/10.3390/app12168368
[24] Berk, A., Brugiapaglia, S., Joshi, B., Plan, Y., Scott, M., Yilmaz, Ö. (2022). A coherence parameter characterizing generative compressed sensing with Fourier measurements. IEEE Journal on Selected Areas in Information Theory, 3(3): 502-512. https://doi.org/10.1109/JSAIT.2022.3220196
[25] Li, Z., Zheng, X., Chen, G., Wei, Y., Lu, K. (2023). A matching pursuit algorithm for sparse signal reconstruction based on Jaccard coefficient and backtracking. Circuits, Systems, and Signal Processing, 42: 6210-6227. https://doi.org/10.1007/s00034-023-02396-1
[26] Melek, M., Khattab, A. (2021). ECG compression using wavelet-based compressed sensing with prior support information. Biomedical Signal Processing and Control, 68: 102786. https://doi.org/10.1016/j.bspc.2021.102786
[27] Ch, M.M.I., Riaz, M.M., Iltaf, N., Ghafoor, A., Saghir, N.J. (2023). Shift-invariant discrete wavelet transform-based sparse fusion of medical images. Signal, Image and Video Processing, 17(4): 881-889. https://doi.org/10.1007/s11760-021-01998-z
[28] Vaidya, S.P., Mouli, P.C. (2024). Robust digital color image watermarking based on compressive sensing and DWT. Multimedia Tools and Applications, 83(2): 3357-3371. https://doi.org/10.1007/s11042-023-15349-2
[29] Heckel, R., Soltanolkotabi, M. (2020). Compressive sensing with untrained neural networks: Gradient descent finds a smooth approximation. In International Conference on Machine Learning, PMLR, pp. 4149-4158.
[30] Pourhadi, A., Mahdavi-Nasab, H. (2020). A robust digital image watermarking scheme based on bat algorithm optimization and SURF detector in SWT domain. Multimedia Tools and Applications, 79(29-30): 21653-21677. https://doi.org/10.1007/s11042-020-08960-0