Accurate Spectral Estimation of Non-periodic Signals Based on Compressive Sensing

Abstract

In this work we propose a method based on compressive sensing (CS) for estimating the spectrum of a signal written as a linear combination of a small number of sinusoids. In practice one deals with signals with finite-length and so the Fourier coefficients are not exactly sparse. Due to the leakage effect in the case where the frequency is not a multiple of the fundamental frequency of the DFT, the success of the traditional CS algorithms is limited. To overcome this problem our algorithm transform the DFT basis into a frame with a larger number of vectors, by inserting a small number of columns between some of the initial ones. The algorithm takes advantage of the compactness of the interpolation function that results from the ℓ₁ norm minimization of the Basis Pursuit (BP) and is based on the compressive sensing theory that allows us to acquire and represent sparse and compressible signals, using a much lower sampling rate than the Nyquist rate. Our method allow us to estimate the sinusoids amplitude, phase and frequency.

18.1 Introduction

The compressive sensing (CS) theory allows us to recover, sparse or compressible signals, from a number of measurements $M$, much smaller than the length $N$ of the signal. Instead of acquiring $N$ samples, compute all the transform coefficients, discard the small $(N-K)$ and then encode the largest $K$, we can acquire a number of random mixtures $M$ proportional to the sparsity $K$. In CS we acquire and compress the signal in one step.

The samples are obtained projecting $x$ on a set of $M$ vectors $\{\Phi _{i}\} \in \mathbb R ^{N}$, that are independent of the signal, with which we can build the measurement matrix $\Phi \in \mathbb R ^{M\times N}$, with $M<N$. In matrix notation, the measurement vector $y=\Phi x$.

To reconstruct the $K$-sparse signal $x$, we search for the sparsest coefficient vector $x$, solving the problem:

$$\begin{aligned} (P0):\min \Vert x\Vert _{0}: y=\Phi x, \end{aligned}$$

(18.1)

where $\Vert x\Vert _{0}$ is the number of nonzero entries. This problem is combinatorial, and so, to avoid this difficult we must use other approach. Since the matrix $\Phi$ is rank deficient, and so it loses information, one can think the problem is impossible, but it can be shown that if the matrix obeys the Restricted Isometry Property (RIP), we can recover $x$ exactly by solving the convex problem, which is the convex relaxation of (P0) [1, 2]:

$$\begin{aligned} (P1):\min \Vert x\Vert _{1}: y=\Phi x, \end{aligned}$$

(18.2)

where $\Vert x\Vert _{1}=\Sigma |x_{i}|$.

Essentially, the RIP requires that every set of less than $K$ columns, approximately behaves like an orthonormal system. More precisely, let $\Phi _{T}$, $T\subset \{1,\cdots ,N\}$, be the $M\times |T|$ submatrix consisting of the columns indexed by $T$. The $K$-restricted isometry constant $\delta _K$ of $\Phi$ is the smallest quantity such that

$$\begin{aligned} (1-\delta _K)\Vert x\Vert ^{2}\le \Vert \Phi _T x\Vert ^{2}\le (1+\delta _K)\Vert x\Vert ^{2} \end{aligned}$$

(18.3)

for all the subset $T\subset N$, with $|T|\le K$ and coefficient sequences $(x_j), j\in T$.

To check if a given matrix $\Phi$ satisfies the RIP is a difficult task. Fortunately, it can be shown that matrices with random entries drawn from certain probability distributions will have the RIP with high probability [1].

The signal $x$, which is $K$-sparse or compressible, can be recovered by solving the indeterminate system $y=\Phi x$, by (P1), from only $M\ge CK \log (N/K)$ samples, particularly with matrices $\Phi$, with Gaussian entries [3].

The problem (P1) cannot be solved analytically, but can be reformulated as a linear programming problem when the data is real, and as a second order cone problem when the data is complex [4, 5]. In the complex case, $\Vert x\Vert _{1}$ is neither a linear nor a quadratic function of the real and imaginary components, and cannot be reformulated as one: ${{\parallel x \parallel}_1}=\sum \sqrt{{{\mathfrak{R}} (x_i)^2 + {\mathfrak {I}} (x_i)^2}}$ In this case, the problem can be reformulated into second order cone programming, (SOCP), and solved with algorithms implemented in the framework of Interior Point Methods, for example using the CVX algorithm [6].

If a signal $x$ can be written as a linear combination of $K$ sinusoids, the signal presents few non-zero spectral lines in the classical Fourier Transform sense, that is, it is $K$-sparse in the frequency domain. However, in practical applications, because we use finite $N$-length signals, the signal is sparse only if the frequencies are multiples of the fundamental frequency $\frac{2\pi }{N}$. Leakage limits the success of the traditional CS algorithms. Here, we propose an iterative algorithm which find a first approximate location of a sinusoid and then refine the sampling in frequency around the neighborhood of this sinusoid up to a required precision. If several sinusoids have to be found, the procedure iterate as many times as needed this locale refinement.

