An Improved Toeplitz Measurement Matrix for Compressive Sensing

Abstract

Compressive sensing (CS) takes advantage of the signal's sparseness in some domain, allowing the entire signal to be efficiently acquired and reconstructed from relatively few measurements. A proper measurement matrix for compressive sensing is significance in above processions. In most compressive sensing frameworks, random measurement matrix is employed. However, the random measurement matrix is hard to implement by hardware. So the randomness of the measurement matrix leads to the poor performance of signal reconstruction. In this paper, Toeplitz matrix is employed and optimized as a deterministic measurement matrix. A hardware platform for signal efficient acquisition and reconstruction is built by field programmable gate arrays (FPGA). Experimental results demonstrate the proposed approach, compare with the existing state-of-the-art method, and have the highest technical feasibility, lowest computational complexity, and least amount of time consumption in the same reconstruction quality.

1. Introduction

Compressive sensing (sampling), as a novel sampling technique, which under certain conditions aims to project a high-dimensional random signal onto a lower-dimensional space with high probability compared to conventional Shannon's sampling rate, is put forward first by Donoho et al. in 2006 [1, 2]. Measurement matrix as the key part of CS research which guarantees the excellent projection effect has recently gained more and more attentions in various fields of applied mathematics, electrical engineering, and remote sensing.

Measurement matrix as the most part of CS research which leads to less sampling points or senor nodes has become a hot topic. It falls broadly into three categories: random measurement [3–5], partial random measurement [6–8], and deterministic measurement [9–18].

Random measurement matrix is not just a simple random variable. It should satisfy restricted isometric property (RIP) condition. The most classic random measurement matrix is Bernoulli and Gaussian matrix [3], as well as Sub-Gaussian Random Projection [4] and over-sparse random projection [5]. According to RIP rules, partial random measurement matrix is only part of the random matrix, which has some different ways: Sub-Gaussian Random Projection [4], over-sparse random projection [5], partial Fourier matrix [6], partial Hadamard matrix [7], partial orthogonal matrix [8], and so forth. It is clear that randomness plays a key role in the design of the measurement matrix. Thus random measurement matrix is universal in the sense, regardless of whether it meets RIP with high probability in most situations.

When the input signal is K-sparse, an $M\times N$ i.i.d. Gaussian random measurement matrix requires generation of $O(KN)$ random elements and implementation of $O(KN)$ independent operations. However N is large enough to delay data acquisition and reconstruction time, which is rarely realized in VLSI digital hardware, and led to particularly trouble for large-scale applications.

While the deterministic measurement matrix has specific matrix value and fixed position, including Toeplitz and circulant matrices [9–12], sparse binary matrices [13], structurally random matrices [14], Chirp sensing codes [15], random convolution matrices [16], finite fields [17], and second order Reed-Muller [18], the most classic is Toeplitz matrix, which uses fast Fourier transforms (FFT) and, as a consequence, requires only $O(N)$ independent variables and $O(N\text{lo}{\text{g}}_{\mathrm{2}}(N))$ operations. More importantly, there are matrix-vector multiplication routines, which can be exploited in recovery algorithms. Furthermore, they arise naturally in certain applications such as identifying a linear time invariant system.

However, deterministic measurement matrix's unchanged element and fixed position result in three main limitations [19]. The first point is that incoherence criterion is hardly met. The second disadvantage is that the reconstruction precision of deterministic measurement matrix is obviously inadequate. Matrix building time being unbearable is the third failing.

To overcome those limitations, our intuitive idea is discrete chaotic system functions to generate a series of random elements in Toeplitz matrix. Then, a circulant/block-diagonal splitting structure is applied to speed up convergence rate. Based on these improvements, an improved Toeplitz-structured matrix is proposed to both improve reconstruction precision and reduce cost time.

Key contributions of this work can be elaborated as follows.

