Maximum Magnitude Deviation between DFT and DTFT

Question

Let $x[n]$ be a finite-length discrete-time signal with length $N$. The continuous DTFT $X(\omega)$ is then $$ X(\omega) = \sum_{n = 0}^{N-1} x[n] e^{-j \omega n}. $$

The length-$N$ DFT of $x[n]$ is $$ X[k] = \sum_{n = 0}^{N-1} x[n] e^{-j 2 \pi \frac{k n}{N}}. $$ For this, the DFT is a sampled version of the DTFT, i.e., $$ X[k] = X(2\pi k / N). $$ Please also see posts here and here. Now, we consider the maximum magnitudes $m_{\textrm{d}} = \max_k |X[k]|$ and $m_{\textrm{c}} = \max_\omega |X(\omega)|$. Because of above, we have $m_{\textrm{d}} \leq m_{\textrm{c}}$.

What is the relation between these maximum values? Is there $\gamma > 1$ such that $\gamma m_{\textrm{d}} \geq m_{\textrm{c}}$?

Answer 1

okay, i'm gonna steal a diagram from this publication:

now this is an approximation that is based on the assumption that the discrete spectral points $|X[k]|$ are close enough to each other that only the discrete peak:

$$m_\textrm{d} = \max_k |X[k]| = |X[m]|$$

