APPENDIX: PROPOSITIONS AND PROOFS

Recall that the two-dimensional mapping of a $N$-dimensional data point is defined by real and imaginary components of:

$$\mathcal{F}_1(\mathbf{x}[n]) = \sum_{n=0}^{N-1}{x[n] \mathbf{W}_N^{n}} = \sum_{n=0}^{N-1}{x[n] e^{-i2\pi n/N}}.$$ (1)

where $\mathbf{W}_N = e^{-i2\pi/N}$ is called twiddle factor, $2\pi/N$ is the base frequency.

Lemma 1 (Conjugate)   For any two complex numbers $z$ and $w$, (1) $\overline{z+w}$ = $\overline{z}$ + $\overline{w}$, (2) $\overline{z \, w}$ = $\overline{z} \, \overline{w}$, (3) $\overline{\overline{z}}=z$.

Lemma 2 (Square Expanding)  

$$\left (\sum_{n=0}^{N-1}{a_n} \right )^2 = \sum_{n=0}^{N-1}{a_n^2} + 2 \sum_{k=1}^{N-1}\sum_{t=0}^{N-k-1}{a_t \, a_{t+k}}.$$

Lemma 3 (Cancellation)   Let $j \in \mathbb{N}$, then $$\sum_{n=0}^{N-1}{e^{-i2\pi j n /N}} = \sum_{n=0} ^{N-1}{\cos(2\pi j n/N )} = \sum_{n=0}^{N-1}{\sin(2\pi j n/N )} = \mathbf{0}$$.
Proof:

$$\sum_{n=0}^{N-1}{e^{-i2\pi jn/N}} = \frac{e^{-i2\pi jN/N}-1}{e^{-i2\pi/N}-1} = \frac {1-1}{e^{-i2\pi/N}-1} = \mathbf{0}.$$

then apply $e^{i\theta}=\cos\theta+i\sin\theta$, we get

$$\sum_{n=0}^{N-1}{e^{-i2\pi jn/N}} = \sum_{n=0}^{N-1}{\cos(2\pi jn/N)} - i\sum_{n=0}^{N-1}{\sin(2\pi jn/N)} = 0 + 0i.$$

Lemma 4 (Homomorphism)   FFHP is homomorphic. $\mathcal{F}_1 (a\, \mathbf{x}[n] + b\,\mathbf{y}[n]) = a\, \mathcal{F}_1 (\mathbf{x}[n]) +b\, \mathcal{F}_1(\mathbf{y}[n])$.

From the formula in Eq. (), we get

$$\mathcal{F}_1 (a\, \mathbf{x}[n] + b\,\mathbf{y}[n]) = \sum_{n=0}^{N-1}{(a\,x[n] + b\,y[n])e^{-i2\pi n/N}} = a\, \sum_{n=0}^{N-1}{x[n] e^{-i2\pi n/N}} + b\,\sum_{n=0}^{N-1}{y[n]e^{-i2\pi n/N}}$$

$$= a\, \mathcal{F}_1(\mathbf{x}[n]) + b\,\mathcal{F}_1(\mathbf{y}[n]).$$

$\Box$

Proposition 1 (Cancellation)   An $N$ -dimensional point with equal dimension values will be mapped onto the origin. If $\mathbf{x}[n] = [a,\ldots,a]$, then $\mathcal{F}_1(\mathbf{x}[n]) = \mathbf{0}$.

Proof: From the formula in Eq. (), we get

$$\mathcal{F}_1(\mathbf{x}[n]) = \sum_{n=0}^{N-1}{a\, e^{-i2\pi n/N}} = a\, \sum_{n=0}^{N-1}{e^{-i2\pi n/N}}.$$

By Lemma , let $j=1$. $\mathcal{F}_1(\mathbf{x}[n]) = \mathbf{0}$. $\Box$

Proposition 2 (Addition by a Constant)   Two $N$-dimensional points with addition of a constant to each dimension value will be mapped onto the same point. If $\mathbf{y}[n] = \mathbf{x}[n] + a$, then $\mathcal{F}_1(\mathbf{y}[n]) = \mathcal{F}_1 (\mathbf{x} [n])$.

Proof: From the formula in Eq. (), we get

$$\mathcal{F}_1(\mathbf{y}[n]) = \sum_{n=0}^{N-1}{(x[n]+a) e^{-i2\pi n/N}} = \sum_{n=0}^{N-1}{(x[n]\,e^{-i2\pi n/N} + a\, e^{-i2\pi n/N})}$$

$$= \sum_{n=0}^{N-1}{x[n]\, e^{-i2\pi n/N} + a\, \sum_{n=0}^{N-1}e^{-i2\pi n/N}} = \mathcal{F}_1(\mathbf{x}[n]) + a\, \sum_{n=0}^{N-1}e^{-i2\pi n/N}$$

By Proposition , the second summation is $\mathbf{0}$. $\Box$

