Deterministic Construction of Compressed Sensing Measurement Matrix with Arbitrary Sizes via QC-LDPC and Arithmetic Sequence Sets

Abstract

It is of great significance to construct deterministic measurement matrices with good practical characteristics in Compressed Sensing (CS), including good reconstruction performance, low memory cost and low computing resources. Low-density-parity check (LDPC) codes and CS codes can be closely related. This paper presents a method of constructing compressed sensing measurement matrices based on quasi-cyclic (QC) LDPC codes and arithmetic sequence sets. The cyclic shift factor in each submatrix of QC-LDPC is determined by arithmetic sequence sets. Compared with random matrices, the proposed method has great advantages because it is generated based on a cyclic shift matrix, which requires less storage memory and lower computing resources. Because the restricted isometric property (RIP) is difficult to verify, mutual coherence and girth are used as computationally tractable indicators to evaluate the measurement matrix reconstruction performance. Compared with several typical matrices, the proposed measurement matrix has the minimum mutual coherence and superior reconstruction capability of CS signal according to one-dimensional (1D) signals and two-dimensional (2D) image simulation results. When the sampling rate is 0.2, the maximum (minimum) gain of peak signal-to-noise ratio (PSNR) and structural similarity index (SSIM) is up to 2.89 dB (0.33 dB) and 0.031 (0.016) while using 10 test images. Meanwhile, the reconstruction time is reduced by nearly half.

1. Introduction

Compressed Sensing (CS) theory is proposed [1,2,3,4], which suggests that sparse signals can be recovered from a small number of linear measurements by finding solutions to the underdetermined linear system of equations. For sparse or compressible signals, under certain conditions, signals can be sampled and reconstructed with much fewer samples than Nyquist theory. The core of this method is to use the measurement matrix to project the original high-dimensional signal into the low-dimensional space [3,4]. Once proposed, the theory has been widely applied in many fields such as single-pixel imaging, image encryption, synthetic aperture radar imaging, and nuclear magnetic resonance imaging [5,6,7,8]. Restricted isometric property (RIP) is an important criterion proposed by Candes and Tao [3]. Elad proposed the definition of mutual coherence in 2007 [9], which is used to measure the coherence within a matrix or between two matrices. Bourgain et al. [10] linked mutual coherence with RIP. RIP [11,12,13] and mutual coherence [14,15,16] are important tools for analyzing the properties of measurement matrices. In this paper, mutual coherence will be used to analyze the performance of the proposed measurement matrix because it is easier to calculate.

Now, the measurement matrix is divided into two main categories: random matrix and deterministic matrix [16,17]. Gaussian random matrix and Bernoulli random matrix have been proved to be suitable for CS, but there are some bottlenecks in the application of the above random matrices [18]. All the measurement matrix elements need to be stored, and this process needs to be repeated when a new implementation is needed, which will consume a lot of storage resources and have high requirements on the system [3,4,5]. Deterministic measurement matrices are convenient to control, and the hardware implementation is also convenient. Moreover, it requires less storage space.

In recent years, many researchers have put forward many principles and methods to construct [19,20,21,22,23,24,25,26,27,28,29,30,31,32,33] and optimize [34,35,36] measurement matrices. This paper mainly studies the construction method of deterministic measurement matrices. Dimakis et al. [19], Jiang et al. [20] and Xia et al. [23] used the binary matrix obtained from the LDPC code as the measurement matrix. Zeng et al. introduced a deterministic structure which combines orthogonal matrices and a chaos-based Toeplitz matrix [24]. Naidu et al. constructed a class of deterministic measurement matrices based on the Euler square principle [25]. Bryant et al. proposed a construction method based on a pair-balanced design [26]. Lu et al. studied how to construct a deterministic binary CS matrix of any size by using the idea of a bipartite graph [27]. Liu et al. proposed a method based on Bose balanced incomplete block design [28]. Fardad et al. designed low-complexity hardware for generating a deterministic measurement matrix based on Euclidean geometric LDPC codes [29]. Torshizi et al. proposed the construction of a deterministic measurement matrix based on Singer perfect difference set [30]. Tong et al. proposed the construction of a deterministic measurement matrix with low storage space and complexity [31]. Kazemi et al. proposed a class of sparse binary matrices constructed based on a finite field algorithm [32]. Liang et al. proposed a method based on combinational design correlation matrix expansion [33].

Since the fabrication cost of single-point detectors is generally lower than that of area array detectors, and it is relatively easier to fabricate single-point detectors that can operate in the non-visible light band, single-pixel imaging technology is of great significance in the field of non-visible light imaging. During the imaging process, the digital micromirror device (DMD) is sampled by the Hadamard matrix. The size of the Hadamard matrix is relatively fixed, and the number of columns is a power of 2. Therefore, the matrix with arbitrary sizes cannot be constructed. In this paper, we propose a method to construct a deterministic measurement matrix by arithmetic sequence sets. The LDPC code uses a QC structure, which makes the matrix very suitable for hardware implementation by simple shift registers. This method is to expand the small base matrix into a matrix of any size, which is more flexible. In addition, we compare the proposed measurement matrix with some typical measurement matrices. The simulation results show that the performance of the proposed measurement matrix is better than the Gaussian matrix, Bernoulli matrix and Toeplitz matrix. The rest of the paper is as follows. Section 2 introduces some basic CS theory and basic concepts of the LDPC code and QC-LDPC code. Section 3 introduces the determination of the shift factor in QC-LDPC cyclic shift matrices by the arithmetic sequence sets and analyzes the performance of the matrix by mutual coherence and girth. Section 4 presents the reconstruction simulation results of 1D signals and 2D images. Moreover, the computational complexity, storage space, and reconstruction time are compared. Section 5 is the conclusion.

