4
$\begingroup$

Consider a discrete time waveform $x[n]$ with $n \in [0...N-1]$ that is zero for all samples $n > N/2$ and non-zero elsewhere. Is there a waveform such that its Discrete Fourier Transform $X[k]$ with $k \in [0...N-1]$ also has the property that $X[k] = 0$ for $k > N/2$?

If so, this could be viewed as a discrete time "causality" in both domains, treating the upper half of both sequences as representing the negative of the independent variable (time or frequency).

More background:

In this related question:

One-sided waveforms in both time and frequency?

MattL provided a succinct answer proving that a one-sided continuous time waveform cannot exist in both time and frequency, meaning we cannot simultaneously have a causal waveform, $x(t) = 0$ for all $t<0$, and a similar positive only spectrum with $X(\omega) = 0$ for all $\omega<0$.

As Matt presented, the sufficiency was based on Schwartz's Paley-Wiener condition which proves that $\int_{-\infty}^\infty|\ln X(\omega)|d\omega$ must converge for all causal waveforms. Therefore beyond singularities which will converge using Cauchy's principal value, $X(\omega)$ cannot be zero over any interval. Since $\ln(\epsilon)\rightarrow -\infty $ as $\epsilon \rightarrow 0$, there can be no causal waveforms that have no negative frequency components.

The values of the DFT are mathematically equivalent to samples of the continuous Discrete Time Fourier Transform. Similarly to what Matt confirmed the DTFT cannot be zero over any interval, but it can regularly pass through zero without violating the constraint provided by the Paley-Wiener Condition. Since the DTFT can periodically pass through zero, this leads me to suspect that there may possibly be a solution? OR how do we prove even this case cannot exist since this doesn’t appear (as far as I can tell) to be covered by Matt’s excellent response for the continuous time cases?

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ Dan, I'm very pressed for time at the moment, but I would start by using the DFT matrix to write a set of linear equations relating $x$ and $X$ as you have defined them, and then seeing if it has any solutions. $\endgroup$
    – MBaz
    Jun 15, 2021 at 16:42
  • 2
    $\begingroup$ @DanBoschen: I just did the same thing. N=2 and N=4 are no go. I think the way to go is expand this into any N and proof it's a no go. $\endgroup$
    – Hilmar
    Jun 15, 2021 at 18:17
  • 1
    $\begingroup$ @OverLordGoldDragon Nice one to you. Do you mean to say you saw instantly that odd N would work? $\endgroup$
    – Dan Boschen
    Jun 16, 2021 at 2:10
  • 1
    $\begingroup$ @DanBoschen Yeah, for "can it be done" I favor an information-oriented perspective. I've learned to pay attention to "left > right" in odd DFT; if "causal" was defined as zeros from $0$ to $N/2$, no cake. $\endgroup$
    – OverLordGoldDragon
    Jun 16, 2021 at 2:37
  • 1
    $\begingroup$ @DanBoschen My perspective's entirely from code - whether indexing or plotting, DC always ends up on left, when output directly by fft(x). Surely this is arbitrary and centering DC is nicer in its own regards, like saying $0$ is neither $+$ nor $-$. But yes, I meant len(x[:N//2+1]) > len(x[N//2+1:]). $\endgroup$
    – OverLordGoldDragon
    Jan 13, 2022 at 12:47

2 Answers 2

Reset to default
2
$\begingroup$

NOTE: answer's for "zero for $n \geq N/2$", rather than $n > N/2$ (I've misread), but logic herein applies and shows that both odd and even have infinite solutions for latter.

Doable. But only for odd $N$. And it will have infinite solutions.

Example:

$$ \begin{align} x &= [x_0, x_1, 0] \\ x_0 &= 0.5 \left(1 + \frac{1}{\sqrt{3}}\right) + j 0.5\left(1 - \frac{1}{\sqrt{3}}\right) \\ x_1 &= 0.5 \left(1 - \frac{1}{\sqrt{3}}\right) + j 0.5\left(1 - \frac{1}{\sqrt{3}}\right) \end{align} $$

