2
$\begingroup$

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}}$?

$\endgroup$
  • $\begingroup$ Hi ! First of all, an infinite length signal's DFT samples are not obtained by sampling its theoretical DTFT, so your equality is not valid, unless there's an exception or assumption that I missed? Then, assuming you wish to you perform a DFT on that infinite length signal then you have to get a truncated verison of $x[n]$, so what's your truncation length $L$ ? $\endgroup$ – Fat32 Sep 30 '18 at 20:33
  • $\begingroup$ @robertbristow-johnson does the question require a little modification (according to my comment) or is there something clear (but unclear to me) about it ? $\endgroup$ – Fat32 Sep 30 '18 at 20:36
  • $\begingroup$ i dunno if you clarified your question or made it worse, Sebastian. $\endgroup$ – robert bristow-johnson Oct 1 '18 at 4:36
  • $\begingroup$ i gotta approach this Dirichlet thing again a little differently. $\endgroup$ – robert bristow-johnson Oct 1 '18 at 4:36
  • $\begingroup$ Ok, I agree, I will revert back the definition to a finite length sequence. $\endgroup$ – Sebastian Schlecht Oct 1 '18 at 10:41
2
$\begingroup$

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

quadratic peak interpolation

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.

$\endgroup$
  • $\begingroup$ Thanks for the answer. I'm aware of the quadratic approximation, but what I'm interested is: what is the worst case error of this quadratic approximation? Are there special signals where this approximation fails considerably? $\endgroup$ – Sebastian Schlecht Sep 29 '18 at 13:35
  • $\begingroup$ it depends on your assumptions. can we start with the assumption that you're trying to determine the frequency and amplitude of a single sinusoid? and, since the FFT is finite in size, your sinusoid will necessarily be windowed (no windowing is actually rectangular windowing). in the frequency-domain, windowing has tails and sidelobes that interfere with other spectral features. then, with the assumption that there are no other nearby sinusoids that interfere, based on the window function, there are results for how bad the quadratic interpolation is. $\endgroup$ – robert bristow-johnson Sep 29 '18 at 20:35
  • $\begingroup$ again, if your window is gaussian and if you look at the log-magnitude (such as dB) rather than just the magnitude (as we did above) and if there aren't any nearby frequency components to interfere, the quadratic interpolation is perfect in this log-magnitude domain. $\endgroup$ – robert bristow-johnson Sep 29 '18 at 20:37
  • $\begingroup$ I agree on your arguments for a single sinusoid. However, my question is for a general real valued signal. How bad can all this interference become in terms of the peak maximum? $\endgroup$ – Sebastian Schlecht Sep 29 '18 at 21:20
  • $\begingroup$ what does the peak mean? "it depends on your assumptions." does the peak mean a sinusoid? if it is assumed that the peak is there because there is a sinusoid there, then it depends on the window function because, in the DTFT domain, the sinusoid is a Dirac spike convolved with the Fourier Transform of the window function. $\endgroup$ – robert bristow-johnson Sep 29 '18 at 21:28
1
$\begingroup$

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} \\ \end{align}$$

(this ain't done yet.)

$\endgroup$
  • $\begingroup$ Thanks for the additional explanation. I agree on your definition of the signal $x[n]$ (only non-zero for $0 \leq n < N$). In terms of my question, are you suggesting: there does not exists any $\gamma$ such that $\gamma m_d > m_c$ for any such signal $x[n]$? I'm not sure whether your construction $x_1$ proofs this point. $\endgroup$ – Sebastian Schlecht Sep 29 '18 at 22:42
  • $\begingroup$ What would be this explicit interpolation formula for the Dirichlet kernel? $\endgroup$ – Sebastian Schlecht Sep 29 '18 at 22:56
  • $\begingroup$ hang on. the Wikipedia article doesn't explicitly say. $\endgroup$ – robert bristow-johnson Sep 29 '18 at 23:51
0
$\begingroup$

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?
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.