2. Related Work

2.1. Compressed Sensing Theory

For a compressible original signal $x\in R^N$, the purpose of CS is to obtain the observed value by projecting signals into the low-dimensional space through the measurement matrix, so as to efficiently reconstruct the original signal. This process can be expressed as follows:

$$y=\mathrm{\Phi }x$$

(1)

where $\mathrm{\Phi }\in R^{M\times N}$ is the measurement matrix, the sampling rate is $R=M/N$, and y is the measurement vector. In the process of restoring an M-dimensional vector to an N-dimensional vector, the following reconstruction algorithms can be selected:

$$\mathrm{argmin}{‖\widehat{\mathit{x}}‖}_p \mathrm{subject} \mathrm{to} \mathit{y}=\mathrm{\Phi }x$$

(2)

where p stands for greedy reconstruction algorithm based on an $l_0$-model or convex optimization reconstruction algorithm based on the $l_1$-model [37]. One of the reconstruction algorithms includes orthogonal matching pursuit (OMP) [38] and its improved algorithms. The other is to turn it into an $l_1$-minimization problem.

In order to reconstruct the original signal from (2), the measurement matrix needs to meet some strict conditions. RIP is a sufficient condition to ensure that the signal can be reconstructed accurately in CS. Let $\mathrm{\Phi }$ be a $M\times N$ matrix, for any k-sparse signal $x\in R^N$, this satisfies the RIP of order k, if there is a constant 0 < ${\delta }_k$ < 1 such that

$$(1-{\delta }_k){‖x‖}_2^2\le {‖\mathrm{\Phi }x‖}_2^2\le (1+{\delta }_k){‖x‖}_2^2$$

(3)

where ${\delta }_k$ is a non-negative restricted isometry constant (RIC). Because RIP is a sufficient condition and difficult to prove, the mutual coherence can be used as the evaluation criterion for the measurement matrix. Let $\mathrm{\Phi }$ be a $M\times N$ matrix, then the mutual coherence of the $\mathrm{\Phi }$ is defined as

$$\mu (\mathrm{\Phi })\triangleq \underset{1\le i\ne j\le n}{\max }\frac{\left|〈{\varphi }_i,{\varphi }_j〉\right|}{{‖{\varphi }_i‖}_2{‖{\varphi }_j‖}_2}$$

(4)

where ${\varphi }_1,{\varphi }_2,\dots ,{\varphi }_n$ are the column vectors of the matrix $\mathrm{\Phi }$.

For an $M\times N$ matrix, there is a famous Welch bound [10,39]:

$$\mu (\mathrm{\Phi })\ge \sqrt{\frac{N-M}{M(N-1)}}$$

(5)

2.2. LDPC Codes and QC-LDPC Codes

LDPC code is a kind of linear block code, which is very close to the Shannon limit [40,41]. The matrix constructed by LDPC codes has good sparsity and strong irrelevance. The check matrix [42] can be constructed by using the Tanner graph. M rows and N columns of a check matrix H correspond to M check nodes and N variable nodes in the Tanner graph, respectively. Variable nodes correspond to columns in the check matrix and represents the actual variable. Check nodes correspond to rows in the check matrix and represent constraints between variable nodes. When elements in the matrix H are non-zero elements, there is an edge connection between the check nodes and variable nodes. Each column has $\lambda$ non-zero elements, and each row has $\rho$ non-zero elements. $\lambda$ and $\rho$ are much smaller, and the number of rows is M, and the number of columns is N, respectively, which is a sparse matrix. A regular LDPC code with a column (row) weight of 2 (3) and its corresponding Tanner graph are shown in Figure 1.

From Figure 1, the edges of the red and blue lines correspond to the first row and second column in H, respectively. If there are closed loops in the Tanner graph of an LDPC code, the shortest loop is called girth. For example, in the above Tanner graph, the girth is 6. The girth greatly affects the performance of LDPC codes.

QC-LDPC codes are important subsets of structured LDPC codes [43], and their parity check matrices (PCM) can be divided into multiple square matrices of equal size, each of which is the cyclic shift matrix of the identity matrix or all-zero matrix, which is very convenient for storage and addressing. The check matrix 𝐻 of a QC-LDPC code is represented by a J × L cyclic matrix array [42]. Each element $I(p_{i,j})$ in the matrix H represents a q × q cyclic submatrix defined by the shift factor $p_{i,j}$ or a q × q zero matrix, I is the q × q identity matrix, and $p_{i,j}$ represents the number of times that each row of the identity matrix is cyclically shifted to the right. If $p_{i,j}=0$, then $I(p_{i,j})$ is an identity matrix, and the specific form is

