Compressed Sensing Technology for Flexible Wireless System

2.1 Basic concept

A simplified explanation of compressed sensing is as follows: A signal projected linearly onto a lower-dimensional space can be used to reconstruct the original higher-dimensional signal with high probability if the signal is sparse (explained in section 2.2) and the projection matrix satisfies the restricted isometry property (RIP, explained in section 2.4).

In a mathematical sense, compressed sensing can be stated as an ill-posed inverse problem. Normally, the solution of an ill-posed inverse problem is not uniquely determined because the number of equations is smaller than the number of variables. However, the solution of an ill-posed inverse problem can be uniquely determined by investigating all possible cases provided that the signal is sparse. Moreover, if an ill-posed inverse problem satisfies RIP and the signal is sparse, the unique solution can be found with a practical degree of complexity.

For an intuitive understanding of compressed sensing, consider the following simple ill-posed inverse problem.

Find m, n, and k such that

m + 3n - 2k = 1

-m – n + k = -1

Normally, the solution is not uniquely determined because the number of equations is smaller than the number of variables. However, if vector [m k n] has only one nonzero element, the unique solution can be obtained by investigating all possible cases, as below.

case 1) m≠0, n=k=0 -> m=1 (unique solution)

case 2) n≠0, m=k=0 -> impossible

case 3) k≠0, m=n=0 -> impossible

Although the unique solution is available, this is an NP-hard problem for which all possible cases must be investigated. Consequently, it becomes impractical as the number of dimensions of the signal increases.

This impracticality is overcome if the equation vector [1 3 -2; -1 -1 1] satisfies RIP. The core achievement of compressed sensing is that the above NP-hard problem can be cast into an l1-norm minimization problem (explained in section 2.5) if the signal is sparse and RIP is satisfied. L1-norm minimization problems can be solved by linear programming, which is a well established convex optimization method, with practical complexity O(n³) [5], [6].

Considering the above example, the following two statements can be made: First the sparsity of the signal assures the unique solution for compressed sensing. Second, RIP assures a practical degree of complexity for finding the unique solution for compressed sensing.

2.2 Sparse signal

A signal is called sparse when it is represented by a small number of nonzero coefficients in any convenient domain. More specifically, N×1 signal X is called S-sparse if X is represented by the multiplication of any N×N transform matrix Ψ and N×1 coefficient vector s, and s has only S nonzero coefficients. The definition of sparsity is not limited to the orthogonal transform domain (i.e., Fourier transform or wavelet transform). If a signal is represented in a non-orthogonal domain, including any user-defined domain, the signal is also called sparse [7].

2.3 Measurement

For a given N×1 signal X, measurement is defined as the linear projection of X onto M×1 signal Y. The M×N matrix Φ that casts X onto Y is called the measurement matrix. Matrix description is given by Y=ΦX. If X is represented by N×1 coefficient vector s in the N×N transform domain Ψ , it is expressed as Y=ΦΨs.

The number of measurements is the number of rows in the measurement matrix (M), which is also equivalent to the number of dimensions of the output signal. Therefore, the compression rate increases as the number of measurements increases. Numerous studies have been performed to investigate the minimum bound of the necessary number of measurements for a given signal sparsity [8 and references therein]. It has been shown that S•log(N/S) measurements are enough for the reconstruction of an S-sparse signal when measurement matrix Φ consists of random ensembles [9].

2.4 RIP

The most outstanding achievement of compressed sensing is the fact that RIP casts an NP-hard problem onto an l1-norm minimization method [10], [11].

When an M×N measurement matrix Φ and a N×N transform domain matrix Ψ satisfy the following inequality for all S-sparse vectors, matrix Θ(=ΦΨ) is said to obey RIP of order S with δ.

(1-δ)||s||₂² ≤||ΦΨs||≤(1+δ)||s||₂²

where ||s||₂=Σ_i s_i² and δ(0 ≤δ <1) is the smallest constant that satisfies the above inequality.

An intuitive explanation of RIP is as follows: the Euclidian distance between any two N×1 S-sparse vectors is approximately preserved after the measurement as long as Θ obeys RIP.

It has been proven that RIP is satisfied if measurement matrix Φ consists of random ensembles, which yields the following surprising result: any unknown sparse signals can be reconstructed by random measurement [10]. This property provides flexibility for the compression of an unknown signal because signal-independent measurement is possible by the random measurement as long as the signal is sparse.

2.5 Reconstruction

Reconstruction of the compressed sensing refers to finding N×1 S-sparse vector s from known M×1 measurement output matrix Y, M×N measurement matrix Φ, and N×N transform matrix Ψ when Y=ΦΨs (S<M<<N). Reconstruction of the original signal s can be found via the l1-norm minimization problem, as described below, as long as RIP is satisfied.