• (1)

  Discrete chaotic system function is proposed to generate a series of pseudo-random numbers. Based on those elements, Toeplitz-structured chaotic sensing matrix (TSCSM) is produced to guarantee the incoherence criterion.

• (2)

  To reduce the building time of TSCSM, circulant/block-diagonal splitting structure is attached on TSCSM. Although about one-third of matrix values are eliminated, ITMM is proved to satisfy Johnson-Lindenstrauss lemma (JL). We can take advantage of the equivalent relation between theorem JL and restricted isometric property (RIP); ITMM achieves the goal of satisfying RIP.

The rest of this paper is organized as follows. The mathematical model and analysis are described in Section 2. Based on the previous analysis, an improved Toeplitz-structured matrix is proposed in Section 3. Several comparative experiments are conducted for the conventional algorithms and the proposed method in Section 4. Discussion and conclusions are summarized in Section 5.

2. Mathematical Model

From the viewpoint of mathematics, CS is to consider the problem with far incomplete measurements as follows:

$$\begin{array}{cc}& y=\mathrm{\Theta }x=\mathrm{\Phi }\mathrm{\Psi }S.\end{array}$$

(1)

If $S\in {\mathfrak{R}}^{N\times \mathrm{1}}$ is a K-sparse one-dimensional signal and Ψ is the orthogonal basis being known, then finding a suitable $\mathrm{\Phi }\in {\mathfrak{R}}^{M\times N}\hspace{0.17em}\hspace{0.17em}M\ll N$ , which is the so-called CS measurement matrix, to obtain the goal of minimizing $M\times \mathrm{1}$ linear measurements y, as Figure 1 shows [1].

Figure 1

Measurement matrix from 1D signal.

The ill-posed problem appears from $M\ll N$ and unknown elements of measurement matrix Φ. So finding a proper measurement matrix Φ is quite a challenging problem. To solve the problem, Candès et al. [2] have proposed that if x is K-sparse and the K locations of the nonzero coefficients in S are known, then for any vector v sharing the same K nonzero entries as S and some ${\epsilon }_K$ > 0, be the smallest constant satisfying following inequality,

$$\begin{array}{cc}& \left(\mathrm{1}-{\epsilon }_K\right){\parallel v\parallel }_{\mathrm{2}}^{\mathrm{2}}\le {\parallel \mathrm{\Phi }\mathrm{\Psi }v\parallel }_{\mathrm{2}}^{\mathrm{2}}\le \left(\mathrm{1}+{\epsilon }_K\right){\parallel v\parallel }_{\mathrm{2}}^{\mathrm{2}}.\end{array}$$

(2)

The sufficient condition (2) is called restricted isometric property (RIP) [1].

That is to say, once orthogonal basis Ψ is known, CS measurement matrix Φ must be irrelevant to Ψ. Candès et al. [2] have demonstrated that an $M\times N$ i.i.d. Gaussian matrix $\mathrm{\Theta }=\mathrm{\Phi }\mathrm{\Psi }=\mathrm{\Phi }$ can meet RIP with high probability when $\mathrm{\Psi }=I$ and $M\ge cK\log (N/K)$ , where c is a small constant.

Specifically, assuming $Z_i$ is independent and identically distributed (i.i.d.) random sequence from Gaussian probability density function with mean zero and variance $\mathrm{1}/N$ , then the $M\times N$ partial Toeplitz measurement matrix Φ has the following form:

$$\begin{array}{cc}& \mathrm{\Phi }=\left[\begin{array}{cccc}{z}_N& z_{N-\mathrm{1}}& \cdots & z_{\mathrm{1}}\\ z_{N+\mathrm{1}}& z_N& \cdots & z_{\mathrm{2}}\\ ⋮& ⋮& \ddots & ⋮\\ z_{N+M-\mathrm{1}}& z_{N+M-\mathrm{2}}& \cdots & z_M\end{array}\right].\end{array}$$

(3)