$$H=\left[\begin{array}{cccc}I(p_{1,1})& I(p_{1,2})& \cdots & I(p_{1,L})\\ I(p_{2,1})& I(p_{2,2})& \cdots & I(p_{2,L})\\ ⋮& ⋮& \ddots & ⋮\\ I(p_{J,1})& I(p_{J,2})& \cdots & I(p_{J,L})\end{array}\right]$$

(6)

where the shifts matrix P can be expressed as

$$P=\left[\begin{array}{cccc}{p}_{1,1}& p_{1,2}& \cdots & p_{1,L}\\ p_{2,1}& p_{2,2}& \cdots & p_{2,L}\\ ⋮& ⋮& ⋮& ⋮\\ p_{J,1}& p_{J,2}& \cdots & p_{J,L}\end{array}\right]$$

(7)

3. Determine QC-LDPC Codes Based on Arithmetic Sequence Sets

3.1. Constructing Elements in the Basis Matrix

We use a special arithmetic algorithm to obtain an arithmetic sequence and take it as the element of the shifts matrix P. An arithmetic sequence is a common mathematical sequence, which belongs to combinatorial mathematics. It is a sequence, from the second term onwards, whereby the difference between each term and its predecessor is equal to the same constant. The arithmetic sequence referred to this paper is a special one whose difference changes constantly by using the idea of mathematical analysis. The specific construction principle is:

$$\left\{\begin{array}{ll}{d}_{1,j}=d,\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}& \hfill d\ge 0\\ d_{3k+2,j}=d_{3k+1,j}+1,\hspace{1em}\hspace{1em}\hspace{1em}& \hfill k\ge 0\\ d_{3k+3,j}=\max \left\{L-j+d_{3k+2,j},j+d_{3k+2,j}\right\}, & \hfill k\ge 0\\ d_{3k+1,j}=D_{3k,j}+1,\hspace{1em}\hspace{1em}\hspace{1em}& \hfill k\ge 1\end{array}\right.$$

(8)

where $d_{i,j}$ (i = 1,3k + 1,…,3k + 3) is the difference between the shift factor at the position of the i(j) th row(column) in the basis matrix P and the previous adjacent element in the same row; d is the difference in the first row and is a constant; k is an integer, and $D_{3k,j}$ represents the sum of the differences $d_{3k,j}$ ($1\le j\le L-1$) between the latter element and the previous element in the 3kth row; and L is the number of rows of the basis matrix. The specific algorithm description is shown in Algorithm 1.

Algorithm 1: Construction of the measurement matrix $\mathrm{\Phi }$