import numpy as np
x = np.array([.5 + .5/np.sqrt(3) + 1j*(.5 - .5/np.sqrt(3)),
              .5 - .5/np.sqrt(3) + 1j*(.5 + .5/np.sqrt(3)), 
              0])
xf = np.fft.fft(x)
assert np.allclose(xf[2], 0)

Proof

We seek to encode $N / 2 - 1$ bits of information${}^1$ with $N / 2$ degrees of freedom; there are infinite such encodings. For even case, we seek to enforce $N/2$ zeros with $N/2$ degrees of freedom. We know one solution is $x=X=0$. By uniqueness (one-to-one), we thus conclude it is the only solution.

I derive the solution for $N=3$, which generalizes for any odd $N$:

x * exp(k) = X
(x.re + x.im) * (cos - i*sin)
(x.re*cos - x.re*i*sin) + (x.im*i*cos - x.im*i*i*sin) = X.re + X.im*i
x.re*cos + x.im*sin = X.re
x.im*cos - x.re*sin = X.im

 cos(k=0) * x.re + sin(k=0) * x.im = X[0].re
 cos(k=1) * x.re + sin(k=1) * x.im = X[1].re
 cos(k=2) * x.re + sin(k=2) * x.im = X[2].re

-sin(k=0) * x.re + cos(k=0) * x.im = X[0].im
-sin(k=1) * x.re + cos(k=1) * x.im = X[1].im
-sin(k=2) * x.re + cos(k=2) * x.im = X[2].im

[1   1   1] * r + [0    0     0] * i = R0
[1 -.5 -.5] * r + [0   .87 -.87] * i = R1
[1 -.5 -.5] * r + [0  -.87  .87] * i = R2

[0    0     0] * r + [1   1   1] * i = I0
[0  -.87  .87] * r + [1 -.5 -.5] * i = I1
[0   .87 -.87] * r + [1 -.5 -.5] * i = I2

r2 = i2 = 0
-->
[1   1   0] * r + [0    0   0] * i = R0
[1 -.5   0] * r + [0   .87  0] * i = R1
[1 -.5   0] * r + [0  -.87  0] * i = R2

[0    0   0] * r + [1   1  0] * i = I0
[0  -.87  0] * r + [1 -.5  0] * i = I1
[0   .87  0] * r + [1 -.5  0] * i = I2

r0 +    r1          = R0;
r0 - .5*r1 + .87*i1 = R1;
r0 - .5*r1 - .87*i1 = R2;

          i0 +    i1 = I0;
-.87*r1 + i0 - .5*i1 = I1;
 .87*r1 + i0 - .5*i1 = I2;

Now we arbitrarily set R0=I0=1 and feed it to Wolfram Alpha, which gives us (I set g as placeholder for sin(2pi/3)):

and for the general case:

1 - Note: it's actually $N - 1$ bits of information ($\lfloor N/2 \rfloor$ reals and imaginaries) and $N + 1$ degrees of freedom ($\lceil N/2 \rceil$ re & im), which shows in the example where we specify two values (R0, I0) to obtain one solution.

Improve this answer
$\endgroup$
4
$\begingroup$

For $N \operatorname{mod} 4 \in \{0, 1\}$, positive examples can be generated by shifting and complex sinusoidal modulating particular eigenfunctions of DFT generated in Octave by function geteig_multiplicative from this answer, here with example $N=4$:

N = 4
x = circshift(geteig_multiplicative(N).*exp(2*pi*i*[0:N-1]/N*floor((N + 2)/4)), floor((N + 2)/4))
X = fft(x)

Prettified output:

$$\begin{eqnarray}x&=&\left[-\frac{i}{2}, 1, \frac{i}{2}, 0\right] \\X&=&[1, -2i, -1, 0]\end{eqnarray}$$

This contradicts the finding by @DanBoschen and @Hilmar that there are no solutions for $N=4$.

For small $N$ with arbitrary $N\operatorname{mod}4$, positive examples can be generated numerically using the function get_example from the following Octave script. The function repeats enforcing the constraints and normalizing the signal alternatingly in time and frequency domain.