min||s^ˆ||₁ subject to Y=ΦΨs^ˆ, s^ˆ∈R^N,

if RIP satisfies s^ˆ=s,

where ||s^ˆ||₁=|s₁|+|s₂|+...|s_N| and R^N is the set of N×1 vector.

The l1-norm minimization problem finds s^ˆ that minimizes the l1-norm subject to Y=ΦΨs^ˆ among all possible S-sparse vectors. This seems to be an NP-hard problem, but it can be cast into a convex optimization problem and solved by the linear programming method. Furthermore, if RIP is satisfied, s^ˆ is identical to the original vector s with high probability [10], [11].

If the measurement matrix consists of random ensembles, flexible reconstruction is possible. In the case that signal X is proved to be more sparsely represented in another basis matrix Ψ’, surprisingly, one does not need to conduct the measurement again since the l1-norm minimization problem can be solved with Y and a new Θ’(=ΦΨ’). This indicates that once the projection has been performed, the reconstruction can be performed with any convenient basis matrix.

There are other approaches to the reconstruction of compressed sensing such as an orthogonal matching pursuit algorithm, which uses a greedy iterative algorithm [12].

2.6 Comparison between conventional compression and compressed sensing

The difference between the conventional compression and compressed sensing is shown in Fig. 2. The conventional sample-then-compress method compresses the signal by the signal-specific compression method, which yields the optimal compression (S dimensions). On the other hand, compressed sensing conducts a signal-independent linear projection of the original signal onto a lower-dimensional space (M-dimensional, S<M<<N), which yields poor compression performance. Therefore, it can be stated that the conventional compression method is superior to compressed sensing for the known signals in terms of compression performance.

Fig. 2. Comparison between conventional compression and compressed sensing.

However, compressed sensing has the following advantages compared with the conventional compression method. First, it is suitable for dealing with an unknown sparse signal. Second, it is robust to the introduction of new types of wireless systems. When new types of wireless systems are introduced, receivers (flexible access points in Fig. 1) do not need to be modified because the signal-specific processing burden is moved from the receivers to the server (flexible signal processing unit in Fig. 1). Third, it reduces the burden on receivers. For example, consider a sparse signal of unknown frequency. In the case of the conventional sampling method, receivers must conduct both a fast Fourier transform and a search for nonzero coefficients. On the other hand, in the case of compressed sensing, receivers only need to conduct a linear projection.

3.1 Combined Nyquist and compressed sampling

The goal of this sampling method is to achieve Nyquist-rate sampling of the known signal (hereinafter called the decoding signal) and compressed-rate sampling of the unknown signal (hereinafter called the sensing signal) in a single analog-to-digital converter. To achieve this goal, the following processes are carried out.

At each flexible access point, multiple signals are simultaneously received, filtered, and down-converted to the intermediate frequency (IF) band. In particular, decoding signals are converted to a lower center frequency band than sensing signals, as shown in Fig. 3. Signal down-conversion is done by tunable local oscillators and mixers. All down-converted signals are sampled by our method and transferred to the flexible signal processing unit.

Fig. 3. Example of frequency alignment of multiple signals.

Details of the combined Nyquist and compressed sampling method are as follows. Suppose that L decoding signals and M sensing signals are aligned in the IF band, and the total bandwidths of these signals are represented by B_dec and B_sens, respectively. For the convenience of the explanation, B_grid and B_Nyq are defined as (4B_dec+2B_sens) and (2B_dec+B_sens), respectively. The purpose of the above setting is to achieve (1) Nyquist-rate sampling of the decoding signals without aliasing from the sensing signals and (2) compressed-rate sampling of the sensing signals in a single analog-to-digital converter simultaneously.

The detailed procedure of our method is as follows. First, B_grid-rate sampling is conducted. Second, only some of the even (odd) samples are randomly discarded while all of odd (even) samples are preserved. The locations of randomly discarded samples, which are determined by the random sequences generator, can be known to the flexible signal processing unit if the initial seed of the random sequence generator is shared. Hereinafter, all the odd samples and the remaining even samples are called fixed samples and random samples, respectively. They are transferred to the flexible signal processing unit via the wired access line.

The mathematical description of our method is as follows. For simplicity, we consider multiple sparse signals in the frequency domain. The IF band signal X=(Ψs) is sparsely represented in the frequency domain. The basis matrix Ψ is an N×N inverse Fourier transform, and s is the N×1 coefficient vector of X in the frequency domain. Note that s has sequential nonzero values in the lower frequency region and randomly sparse nonzero values in the higher frequency region (e.g., s=[1111100100010001]). The K×N projection matrix Φ has the following sparse representation.