The idea comes from the dual problem of fractional time-delay estimation, as studied in the work of Fuchs and Deylon [7]: the true value of the frequency can be obtained by BP between frequencies values having the higher values.

18.2 Spectral Estimation with Compressive Sensing

Consider ${\Psi \in {\mathbb {C}} }^{N\times N}$ as the inverse of the DFT matrix. Then, if $x$ is a time domain discrete signal with length $N$, the DFT of $x$ will be $s=\Psi ^{-1}x$. If $x$ is observed using random measurements, we have $y=\Phi x$, and we can write the problem (P1), from the Eq. (18.2):

$$\begin{aligned} \min \Vert s\Vert _{1}: y=\Phi \Psi s =\Theta s, \end{aligned}$$

(18.4)

The CS theory ensures that a signal that is sparse or compressible in the basis $\Psi$ can be reconstructed from $M=O(K \log (\frac{N}{K}))$ linear projections onto a basis $\Phi$ that is incoherent with the first, solving the problem (P1) using the Eq. (18.4), [8, 9]. Random matrices are largely incoherent with any fixed basis [10].

If $x$ contains only sinusoids with frequencies multiples of $\frac{2\pi }{N}$ rad, then $s$ will be a sparse signal. Otherwise, $s$ will be not sparse. If we apply the CS to solve this problem, the recovered signal $s$ will not be sparse, as we can see in the example depicted in Fig. 18.1. The error is $0.5986$ and even if we increase the number of measurements, the error remains large, having a value of $0.4368$ for $M=80$ and a value of $0.2892$ for $M=150$. Since the signal is not sparse we will need more measurements to get a better result.

Fig. 18.1

Spectrum of a signal with length N=1,024 composed of three sinusoids that are not multiple of the fundamental frequency of the DFT, using the DFT and the CS using $M=50$ measurements

This comes from the fact that no column vector in the matrix $\Psi$ has a frequency matching one of the frequencies present in the signal. The first idea is to expand the matrix $\Psi$, so that each frequency present in the signal is represented by a column. We would have a redundant frame instead of the orthogonal basis of the DFT. By increasing the frame size, signals with frequencies that are not multiples of the fundamental frequency of the DFT become more compressible, resulting into a recovery performance improvement, but in return, the frame becomes increasingly coherent, which leads to a decrease in performance recovery. So the idea was to add only a small number of columns. If we know between which columns of the $\Psi$ matrix, are the frequencies that are not multiples of the fundamental frequency, we can add columns to the matrix $\Psi$, only in that interval, but in CS we only have access to the signal $y$.

18.2.1 Problem of Fractional Time-Delay Estimation

The dual problem of the fractional frequency spectral estimate is the fractional time-delay estimation. Fuchs and Deylon, in [11], presented an analytical expression of the minimal $\ell _1$-norm interpolation function which is independent of the signal, to solve the problem to get an estimate of the delay $\tau$, having a bandlimited signal $x(t)$, with a maximal sampling period $h = 1$, which is given by $y(t)= x(t-\tau )$. One possibility is to seek the values $s_n$ in

$$\begin{aligned} y(t)= x(t-\tau )=\sum _n x(t-nh)s_n. \end{aligned}$$

An estimation of the delay $\tau$ is determined from the maximum location of the interpolating function which is given by

$$\begin{aligned} \psi (t)=\sum _{k\ge 0} \beta _k \frac{\phi (|t|-k)}{|t|},\quad |t|\in [k,k+\frac{1}{l}], \end{aligned}$$

with

$$\begin{aligned} \phi (x)=\frac{1}{\Gamma (x) \Gamma (\frac{1}{l}-x)},\quad x\in [0,\frac{1}{l}], \end{aligned}$$

$$\begin{aligned} \beta _k=(-1)^k\frac{\Gamma (k+\frac{1}{l})}{\Gamma (k+1)}, \end{aligned}$$

where $\Gamma$ is the standard gamma function. This reconstruction function is very localised and as the oversampling factor, $l$, increases more localised it will be, unlike what happens with the sinc function, which keeps the width of the main lobe, as one can see in Fig. 18.2.

Fig. 18.2

$\ell _1$-norm interpolating function with oversampling factors $l=2$ and $l=5$, compared with the sinc function

Since the minimal $\ell _1$- norm reconstruction function is quite localised, the $s_n$ values can be obtained by solving the minimal $\ell _1$-norm problem

$$\begin{aligned} \min \Vert s_n\Vert _1:y(t)=\sum _n x(t-nh)s_n,\quad h<1, \end{aligned}$$

which is the BP.

