TL;DR
This paper introduces a novel method for learning "circulant sensing kernels" that are more efficient and effective for compressive sensing (CS) than traditional random sensing matrices. By optimizing these kernels, the authors demonstrate improved signal and image recovery, especially for real-world data.
What Problem Does This Paper Address?
Compressive sensing (CS) allows us to acquire signals using fewer measurements than traditional methods, but this requires a carefully designed "sensing matrix." In many practical applications, especially those involving physical implementations like optical systems, the sensing matrix needs to be easily realizable. Circulant matrices are attractive because they correspond to discrete convolutions, which are computationally efficient and can be physically implemented. However, random circulant matrices, while effective, are not optimal. This paper addresses the challenge of learning optimized circulant sensing matrices that can significantly improve the performance of CS recovery, particularly for image and video data, by going beyond the limitations of previous patch-based learning approaches.
Methods
The core of this work lies in learning optimal circulant sensing matrices and dictionaries. The authors propose to optimize the sensing matrix $\Phi$ and the dictionary $\Psi$ together, a concept they call "coupled learning."
For 1D signals, they formulate an optimization problem to learn a circulant matrix $C$ by minimizing the difference between $C^*C$ and the identity matrix, aiming for $\Psi^*C^*C\Psi \approx I$. This problem is then reformulated as a convex quadratic program. They also explore learning the downsampling operator $P$ to form a partial circulant matrix $\Phi = PC$.
For 2D signals (images/videos), they extend these ideas to 2D circulant operators. The learning process involves optimizing a 2D circulant kernel $M$ and a downsampling operator $\Omega$. They also introduce a method to construct "image-scale dictionaries" from patch-based dictionaries, enabling the learning of circulant operators that can directly process entire images, overcoming a significant limitation of prior work.
Datasets
- Synthetic Data: Used for initial testing and validation of the proposed methods. This includes synthetic 1D signals and synthetic images with known sparsity properties.
- Berkeley Segmentation Dataset [17]: A standard dataset of natural images used for training dictionaries and evaluating the performance of the learned sensing matrices on real-world image recovery tasks.
Key Insights and Ideas
- Learned Circulant Kernels Outperform Random Ones: The paper convincingly shows that optimizing circulant sensing matrices leads to significantly better recovery performance compared to using randomly generated circulant or even Gaussian random matrices, especially for structured signals like images.
- Coupled Learning is Crucial: Learning the sensing matrix and the signal dictionary simultaneously ("coupled learning") yields superior results compared to learning them independently. This suggests that the sensing process and the signal's representation are deeply intertwined.
- Image-Scale Learning is Achievable and Beneficial: By constructing image-scale dictionaries from patch-based ones, the authors successfully extend their learning approach to operate on entire images, overcoming the patch-size limitations of prior methods and achieving better recovery.
- Circulant Structure Enables Efficient Recovery: The inherent structure of circulant matrices allows for fast signal and image recovery using Fast Fourier Transforms (FFTs), making the learned matrices not only effective but also computationally efficient.
Key Results
- Improved Recovery Accuracy: Experiments on synthetic and real image data show that the learned circulant sensing matrices consistently achieve higher recovery accuracy (measured by MSE and PSNR) compared to random circulant and Gaussian random matrices. For instance, in image tests, coupled learned circulant matrices often outperformed Gaussian random matrices, especially for smaller measurement sizes ($m=16$).
- Robustness to Noise: The learned methods demonstrate good performance even in the presence of significant Gaussian noise.
- Efficiency: While not the primary focus, the circulant structure allows for faster recovery than general matrices, making the learned kernels practical for real-world applications.
Limitations and Future Work
- Computational Cost of Learning: While the recovery process is fast, the learning of optimized circulant matrices and dictionaries, especially for large images, can be computationally intensive. The paper notes that learning 2D operators for larger images took a considerable amount of time.
- NP-Hardness of Downsampling Optimization: Optimizing the downsampling operator $P$ (problem 3.10) is generally NP-hard, and the paper mentions that it was only "approximately solved" using solvers like Gurobi.
- Future Work: The authors suggest exploring more efficient learning algorithms and potentially extending the approach to other types of structured matrices. They also hint at the possibility of learning more complex signal representations.
Summary updated