Using fast Fourier transforms (FFT), Φ requires only $O(N)$ independent variables and $O(N\text{lo}{\text{g}}_{\mathrm{2}}(N))$ operations instead of $O(KN)$ random elements and $O(KN)$ independent operations from Gaussian measurement matrix. Consequently, it is often easily (or even naturally) realized in VLSI hardware.

Toeplitz matrix verifying RIP has two main limitations. One is a large amount of calculating the spectral norm of $C_N^M$ submatrices built by selecting M arbitrary columns from N dimensions. The other is difficult to validate these submatrices one by one whether satisfies RIP bounded condition.

Further research is being carried out to be closely linked to the famous Johnson-Lindenstrauss lemma [20, 21], which is extensively utilized in numerical linear algebra, machine learning, or other areas requiring dimension reduction.

Theorem (J-L Embedding with Beta-like Matrix): given a Beta-like matrix $\mathrm{\Phi }={\mathfrak{R}}^{m\times s}$ , there exists a constant ${\delta }_s>\mathrm{0}$ , such that, for any vector $u\in {\mathfrak{R}}^s$ , the following inequality $(\mathrm{1}-{\delta }_s){\parallel u\parallel }_{\mathrm{2}}^{\mathrm{2}}\le {\parallel \mathrm{\Phi }u\parallel }_{\mathrm{2}}^{\mathrm{2}}\le (\mathrm{1}+{\delta }_s){\parallel u\parallel }_{\mathrm{2}}^{\mathrm{2}}$ is satisfied with overwhelming probability.

Consider

$$\begin{array}{cc}& \text{Pr}\lfloor \left|{\parallel \mathrm{\Phi }u\parallel }^{\mathrm{2}}-\mathrm{1}\right|\ge {\delta }_s\rfloor \le \mathrm{2}\exp \left(-c\left({\delta }_s\right)m\right).\end{array}$$

(4)

Here $c({\delta }_s)$ is a constant related to ${\delta }_s$ . By the Egodicity property of the chaotic system, the theorem has been verified in [22]; different constant $c({\delta }_s)$ is equal to ${\delta }_s$ with Gaussian matrix.

3. The Proposed Approach

The challenge of optimizing Toeplitz measurement matrix is how to both improve its reconstructed precision and shorten its processing time. Based on above mathematical analysis, an improved Toeplitz-structured matrix is presented in this paper, as shown in Figure 2. In the first step, pseudo-random chaotic elements in a Toeplitz measurement matrix are selected to replace random elements. Next, circulant/block-diagonal splitting structure is employed as discussed in Section 3.2. Finally, an improved Toeplitz measurement matrix (ITMM) is shown in Figure 2 and proved that this matrix also retains the RIP property with overwhelming probability. See more details in Section 3.3.

Figure 2

The improved scheme by different methods.

3.1. Toeplitz-Structured Chaotic Sensing Matrix

In order to achieve the purpose of random Toeplitz matrix, pseudo-random chaotic sequences have been entirely replaced by random ones because of better randomness. Logistic map [22, 23], as the simplest dynamic systems evidencing chaotic behavior, is described as follows:

$$\begin{array}{cc}& x_{n+\mathrm{1}}=\mu x_n\left(\mathrm{1}-x_n\right),\hspace{1em}\text{with\hspace{0.17em}\hspace{0.17em}}\mu \in \left[\mathrm{0,4}\right],\hspace{0.17em}\hspace{0.17em}{x}_n\in \left[\mathrm{0,1}\right]\subset R,\end{array}$$

(5)

where $\mu \in (\mathrm{3.5699,4}]\subset R$ is the discrete state.

When parameter μ is 4, the sequence $x_n(t)$ satisfies beta distribution with $\alpha =\mathrm{0.5}$ and $\beta =\mathrm{0.5}$ ; the next probability density function $f(x;\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{0.5,0.5})=(\mathrm{1}/\pi )(x-x^{\mathrm{2}}{)}^{-\mathrm{1}/\mathrm{2}}$ has been used for simulation.