The problem we are dealing with is the dual of the problem studied by these authors. If we have a signal with a frequency $f_i$, which is a multiple of the fundamental frequency of the DFT, we know that the DFT of the signal has a maximum in the position of this frequency.

Looking to the frequency of the signal as the dual of the delay, the interpolating function will have a maximum exactly in the same place, independently of the considered $l$ value. If we have a signal with a frequency $f_i$, which is not multiple of the DFT fundamental frequency, the signal is not sparse, therefore there are no maximums. However, the interpolating function will have a maximum in the position of the frequency, regardless of the amount of $l$ which is considered. If the signal has two frequencies that are not multiples of the fundamental frequency, the interpolating function has two maximums, both between the values of the frequencies with higher values obtained by BP. See the example depicted in Fig. 18.3.

Thus, one possible solution to our problem of knowing where the frequencies are, is to apply the BP. Each of the frequencies in question, will be between the position of the two frequencies multiple of the fundamental frequency, where BP obtains maximum values.

Fig. 18.3

Minimal $l_1$ norm using BP and using the $l_1$ interpolating function

If the frequencies are very close, a greater value of $l$ must be used in order to discover them. See Fig. 18.4.

Fig. 18.4

Minimal $l_1$ norm using BP and using the interpolating function with frequencies very close, using two values of $l$

The proposed algorithm starts by finding the first interval where BP obtains maximum values. After that, we add columns among those corresponding to the endpoints of the interval. Then, we choose the column position where is the maximum value between the added columns, which is an estimation for the position of the desired frequency. Therefore, to determine the approximated value of another frequency, we expand the original matrix by adding that column. Then, by applying again the BP we find another interval and we repeat the same procedure.

This algorithm can be easily extended for more frequencies as shown in the next section.

18.2.2 Proposed algorithm

We begin by calculating $\hat{s}$, which is the approximate value of $s$, solving the minimisation $\ell _1$-norm problem:

$$\begin{aligned} \ell _1: \min \Vert s\Vert _{1}:y=\Theta s. \end{aligned}$$

(18.5)

Then:

• 1. We will calculate the argmax of $\hat{s}$, $s_{max}$;

• 2. The interval $[s_{max}-1,s_{max}]$ or $[s_{max},s_{max}+1]$ is chosen as the image nearest to $s_{max}$. Let’s call this interval [a,b];

• 3. We will add columns between the two extremes that correspond to the interval considered in the previous point:

  • $I:=0$

  • while ($I <$ Nmaxpoint and $\upvarepsilon >$ error threshold)

  • a. $I:=I+1$

  • b. We will consider matrix $\Psi _1$, adding $I$ columns to $\Psi$. The $I$ frequencies of columns to add are given by: $(a+(1:I)/(I+1))-1$.

  • c. We will calculate the $\hat{s}$ values solving the problem 18.5 and considering the matrix $\Psi _1$;

  • d. We will calculate the argmax of $\hat{s}$, only in the interval $[a,b]$, which contain the $I$ added columns;

  • e. We will consider a new matrix, $\Psi _2$, from $\Psi$, where in the interval $[a,b]$ is added the column which corresponds to the argmax of the values obtained in the previous point;

  • f. We will calculate the $\hat{s}$ values, using the matrix $\Psi _2$;

  • g. We compute the value of $\upvarepsilon$

• 4. $\Psi =\Psi _2$

• 5. We will repeat the steps from 1. to 4. as many times as the sparsity of the signal.

In the end we calculate the value $\hat{x}=\Psi \hat{s}$.

In this algorithm, we use the standard error, given by ${\text{ erro }}=\frac{\Vert x-\hat{x}\Vert }{\Vert x\Vert }$. The stopping criterion in the reconstruction of the approximate value for each frequency, $\upvarepsilon$, i.e, the criteria used to stop adding columns in the range $[a,b]$ is given by the difference between the errors obtained in two consecutive iterations. In each iteration the error is given by the sum of absolute values of $\hat{s}$ excluding the $K$ higher values, with $K$ the value of sparsity. If in the interval $[a,b]$, on the step 3f., we add the column corresponding to the frequency of the sinusoid, this error is very small [10].

18.3 Experimental Results

In our experiments we use signals of length $N=1,024$ samples and all the signals contain real-value sinusoids, with random frequencies. The amplitudes of each frequency is 1 except in the experiment III.

18.3.1 Experiment I

In our first experiment, we apply the proposed algorithm to a signal containing three real-value sinusoids, $K=6$, using $M=100$ measurements. Therefore we can reconstruct the signal with an error of 0.0268, which had an initial error of 0.5275, see Fig. 18.5.

Fig. 18.5

The approximate value of $s$, first using CVX to solve the BP, and then with the proposed algorithm in the first, second and third frequencies

Fig. 18.6

The error in the first frequency in function of the number of added columns

Fig. 18.7

