# 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?

• A "best" way to improve frequency resolution is to use more independent time samples. You can oversample the DFT all you want, but it will not change its frequency resolution. Super resolution methods are in general non-linear. – AnonSubmitter85 Jul 4 '18 at 18:22
• The problem is I have a fixed sampling rate and cannot operate beyond that rate. I was considering converting the signal to baseband and then apply super resolution. Not sure if this works well in practice and what measures do I need to consider for perfect reconstruction. – Maxtron Jul 4 '18 at 19:24

First, 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.