Set $z_i(t)$ as the output sequence generated by (5) with initial condition $z_i(\mathrm{0})$ , and let $x_i(t)$ denote the regularization of $z_i(t)$ as the following form:

$$\begin{array}{cc}& x_i\left(t\right)=z_i\left(t\right)-\mathrm{0.5},\hspace{1em}i=\mathrm{0,1},\mathrm{2}\dots .\end{array}$$

(6)

Approximately, $x_i(t)$ can be considered as random variable, and it satisfies the following distribution: $f(x)=(\mathrm{1}/\pi )(\mathrm{0.25}-x^{\mathrm{2}}{)}^{-\mathrm{1}/\mathrm{2}}$ . Then, by selecting m different initial conditions $z(\mathrm{0})\in [\mathrm{0,1}{]}^m\subset R^m$ , one can obtain m vectors with dimension R, which enables us to construct the following matrix Φ scaled by $\sqrt{\mathrm{8}/m}$ .

$$\begin{array}{cc}& \mathrm{\Phi }=\sqrt{\mathrm{8}/m}\left(\begin{array}{ccc}{x}_{\mathrm{0}}\left(\mathrm{0}\right)& \cdots & x_{\mathrm{0}}(n-\mathrm{1})\\ \cdots & \ddots & \cdots \\ x_m\left(\mathrm{0}\right)& \cdots & x_m(n-\mathrm{1})\end{array}\right).\end{array}$$

(7)

Here (7) is called the Beta-like matrix.

According to (7), set one initial condition $z\in (\mathrm{0})\in \mathfrak{R}$ , and generate a sequence $x\in {\mathfrak{R}}^n$ in the chaotic system. Then Toeplitz-structured matrix $\mathrm{\Phi }={\mathfrak{R}}^{m\times n}$ is constructed in the following form:

$$\begin{array}{cc}& \mathrm{\Phi }=\sqrt{\frac{\mathrm{8}}{m}}\left(\begin{array}{cccc}x(n-\mathrm{1})& x(n-\mathrm{2})& \cdots & x\left(\mathrm{0}\right)\\ x\left(\mathrm{0}\right)& x(n-\mathrm{1})& \cdots & x\left(\mathrm{1}\right)\\ ⋮& ⋮& \ddots & ⋮\\ x(m-\mathrm{2})& x(m-\mathrm{3})& \cdots & x(m-\mathrm{1})\end{array}\right).\end{array}$$

(8)

Here $\sqrt{\mathrm{8}/m}$ is for normalization and Φ is called Toeplitz-structured chaotic sensing matrix (TSCSM), which meets J-L theorem.

3.2. Circulant/Block-Diagonal Splitting Structure

If independent random elements are cut one third from either bevel edge band or column band in the measurement matrix, the overall amount of calculation can be saved more than one-third.

To reduce the amount of intensive computing from TSCSM, Toeplitz matrix Φ is divided into block-diagonal and skew-circulant part $\mathrm{\Phi }={\mathrm{\Phi }}_{\mathrm{1}}+{\mathrm{\Phi }}_{\mathrm{2}}$ . The skew-circulant part ${\mathrm{\Phi }}_{\mathrm{1}}$ is shown as (9).

Consider

$$\begin{array}{cc}& {\mathrm{\Phi }}_{\mathrm{1}}=\sqrt{\frac{\mathrm{8}}{m}}\left[\begin{array}{ccccccccc}x(n-\mathrm{1})& \cdots & x(l+\mathrm{1})& \mathrm{0}& \cdots & \mathrm{0}& x\left(l\right)& \cdots & x\left(\mathrm{0}\right)\\ x\left(\mathrm{0}\right)& x(n-\mathrm{1})& \cdots & x(l+\mathrm{1})& \mathrm{0}& \cdots & \mathrm{0}& \cdots & x\left(\mathrm{1}\right)\\ ⋮& ⋮& \ddots & \ddots & \ddots & \ddots & \ddots & ⋮& ⋮\\ x(m-\mathrm{2})& x(m-\mathrm{3})& \cdots & x(l+\mathrm{1})& \mathrm{0}& \cdots & \mathrm{0}& \cdots & \mathrm{0}\end{array}\right].\end{array}$$