Performance of CS signal recovery with the proposed algorithm for signals with one, two, three and four frequencies which correspond to $K=2$, $K=4$ and $K=6$ respectively. All quantities are averaged over 400 independent trials

Fig. 18.8

The approximate value s, for a signal containing three real-value sinusoids with frequencies of amplitudes 1, 0.01 and 0.05

Fig. 18.9

Performance of signal recovery using the proposed algorithm for a signal composed by two and three different frequencies with 150 noisy measurements. All quantities are averaged over 100 independent trials

As shown in Fig. 18.6, the error decreases exponentially as we add columns in the interval, so we can initialise the number of adding columns, step 1. of the proposed algorithm, with a greater value than $I=1$. In our experiments we initialised with $I=650$.

18.3.2 Experiment II

Our second experiment compares the performance of the proposed algorithm for signals with one, two and three frequencies. We verify that the number of measurements we need for the same performance increases with the sparseness of the signal. See Fig. 18.7.

18.3.3 Experiment III

This experiment shows the behaviour of the proposed algorithm, when the amplitudes of the signal frequencies are different. Figure 18.8 presents the result of the signal recovery using our algorithm for a signal composed by three random frequencies with amplitudes 1, 0.01 and 0.05. The proposed algorithm performs better for different amplitudes, than Thresholding based algorithms, like Spectral Iterative Hard Thresholding (SIHT) proposed by M. Duarte and et al. in [12], since the Thresholding algorithms consider, in each iteration, only the $K$ largest spectral components, removing the others. With this approach, the smallest frequencies can be discarded.

18.3.4 Experiment IV

Our fourth experiment tests the robustness of the proposed algorithm to additive noise in the measurements of a signal written as a linear combination of two and three sinusoids. The error was evaluated for ten signal to noise ratios (SNR) and the results are depicted in Fig. 18.9. As we can see, the proposed algorithm performs quite well.

18.3.5 Experiment V

This experiment compares the performance of the proposed algorithm with two of the algorithms proposed by M. Duarte and et al. in [3], which they called by Spectral CS (SCS), Spectral Iterative Hard Thresholding (SIHT) using a heuristic approximation and a Line Spectral Estimation (Root Music). See Fig. 18.10.

Fig. 18.10

Performance of signal recovery using the proposed algorithm, using the SIHT implemented via heuristic algorithm and using the Root Music algorithm. All quantities are averaged over 400 independent trials

For the SIHT, the authors use an over-sampled DFT frame and a coherent-inhibiting structured signal model, that inhibits closely spaced sinusoids, and the classical sinusoid parameter estimation algorithm, periodogram. In our algorithm we do not need to impose a model based, to inhibit the coherence of the frame, because our interpolating function is very localised.

18.3.6 Experiment VI

Our last experiment shows how the proposed algorithm behaves for two close frequencies and compares its performance with the performance of the SIHT and the Root Music algorithms. We have considered a fixed frequency, $f_1$ and a second frequency, $f_2 = f_1 + \delta$, where ${{\delta}} =[0.1:0.1:1,\, 1.25:0.25:5.5]$. As shown in Fig. 18.11, our algorithm presents a better performance than the others.

Fig. 18.11

Performance of signal recovery using the proposed algorithm, the SIHT implemented via heuristic algorithm and the Root Music algorithm, considering a signal with two frequencies where $f_2=f_1+\delta$. We have used 100 measurements. All quantities are averaged over 200 independent trials

Note that, although the errors are small for delta values smaller than 1, the frequencies values can be very different from the correct ones, as we can see in Table 18.1

Table 18.1 Recovered values obtained with the proposed algorithm, the Root Music algorithm and the siht algorithm, using the fixed frequency $f_1$ and $f_2=f_1+\delta$

The results of the proposed algorithm were as it was expected, since the minimal $\ell _1$-norm interpolation function is very localised, unlike the minimal $\ell _2$-norm interpolation function - the sinc function, as one can see in Fig. 18.12.

Fig. 18.12

Minimal $\ell _1$-norm using BP and using the interpolating function with an over sampling factor of $l=9$. The dotted curve is the minimal $\ell _2$-norm interpolating function: the sinc function

18.4 Conclusion

We have developed a new algorithm to estimate the spectral components in the case of sparse finite-length signals. The algorithm uses a redundant frame, transforming the DFT basis into a frame with a larger number of vectors, by inserting columns between some of the initial ones. The frame has a maximum of $N+K$ vectors, with $K$ the sparsity of the signal.

From the results can be seen that the proposed algorithm can recover the sparse signals with an error smaller than $0.001$, even for a signal with $K=6$.

Furthermore, it presents a good performance in the presence of noise. In addition to this, it can deal with signals where the frequency amplitudes are very different, overcoming other algorithms in this field. Moreover, the proposed algorithm performs better than others that we have compared for the same signal while using the same number of measurements.