Structured Measurement Matrices Based on Deterministic Fourier Matrices and Gram Matrices

The measurement matrices play a crucial role in compressed sensing, directly impacting the performance of signal sampling and reconstruction. As one of the primary construction methods for measurement matrices, designing structured measurement matrices is a challenging problem. In practical sampling, the measurement matrices often have strong coherence. Therefore, it is significant to design structured measurement matrices with superior reconstruction performance at low sampling, although the coherence is strong. In this paper, by introducing a special Gram matrix and merging it with the deterministic Fourier matrix, we construct a kind of measurement matrices with superior signal recovery performance under strong coherence. Furthermore, utilizing Katz’ character sum estimation allows us to establish an upper bound on the coherence of the constructed matrices. All experimental results demonstrate that the performance of the proposed matrices outperform that of Fourier matrices and Gaussian random matrices. Consequently, the proposed matrices hold significant application in sparse signal processing.