CONTINUOUS SIGNALS WITH DISCRETE SPECTRA

Let us suppose we have a one dimensional, continuous signal s(t) that has a finite time duration T. Within the time interval T, this signal can be represented by a Fourier series expansion as follows:  

$$s(t) = \sum_k S_k e^{j\omega_k t},$$ (2)

where S_k is the discrete spectrum of the signal at the discrete frequency

$$\omega_k = k \Delta \omega = {2\pi k \over T}.$$

Let $\{s_i=s(t_i);\ \ i=1,2,\ldots,N\}$ be a sequence of samples of this signal. If one can reconstruct the original continuous signal from this finite number of samples, then one can interpolate or resample this signal arbitrarily. This reconstruction is possible if the spectrum of the signal is band-limited, in other words, if the Fourier series expansion in equation (2) has a finite number of terms. With this assumption, equation (2) tells us that the continuous signal can be fully described by a finite number of samples of its spectrum. Thus, the key step of the reconstruction is to estimate the spectrum.

Substituting the known samples into equation (2) gives  

$$s_i= \sum_k S_k e^{j\omega_k t_i} \ \ \ \ i=1,2,\ldots,N.$$ (3)

If we define

$$s^T = \pmatrix{s_1 & s_2 & \ldots & s_N},$$

$$S^T = \pmatrix{S_1 & S_2 & \ldots & S_K}$$

and

$${\bf A} = {\pmatrix{e^{j\omega_1t_1} & e^{j\omega_2t_1} & \... ...ega_1t_N} & e^{j\omega_2t_N} & \ldots & e^{j\omega_Kt_N} \cr}},$$

where K is the number of frequencies required to model the signal, we can rewrite equation (3) into the corresponding matrix form

$${\bf A}S = s.$$ (4)

The least squares solution of this system equation is defined by the following normal equation:  

$${\bf R}S = {\bf A}^Hs,$$ (5)

where ${\bf R}={\bf A}^H{\bf A}$ is a $K \times K$ matrix with complex elements and ${\bf A}^H$ is the conjugate transpose of ${\bf A}$.

There exist many numerical algorithms for solving a general normal equation. But the computation required is generally in an order of K³. Fortunately, as we will see later, the matrix ${\bf R}$ has a special structure that makes it possible to solve equation with an order of K² operations.