and the two adjacent neighbors $|X[m-1]$ and $|X[m+1]|$ need be considered. (these are shown as $k$ in the diagram above, not $m$, but i don't know if i should change the convention of discrete variables we're using and i don't wanna draw out another diagram.)

the assumption is, within this very tight range of $\omega$, that the peak is adequately approximated by a quadratic:

$$ |X(\omega)| = m_\textrm{c} - a(\omega - \omega_\textrm{m})^2 $$

where $a > 0$, and the "spectral peak":

$$\star \quad |X(\omega_\textrm{m})| = m_\textrm{c} = \max_\omega |X(\omega)|$$

so we have three unknowns: $|X(\omega_\textrm{m})| = m_\textrm{c}$, $a$, and $\omega_\textrm{m}$ and three equations by evaluating this quadratic at the discrete points $|X[m-1]|$, $|X[m]|$, $|X[m+1]|$:

$$\begin{align} |X[m-1]| &= |X\left(2\pi \tfrac{m-1}{N}\right)| &= m_\textrm{c} - a (2\pi \tfrac{m-1}{N} - \omega_\textrm{m})^2 \\ |X[m]| &= |X\left(2\pi \tfrac{m}{N}\right)| &= m_\textrm{c} - a (2\pi \tfrac{m}{N} - \omega_\textrm{m})^2 \\ |X[m+1]| &= |X\left(2\pi \tfrac{m+1}{N}\right)| &= m_\textrm{c} - a (2\pi \tfrac{m+1}{N} - \omega_\textrm{m})^2 \\ \end{align}$$

so you can solve those three equations for the three unknowns. we're not so interested in $a$, but we are interested in the frequency location of the peak $\omega_\textrm{m}$ and the height of the peak, $m_\textrm{c}$. if you slug out solving this set of three equations and three unknowns, you get for those two parameters:

$$\begin{align} \omega_\textrm{m} &= \frac{2 \pi}{N}\left( m + \tfrac12 \frac{|X[m+1]| - |X[m-1]|}{2|X[m]| - |X[m+1]| - |X[m-1]|} \right) \\ \\ |X(\omega_\textrm{m})|= m_\textrm{c} &= |X[m]| + \frac{\tfrac18 \big( |X[m+1]| - |X[m-1]| \big)^2}{2|X[m]| - |X[m+1]| - |X[m-1]|} \\ \end{align}$$

Now this makes no assumptions about the nature of the spectrum except that the discrete spectral peak is at $|X[m]|$ and the neighboring spectral samples, $|X[m-1]|$ and $|X[m+1]|$ are no larger. With no other information, this is about the best or only guess you can make. It's not always perfect, but it should get you to within one-half FFT bin of the true DTFT peak.

It is perfect if you're looking at the peak of an isolated sinusoid, that was windowed with a gaussian window before going to the FFT, and you're looking at the dB or log magnitude. Then this quadratic behavior in the log magnitude scale is mathematically the correct model and this quadratic peak interpolation is exactly correct. So then you replace $|X[m]|$ and $|X[m-1]|$ and $|X[m+1]|$ with the logarithms (or dB values) of the same before using the above formulae to get the continuous-frequency peak.

Answer 2

suppose your original, infinitely long discrete-time sequence, $x[n]$ was defined in such a way that $x[n]=0$ for all $n>N$ and $n<0$. then the DTFT is:

$$\begin{align} X(e^{j\omega}) &\triangleq \sum\limits_{n=-\infty}^{\infty} x[n] e^{-j \omega n} \\ &= \sum\limits_{n=0}^{N-1} x[n] e^{-j \omega n} \\ \end{align}$$

and one way (not the only way) of looking at the DFT evaluates that at $N$ discrete values of $\omega$:

$$\begin{align} X[k] &= X(e^{j\omega}) \Bigg|_{\omega = \frac{2 \pi}{N}k} \\ &= \sum\limits_{n=0}^{N-1} x[n] e^{-j 2 \pi n k/N} \\ \end{align}$$

now, suppose we define another infinitely long discrete-time sequence, $x_1[n]$ in terms of the $x[n]$ above as

$$x_1[n] \triangleq \begin{cases} \tfrac12 x[n] \qquad & \text{for } \ 0 \le n < N \\ \tfrac12 x[n-N] \qquad & \text{for } \ N \le n < 2N \\ 0 \qquad & \text{otherwise} \\ \end{cases}$$

what is the DTFT?

$$\begin{align} X_1(e^{j\omega}) &\triangleq \sum\limits_{n=-\infty}^{\infty} x_1[n] e^{-j \omega n} \\ &= \sum\limits_{n=0}^{2N-1} x_1[n] e^{-j \omega n} \\ &= \sum\limits_{n=0}^{N-1} x_1[n] e^{-j \omega n} + \sum\limits_{n=N}^{2N-1} x_1[n] e^{-j \omega n} \\ &= \sum\limits_{n=0}^{N-1} \tfrac12 x[n] e^{-j \omega n} + \sum\limits_{n=N}^{2N-1} \tfrac12 x[n-N] e^{-j \omega n} \\ &= \tfrac12 \sum\limits_{n=0}^{N-1} x[n] e^{-j \omega n} + \tfrac12\sum\limits_{n=0}^{N-1} x[n] e^{-j \omega (n+N)} \\ &= \tfrac12 \sum\limits_{n=0}^{N-1} x[n] e^{-j \omega n} + x[n] e^{-j \omega (n+N)} \\ &= \tfrac12 \sum\limits_{n=0}^{N-1} x[n] \big(e^{-j \omega n} + e^{-j \omega (n+N)}\big) \\ &= \sum\limits_{n=0}^{N-1} x[n] \ \tfrac12\big(1 + e^{-j \omega N}\big) \ e^{-j \omega n} \\ \end{align}$$

now what is this evaluated at the same $N$ frequencies?

$$\begin{align} X_1(e^{j\omega}) \Bigg|_{\omega = \frac{2 \pi}{N}k} &= \sum\limits_{n=0}^{N-1} x[n] \ \tfrac12\big(1 + e^{-j \omega N}\big) \ e^{-j \omega n} \Bigg|_{\omega = \frac{2 \pi}{N}k} \\ &= \sum\limits_{n=0}^{N-1} x[n] \ \tfrac12\big(1 + e^{-j 2 \pi k / N}\big) \ e^{-j 2 \pi nk/N} \\ &= \sum\limits_{n=0}^{N-1} x[n] \ \tfrac12\big(1 + 1\big) \ e^{-j 2 \pi nk/N} \\ &= \sum\limits_{n=0}^{N-1} x[n] \ e^{-j 2 \pi nk/N} \\ &= X[k] \\ \end{align}$$

at those $N$ discrete frequencies, the two DTFTs, $X(e^{j\omega})$ and $X_1(e^{j\omega})$, evaluate to be exactly the same. but, in between those $N$ discrete frequencies, we do not expect $X(e^{j\omega})$ and $X_1(e^{j\omega})$ to be the same, because $x_1[n]$ and $x[n]$ are not the same for $-\infty < n < \infty$. so i do not know precisely what $X(e^{j\omega})$ would be between those discrete frequencies unless i make some assumptions about the nature of $x[n]$ outside the interval $0 \le n < N$.

if you make the assumption that $x[n]=0$ outside that interval, and there is no other windowing done to $x[n]$ inside that interval, then you're making the same assumption as Dirichlet in the so-called "Dirichlet kernel" and there is an explicit interpolation formula.

$$\begin{align} \sum_{n=0}^{N-1} e^{j 2 \pi n f/N} &= \sum_{n=0}^{N-1} (e^{j 2 \pi f/N})^n \\ \\ &= \frac{ (e^{j 2 \pi f/N})^N - 1 }{e^{j 2 \pi f/N} - 1} \\ \\ &= \frac{ e^{j 2 \pi f} - 1 }{e^{j 2 \pi f/N} - 1} \\ \\ &= \frac{ e^{j \pi f} (e^{j \pi f} - e^{-j \pi f}) }{e^{j \pi f/N} (e^{j \pi f/N} - e^{-j \pi f/N}) } \\ \\ &= e^{j\pi(N-1)f/N}\frac{\sin(\pi f)}{\sin(\pi f/N)} \\ \end{align} $$

Now we know that when $f=0$ or an integer multiple of $N$ then $e^{j 2 \pi n f/N}=1$ and $$\sum_{n=0}^{N-1} e^{j 2 \pi n f/N} = N $$. But we also know that when $f=k$ where $k$ is an integer other than a multiple of $N$, then

$$ e^{j\pi(N-1)f/N}\frac{\sin(\pi f)}{\sin(\pi f/N)} = 0 $$

because $\sin(\pi f)=0$ and $\sin(\pi f/N) \ne 0$.

$$\begin{align} \sum_{n=0}^{N-1} e^{j 2 \pi n f/N} &= e^{j\pi(N-1)f/N}\frac{\sin(\pi f)}{\sin(\pi f/N)} \\ \\ \frac{1}{N}\sum_{n=0}^{N-1} e^{j 2 \pi n (f-k)/N} &= \frac{1}{N} e^{j\pi(N-1)(f-k)/N}\frac{\sin(\pi (f-k))}{\sin(\pi (f-k)/N)} \\ \\ &= e^{j\pi(N-1)(f-k)/N}\frac{\sin(\pi (f-k))}{N \sin(\pi (f-k)/N)} \\ \\ &= \begin{cases} 1 \quad \text{for } f=k+mN, \ k,m\in \mathbb{Z} \\ 0 \quad \text{for } f=i, \ i\in \mathbb{Z}, \ i \ne k+mN \\ \end{cases} \\ \end{align} $$

so, if you define

$$ \hat{X}(f) \triangleq \sum\limits_{k=0}^{N-1} X[k] \, e^{j\pi(N-1)(f-k)/N}\frac{\sin(\pi (f-k))}{N \sin(\pi (f-k)/N)} $$

you will see that

$$\hat{X}(k) = X[k] \qquad \text{for } 0 \le k < N $$

but this is the same $ \hat{X}(f) $

$$\begin{align} \hat{X}(f) &= \sum\limits_{k=0}^{N-1} X[k] \, \frac{1}{N}\sum_{n=0}^{N-1} e^{j 2 \pi n (f-k)/N} \\ &= \sum_{n=0}^{N-1} e^{j 2 \pi n f/N} \frac{1}{N} \sum\limits_{k=0}^{N-1} X[k] \, e^{-j 2 \pi nk/N} \\ &= \sum_{n=0}^{N-1} e^{j 2 \pi n f/N} \frac{1}{N} \sum\limits_{k=0}^{N-1} X[k] \, e^{-j 2 \pi nk/N} \\ &= \sum_{n=0}^{N-1} e^{j 2 \pi n f/N} x[n] \\ \end{align}$$

So when $f=k \in \mathbb{Z}$, then

$$\begin{align} \hat{X}(f)\bigg|_{f=k} &= X[k] \\ &= \sum_{n=0}^{N-1} x[n] e^{j 2 \pi n k/N} \\ \end{align}$$

Answer 3

I believe to have found a partial answer in the paper:

Gronwall, T. H. (1921). A sequence of polynomials connected with the $n$th roots of unity. Bulletin of the American Mathematical Society, 27(6), 275–279. http://doi.org/10.1090/S0002-9904-1921-03411-2

It actually gives a full construction of a polynomial $X(z)$ such that $|X(e^{i2\pi k/N})| \leq 1$, but $\max |X(z)| = \frac{1}{N} \sum_{n=0}^{N-1} \frac{1}{\sin \frac{2n + 1}{2N}\pi}$.

This makes the upper bound $\gamma$ in the original question to be asymptotically equal to

$$ \frac{2}{\pi}\left( \log N + C + \log \frac{2}{\pi} \right) + o(1), $$
where $C$ is the Euler's constant, and $o(1)$ tends to zero as $N$ increases indefinitely. There are various follow up questions:

1. $X(z)$ has complex coefficients. What is the bound for real coefficients?
2. How does this bound change if we add zero padding? It will tend to 1, but how quickly?
3. $X(z)$ gives the worst case bound, but how is this bound for random (Gaussian) distributed coefficients?