Orthonormal Dictionaries for Band Limited Signals

Question

If $\mathbf{x} = [x_0, x_1, \ldots, x_{N-1}]^T$ is the time sampled input signal and $\mathbf{Y} = [Y_0, Y_1, \ldots, Y_{N-1}]^T$ is the Fourier transform of the input signal, then a linear relationship between the input and output can be established with the help of a discrete Fourier transform (DFT) matrix and is given as \begin{align} \mathbf{Y} = \mathbf{D} \mathbf{x} \end{align} where \begin{align} \mathbf{D} = \frac{1}{\sqrt{N}} \begin{bmatrix} \omega^{0 \cdot 0} & \omega^{0 \cdot 1} & \ldots & \omega^{0 \cdot N-1} \\ \omega^{1 \cdot 0} & \omega^{1 \cdot 0} & \ldots & \omega^{1 \cdot N-1} \\ \vdots & \vdots & \ldots & \vdots \\ \omega^{N-1 \cdot 0} & \omega^{N-1 \cdot 1} & \ldots & \omega^{N-1 \cdot N-1}\end{bmatrix}, \end{align} and $\omega = e^{\frac{-2 \pi i}{N}}$ is a primitive $N$-th root of unity. We can also see that, $\mathbf{D}^H \mathbf{D} = \mathbf{I}_N$, where $\mathbf{I}_N$ is an Identity matrix of size $N \times N$. The good thing about DFT matrix it covers frequencies from $[0,2\pi]$ and can be used as a dictionary to represent the input signal. This works well in practice when we don't know anything about the nature of the input signal.

Consider the case when we have some prior knowledge of the input signal. For example, let us assume that the input signal is band limited, i.e., if the signal is sampled at a sampling rate of $f_s$, then the input signal contains frequency components belonging to a specific frequency band, $[f_1, f_2]$, where $f_1 < f_2 \le f_s/2$. In such cases, only those columns of the DFT matrix that belong to the specific frequency range are useful. Instead of using $\mathbf{D}$, we may as well construct a new dictionary, say $\mathbf{D}_o$ with an improved resolution, i.e., instead of $N$-point DFT matrix on all possible frequencies, we have $N$-point matrix, but these points lie in the frequency range of $[f_1, f_2]$. This can be obtained by oversampling the current dictionary $\mathbf{D}$ and only extracting $N\times N$ subset of the overcomplete dictionary which belongs to the frequency range. However, the new dictionary (super resolution) does not demonstrate the orthonormal property of the DFT matrix, i.e., $\mathbf{D}_o^H \mathbf{D}_o \ne \mathbf{I}_N$.

What is the best way to design an orthonormal dictionary for a specific range of continuous frequencies? In other words, how to perform DFT for band limited signals with an improved resolution?

Answer 1

Why would you add the constraint of being Orthonormal Dictionary?
It doesn't make sense in the context of what you ask.

First we need to define resolution.
If you mean the grid to be denser than indeed what you need is to create the DFT matrix of zero padded signal and take the subset which you're interested in as you wrote in your question.

If you define resolution as the ability to discern between 2 close (In frequency relative to the observation window) harmonic signals then there is a subtle thing to keep in mind.
While indeed by Uncertainty Principle you're limited by the observation time what's important is under what model.
If you have no knowledge about the signal but it is band limited than this holds and probably there is nothing to do.

Yet if you have some prior on it you can do something and indeed gain some ability to "Bypass" the limitation.

For instance, if you assume the signal is sparse relative to the DFT matrix than solving the problem with $ {L}_{1} $ regularization (Sparse Model / MAP Model with Laplacian Prior) will yield ability to have "Super Resolution".

I can't, currently, think on a prior to work on range of resolutions, but if you believe your signal is sparse in that range you certainly can build an optimization problem to gain extra resolution.

Answer 2

Hoyer, E., and R. Stork. "The zoom FFT using complex modulation." Acoustics, Speech, and Signal Processing, IEEE International Conference on ICASSP'77.. Vol. 2. IEEE, 1977.

Abstract: A recent paper by Yip discussed the zoom transform as derived from the defining equation of the FFT. This paper simplifies the concepts and removes some of the restrictions assumed by Yip; ie., the total number of points need not be a power of 2. The technique is based on first specifying the desired center frequency, bandwidth, and frequency resolution. The signal is then sampled, modulated, and lowpass filtered. This result is purposely aliased, then transformed using an FFT algorithm. The result is an M-point frequency spectra of the desired bandwidth centered about the center frequency with a higher degree of resolution than could be directly obtained using an M-point transform.

There are many more references to the zoom DFT and variations A related technique known at the Vernier DFT also has several references.

In terms of matrix operations, bandshift, filter, and resample.

A search in IEEE Explore or Google Scholar will return many references

As mentioned in the comments, resolution depends on sample length, but this is an accepted and common technique to generate a band limited orthogonal basis.