TL;DR
This paper tackles the trade-off between storage efficiency and reconstruction accuracy in compressed sensing (CS). They propose a novel method to construct "structured random" measurement matrices by combining combinatorial designs with orthonormalized random matrices. These new matrices offer a better balance, achieving good reconstruction performance for both 1D signals and 2D images while requiring less storage and being more hardware-friendly than traditional random matrices.
What Problem Does This Paper Address?
Compressed sensing (CS) allows us to acquire signals using fewer measurements than traditional methods, but this comes with challenges. Random measurement matrices, while effective for reconstruction, are memory-intensive and difficult to implement in hardware. On the other hand, deterministic matrices are more efficient but often suffer from significant reconstruction errors. This paper aims to bridge this gap by developing measurement matrices that are both efficient in terms of storage and hardware implementation and robust in their reconstruction capabilities, specifically within the context of Semi-Tensor Product Compressed Sensing (STP-CS).
Methods
The core of this work lies in the construction of "structured random" measurement matrices. This is achieved through an "embedding operation" that combines two "seed matrices":
- Incidence Matrix from Combinatorial Designs: The paper leverages the properties of symmetric balanced incomplete block designs (SBIBDs), specifically the incidence matrix of a projective plane of order q (denoted as M). These matrices have inherent structure derived from combinatorial mathematics.
- Gram-Schmidt Orthonormalization of Random Matrices: A random matrix (C) is generated and then orthonormalized using the Gram-Schmidt process. This ensures the random component has desirable properties for coherence reduction.
The structured random matrix (Φ) is then formed by embedding the orthonormalized random matrix (C) into the incidence matrix (M) using a specific operation (denoted by ⊙). This approach aims to inherit the structural advantages of combinatorial designs while retaining the flexibility and good statistical properties of random matrices. The authors then propose a new STP-CS model that utilizes these structured random matrices.
Datasets
The paper does not introduce new datasets. Instead, it uses standard techniques for generating synthetic sparse signals and employs publicly available images for testing the reconstruction of 2D data. The specific images used are mentioned as being randomly selected from the MSCOCO dataset.
Key Insights and Ideas
- Bridging the Gap: The paper successfully demonstrates a method to create measurement matrices that offer a compelling compromise between the storage efficiency of deterministic matrices and the reconstruction accuracy of random matrices.
- Combinatorial Design Power: Utilizing incidence matrices from combinatorial designs (like projective planes) provides a structured foundation that can be exploited for efficient matrix construction.
- Orthonormalization is Key: Applying Gram-Schmidt orthonormalization to the random component of the matrix is crucial for reducing coherence and improving reconstruction performance.
- STP-CS Advantage: The proposed matrices are shown to be particularly effective within the Semi-Tensor Product Compressed Sensing (STP-CS) framework, which itself offers advantages in terms of measurement matrix column count and storage.
- Structured Randomness: The concept of "structured random" matrices is highlighted as a promising direction for future research in compressed sensing.
Key Results
The paper presents experimental results demonstrating the effectiveness of their proposed structured random measurement matrices.
- 1D Signal Reconstruction: For 1D signals, the proposed matrices (specifically, combinations of the incidence matrix M and orthonormalized matrices C from Gaussian, Bernoulli, and Toeplitz distributions) showed superior or comparable perfect recovery percentages compared to standard Gaussian, Bernoulli, and Toeplitz matrices under both Orthogonal Matching Pursuit (OMP) and Basis Pursuit (BP) algorithms.
- 2D Image Reconstruction: For 2D images, the proposed matrices achieved comparable or better Peak Signal-to-Noise Ratios (PSNRs) than Gaussian, Bernoulli, and Toeplitz matrices across various reconstruction algorithms (OMP, BP, IST, SP). Crucially, the CPU times for reconstruction were not longer than those of the compared matrices, indicating efficiency.
- Noise Robustness: The matrices also demonstrated robust performance in the presence of both data-domain and measurement-domain noise, with reconstruction SNR comparable to or better than standard matrices.
Limitations and Future Work
- Specific Combinatorial Designs: The paper focuses on a particular type of combinatorial design (SBIBD derived from projective planes). Exploring other combinatorial designs could yield further improvements.
- Random Matrix Generation: While Gram-Schmidt orthonormalization is applied, the initial random matrix generation could be further investigated for its impact on performance.
- Generalization: While the paper shows promise for 1D signals and 2D images, further exploration into other signal types and more complex data structures might be beneficial.
- Hardware Implementation: While the matrices are presented as more hardware-friendly due to their structure and reduced storage, a detailed hardware implementation study is not provided.
The authors suggest future work could involve exploring the "special structure of the incidence matrix" and further optimizing the "Gram-Schmidt orthonormalization of random matrices" to enhance performance.
Summary updated