Sub-Nyquist sampling for short pulses with Gabor frames

Sub-Nyquist sampling, which can acquire signals even at very low sampling rate and yet maintain high approximation precision, has been developed over the past years to process certain signal models [1]. Unlike the traditional sub-Nyquist methods such as demodulation, under sampling ADC, and periodic nonuniform sampling, Xampling originates from CS theory (compressed sensing) and ends up in some less sophisticated front-end hardware [2‐5]. Until now, a variety of different applications of Xampling is developed for multipulse signals, such as radar signals [6, 7], ultrasound signals [8], and certain signals prevalent in smart power system [9, 10] and smart city [11, 12]. However, all the applications are based on finite-rate-of-innovation (FRI) signals sampling [13, 14], and the pulse shape should be a priori known. Gabor frame sub-Nyquist sampling is proposed for making up for the weakness of FRI signals sampling and can acquire both location and shape information for multipulse signals [15]. Unlike the FRI signals sampling, which just collects the signal Fourier coefficients and reconstruct original signal with kernel functions, it operates short-time Fourier transform on signal and collects the Gabor time-frequency coefficients. Structurally, Gabor frame sub-Nyquist sampling scheme gets a little more closer to the time domain edition of modulated wideband converter (MWC) [16], which cuts the frequency domain into many lattices and measures the linear compressive translations [17]. It cuts the time domain with modulated window sequences, namely Gabor frames, and recovers exact time locations and shape with CS algorithms.

We focus here on a class of multipulse signals, which have limited time duration and short pulses with arbitrary shapes and positions, and may even overlap. The only parameters assumed are the duration T, the number N _p of pulses, and the maximal width W. The multipulse signal, x(t), supported on the interval [−T/2, T/2], which can be expressed as

If ϵ _Ω  < 1, a signal with ϵ _Ω —bandlimited to F = [−Ω/2, Ω/2], named as essential band, is defined aswhere \( \widehat{x}(if) \) denotes the Fourier transform of x(t) and the symbol F ^c the complement of the set F.

Theoretically, all square-integrable time-limited signals can be well approximated by truncated Gabor series. Under Gabor sampling scheme, the sampling rate equals 1/T and the sampling number is about only 4μ ^− 1 Ω′WN _p , where Ω′ is related to the essential bandwidth of the signal and μ ∈ (0, 1) is the redundancy of the Gabor frames used for processing. The sampling scheme in [15] is demonstrated to possess great reconstruction performance with time domain modulation measurement functions constructed by Bernoulli random matrix and Gabor window sequences, such as piecewise spline or B-spline window sequences. Unfortunately, there still exists a gap between the theory and practice, because the shifting Gabor windows modulated by random measurement matrix is hard to be realized with simple circuit, and its complexity and synchronization precision also greatly affect the reconstruction performance.

The first and main contribution of this paper is introducing the exponential reproducing windows into Gabor sampling scheme and reducing the time domain modulation functions, constructed by appropriately weighted window sequences, to simple exponential functions. The time domain modulation functions of this study can avoid holding complicated function structures and intricate system functions, which are difficult to realize in real world. Any time domain response function from E-spline system could be defined as exponential reproducing function, the simplest one being E-spline itself [18]. Interestingly, with appropriate weighting coefficients, the exponential reproducing window sequences can be synthesized to a simple exponential function. It could be viewed as the impulse response representation of an exponential filter, which can be carried out with simple passive electric circuit [19, 20]. For this study, we deduced the representation of the filter form of the time domain modulation functions in Gabor sampling scheme and chose the appropriate E-spline parameter vector α for guaranteeing the window positive real functions. Then, we constructed the measurement matrix for CS recovery and calculated each entry and proved that such measurement matrix has better coherence than that of DFT matrix. Hence, the measurement matrix satisfies the RIP, making it possible to recover the sparse Gabor coefficient matrix perfectly.

Next, we study the effect of frame window width W _g on the signal reconstruction performance. In [15], the frame window width is the same as the pulse width of the signal to be measured and the Gabor frames is not quite redundant. So the sparsity S of the Gabor coefficients recovered for signal representation is very small and the column dimension to row number ratio r of the measurement matrix is large enough to result in good RIP. However, to ensure enough sampling channel number in the sampling scheme proposed here, the E-spline smoothness order N should not be too small. According to [21], if N is large, which means the frame windows are high order exponential reproducing windows, the frames will be very redundant, and so the RIP may be hard to be satisfied [22]. In this study, we find that, for neutralizing the disadvantage caused by the redundancy, the frame windows width W _g could be stretched wider to bring down S and increase r, enhancing the measurement matrix RIP. Then, we deduce the signal reconstruction error bound, proving that it is effective for improving signal reconstruction performance.

