Nonlinear examples
1. Sum of square moduli
$$
f(\cdot) = \sum |\cdot|^2 \tag{1}
$$
-->
$$
\texttt{DFT}\left\{ \sum_{n=0}^{N-1} \left|x[n]\right|^2 \right\} =
\sum_{k=0}^{N-1} \left| \texttt{DFT}\left\{ x[n] \right\} \right|^2
$$
assuming the $1/\sqrt{N}$ definition. This is simply Parseval-Plancherel's theorem.
The result can be interpreted as a joint statement on conservation of energy and information, in that the equality of sums is former, and that the fft(x) == x
for len(x) == 1
is enabled by an invertible basis which returns an identity to refelct that there's no "variation" in a length-one sequence, only an offset that equals itself.
$(1)$ can be made much stronger by realizing that the result is permutation-invariant - e.g.
$$
f(\cdot) = \sum \left| \texttt{random_shuffle}(\cdot) \right|^2 \tag{1b}
$$
so now $f$ is non-deterministic.
$$
f(\cdot) = \sum \lambda (\cdot ) \tag{2}
$$
-->
$$
\begin{align}
\texttt{DFT}\left\{ \sum_{n=0}^{N-1} \lambda(x[n]) \right\}
&=
\sum_{k=0}^{N-1} \lambda\left( \texttt{DFT}\left\{ x[n] \right\} \right) \\
\Rightarrow N &= N
\end{align}
$$
This is simply fft(len(x)) == len(fft(x))
. This is trivial-looking, but in general the Lebesgue measure is far from trivial.
The result is nothing special besides implying a possibility for invertibility via N_in >= N_out
- but also the bit on fft(x) == x
.
1 & 2 generalization
Works for all operation(x) == operation(fft(x))
if len(operation(x)) == 1
.
3. Non-aggregate results
Aggregation destroys tons of information, which eases attaining commutativity and a bunch of other things. Still, $(1)$ isn't trivial.
If $f$ is to be nonlinear and pointwise-only, it must concern itself with symmetries and complex values. If $x$ is real-valued, then $\texttt{DFT}(x)$ is Hermitian-symmetric even if $x$ isn't, which forces symmetry and uniqueness (avoiding one-to-many) considerations onto $f(\texttt{DFT}(x))$. And $\texttt{DFT}(f(x))$ is guaranteed to be not Hermitian symmetric if $f(x)$ is complex-valued. Note that Royi's answer isn't pointwise-only, and the only pointwise-only $f$ that's linear appears to be the trivial $f(x) = \text{const} \cdot x$.
The case of non-aggregate output that involves aggregate operations has lot more freedom per not restricting its output at index $n$ to be derived only from input at index $n$; symmetry considerations remain, but are easier to satisfy.
Code
import numpy as np
def f1(g):
np.random.shuffle(g) # test the stronger version; in-place op
return np.sum(np.abs(g)**2)
def f2(g):
return np.sum(np.ones(len(g)))
def fft_alt_norm(x):
x = np.atleast_1d(x) # in case len(x) == 1
return 1/np.sqrt(len(x)) * np.fft.fft(x)
for N in (128, 129):
x = np.random.randn(N) + 1j*np.random.randn(N)
for f in (f1, f2):
a = fft_alt_norm(f(x))
b = f(fft_alt_norm(x))
assert np.allclose(a, b)