Input: Two positive integers m and n, where m < n, constant d, J, L and q. Output: measurement matrix $\mathrm{\Phi }$ Initialization: Initialize an $q\times q$ identity matrix I. We can obtain the shifts matrix P by determining the d $$\left\{\begin{array}{ll}{d}_{1,j}=d,& \hfill d\ge 0\\ d_{3k+2,j}=d_{3k+1,j}+1,& \hfill k\ge 0\\ d_{3k+3,j}=\max \left\{L-j+d_{3k+2,j},j+d_{3k+2,j}\right\}, & \hfill k\ge 0\\ d_{3k+1,j}=D_{3k,j}+1,& \hfill k\ge 1\end{array}\right.$$ For i = 1 to m  For j = 1 to n do 2. $I\left(p_{i,j}\right)$ is an $q\times q$ identity matrix if $p_{i,j}=0$; 3. Except in this case, according to the value of $p_{i,j}$, each row of the identity matrix I is cyclically shifted to the right $p_{i,j}$ times. 4. End for 5. With each $I\left(p_{i,j}\right)$ determined, $\mathrm{\Phi }$ can be determined. 6. By changing the values of J, L, q, measurement matrices of different sizes can be obtained. 7. $\mathrm{\Phi }=\left[\begin{array}{cccc}I(p_{1,1})& I(p_{1,2})& \cdots & I(p_{1,L})\\ I(p_{2,1})& I(p_{2,2})& \cdots & I(p_{2,L})\\ ⋮& ⋮& \ddots & ⋮\\ I(p_{J,1})& I(p_{J,2})& \cdots & I(p_{J,L})\end{array}\right]$

Storing random measurement matrices takes up a large amount of storage space. On the contrary, deterministic structure consumes less memory and reduces computational complexity. Therefore, a deterministic structure of matrices is adopted in this paper. In QC structure, each matrix consists of several square matrices. Since each row of a submatrix is obtained by looping the elements of its previous row to the right, each submatrix requires only one cell of memory for storage [44]. In other words, the amount of memory required to store each parity matrix is equal to the number of its submatrices, saving a lot of storage space. The current work is to construct a measurement matrix with high memory efficiency, easy implementation and good performance, and it is suitable for portable applications such as single pixel imaging. In order to achieve this goal, we adopt the structure of QC-LDPC and use the arithmetic sequence as the shift factor in the cyclic shift matrix. Different measurement matrices can be obtained by setting different d values and the size of the H.

3.2. Girth Analysis

Theoretically, a check matrix with a long girth is preferred, and it implies that the nodes maintain independence [42,45]. Fossorier [43] proved that the PCM of this code does not have a Tanner graph with a girth greater than 12. On this basis, the sufficient and necessary conditions of codes with different girth values are given. Khajehnejad et al. [46] proved the good performance of sparse binary measurement matrix by using girth. Suppose $\mathrm{\Phi }$ is a CS measurement matrix, girth is g and the column weight is $\gamma$. Consider any two different columns of $\mathrm{\Phi }$ that have at most $\lambda$ common ones; $\lambda =1$ when $g\ge 6$. The corresponding conditions of the CS measurement matrix are given. The girth of the proposed measurement matrix is at least 8. The specific proof process can be found in Appendix A. Notably, on the one hand, the results show that there is a significant relationship between the size of the circulant permutation matrix (CPM) and the girth of the measurement matrix, it is because the codes with large girth have better bit-error rate performances; on the other hand, there is a significant relationship between the girth of the measurement matrix and the performance of the CS method [47,48,49].

3.3. Mutual Coherence Analysis

Given an $M\times N$ binary matrix $\mathrm{\Phi }$ $(M<N)$, the column weight is J, and we have the following bounds:

$$\mu \left(\mathrm{\Phi }\right)\ge \frac{1}{J}$$

(9)

Proof. 

Because $M<N$, column weight $J\ge 2$, the following can be easily obtained:

$$〈{\varphi }_i,{\varphi }_j〉\ge 1$$

(10)

where ${\varphi }_i,{\varphi }_j$ are the columns of the matrix $\mathrm{\Phi }$. □

The relationship between mutual coherence and girth can be expressed as follows: given an $M\times N$ binary matrix $\mathrm{\Phi }$ $(M<N)$, the column weight is J, and if girth $g>4$, then the matrix $\mathrm{\Phi }$ can achieve the optimal coherence $\mu \left(\mathrm{\Phi }\right)=1/J$.

Proof. 

For a given binary matrix $\mathrm{\Phi }$, if $\mu \left(\mathrm{\Phi }\right)>1/J$, then considering $\exists {\varphi }_i,{\varphi }_j\in \mathrm{\Phi }$, we can obtain $〈{\varphi }_i,{\varphi }_j〉\ge 1$. The elements of the proposed measurement matrix are “0” and “1”. Then, we can obtain the result of $〈{\varphi }_i,{\varphi }_j〉\ge 2$. This means that there are at least two “1” elements between the columns ${\varphi }_i$ and the columns ${\varphi }_j$ of the matrix. Through the girth analysis in 3.2, it is proved that the girth of the proposed measurement matrix is at least 8. According to the definition of girth, when girth $g>4$, there is $\mu \left(\mathrm{\Phi }\right)\le 1/J$. From (9), we can obtain $\mu \left(\mathrm{\Phi }\right)\ge 1/J$. Thus, we finally prove $\mu \left(\mathrm{\Phi }\right)=1/J$. □

4. Experiment and Discussion

In this section, through simulation experiments of 1D signals and 2D images, the performance of the proposed measurement matrix and several typical measurement matrices are compared. Simulation results show that the performance of our proposed measurement matrix is better than other typical matrices under the OMP algorithm.

4.1. Reconstruction Performance of One-Dimensional Signals

In our simulation, we conducted 1000 experiments for each k-sparse signal and obtained the relationship between signal sparsity and reconstruction success rate. Sparse signals are uniformly and randomly generated, whereas the corresponding values of non-zero elements are generated according to the standard Gaussian distribution. Relative reconstruction error can be expressed as

$$e=\frac{{‖x^{’}-x‖}_2}{x_2}$$

(11)

where $x^{’}$ is the reconstructed signal, and x is the original signal. We set $e\le 0.001$, which means that the experiment is a “perfect reconstruction”, and we use the OMP algorithm as the reconstruction algorithm to compare the reconstruction performance.

We construct the measurement matrix according to the construction rules of (6)~(8). According to the construction rules, $d=1$ or $d=0$, $q>L$. When $d=1$, we set $J=5,L=10,q=11$, and then we can obtain the basis matrix P of the CPM, as shown in (12):

$$P=\left[\begin{array}{cccccccccc}0& 1& 2& 3& 4& 5& 6& 7& 8& 9\\ 0& 2& 4& 6& 8& 10& 12& 14& 16& 18\\ 0& 11& 21& 30& 38& 45& 53& 62& 72& 83\\ 0& 84& 168& 252& 336& 420& 504& 588& 672& 756\\ 0& 85& 170& 255& 340& 425& 510& 595& 680& 765\end{array}\right]$$

(12)

Then, the measurement matrix based on the CPM can be obtained, which can be simplified, as shown in (13):

$$\mathrm{\Phi }=\left[\begin{array}{cccccccccc}I& I(1)& I(2)& I(3)& I(4)& I(5)& I(6)& I(7)& I(8)& I(9)\\ I& I(2)& I(4)& I(6)& I(8)& I(10)& I(1)& I(3)& I(5)& I(7)\\ I& I& I(10)& I(8)& I(5)& I(1)& I(9)& I(7)& I(6)& I(6)\\ I& I(7)& I(3)& I(10)& I(6)& I(2)& I(9)& I(5)& I(1)& I(8)\\ I& I(8)& I(5)& I(2)& I(10)& I(7)& I(4)& I(1)& I(9)& I(6)\end{array}\right]$$

where (.) represents the number of the identity matrix I that is cyclically shifted to the right. The measurement matrix is ${\mathrm{\Phi }}_{55\times 110}$.

Set $J=6,L=18,d=1,q=19$, $J=5,L=16,d=1,q=17$ and $J=5,L=16,d=1,q=32$. Then, through (6)~(8), the proposed measurement matrix can be finally obtained and expressed separately by ${\mathrm{\Phi }}_{114\times 342}$, ${\mathrm{\Phi }}_{85\times 272}$, ${\mathrm{\Phi }}_{160\times 512}$.

Table 1. Comparison of coherence values.

Measurement Matrix	${\mathbf{\Phi }}_{55\times 110}$	${\mathbf{\Phi }}_{114\times 342}$	${\mathbf{\Phi }}_{85\times 272}$	${\mathbf{\Phi }}_{160\times 512}$
	Coherence $\mu \left(\mathrm{\Phi }\right)$
Gaussian Matrix	0.5204	0.4878	0.3953	0.3657
Bernoulli Matrix	0.4909	0.4588	0.3860	0.3375
Toeplitz Matrix	0.4545	0.3882	0.3333	0.3000
Hadamard Matrix	/	/	/	0.1875
Proposed Matrix	0.2501	0.1667	0.2010	0.2000

compares the mutual coherence values of the random Gaussian matrix, Bernoulli matrix, Toeplitz matrix, Hadamard Matrix and the proposed matrix with four sizes. It can be seen from Table 1 that the mutual coherence of the proposed measurement matrix is lower than the other three measurement matrices except Hadamard Matrix, among which the random Gaussian matrix has the highest mutual coherence. Although the Hadamard matrix has the lowest mutual coherence, the Hadamard matrix has some disadvantages. The size of the Hadamard matrix is relatively fixed, and the number of columns is a power of 2, so the matrix with various sizes cannot be constructed. Due to these limitations, the following simulation experiments will not use the Hadamard matrix as a comparison object.

When $d=0$, the above parameters J, L and q are also set to the same values. Set parameters as $J=5,L=10,d=0,q=11$, $J=6,L=18,d=0,q=19$, $J=5,L=16,d=0,q=17$ and $J=5,L=16,d=0,q=32$, and then through (6)~(8), the proposed measurement matrix can be finally obtained and expressed separately by ${\mathrm{\Phi }}_{55\times 110}$, ${\mathrm{\Phi }}_{114\times 342}$, ${\mathrm{\Phi }}_{85\times 272}$, ${\mathrm{\Phi }}_{160\times 512}$.

Figure 2 shows the relationship between signal sparsity and the percentage recovered of one-dimensional signals. Signal lengths are set to $110\times 1$, $342\times 1$, $272\times 1$ and $512\times 1$. OMP is used as reconstruction algorithm. Therefore, from Figure 2, we can easily see that the performance of the proposed measurement matrix is significantly better than that of the Gaussian matrix and Bernoulli matrix, and slightly better than that of Toeplitz matrix. As for the proposed measurement matrix, the girth of the matrix when $d=0$ is larger than that when $d=1$, so it can be seen from Figure 2 that the performance of the measurement matrix when $d=0$ is better than that when $d=1$.

Figure 3 shows the relationship between the percentage recovered of the one-dimensional signal and the number of measurements. Signal lengths are set to $110\times 1$, $342\times 1$, $272\times 1$ and $512\times 1$. OMP is used as reconstruction algorithm. It can be seen from Figure 3 that the percentage recovered of signal increases with the increase in measurements. The performance of proposed measurement matrix is significantly better than that of the Gaussian matrix, Bernoulli matrix and Toeplitz matrix. As for the proposed measurement matrix, the girth of the matrix when $d=0$ is larger than that when $d=1$, so it can be seen from Figure 3 that the performance of the measurement matrix when $d=0$ is better than that when $d=1$.

4.2. Reconstruction Performance of Two-Dimensional Images

In the experiment, we use MATLAB R2019a for simulation. Ten images (512 × 512 pixels), from the image library of the Institute of Signal and Image Processing of University of Southern California, USA, are selected as test images, as shown in Figure 4. The discrete cosine transform (DCT) is used as the sparse basis for signals, and block sampling is adopted. The block size is set as 32 × 32, and the OMP algorithm is used as the reconstruction algorithm. Then, we compare the PSNR and SSIM of reconstructed images by changing the sampling rate to illustrate the performance of the reconstruction.

In Figure 5, the random Gaussian matrix, Bernoulli matrix, Toeplitz matrix and the proposed measurement matrix are selected, respectively. The PSNR and SSIM of Barbara and Peppers are compared, and the sampling rates are, respectively, 0.05, 0.1, 0.2, 0.3, 0.4 and 0.5. The dotted line represents SSIM and the solid line represents PSNR. As can be seen from Figure 5, both PSNR and SSIM of the proposed measurement matrix are higher than other three measurement matrices, and the reconstruction performance is better. When the sampling rate is 0.2, four images (Barbara, Peppers, Resolution Chart and Camera Test) are selected to compare the reconstruction performance, as shown in Figure 6. The red boxes in Figure 6 indicate that the image is partially enlarged to show some details more clearly. Numerical values above Figure 6 represent the values of PSNR(dB)|SSIM. It can be seen from Figure 6 that the local details of the reconstructed image of the four measurement matrices are basically visible, and the texture details are basically clear. The reconstructed images of the Gaussian matrix and the Bernoulli matrix still have artifacts of different degrees, the reconstructed images of the Toeplitz matrix have local artifacts of small range, the PSNR and SSIM values of the proposed matrix are higher, the reconstruction performance is better, and the reconstructed images are processed better in some texture details. The visual effect is better than the other three measurement matrices, so the reconstruction effect is better.

Table 2. PSNR(dB) and SSIM of 10 test images.

Image	Measurement Matrix		PSNR(dB)|SSIM
		0.05	0.1	0.2	0.3	0.4	0.5
Barbara	Gaussian matrix	15.29|0.6933	18.90|0.8617	21.58|0.9253	24.31|0.9598	26.00|0.9727	27.63|0.9813
	Bernoulli matrix	15.99|0.7308	18.96|0.8638	21.61|0.9256	24.40|0.9606	26.16|0.9737	27.64|0.9813
	Toeplitz matrix	15.34|0.6978	18.93|0.8646	21.61|0.9256	24.30|0.9597	26.09|0.9732	27.96|0.9826
	Proposed matrix	17.92|0.8211	21.25|0.9187	23.91|0.9560	25.26|0.9676	27.98|0.9826	30.00|0.9901
Peppers	Gaussian matrix	16.33|0.7526	21.05|0.9130	24.79|0.9629	28.16|0.9829	30.19|0.9893	31.85|0.9927
	Bernoulli matrix	16.65|0.7735	21.16|0.9146	24.79|0.9628	28.32|0.9835	30.20|0.9893	31.96|0.9929
	Toeplitz matrix	16.21|0.7487	20.99|0.9119	24.89|0.9637	28.37|0.9837	30.37|0.9898	32.13|0.9931
	Proposed matrix	19.21|0.8765	23.64|0.9517	27.45|0.9799	29.06|0.9860	31.80|0.9914	33.86|0.9960
Woman	Gaussian matrix	16.98|0.6532	19.87|0.8189	22.18|0.8925	24.95|0.9429	26.73|0.9620	28.32|0.9736
	Bernoulli matrix	16.36|0.6012	19.80|0.8163	22.21|0.8935	25.04|0.9442	26.69|0.9616	28.28|0.9734
	Toeplitz matrix	16.47|0.6102	19.85|0.8174	22.16|0.8921	24.95|0.9430	26.91|0.9636	28.53|0.9749
	Proposed matrix	18.67|0.7654	21.99|0.8872	24.59|0.9379	25.87|0.9538	26.61|0.9609	29.71|0.9713
Mandrill	Gaussian matrix	15.28|0.4993	16.14|0.5787	17.26|0.6755	18.52|0.7531	19.50|0.8014	20.50|0.8411
	Bernoulli matrix	15.32|0.4919	16.05|0.5809	17.04|0.6616	18.51|0.7535	19.49|0.8014	20.46|0.8393
	Toeplitz matrix	15.44|0.4987	16.05|0.5757	17.11|0.6680	18.44|0.7506	19.54|0.8033	20.56|0.8433
	Proposed matrix	16.01|0.5801	15.67|0.5678	17.44|0.6810	18.44|0.7486	20.55|0.8431	21.45|0.8601
House	Gaussian matrix	17.12|0.7856	21.41|0.9036	23.79|0.9445	26.17|0.9677	27.64|0.9769	29.09|0.9835
	Bernoulli matrix	17.79|0.7864	21.25|0.9030	23.88|0.9454	26.15|0.9676	27.64|0.9769	28.99|0.9831
	Toeplitz matrix	17.82|0.7877	21.46|0.9055	23.85|0.9452	26.19|0.9678	27.83|0.9779	29.29|0.9842
	Proposed matrix	20.12|0.8945	23.36|0.9382	25.82|0.9649	26.92|0.9727	28.60|0.9813	30.01|0.9915
Boat	Gaussian matrix	15.83|0.6414	19.18|0.8226	21.72|0.9004	24.47|0.9469	26.19|0.9642	27.88|0.9757
	Bernoulli matrix	15.36|0.6398	19.36|0.8307	21.74|0.9012	24.38|0.9459	26.16|0.9639	27.88|0.9757
	Toeplitz matrix	15.01|0.6301	19.37|0.8302	21.84|0.9035	24.47|0.9469	26.42|0.9660	28.06|0.9766
	Proposed matrix	18.97|0.8119	21.55|0.8966	24.20|0.9434	25.45|0.9575	26.22|0.9644	28.21|0.9786
Cameraman	Gaussian matrix	14.86|0.7487	20.09|0.9176	24.01|0.9665	28.38|0.9877	30.99|0.9933	33.16|0.9959
	Bernoulli matrix	14.61|0.7412	20.00|0.9166	23.87|0.9654	28.34|0.9876	31.07|0.9934	33.30|0.9961
	Toeplitz matrix	14.58|0.7401	20.06|0.9178	23.77|0.9647	28.57|0.9883	31.06|0.9934	33.70|0.9964
	Proposed matrix	17.45|0.8231	22.74|0.9552	25.41|0.9747	29.61|0.9908	31.67|0.9947	33.66|0.9971
Couple	Gaussian matrix	16.61|0.6623	19.29|0.8077	21.64|0.8883	24.33|0.9394	26.07|0.9592	27.40|0.9700
	Bernoulli matrix	16.91|0.6812	19.26|0.8078	21.70|0.8896	24.29|0.9389	25.84|0.9571	27.42|0.9701
	Toeplitz matrix	16.98|0.6835	19.25|0.8096	21.66|0.8889	24.36|0.9397	26.10|0.9596	27.59|0.9712
	Proposed matrix	19.01|0.8011	21.64|0.8870	24.09|0.9360	25.13|0.9496	26.99|0.9634	28.89|0.9821
Resolution chart	Gaussian matrix	12.39|0.6292	14.18|0.7423	16.66|0.8899	18.93|0.9118	20.13|0.9330	22.33|0.9507
	Bernoulli matrix	12.14|0.6128	14.40|0.7491	16.09|0.8805	18.85|0.9189	20.37|0.9343	22.04|0.9563
	Toeplitz matrix	12.58|0.6425	14.59|0.7546	16.85|0.8894	18.47|0.9162	20.92|0.9346	22.34|0.9579
	Proposed matrix	14.61|0.7547	16.30|0.8372	18.46|0.9124	20.04|0.9310	22.55|0.9509	24.96|0.9732
Camera test	Gaussian matrix	9.45|0.1945	12.33|0.6462	14.74|0.8333	16.12|0.9220	18.11|0.9669	21.92|0.9827
	Bernoulli matrix	9.25|0.2229	12.03|0.6412	14.78|0.8353	16.22|0.9240	18.15|0.9668	21.50|0.9812
	Toeplitz matrix	10.62|0.2667	12.07|0.6256	14.87|0.8399	16.15|0.9229	18.45|0.9670	21.68|0.9823
	Proposed matrix	12.27|0.6410	14.82|0.7963	16.35|0.8831	18.36|0.9412	20.03|0.9696	22.65|0.9919

shows all values of PSNR and SSIM of 10 test images with sampling rates of 0.05, 0.1, 0.2, 0.3, 0.4 and 0.5, respectively. The best values are shown in bold for observation. From Table 2, it can be observed that the proposed matrix significantly outperforms the other matrices at low sampling rates. When the sampling rate is 0.2, it can be seen from the data in Table 2 that compared with the other three types of measurement matrices, for the proposed measurement matrix, the maximum gain of PSNR and SSIM can reach 2.89 dB and 0.031, and the minimum gain of PSNR and SSIM can reach 0.33 dB and 0.016. In Table 2, when the sampling rate is 0.4, the PSNR|SSIM values of “Woman” and “Boat” are not the highest when selecting the proposed matrix measurement matrix, the numerical difference is not obvious, and mainly from the point of the numerical results, the Toeplitz matrix reconstruction effect is slightly better than the proposed matrix, but visually, there is no obvious difference.

4.3. Comparison of Computing Complexity, Storage Space and Reconstruction Time

In this section, we will examine the amount of addition, multiplication and storage space allocation required for some different matrices in CS. We consider the sum of the required number of additions and multiplications to be computational complexity.

Table 3. Computational complexity and storage space allocation of measurement matrices.

Measurement Matrix	Number of Additions	Number of Multiplications	Required Storage Space
Gaussian Matrix	$M\times (N-1)$	$M\times N$	$16\times M\times N$
Bernoulli Matrix	$M\times (N-1)$	0	$16\times M\times N$
Toeplitz Matrix	$M\times (N-1)$	0	$16\times M\times N$
Proposed Matrix	$J\times L\times q$	$(J-1)\times (L-1)$	$16\times (J-1)\times (L-1)$

shows the numerical comparison of computational complexity and storage space for several measurement matrices. J = M/q, L = N/q.

Table 3 shows that the proposed measurement matrix has the lowest computational complexity because it is generated based on CPM and requires less storage space. In addition, due to the sparsity and QC structure of the proposed measurement matrix, it can be more easily implemented in hardware and uses the shift register for storage. Furthermore, we can see that the Gaussian matrix has the highest computational complexity because the corresponding CS encoder must perform both multiplication and addition operations. Bernoulli matrix and Toeplitz matrix simplify the calculation and reduce the computational complexity by abandoning the multiplication operation. Specifically, we give the Landau notation for these measurement matrices. Thus, the computational complexity of the Gaussian matrix can be expressed as $O\left(2q^{2}JL-Jq\right)$, and both the Bernoulli matrix and Toeplitz matrix can be expressed as $O\left(q^{2}JL-Jq\right)$. Then, the computational complexity of our proposed measurement matrix is $O\left(qJL+JL\right)$. In order to compare the storage space of the four types of measurement matrices, we choose the measurement matrix ${\mathrm{\Phi }}_{55\times 110}$, ${\mathrm{\Phi }}_{114\times 342}$, ${\mathrm{\Phi }}_{85\times 272}$ and ${\mathrm{\Phi }}_{160\times 512}$. The quantization results of computational complexity are shown in

Table 4. Quantization results of computational complexity with different measurement matrices.

Measurement Matrix	Computational Complexity
	${\mathrm{\Phi }}_{55\times 110}$	${\mathrm{\Phi }}_{114\times 342}$	${\mathrm{\Phi }}_{85\times 272}$	${\mathrm{\Phi }}_{160\times 512}$
Gaussian Matrix	12,045	77,862	46,155	163,680
Bernoulli Matrix	5995	38,874	23,035	81,760
Toeplitz Matrix	5995	38,874	23,035	81,760
Proposed Matrix	586	22,137	1420	2620

. For a matrix element $a_{ij}$, it takes 8 Bytes to store the value of this element and 4 Bytes to store the subscripts i and j, respectively, so a total of 16 Bytes are needed to store a matrix element (1 KB = 1024 Bytes). From Table 3 and

Table 5. Quantization results of storage space with different measurement matrices.

Measurement Matrix	Required Storage Space (Unit: KB)
	${\mathrm{\Phi }}_{55\times 110}$	${\mathrm{\Phi }}_{114\times 342}$	${\mathrm{\Phi }}_{85\times 272}$	${\mathrm{\Phi }}_{160\times 512}$
Gaussian Matrix	95	610	362	1280
Bernoulli Matrix	95	610	362	1280
Toeplitz Matrix	95	610	362	1280
Proposed Matrix	0.625	1.4	1	1.94

, we can see that the storage space required by the proposed measurement matrix is significantly smaller than that of Gaussian, Bernoulli and Toeplitz matrices. It is worth noting that with the increase in measurement matrix size, the performance superiority of the proposed method becomes more obvious.

We consider reconstruction time as another performance index to evaluate the performance of the proposed measurement matrix. According to the construction rules, it can be seen that the proposed measurement matrix is very sparse, in which most matrix elements are zero. The sparsity of the matrix helps to reduce the reconstruction time of different reconstruction algorithms. The zero elements in the sensor matrix transmit almost no information to the measurement vector without any effort. Therefore, the sparsity of the matrix is very important to reduce computational complexity and recovery time. Figure 7a shows the relationship between reconstruction time and sparsity for a 512 × 1 one-dimensional signal. OMP algorithm is selected as the reconstruction algorithm, the measurement matrix is ${\mathrm{\Phi }}_{160\times 512}$, and the value range of sparsity is $10\le K\le 80$. Figure 7b selects 5 test images (Cameraman, Peppers, Airplane, Barbara and Camera test) to compare their reconstruction time, and the sampling rate is 0.2. It can be seen from Figure 7 that the reconstruction time of the proposed measurement matrix is shorter than that of the random Gaussian matrix, Bernoulli matrix and Toeplitz matrix. In the reconstruction of the one-dimensional signal, the record is the total time for 1000 experiments. The proposed measurement matrix saves nearly half of the time in the reconstruction process. In the reconstruction of the two-dimensional image, because the OMP algorithm is selected, the reconstruction speed itself is very fast, so for different measurement matrices, the reconstruction time difference is 1~2 s.

5. Conclusions

This paper proposes a new method to design a measurement matrix. We use the arithmetic sequence sets and QC-LDPC structure to construct the binary measurement matrix. We further analyze the performance of the proposed measurement matrix through girth and mutual coherence. We also express the necessary conditions for the proposed measurement matrix to have a girth $g\ge 6$, and we prove that the girth $g\ge 8$. Our method has some other advantages besides their deterministic, sparsity and QC structure. Among them, the proposed method expands the small base matrix into a matrix of any size, which is more flexible and more suitable for resource-constrained applications, such as single-pixel imaging. At the same time, it can reduce computational complexity. Theoretical analysis and numerical simulation results show that the reconstruction performance of the proposed measurement matrix is better than several typical measurement matrices. In 2D image reconstruction, the maximum gain of PSNR and SSIM can reach 2.89 dB and 0.031, and the minimum gain of PSNR and SSIM can reach 0.33 dB and 0.016, respectively, when the sampling rate is 0.2. The proposed method outperforms others at a low sampling rate. Our group is studying the deep learning method used in the reconstruction of compressed sensing images, which can reconstruct the image at a very low sampling rate with good reconstruction quality. This paper uses OMP as the reconstruction method, and our next work will try to add other algorithms and use the deep learning method.