# Orthonormal Dictionaries for Band Limited Signals

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?

• You cannot improve the resolution of the DFT by restricting it to a frequency band. Bilinear time-frequency maps are limited by the Heisenberg uncertainty product. If you want to obtain "super resolution" you need to leave this class of time-frequency representations. – Jazzmaniac Jul 4 '18 at 16:56
• Can I use wavelets? For example chirp wavelets defined for a specific frequency range. – Maxtron Jul 4 '18 at 17:00
• No, wavelets are also an inner product time frequency representation (or an ordinary basis change in other words). – Jazzmaniac Jul 4 '18 at 19:38
• Can I transform the signal to baseband and then apply super resolution? – Maxtron Jul 4 '18 at 19:44
• You'll have to define what exactly you mean with "super resolution". It's a very generic and collective term for all sorts of methods that visualise certain aspects of a signal in time-frequency with an apparent resolution that is better than the default time-frequency uncertainty. So, what exactly do you want to achieve? – Jazzmaniac Jul 4 '18 at 19:49

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.

• This method makes sense when the sampling frequency $f_s > N$, where $N$ is the $N$-point DFT. If the $N > f_s$, then the regular DFT matrix offers a better resolution. – Maxtron Jul 5 '18 at 23:28
• the way you are expressing your inequalities should be restated, N is an integer. f_s is a real – user28715 Jul 5 '18 at 23:43
• The method above is a trick to better have a look on the data. It doesn't allow better resolution in the sense of seeing different harmonic component. – Royi Jul 6 '18 at 11:41
• it answers the question, as asked, an orthogonal basis that covers a subset of frequencies. – user28715 Jul 6 '18 at 12:18
• Not really. It just uses a subset of the same basis. The OP wanted basis which given the knowledge of bandwidth will give something in return - more resolution. – Royi Jul 6 '18 at 13:19

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.

• this doesn’t answer the OP question. It blows smoke – user28715 Jul 6 '18 at 13:08
• No it doesn't. Take 2 Sines which are close to each other beyond recognition in FFT. Use Laplacian Prior and see what happens. Suddenly they can be seen. – Royi Jul 6 '18 at 13:17
• not the question that was asked. it might be useful to the OP but assumptions introduce bias. How do you know that the OP wants to resolve just 2 sines. You defined resolution in those terms, the OP was more vague. The core question was for an orthogonal dictionary. You don’t answer that. If you are going to criticize others about the relevance of their answers, you should expect the same. Not just smoke but weasel words. – user28715 Jul 6 '18 at 14:01
• The OP specifically says the following: >Instead of using D, we may as well construct a new dictionary, say Do with an improved resolution. Namely he doesn't want a sub section of the DFT Dictionary but a dictionary with improved resolution. The dictionary yielded by the DFT Matrix + ${L}_{1}$ regularization indeed yields better resolution. – Royi Jul 6 '18 at 14:51
• The OP states that the subset of the DFT is not orthogonal. I'm sure you know the difference between a square and rectangular matrix. The zoom DFT is orthogonal and full rank.. The OP wants "improved" resolution but was unsure what that meant. If you really want to advance the knowledge of the universe, cite some references. I would find that interesting and helpful but so far, just smoke, no fire, and a selective interpretation of what was asked. – user28715 Jul 6 '18 at 15:52