Proposition 3 (Scaling by a Constant)   Two $N$-dimensional points with scaling of a constant to each dimension value will be mapped onto two points on a line through the origin. If $\mathbf{y}[n] = a\,\mathbf{x}[n]$, then $\mathcal{F}_1 (\mathbf{y}[n]) = a\;\mathcal{F}_1(\mathbf{x}[n])$.

Proof: From the formula in Eq. (), we get

$$\mathcal{F}_1(\mathbf{y}[n]) = \sum_{n=0}^{N-1}{a \, x[n] e^{-i2\... ...= a\, \sum_{n=0}^{N-1}{x[n] e^{-i2\pi n/N}} = a\, \mathcal{F}_1(\mathbf{x}[n])$$

$\Box$

Proposition 4 (Time Shifting)   Two $N$-dimensional points with constant time shifting will be mapped onto a circle concentric to the unit circle. The angle between two images is $d 2\pi/N$. If $\mathbf{y}[n] = \mathbf{x} [n-d]$, then $\mathcal{F}_1(\mathbf{y}[n]) = \mathcal{F}_1 (\mathbf{x}[n]) \mathbf{W}_N^d$.

Proof: Assume $0\leq n<N$, let $l=n-d$, then $n=l+d$. When $n=0$, $l=-d$ and when $n=N-1$, $l=N-1-d$. From the formula in Eq. (), we get

$$\mathcal{F}_1(\mathbf{y}[n]) = \mathcal{F}_1(\mathbf{x}[n-d]) = \sum_{l=-d}^{N-1-d}{x[l] e^{-i2\pi (l+d)/N}}$$

$$= \sum_{l=-d}^{N-1-d}{x[l] e^{-i2\pi l/N} e^{-i2\pi d/N}} = \mathbf{W}_N^d\, \sum_{l=-d}^{N-1-d}{x[l] e^{-i2\pi l/N}}$$

However, $e^{i2\pi n/N} = e^{i2\pi (n+N)/N}$ and $x[n]=x[n+N]$,

$$\sum_{l=-d}^{N-1-d}{x[l] e^{-i2\pi l/N}} = \sum_{l=-d}^{-1}{x[l+N]\, e^{-i2\pi (l+N)/N}} + \sum_{l=0}^{N-1-d}{x[l]\, e^{-i2\pi l/N}}$$

Let $t=l+N$ for the first summation and $t=l$ for the second summation, we get

$$\sum_{l=-d}^{N-1-d}{x[l] e^{-i2\pi l/N}} = \sum_{t=N-d}^{N-1}{x[t... ...i t/N}} = \sum_{t=0}^{N-1}{x[t] e^{-i2\pi t/N}} = \mathcal{F}_1(\mathbf{x}[n])$$

Therefore, $\mathcal{F}_1(\mathbf{y}[n]) = \mathcal{F}_1 (\mathbf{x}[n]) \mathbf{W}_N^d$. $\Box$

Proposition 5 (Line)   Under FFHP, an $N$-dimensional line will be mapped onto a two dimensional.

Proof: A $N$-dimensional line $l$ through point $P$ and parallel to a $N$-vector $\Delta$ can be expressed as $P + t \Delta$ where $-\infty \leq t \leq \infty$. Let $Q$ and $R$ are two different points on $l$, then $Q = P + \alpha \Delta$ and $R = P+\beta \Delta$, for some $\alpha,\beta\in\mathbb{R}$. Let the corresponding signals for $P$, $Q$, $R$, and $\Delta$ be $\mathbf{p}[n]$, $\mathbf{q}[n]$, $\mathbf{r}[n]$, and $\delta[n]$. By Lemma , $\mathcal{F}_1(\mathbf{q}[n]) = \mathcal{F}_1(\mathbf{p}[n]+\alpha \mathbf{\delta}[n])) = \mathcal{F}_1(\mathbf{p}[n]) + \alpha \mathcal{F}_1(\delta[n])$ and $\mathcal{F}_1(\mathbf{r}[n]) = \mathcal{F}_1(\mathbf{p}[n]) + \beta \mathcal{F}_1(\delta[n])$. Compare the definition of a line above, $\mathcal{F}_1 (\mathbf{q}[n])$ and $\mathcal{F}_1(\mathbf{r}[n])$ are two points on a two dimensional line through $\mathcal{F}_1(\mathbf{p}[n])$ and parallel to the vector $\mathcal{F}_1(\delta[n])$. $\Box$

Definition 1 (Mean, Autocovariance, Variance, Autocorrelation Coefficient)   The mean of a signal $\mathbf{x}[n]$ is defined as $\widehat{x} = \sum_{n=0}^{N-1}{x[n]/N}$. The $k$-th sample autocovariance coefficient of a signal $\mathbf{x}[n]$ is defined as $g_k = \sum_{n=0}^{N-1-k} {(x[n]- \widehat{x})(x[n+k]-\widehat{x})}/N$. $g_0$ is called the variance of $\mathbf{x}[n]$. The $k$-th sample autocorrelation coefficient is defined as $r_k=g_k/g_0$.

Proposition 6 (Fundamental Distance)   Let $\mathbf{w}[n]$ = $\mathbf{x}[n] - \mathbf{y}[n]$, be the difference between $\mathbf{x}[n]$ and $\mathbf{y}[n]$. The distance between $\mathcal{F} _1(\mathbf{x}[n])$ and $\mathcal {F}_1(\mathbf{y}[n])$ is

$$\Vert\mathcal{F}_1(\mathbf{w}[n])\Vert^2 = g_0 N \left (1 + 2 \sum_{k=1}^{N-1} {r_k \cos(2\pi k/N)} \right ).$$

Proof: By Lemma , the distance between $\mathcal {F}_1(\mathbf{y}[n])$ and $\mathcal{F} _1(\mathbf{x}[n])$ is $\Vert\mathcal{F}_1(\mathbf{w}[n])\Vert$. From Eq. (), we get

$$\Vert\mathcal{F}_1(\mathbf{w}[n])\Vert \ = \ \Vert \sum_{n=0}^{N-... ...rt \ = \ \Vert\sum_{n=0}^{N-1}{w[n]\cos(2\pi n/N) -i w[n] \sin(2\pi n/N)}\Vert$$

Let $\omega=2\pi/N$, by Lemma , we have $$\sum_{n=0}^{N-1}{\cos(n\omega)} = \sum_{n=0}^{N-1} {\sin(n\omega)} = 0$$. Now add a term $\widehat{w}$, the mean of $\mathbf{w}[n]$,

$$\Vert\mathcal{F}_1(\mathbf{w}[n])\Vert^2 = \left (\sum_{n=0}^{N-1} {w[n]\cos(n\omega)} \right )^2 + \left (\sum_{n=0}^{N-1} {w[n]\sin(n\omega)} \right)^2$$

$$= \left (\sum_{n=0}^{N-1} {(w[n]-\widehat{w}) \cos(n\omega)} \right )^2 + \left (\sum_{n=0}^{N-1} {(w[n]-\widehat{w}) \sin(n\omega)} \right)^2$$

Expending each squaring terms by Lemma , we get

$$\sum_{n=0}^{N-1}{(w[n]-\widehat{w})^2(\cos^2(n\omega)+\sin^2(n\om... ...}^{N-1} {\sum_{t=0}^{N-1-k}{[(w[t]-\widehat{w}) (w[t+k]-\widehat{w}) \Delta]}}$$

where $\Delta = \cos(t\omega)\cos((t+k)\omega) + \sin(t\omega)\sin((t+k)\omega)$. By trigonometry identity $\cos \theta\cos \phi + \sin \theta\sin \phi = \cos (\phi - \theta)$, $\Delta =\cos(k\omega)$. Now we have

$$\Vert\mathcal{F}_1(\mathbf{w}[n])\Vert^2 = \sum_{n=0}^{N-1}{(w[n]-\widehat{w})^2} + 2 \sum_{k=1}^{N-1}{\sum_{t=0}^{N-1-k}{[(w[t]-\widehat{w}) (w[t+k]-\widehat{w}) \cos(k\omega)]}}$$

$$= N (g_0 + 2 \sum_{k=1}^{N-1}{g_k \cos(k\omega)}) = g_0 N \left (1 + 2 \sum_{k=1}^{N-1} {r_k \cos(2\pi k/N)} \right )$$

$\Box$

Definition 2 (Twiddle Power Index)   For an $N$-point signal, the $k$-th harmonic twiddle power index (HTPI in short) is a sequence of $N$ time indices chosen from $0,\ldots,N-1$. It corresponds to the order that a particular time point being mapped on to the consecutive powers of twiddle factor $\mathbf{W}_N^0$,..., $\mathbf{W}_N^{N-1}$, by the $k$-th harmonic.

Example 1   For a $5$-point signal, the first harmonic twiddle power index is $[0, 1, 2, 3, 4]$. The second HTPI is $[0, 3, 1, 4, 2]$. The third HTPI is $[0, 2, 4, 1, 3]$. Take a closer look at the second HTPI. Since $\mathcal{F}_2 (\mathbf{x}[n]) = \sum_{n=0}^{N-1} {x[n] \mathbf{W}_N^{2k}}$, we have $\mathcal{F}_2 (\mathbf{x}[n]) = x[0]\mathbf{W}_5^0 +x[1]\mathbf{W}_5^2 +x[2]\m... ...+ x[3]\mathbf{W}_5^1+ x[1]\mathbf{W}_5^2+x[4]\mathbf{W}_5^3 +x[2]\mathbf{W}_5^4$.

Proposition 7 (Harmonic Equivalence)   A $k$-th harmonic of a signal ($k>1$) is equivalent to the first harmonic of the the origin signal being reordered by the $k$-th harmonic twiddle power index.

Proof: By definition of harmonic and twiddle power index. $\Box$