(9)

In [24, 25], Φ satisfies J-L theorem, by the Egodicity property of the chaotic system; J-L condition can replace RIP condition. So Φ satisfies RIP property with overwhelming probability. According to the linearity property of Toeplitz measurement matrix, ${\mathrm{\Phi }}_{\mathrm{1}}$ satisfies J-L property with overwhelming probability. So ${\mathrm{\Phi }}_{\mathrm{1}}$ also satisfies RIP property with overwhelming probability.

3.3. ITMM Based on Recovery Algorithm

As to previously described, the recovery algorithm corresponding to ITMM is at least as important in the excellent sparse sampling system. Recently, recovery algorithms, typically, have three categories: linear programming (LP) [26], Basis Pursuit (BP) [27], Matching Pursuit (MP) [6, 28, 29]. Based on MP, it develops kinds of new methods: Orthogonal Matching Pursuit (OMP) [30], Regularized Orthogonal Matching Pursuit (ROMP) [31], Stage wise Orthogonal Matching Pursuit (StOMP) [32], Compressive Sampling Matching Pursuit, (CoSaMP) [33] and Optimized Orthogonal Matching Pursuit (OOMP) [34] for sparse signal approximation is an effective way. Software implementing this algorithm can be found in the SparseLab MATLAB software package [35].

A fused optimization method (ITMM + StOMP) is now presented. These main steps are as follows. Firstly, by selecting some particular elements in Toeplitz measurement matrix, discrete chaotic system function is employed to generate a series of random sequence. Secondly updating Toeplitz-structured matrix by reducing variable numbers, an improved Toeplitz-structured matrix (ITMM) is presented to find the sparse approximation solution and faster converge to this value in compressive sensing. Finally, under the same K-sparse degree, reconstructed 1D signal or 2D image is built up by stagewise orthogonal matching pursuit (StOMP) [32]. As is shown in Algorithm 1.

Algorithm 1: Final Algorithm: based ITMM reconstructed signal is built up by StOMP.

Input:

(1) Number of iterations S to perform;

(2) Threshold value $t_s$ ;

(3) $y\in {\mathfrak{R}}^m$ and the measurement matrix $y\in {\mathfrak{R}}^m$ ;

Start:

 (a) generate a series of random sequence $x_i(t)$ ;

 (b) construct Toeplitz-structured matrix Φ;

 (c) reduce partial random variables ${\mathrm{\Phi }}^{\mathrm{*}}$ ;

 (d) Initialize $r^{\mathit{0}}=x$ , $y^{\mathit{0}}=\mathit{0}$ , ${\mathrm{\Gamma }}^{\mathit{0}}=\varphi$ ;

 (e) for $\mathrm{n}=\mathrm{1,2},\dots ,\mathrm{S}$ do:

    $g^n={{\mathrm{\Phi }}^{\mathrm{*}}}^T{r}^{n-\mathrm{1}}-y^n$ ;          Residual

    $i^n=\underset{i}{\arg \max }(\left|g_i^n\right|>t_s)$ ;        Select components larger than the threshold $t_s$

    ${\mathrm{\Gamma }}^n={\mathrm{\Gamma }}^{n-\mathit{1}}\cup i^n$ ;              Projection

    $d_{{\mathrm{\Gamma }}^n}={\left({{\mathrm{\Phi }}^{\mathrm{*}}}_{{\mathrm{\Gamma }}^n}^T{\mathrm{\Phi }}_{{\mathrm{\Gamma }}^n}^{\mathrm{*}}\right)}^{-\mathrm{1}}$ ;

    $c^n={\mathrm{\Phi }}_{{\mathrm{\Gamma }}^n}^{\mathrm{*}}{d}_{{\mathrm{\Gamma }}^n}$ ;

    $y_{{\mathrm{\Gamma }}^n}^n:=y_{{\mathrm{\Gamma }}^n}^{n-\mathrm{1}}+{\mathrm{\alpha }}^n{d}_{{\mathrm{\Gamma }}^n}$ ;

    $r^n=r^{n-\mathrm{1}}-{\mathrm{\alpha }}^n{c}^n$ ;

  end for

 (f) Return $\widehat{\mathrm{x}}=r^S$ , $y^S$ .

