Frequency (DFT / FFT) Super Resolution

Background

In many fields, such as RADAR (RAdio Detection And Ranging), SONAR (SOund Navigation and Ranging), Ultra Sound and many other there is a simple problem called resolution.

The make the model simple, the resolution problem in those fields comes to ability to discern 2 distinct harmonic signals which have similar frequency.
Since the resolution depends on the observation time, a simple rule of thumb was created:

In order to be able to observe 2 harmonic signals their frequency difference must be greater than $\frac{2}{T} \text{[Hz]}$ where $T$ is the observation interval.

Demonstration of Classic DFT Analysis

So in order to see this simplified model, let’s have a look on some data.
We’ll define 2 signals:

• ${y}_{1} \left[ n \right] = \sin \left( 2 pi \frac{{f}_{1}}{{f}_{s}} n \right)$.
• ${y}_{2} \left[ n \right] = \sin \left( 2 pi \frac{{f}_{2}}{{f}_{s}} n \right)$.

We’ll set the sampling frequency ${f}_{s} = 50 \text{[Hz]}$ and $n = 0, 1, \ldots, 49$, which means we have an observation period of $T = 1 \text{[Sec]}$.

As can be seen from above, indeed when $\left| {f}_{1} - {f}_{2} \right| \geq \frac{2}{T}$ it is easy to discern between the 2 frequencies using the DFT.
Yet in reality, we can not always chose the the observation interval, then, how can we have better resolution with limited observation time?

Frequency Super Resolution Model

To answer the question:

How can we have better resolution of the spectrum without longer observation time?

One can employ few approaches:

1. Maximum Likelihood Estimator
   In case we have a parameterized model of the data we can use the Maximum Likelihood Estimator (ML) method. For instance using the DFT for 2 Sines is using the ML of a single Sine for the wrong data model. Using the model of 2 sines will generate a non linear optimization problem which isn’t trivial to solve. To answer that have a look at Estimate the Frequency of a Linear Combination of Harmonic Signals.
2. Prior Model
   In case we don’t have a parametric model of the data we can build an inverse problem with a prior model.
   This is the approach we’ll show in this post.

The model we’ll employ to solve the problem is with the form:

$$ \hat{ \boldsymbol{x} } = \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| F \boldsymbol{x} - \boldsymbol{y} \right\|}_{2}^{2} + \lambda R \left( \boldsymbol{x} \right) $$

Where $\boldsymbol{y} \in \mathbb{R}^{m}$ is the input data, $F \in \mathbb{C}^{m \times n}$ is a DFT Like matrix and $\boldsymbol{x} \in \mathbb{C}^{n}$ is the Super Resolution DFT vector we’re after. For Super Resolution we usually use $n > m$.

The secrete sauce here is given by the Regularization Function $ R : \mathbb{C}^{n} \to \mathbb{R}_{+}$.

In this post we’ll test 4 models:

1. Normal Distribution Model.
2. Sparse Model (Using ${L}_{1}$ Norm, Which is equivalent to Laplace Distribution).
3. Fixel’s Proprietary Model - In house developed model.

Normal Distribution Model

In order not to get into tedious Math based on Bayesian Model we’ll just say that the optimization problem for the case the data in $\boldsymbol{x}$ is distributed normally will be given by:

$$ \hat{ \boldsymbol{x} } = \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| F \boldsymbol{x} - \boldsymbol{y} \right\|}_{2}^{2} + \frac{\lambda}{2} {\left\| \boldsymbol{x} \right\|}_{2}^{2} = {\left( {F}^{T} F + \lambda I \right)}^{-1} {F}^{T} \boldsymbol{y} $$

The model above will basically yield what we know as Zero Padding which in practice produce no better resolution. With values of $\lambda > 0$ we’ll have some damping to compensate for noise. It can actually be formulated more compactly to show it is basically scaled down DFT.

Sparse Model

In case we know / want to promote the case of sparse number of active / non zero bins in DFT we can use this approach. The most popular sparse promoting model is using the ${L}_{1}$ Norm as a regularizer. This model is equivalent (In the Maximum A Posteriori [MAP] sense) to applying a Laplace Distribution prior over the data in Frequency Domain. The model is given by:

$$ \hat{ \boldsymbol{x} } = \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| F \boldsymbol{x} - \boldsymbol{y} \right\|}_{2}^{2} + \lambda {\left\| \boldsymbol{x} \right\|}_{1} $$

This model doesn’t have a closed form solution but can be solved efficiently by using some modern Convex Optimization tools (Such as Proximal Gradient Method).

Fixel’s Proprietary Model

We also derived a model in house which promotes sparsity. It has better resolution than teh model above. Obviously, we can’t go into details here, but we’ll see how it performs in the next sections.

Benchmark

We benchmarked all the models above. The test case was 2 sines with similar frequency.

In the case above we examined the the Zero Padding, Gaussian Model and Sparse (L1) Model.
As one can see in the image above, as expected the Gaussian Model results matches the Zero Pad method with some damping (As the model derivation assumes some noise model). This gives a formal background to the zero padding method which is widely used.
On the other hand, the Sparse Model can actually resolve the 2 sines once their frequency is $1 \text[Hz]$ apart. Namely it can increase the actual resolution by a factor of $2$.

Can we do any better? Let’s try with some even closer sines and add our own, Fixel’s Model.

Well, from the above figure one could see that Fixel’s Method can resolve 2 sines which their frequency is only $0.05 \text[Hz]$ apart! This is equivalent of increasing the observation interval by a factor of $40$.
What does it mean? Better resolution of targets in RADAR, Better resolution of targets in SONAR, Better image in Ultra Sound without changing anything in hardware.