Note that each column indicates a sample point of the signal. Every odd sample is preserved while some of the even samples are randomly discarded.

Then, the compressed sensing matrix Θ(=ΦΨ) becomes a K×N matrix consisting of every odd row and randomly selected even rows of the inverse Fourier transform matrix. Projection vector Y is represented by Θs and signal reconstruction becomes the inverse problem of s =Θ^-1Y. This inverse problem is solvable as an l1-norm minimization problem because s is sparse and Θ consists of randomly selected rows of the inverse Fourier transform matrix^*.

Using transferred fixed and random samples from flexible access points, the flexible signal processing unit conducts the decoding and sensing process as follows.

First, the decoding signals are decoded using only fixed samples, which is equivalent to B_Nyq-rate sampling. Note that aliasing of the sensing signals occurs because the sampling rate is insufficient. However, it does not cause interference with the decoding signals. Therefore, the decoding signals can be decoded by using conventional decoding algorithms without aliasing. An example of fixed samples in the frequency domain is shown in Fig. 4. Although the aliasing of the sensing signals occurred owing to the insufficient sampling rate, the decoding signal parts are intact. Consequently, Nyquist-rate decoding performance is achieved for the decoding signals. Second, the decoding signal is subtracted from both the fixed and random samples. Third, the sensing signals are reconstructed using both fixed and random samples, whose decoding signals have been subtracted. The reconstruction is done by solving the l1-norm minimization problem. An example of the reconstructed signal in the frequency domain is shown in Fig. 5. Note that only sensing signals are reconstructed because the decoding signals have been removed. Fourth, the sensing signals are identified in the reconstructed signal by a conventional spectrum sensing algorithm such as energy detection.

Fig. 4. Frequency domain representation of fixed samples.

Fig. 5. Frequency domain representation of sensing signals reconstructed from fixed and random samples after subtraction of the decoding signal.

Some experimental results are shown in Figs. 6 and 7. Experiments were performed on 310-MHz-band frequency shift keying (FSK) signals transmitted by radio frequency identification (RFID) tags. The RFID tag bandwidth and the total bandwidths of decoding signals and sensing signals were 0.3, 1.73, and 6.54 MHz, respectively. The channel between the RFID tags and a flexible access point was a non-fading additive white Gaussian noise channel.

Fig. 6. Symbol error rate comparison.

Fig. 7. Probability of detection success.

Figure 6 compares the theoretical and experimental symbol error rates for the decoding signal in terms of Es/No (energy per symbol per noise power spectral density). In the experiment using the conventional method, only the down-converted decoding signal was sampled at the Nyquist rate. In the experiment using our method, the decoding signal and the sensing signals were combined in the IF band and sampled by using our method. The performance curve for our method matches those for the theoretical and conventional methods well, which shows that our sampling method guarantees Nyquist-rate decoding performance for the decoding signal.

The detection success rate is shown in Fig. 7. All curves show relatively poor performance at a low compression ratio. This is because reconstruction fails if the number of samples is insufficient. However, P_d (detection success rate) increases with the compression ratio. Approximately, 70% of the compression ratio can be achieved when E_s/N_o is higher than 17.5 dB.

3.2 Compressed sensing with weighted measurement matrix

Our goal for the weighted measurement matrix generation is to reduce the required number of measurements by using prior knowledge of the signal.

A block diagram of compressed sensing with weighted measurement matrix generation is shown in Fig. 8. The weighted measurement matrix is generated by multiplying the random measurement matrix and weight matrix, where the weight matrix is generated taking into consideration prior knowledge such as the signal’s history. Note that identical weighted and random measurement matrices are generated by both the flexible access points and the signal processing unit for the reconstruction. If the weight needs to be updated, necessary parameters are transmitted from the signal processing unit to the flexible access points.

Fig. 8. Block diagram of compressed sensing with weighted measurement matrix generation.

To verify the efficiency of this method, we conducted an experiment using an RFID signal consisting of a periodically transmitted FSK signal. The total bandwidth and the received signal bandwidth were 5 and 0.6 MHz, respectively. The time occupancy rate of the received signal was 0.25. Therefore, the time-frequency domain signal sparsity was 0.03. The time and frequency domain weights were set to 2.0 and 1.5 using the signal reception history. The detection success rates for the conventional method and our method are compared in Fig. 9. The compression rates needed for perfect signal detection were 0.13, 0.12, 0.09, and 0.08, respectively, when the applied weights were no weight, time domain weight, frequency domain weight, and time-frequency domain weight. These results confirm that enhanced compression is achieved by our method.

Fig. 9. Probability of detection success.