Output:

$\mathrm{x}\in {\mathfrak{R}}^n$ Such that x is s-sparse and $y=\mathrm{\Phi }\mathrm{x}$ .

4. Experiments and Result Analysis

In this section, all existing state-of-the-art measurement matrix (Gaussian, partial Fourier, Hadamard, circulant, and Toeplitz) size is turned into 64 × 256 pixels, signal sparsity method is DCT, and reconstruction algorithm is StOMP. We first carried out 1D random signal experiments to investigate the efficiency of the proposed approach. Subsequently, we report the results for the classical 2D test images. Finally, prototype onboard recovery system is stimulated by the proposed approach. All these algorithms are implemented using Matlab 7.10 on a laptop with Athlon, Processor 1.60 G HZ, 1 GB RAM, and Windows XP operation platform.

4.1. The 1D Random Signal Experiment

If the 1D signal amplitude becomes $\mathrm{0.3}\sin (\mathrm{2}\pi f_{\mathrm{1}})+\mathrm{0.6}\sin (\mathrm{2}\pi f_{\mathrm{2}})+\mathrm{0.1}\sin (\mathrm{2}\pi f_{\mathrm{3}})+\mathrm{0.9}\sin (\mathrm{2}\pi f_{\mathrm{4}})$ , where $f_i$ size varies from 50 Hz to 400 Hz in intervals of 50, sampling period is 1/800, and sampling signal number is 256, all testify experiment results of recovery 1D signals by StOMP and their amplification part are shown in Figure 3.

Figure 3

Recovery 1D random signal (a) original (b) amplification part.

Figure 3 features the recovery performance for 1D random signal by different measurement matrix. It is clear from Figure 3 that recovery curve from Gaussian (black line), partial Fourier (blue line), Hadamard (red line), circulant (yellow line), and Toeplitz (green point line) has a great deviation from the original curve (red block line). All recovery curves from the proposed approach (black point line) have both black point fallen into red block from the original curve and occupied the original curve accurately. Furthermore, the objective evaluation, including signal-to-noise ratio (SNR) and cost time (Time), is shown in Table 1.

Table 1

SNR and times (sec) of recovery of the original 1D random signal.

Algorithm	Original 1D random signal
	SNR	Time
Gaussian	$\mathit{7.0210}e-\mathit{014}$	0.0411
Partial Fourier	0.5000	0.0342
Hadamard	0.9853	0.0402
Circulant	1.0770	0.0406
Toeplitz	1.1556	0.0256
ITMM	1.2785	0.0232

Table 1 shows detailed recovery performances and cost time for all of the six measurement matrixes. In Table 1, we show the recovery performance for ITMM is better than that obtained by the other five measurement matrixes. And computational cost time is the shortest among the six measurement matrixes. Thus, we can use only ITMM to both decrease computational cost and maintain the performance.

4.2. The 2D Classical Test Images Experiment

To verify the proposed approach, the size of all classical test images, including Lena, Cameraman, Couple, Face, and Brain, obtained at http://decsai.ugr.es/cvg/dbimagenes/, is adjusted to 256*256, while all images are divided into 16*16 blocks, and sample rate (M/N) is set as 0.6.