As a third contribution, we study the robustness of the proposed sampling scheme. We deduce the signal reconstruction error bound with noise injected to the sampling scheme. From the error bound representation, we discover that when N is raised to a bigger number, the redundancy would be μ ≪ 1, which enables the Gabor frames to hold good robustness. If the sampling channel numbers are the same, our sampling scheme can suppress noise better than in [15].

We now present a sampling scheme with exponential reproducing windows that can greatly simplify the time domain transform function s _m (t) using the exponential reproducing property. Primarily, compared with the time duration [−T/2, T/2] set in [15], shifting the time duration to a complete positive scope [0, T], E-splines are generally defined in a positive domain. For short pulse stream, it satisfies that WN _p  ≪ T and matrix Z is sparse.

In sampling scheme, K is the dimension of vectors Z[l], where there exists \( K=\left\lceil \frac{T+{W}_g}{W_g} N\right\rceil + N-1 \) from Eq. (12). Here, we represent window width as W _g  = ζW, ζ ≥ 1, then \( a=\zeta W/ N\mathrm{and} K=\left\lceil \left(\frac{T}{\zeta W}+2\right) N\right\rceil -1 \). We can see that the larger the ζ is increased, the smaller the K is. In [15], there exists W _g  = W, and so \( {K}^{\prime }=\left\lceil \left(\frac{T}{W}+2\right) N\right\rceil -1 \). For T ≫ W, we can greatly reduce K by this way.

In another parameter, the sparsity is represented as \( S=\left[\frac{W_g+ W}{a}{N}_p\right] \). As discussed in [15], W _g  = W and S = [2μ ^− 1] = 2N _p N. Here, forming W _g  = ζW, we get \( S=\frac{\zeta +1}{\zeta}{N}_p N\le 2{N}_p N \). If W _g  ≫ W, S ≈ [μ ^− 1]N _p  = N _p N. As we can see, wider window width also means smaller sparsity S.

For more accurate analysis, we take a good property of E-splines into account: the higher the order N, the more the energy is centralized to a shorter time domain support [18]. Here, introducing the concept of “essential frame windows width,” we say that φ(t) has ϵ _W -essential window width W _E  = |T _E |, when T _E  = [t ₁, t ₂], where 0 ≤ t ₁ < t ₂ ≤ W _g . Defining \( {T}_{E1}^c=\left[0,{t}_1\right] \), \( {T}_{E2}^c=\left[{t}_2,{W}_g\right] \), if for some ϵ _W  < 1

With the increase in the order N, the ϵ _W -essential windows width W _E gets shorter. Defining essential window width factor η = W _E /W _g , we can measure precisely how much of the window width has been cut down, with the reserved part still holding most energy. When the order N of E-spline is high enough, the essential window width factor η becomes very small, whereas stricter ϵ _W means wider scope of permissible η. Based on the foregoing assumption, the sparsity can be described as \( S=\left[\frac{W_E+ W}{a}{N}_p\right]=\frac{\eta \zeta +1}{\zeta}{N}_p N \).

Then, the practical sparsity get smaller. As a result, to ensure that C satisfy RIP, we need \( M= O\left(\frac{\eta \zeta +1}{\zeta}{N}_p N{ \log}^4\left( TN/\zeta W\right)\right) \). Note, in this study, M = N. So, for perfect subspace detection, if there exists constant C ^' > 0, the following equation must be satisfied:

For matrix C, the ratio \( \raisebox{1ex}{$ M$}\!\left/ \!\raisebox{-1ex}{$ K$}\right.\approx \raisebox{1ex}{$\zeta W$}\!\left/ \!\raisebox{-1ex}{$ T$}\right. \) is mainly decided by ζ. So, larger ζ means C has better orthogonality and better RIP. In addition, if we enlarge ζ, Eq. (23) is easier to be satisfied. As the channel number of the sampling scheme is decided by M, we can increase N to acquire more measured samples, which means better reconstruction performance. As η and N are inversely correlated in Eq. (23), sometimes we need not to worry that N is too large to prevent Eq. (23) from being satisfied.

Next, we will analyze the effect of stretching the frame windows width on the signal reconstruction error. First, we offer a lemma here.