function retval = calc_error(x, N)
  retval = sqrt(sumsq(x.*([0:(N-1)] > N/2)));
endfunction
    
function retval = constrain(x, N)
  x = x.*([0:(N-1)] <= N/2);
  x /= sumsq(x);
  retval = x;
endfunction

function retval = get_example(N, precision = 0, x = ones(1, N))
  lasterror = Inf;
  iter = 0;
  do
    x = constrain(x, N);
    X = fft(x)/sqrt(N);
    error = calc_error(X, N);
    X = constrain(X, N);
    x = ifft(X)*sqrt(N);
    error += calc_error(x, N)
    iter++;
    if (error >= lasterror)
      break;
    endif
    lasterror = error;
  until (error <= precision)
  printf("Iterations: %d\n", iter);
  retval = constrain(x, N);
endfunction

I recently learned that these kinds of algorithms are known as Projection Onto Convex Sets (POCS) algorithms. I also tried a variant, Dykstra's algorithm, but it converges only marginally faster:

function retval = calc_error(x, N)
  retval = sqrt(sumsq(x.*([0:(N-1)] > N/2)));
endfunction

function retval = constrain_dykstra(x, N)
  x = x.*([0:(N-1)] <= N/2);
  retval = x;
endfunction

function retval = get_example_dykstra(N, precision = 0, x = ones(1, N))
  secondlasterror = Inf;
  lasterror = Inf;
  iter = 0;
  p = zeros(size(x));
  q = zeros(size(x));
  do
    y = constrain_dykstra(x + p, N);
    p = x + p - y;
    x = ifft(constrain_dykstra(fft(y + q)/sqrt(N), N))*sqrt(N);
    q = y + q - x;
    p /= sqrt(sumsq(x));
    q /= sqrt(sumsq(x));
    x /= sqrt(sumsq(x));
    error = calc_error(x, N)
    iter++;
    if (error >= secondlasterror)
      break;
    endif
    secondlasterror = lasterror;
    lasterror = error;
  until (error <= precision)
  printf("Iterations: %d\n", iter);
  x = constrain_dykstra(x, N);
  retval = x;
endfunction
Improve this answer
$\endgroup$
10
  • 1
    $\begingroup$ Nice one Olli! Nice to see you here. This also contradicts finding by @OverlordGoldDragon that is is doable only for odd N. $\endgroup$
    – Dan Boschen
    Feb 11 at 18:03
  • $\begingroup$ hmm I appear to have thought $n\geq N/2$, if it's $>$ then "left > right" always holds. Dunno about filing Nyquist under positives but sure. I'll look again tomorrow $\endgroup$
    – OverLordGoldDragon
    Feb 11 at 20:33
  • 1
    $\begingroup$ I tried modifying constrain and calc_error in the iterative algorithm get_example to require zeros in $n \ge N/2$ as in @OverLordGoldDragon's answer. Then it converges only for odd $N$, so there is no contradiction against the answer. $\endgroup$
    – Olli Niemitalo
    Feb 13 at 12:06
  • 1
    $\begingroup$ @DanBoschen: For zeros required at $n > N/2$: I showed how to calculate solutions when $N \operatorname{mod} 4 \in \{0, 1\}$, and also gave two iterative algorithms that produce solutions for any $N$ although it gets impractically slow for $N$ larger than about $20$. For zeros required at $n \ge N/2$: I was only able to generate solutions for odd $N$ using the iterative algorithm. Note that at odd $N$ the conditions $n \ge N/2$ and $n > N/2$ are equivalent (with $n$ an integer and $N/2$ an integer plus $1/2$) so any solution found for $n > N/2$ is also valid for $n \ge N/2$. $\endgroup$
    – Olli Niemitalo
    Feb 28 at 19:34
  • 1
    $\begingroup$ @DanBoschen For even $N$, you don't need to worry about a Nyquist bin if you choose a frequency-shifted variant of the discrete Fourier transform, with a half bin-width shift. Maybe throw in a half sampling-period time shift too... :D $\endgroup$
    – Olli Niemitalo
    Feb 28 at 20:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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