Figures 4, 5, 6, 7, and 8 compare our proposed method with the other four measurement matrixes (Gaussian, Hadamard, circulant, and Toeplitz). In the experiment, we can see that the performance of Hadamard measurement matrix is inferior to the other measurement matrixes for all five classical test images. The difference between the performances of circulant and Toeplitz measurement matrix is not salient. The performance of Gaussian measurement matrix is surprisingly close to that of our proposed method. It is far from enough to only rely on the experiences of the individual but not on systematic, objective, and accurate method. The objective evaluation is necessary to correctly estimate these various measurement matrixes, including mean squared error (MSE) and cost time (CT). See more details as Table 2 shows.

Table 2

MSE and times (sec) of different matrices of recovery of the original 2D tests images.

Algorithm	Classical 2D test images
	Lena		Cameraman		Couple		Face		Brain
	MSE	Time	MSE	Time	MSE	Time	MSE	Time	MSE	Time
Hadamard	129.1	48.5	114.5	48.27	128.1	47.84	138.3	47.23	52.5	41.18
Circulant	65.3	41.16	45.7	41.70	62.2	40.61	59.5	40.31	27.8	35.44
Toeplitz	65.4	37.32	46.2	37.43	163.4	37.69	62.7	36.35	29.1	31.36
Gaussian	42.2	41.22	48.7	40.45	42.6	45.66	39.4	39.85	23.7	37.87
ITMM	36.5	35.98	38.5	36.1	33.6	36.07	28.8	35.42	20.8	30.12

Figure 4

Recovery Lena by (b) Gaussian, (c) Hadamard, (d) circulant, (e) Toeplitz, and (f) ITMM.

Figure 5

Recovery Cameraman by (b) Gaussian, (c) Hadamard, (d) circulant, (e) Toeplitz, and (f) ITMM.

Figure 6

Recovery Couple by (b) Gaussian, (c) Hadamard, (d) circulant, (e) Toeplitz, and (f) ITMM.

Figure 7

Recovery Face image by (b) Gaussian, (c) Hadamard, (d) circulant, (e) Toeplitz, and (f) ITMM.

Figure 8

Recovery Brain by (b) Gaussian, (c) Hadamard, (d) circulant, (e) Toeplitz, and (f) ITMM.

As shown in Table 2, the objective evaluation criteria (MSE and CT) are achieved by several state-of-the-art methods and our approach with Lena, Cameraman, Couple, Face, and Brain data sets. From the bold numbers, we can draw the conclusion that our approach method outperforms the existing state-of-the-art method.

4.3. Prototype Recovery System Experiment

A prototype onboard recovery, which is only fabricated by Toeplitz and its improvement, is one of the applications from CS Technology. Figure 9 shows the prototype recovery engine (RE) board and final recovery result. It is composed of 8*16 standalone REs each with the ability to recover spectral vectors in parallel. These are autonomous devices programmed to perform recovery in continuous mode, subset by subset. An RE is composed of a field programmable gate arrays (FPGAs) chip. It took a half second for the prototype to recover, while a powerful computer platform would take a few minutes to reconstruct. The throughput can be increased by using more CEs in parallel. The experimental results showed that MSE and fidelity achieved by the prototype recovery are similar to those obtained by software simulation.

Figure 9

Recovery Lena image by FPGA (a) Matrix grayscale, (b) standalone RE, and (c) final result.

5. Conclusions

In summary, an optimization method is proposed on Toeplitz-structured chaotic sensing matrix with circulant/block-diagonal splitting structure. It has retained the RIP property with overwhelming probability and decreased time consumption to the largest extent. We demonstrate that the proposed method has the most significant recovery performance in 1D and 2D input signal sources. And prototype recovery system is built by FPGA, whose fidelity is similar to those obtained by software simulation. Therefore, we believe that this framework gives an unconventional way to solve the optimization problem of deterministic measurement matrix and will vastly and widely benefit large-scale applications and is realized in VLSI hardware.