According to the definition of Segal algebraic space, for any g(t) ∈ S ₀, \( {\left\Vert g(t)\right\Vert}_{S_0}<\infty \) is able to be satisfied under condition 0 < ζ < ∞. So \( {\left\Vert g\hbox{'}(t)\right\Vert}_{S_0}=\zeta {\left\Vert g(t)\right\Vert}_{S_0}<\infty \) and g(t/ζ) ∈ S ₀. Prove up.

According to the lemma, if the windows are stretched ζ times, the S ₀-norm is proportional to the stretching factor. What is surely guaranteed is that the S ₀-norm does not relate to the size of the grid in time and frequency plane and the redundancy. Consequently, we can propose the following theorem about the signal reconstruction error bound.

The proof is rooted [15] with appropriate adjustments according to Lemma 1.

Theorem 2 shows that the reconstruction error is comprised of two parts. The first part comes from Gabor series truncating and window cutting. For Gabor windows g(t) supported on a quite short time interval, \( {C}_{\zeta}\approx {\left(1+\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$\zeta WN$}\right.\right)}^{\frac{1}{2}}\gg 1. \). With ζ increasing, C _ζ decreases evidently and C ₀ is brought down. Meanwhile, the higher the E-spline smoothness order N is, the smaller C _ζ is, which results in the error reduction. The second part ζ comes from subspace detection error. As analyzed, larger ζ means that C has better RIP, which can also decrease the error. So, we can reduce the signal reconstruction error bound by enlarge window width.

The total number of Gabor coefficients is related to a somewhat larger interval [0, T ^'], where T ^' = T + 2ζW, with \( K\approx \raisebox{1ex}{${T}^{\hbox{'}} N$}\!\left/ \!\raisebox{-1ex}{$\zeta W$}\right. \) in time domain, and [0, Ω ^'], where \( {\varOmega}^{\hbox{'}}=\varOmega +\raisebox{1ex}{$ B$}\!\left/ \!\raisebox{-1ex}{$\zeta $}\right. \), with L ≈ ζWΩ ^' in the frequency domain. Overall, the required number of samples is \( K L\approx \frac{T^{\hbox{'}} N}{\zeta W}\zeta W{\varOmega}^{\hbox{'}}={T}^{\hbox{'}}{\varOmega}^{\hbox{'}} N \). To decrease KL further, b can be maintained constant at \( b=\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$ W$}\right. \). Then L ≈ WΩ ^' and the size of matrix Z becomes \( K L\approx \raisebox{1ex}{${T}^{\hbox{'}}{\varOmega}^{\hbox{'}} N$}\!\left/ \!\raisebox{-1ex}{$\zeta $}\right. \). By this method, if ζ is big enough, the calculation load can be greatly reduced. Reducing Gabor coefficient numbers may enlarge the error bound, but we still can acquire acceptable error with suitable factor ζ.

All the signals, hitherto considered for sampling, were noise-free or exactly multipulse. But when the signals to be measured are noisy, according to [15], the Gabor sampling scheme is robust to bounded noise in both the signal and the samples. Here, we will study the robustness of the sampling scheme proposed in this paper.

The signals are limited to the interval [0, T], which means the noise or the energy leaks between the pulses are also limited. As a result, the column vectors Z[l] are no longer sparse. Nonetheless, according to earlier analysis, Z can be well approximated to a sparse Z, which consists of |Λ| rows of Z with largest l ₂ norm, and zeros, otherwise referred to as the best |Λ|-term approximation. If the indice sets Λ is complete, |Λ| = S. Then, Eq. (7) can be written as

With D having a full column rank, the relation to Eq. (25) can be reduced to U = CZ + N, where N = D ^† N′. By utilizing CS algorithms, Z ^' can be resolved well even with noisy terms, and the following inequality, satisfying [25]:where C ' ₁ and C ' ₂ are constants depending on the RIP constant δ _2S of C. Then, according to Theorem 2, we can deduce the error bound as follows:where C ₀ is the same as that in Theorem 2, while \( {C}_1=\eta \zeta {\overline{C}}_{\zeta}{C}_1^{\prime}\parallel \gamma {\parallel}_{S_0} \) and \( {C}_2=\eta \zeta {\overline{C}}_{\zeta}{C}_2^{\prime}\parallel \gamma {\parallel}_{S_0} \).

Here, the third part of the error bound comes from the noise. As analyzed above, increasing ζ and N is also beneficial to bring down C _ζ and minimize the impact of the noise. What is more, with increase in the smoothnees order N of the windows, the norms \( {\left\Vert g\right\Vert}_{S_0} \) and \( {\left\Vert \gamma \right\Vert}_{S_0} \) decrease rapidly, which is able to make the error bound going down as well. To the contrary, if we increase N, the RIP of C may get worse, and C ^' ₂, which is the convergence factor for the noise, may be enlarged. Then, the noise suppression generated by the CS iteration will be weak. However, comparing the variation trends of the several factors following N, C _ζ and \( {\left\Vert \gamma \right\Vert}_{S_0} \) play a leading role on improving the sampling scheme robustness. If N rises, the redundancy of the Gabor frames would get higher. So, the analysis happens to coincide the conclusion in Eq. (26), which indicates that higher frames redundancy causes better robustness.

We now present some numerical experiments to illustrate the reconstruction performance of short pulses with sub-Nyquist sampling, using the scheme proposed above.

The sampling scheme was tested on a range of multipulse signals of duration T = 20ms, and the pulses making up the signals were randomly chosen as a set of three different pulses: cosine, Gaussian, and B-spline of three orders. The number of pulses was varied between N _p  = 1, 3, 5, the maximum pulse width being W = 0.5ms. The locations of the pulses were also chosen at random. Monte Carlo method was used for simulations averaged over 500 trials. Throughout the experiments, we chose D = I and measured the relative error \( {\left\Vert x-\widehat{x}\right\Vert}_2/{\left\Vert x\right\Vert}_2 \).

In the first experiment, we studied the effects of stretching Gabor frame windows width on the reconstruction error. The smoothness order of the E-spline windows was chosen as a fixed number M = N = 100. The Gabor coefficients Z was acquired by solving the MMV problem with SOMP.

Figure 3 shows the relative error between the reconstructed signals and the original signals with the increase in window stretching factor ζ and the pulse number N _p . The two curved surfaces represent respectively the error variation trends under the conditions of b = 1/W and b = 1/ζW. It can be seen that when b = 1/ζW and ζ ≥ 7, the signals can be reconstructed with minimum error, and the variation of N _p had little effect on the error. With increasing ζ, the dimension K of Z significantly decreased, which means that the measurement matrix has correspondingly fewer columns, and can hence be recovered with higher accuracy. In this case, time samples satisfied K ≤ 716; also, Eq. (21) can be easily satisfied and even more pulses reconstructed. For reducing the size of Gabor coefficient matrix Z, we can also choose b = 1/W. When ζ ≈ 7, the recovery error of the signal will be approximately the same as that when b = 1/ζW.

In the second experiment, we studied the effects of E-spline smoothness order N on the relative reconstruction error under different stretching factor ζ. We chose N _p  = 3 with no other signal parameters not changed. The simulation was started with N = 25, adding N at uniform interval Δ _N  = 5 until N = 100, while the windows stretching factor ζ was raised from 2 to 15. The results are shown by Fig. 4a, b. According to the figures, when N was small, the error was generally large. In the case that ϵ _W  = 0.1 and N = 25, there existed η ≈ 0.2, and the minimum error was on the row ζ = 5. When N was not large enough, the measurement matrix C was too flat to recover Z perfectly. With increasing N, the optimal stretching factor was raised to about ζ = 7. When N was large enough, with appropriate ratio M/K and essential W _E , the errors became quite small, enabling broadening of the range of feasible window width.

In the third experiment, we verified the robustness of the proposed sampling scheme. In the simulation, with N _p  = 3, Gaussian noise with noise/signal ratio (SNR) of 15 dB was injected into the channel. The smoothness order N was equivalent to M, increasing from 25 to 100. Figure 5 shows the SNR of output signals from the sampling schemes with redundancy \( \mu =\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$ N$}\right. \) relating to this study, and with μ = 0.5, μ = 0.3, μ = 0.75 relating to [15]. It was seen that for the sampling scheme proposed, the SNR increased with the raising of N, improved by about 20 dB compared with that of the input signals. When the channel numbers were the same, it was generally much higher than that of the sampling scheme in [15], showing better performance on noise suppression.

Finally, we compared the reconstruction error of the sampling scheme proposed in this paper with that of a specific example in [15]. In Table 1, Schemes I and II relate respectively to the sampling schemes proposed in this paper and that in [15]. As the scheme structure changed significantly and, at the same time, the parameters M, K, μ, and ζ could not remain the same, the comparison was restricted to some typical cases with the same signal. Here, we chose N _p  = 3 and set other signal parameters as they were before. Table 1 shows that, under appropriate parameter setting, the reconstruction performance of both schemes were similar. Therefore, the sampling scheme proposed here can be considered effective and feasible.

We introduced high order exponential reproducing windows into Gabor sampling scheme for sub-Nyquist sampling of short pulses, which notably simplified the filter’s structure of the sampling system and enabled it to be realized by RC filters. Subject to choosing an appropriate E-spline parameter vector α, the Gabor windows could be a positive real function and it is possible to construct the measurement matrix as a weighted DFT matrix for Gabor coefficients recovery, which is proved to have good coherence. Meanwhile, we developed methods for good RIP by stretching windows and increasing E-spline smoothness order N. With that, the ratio r of the row dimension and the column dimension of the measurement matrix could be improved. Also, the sampling system was proved to hold acceptable reconstruction error bound. Because the energy of the E-splines would concentrate to a narrower support with the increasing of N, the Gabor coefficient matrix holds lower sparsity and hence its recovery by using CS algorithms is more reliable. For reducing the coefficients of samples further, we compressed the dual Gabor frames and proved that the reconstruction of the original signals was still under a low error bound and that it benefited from the nice robustness caused by high frames redundancy. With high frames redundancy, the sampling scheme holds nice robustness.