🔢 mathematics

A Dimension-Keeping Semi-Tensor Product Framework for Compressed Sensing

This paper proposes a novel Dimension-Keeping Semi-Tensor Product Compressed Sensing (DK-STP-CS) framework that leverages intra-group correlations and inter-group incoherence to design an enhanced sensing matrix, achieving superior noise suppression, visual fidelity, and reconstruction performance compared to traditional methods in image processing tasks.

Original authors: Qi Qi, Abdelhamid Tayebi, Daizhan Cheng, Jun-e Feng

Published 2026-03-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Qi Qi, Abdelhamid Tayebi, Daizhan Cheng, Jun-e Feng

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Too Much Data" Traffic Jam

Imagine you are trying to send a high-definition movie to a friend. In the old days (the Nyquist-Shannon era), you had to send every single frame and every single pixel to make sure the picture looked right. If the movie is huge, this takes forever and clogs up the internet.

Compressed Sensing (CS) is like a clever trick that says: "Wait! You don't need to send the whole movie. Most of the movie is just blue sky or black space. You only need to send the important parts (the actors, the action) and the computer can figure out the rest."

However, there's a catch. To make this trick work, the "mailman" (the measurement matrix) has to be very random and chaotic. If the mailman is too organized, the computer gets confused and the picture comes out blurry or full of static (noise).

The New Solution: The "Group Hug" Strategy (DK-STP-CS)

The authors of this paper, Qi Qi and his team, came up with a new way to organize the mailman. They call it DK-STP-CS.

Here is how it works, using a simple analogy:

1. The Old Way: The Solo Runners

In traditional Compressed Sensing, imagine you have a team of 100 runners (pixels) trying to cross a finish line. The coach (the computer) asks them to run one by one, completely randomly. The coach has to remember exactly who ran when. It's chaotic, and if a few runners trip (noise), the coach gets confused about the final race time.

2. The New Way: The Group Huddle

The DK-STP method changes the rules. Instead of asking runners to go solo, the coach groups them into teams of, say, 2 or 3.

The Trick: The coach asks the team to huddle up, hold hands, and report their combined speed as a single number.
The Magic: Because neighbors in an image (like pixels in a photo of a cat's fur) usually look very similar, adding them together doesn't lose much information. It's like asking a group of friends, "What's the average height of your group?" instead of measuring everyone individually.

This is the "Dimension-Keeping" part. The system keeps the "dimension" (the size of the data) manageable but changes how the data is grouped.

Why is this better? (The Three Superpowers)

The paper proves that this "Group Huddle" method has three major advantages:

1. The Noise Filter (Static Reduction)
Imagine you are listening to a radio station with a lot of static.

Old Method: If one static burst hits a specific frequency, that part of the song sounds terrible.
New Method: Because the new method groups neighbors together, a little bit of static on one pixel gets "averaged out" by its neighbors. It's like if one person in a choir sings slightly off-key, but the whole group sings together, the mistake is hidden. The result is a much clearer, smoother picture.

2. The Storage Saver (Fitting a Elephant in a Suitcase)
Usually, to send a compressed image, you need to send a huge "key" (the measurement matrix) so the receiver knows how to unlock the picture. This key takes up a lot of space.

The DK-STP Trick: Because the new method groups the data, the "key" needed to unlock it is much smaller. It's like sending a tiny instruction manual instead of a giant encyclopedia. This saves bandwidth and storage space.

3. The "Smoothness" Guarantee
The paper shows that while this method might blur the very sharpest edges (like the edge of a razor blade) slightly, it makes the rest of the image look incredibly smooth and natural. For most photos (like a face or a landscape), this trade-off is worth it because the image looks less "grainy" and more like a real photo.

The Results: What the Experiments Showed

The researchers tested this on famous test images (like "Pepper" and "Baboon").

Visuals: When they reconstructed the images, the new method (DK-STP) looked much cleaner than the old methods. The "Pepper" image looked less like a blurry mess and more like a real pepper.
Numbers: They used a score called PSNR (Peak Signal-to-Noise Ratio). Think of this as a "Clarity Score." The higher the score, the better the picture.
- The new method consistently got higher scores than the old methods, even when the signal was noisy or the data was very compressed.
Robustness: Even when they added "noise" (like static on a TV) to the data before sending it, the new method recovered the image much better than the others.

The Bottom Line

Think of DK-STP-CS as a smarter way to pack a suitcase.

Old way: You try to fit every single item in the house into the suitcase, but you have to pack them randomly. It's messy, and if you lose one item, you can't find it.
New way: You group similar items together (socks with socks, shirts with shirts). You compress the groups. If you lose a little bit of info about one sock, the fact that you know the "sock group" is there helps you reconstruct the whole picture perfectly.

In short: This paper introduces a mathematical trick that groups neighboring data points together before compressing them. This makes the resulting images clearer, less noisy, and easier to store, especially when internet connections are slow or data is corrupted.

1. Problem Statement

Compressed Sensing (CS) allows for the reconstruction of sparse signals from sub-Nyquist measurements, addressing the storage and transmission bottlenecks of modern digital systems. However, conventional CS faces two primary challenges:

Measurement Matrix Storage: Traditional CS requires transmitting a large measurement matrix ( $A \in \mathbb{R}^{m \times n}$ where $m \ll n$ ), which consumes significant bandwidth and memory.
Reconstruction Quality vs. Noise: While random matrices satisfy the Restricted Isometry Property (RIP), they often introduce noise artifacts during image reconstruction, particularly in regions with high-frequency details or under noisy transmission conditions.
Sparsity Constraints: Standard CS relies heavily on the incoherence of matrix columns. The paper seeks to leverage intra-group correlations (correlations within specific groups of signal components) while maintaining inter-group incoherence to improve reconstruction without sacrificing the compression ratio.

2. Methodology: DK-STP-CS

The authors propose a novel framework called Dimension-Keeping Semi-Tensor Product Compressed Sensing (DK-STP-CS). The core innovation lies in replacing the standard matrix-vector multiplication with a specialized operation.

A. Dimension-Keeping Semi-Tensor Product (DK-STP)

The method utilizes a variation of the Semi-Tensor Product (STP).

Standard STP: Uses Kronecker products with identity matrices to handle dimension mismatches.
DK-STP: Replaces the identity matrix with a row vector of ones ( $\mathbf{1}^T$ ) and applies a weighting factor ( $\varepsilon = \frac{1}{\sqrt{\gamma}}\mathbf{1}$ ).
Operation: Given a signal vector $x$ of dimension $p$ and a measurement matrix $A$ of dimension $m \times n$ , the DK-STP operation groups consecutive elements of $x$ (where $\gamma = p/n$ ) and sums them.
$y = A \ltimes x = (A \otimes \varepsilon^T_\gamma) x = \frac{1}{\sqrt{\gamma}} A x_\gamma$
Here, $x_\gamma$ represents a vector where adjacent $\gamma$ elements of the original signal are summed. This effectively reduces the dimensionality of the signal being processed by the matrix $A$ while keeping the output dimension $m$ consistent with the measurement.

B. Theoretical Framework

The paper establishes the mathematical validity of DK-STP-CS through three key properties:

Spark and Uniqueness: The authors prove that if the original matrix $A$ satisfies the Spark condition ( $k < \text{spark}(A)/2$ ), the DK-STP system guarantees a unique solution for the grouped signal $x_\gamma$ . While the specific distribution of individual pixels within a group is lost, the sum is uniquely recoverable.
Intra-Group Correlation: The method intentionally introduces correlation between adjacent elements (intra-group) while ensuring the groups themselves remain incoherent (inter-group). This structure is shown to be beneficial for smooth signals like images.
Restricted Isometry Property (RIP): The paper proves that if $A$ satisfies the RIP of order $2k$ , the DK-STP system also satisfies the RIP, ensuring that exact recovery via $L_1$ optimization (Basis Pursuit) is possible.
Error Analysis: The total reconstruction error is decomposed into three components:
- Original Signal Error: Deviation of adjacent pixels from their mean (small for natural images).
- Compressed Sensing Error: Error in recovering the sum values (reduced due to higher effective sampling of the sum).
- Distribution Error: Error introduced when distributing the recovered sum back to individual pixels (mitigated by the smoothness of natural images).

C. Algorithm

The reconstruction pipeline involves:

Grouping and summing signal components to form $x_\gamma$ .
Solving the $L_1$ minimization problem: $\min \|z\|_1$ subject to $Az = y$.
Reshaping the result and distributing the sum values back to the original dimensions (e.g., via equalization).

3. Key Contributions

Novel Measurement Design: Introduction of the DK-STP operation, which allows for the transmission of a smaller measurement matrix ( $A \in \mathbb{R}^{m \times n/\gamma}$ ) while achieving the same compression ratio as traditional CS.
Theoretical Guarantees: Rigorous proofs demonstrating that DK-STP-CS maintains RIP and Spark conditions, ensuring signal recovery uniqueness and stability.
Noise Suppression Mechanism: By reconstructing grouped sums rather than individual pixels, the method inherently suppresses high-frequency noise, leading to smoother image textures.
Comprehensive Validation: Extensive experiments comparing DK-STP-CS against standard CS and STP-CS across various metrics (PSNR, MSE), sampling rates, and noise levels.

4. Experimental Results

The authors evaluated the method using standard grayscale images (Barbara, Pepper, Baboon) with a compression ratio of 0.5 (50% sampling).

Visual Quality: DK-STP-CS produced significantly smoother images with reduced granular noise compared to CS and STP-CS. While edge sharpness was slightly compromised (aliasing), the overall visual fidelity was superior.
Quantitative Performance (PSNR):
- Barbara: DK-STP-CS achieved 34.36 dB vs. 32.02 dB (CS) and 30.63 dB (STP-CS).
- Pepper: DK-STP-CS achieved 31.25 dB vs. 29.43 dB (CS).
- Baboon: DK-STP-CS achieved 27.21 dB vs. 24.33 dB (CS).
- Conclusion: DK-STP-CS consistently outperformed baselines by 1.8 to 2.8 dB.
Robustness to Noise: Under Gaussian noise interference ( $D[\sigma]=0.001$ ), DK-STP-CS maintained the highest PSNR values, demonstrating superior noise resilience.
Sampling Rate Sensitivity: The performance gap between DK-STP-CS and baselines widened as the sampling rate increased, with the most significant gains observed at higher sampling rates (0.4–0.5).
Matrix Independence: The method performed robustly across Gaussian, Bernoulli, and Toeplitz measurement matrices, though Gaussian and Bernoulli matrices yielded the most stable results.

5. Significance and Impact

Resource Efficiency: By reducing the size of the measurement matrix required for transmission, DK-STP-CS lowers bandwidth costs and storage requirements, making it highly suitable for resource-constrained environments (e.g., sensor networks, IoT).
Enhanced Image Fidelity: The method offers a practical trade-off where slight blurring of fine edges is exchanged for significant noise reduction and better preservation of global structural integrity.
Practical Applicability: The framework provides a mathematically sound alternative to standard random matrix CS, particularly for applications involving natural images where local pixel correlation is high.
Future Directions: The paper suggests future work on sparse tensor architectures and machine learning-based adaptive generation of measurement matrices to further optimize group correlations.

In summary, the paper presents a mathematically rigorous and experimentally validated advancement in Compressed Sensing that leverages dimension-keeping semi-tensor products to achieve superior noise suppression and reconstruction quality while reducing transmission overhead.