Erratum for “Deterministic Cramer-Rao Bound for Strictly Non-Circular Sources and Analytical Analysis of the Achievable Gains”

I am posting since since we were recently made aware of an error in our journal paper “Deterministic Cramer-Rao Bound for Strictly Non-Circular Sources and Analytical Analysis of the Achievable Gains” (T-SP vol. 64, no. 17). Unfortunately, T-SP does not allow (yet?) to publish errata alongside the original papers, nor to send updates. Therefore, right now the best we can do is to update the arxiv version and inform the community via this blog post.

In fact, the error is more or less a copy-paste error from the earlier conference version “Deterministic Cramér-Rao Bounds for strict sense non-circular sources” (WSA 2007) that contains the same error, although harder to spot.

As the title says, both papers are concerned with Deterministic Cramér-Rao Bounds (CRBs) for strictly non-circular sources. A closed-form expression of the CRB was derived and given by the expression (8) in WSA2007, which reads as

\newcommand{ma}[1]{{\mathbf {#1}}}
\ma{C} = & \frac{\sigma^2}{2N} \Big\{ \left(\ma{G}_2-\ma{G}_1 \ma{G}_0^{-1} \ma{G}_1^T \right) \odot \ma{\hat{R}}_{S,0}
\\ & + \left[ \left( \ma{G}_1 \ma{G}_0^{-1} \ma{H}_0 \right) \odot \ma{\hat{R}}_{S,0} \right] \left[ \left( \ma{G}_0-\ma{H}_0^T \ma{G}_0^{-1} \ma{H}_0 \right) \odot \ma{\hat{R}}_{S,0} \right]^{-1}
\\ & \cdot \left[ \left(\ma{H}_1^T- \ma{H}_0^T \ma{G}_0^{-1} \ma{G}_1^T \right) \odot \ma{\hat{R}}_{S,0} \right]
\\ & + \left[ \ma{H}_1 \odot \ma{\hat{R}}_{S,0} \right] \cdot \left[ \ma{G}_0 \odot \ma{\hat{R}}_{S,0} \right]^{-1} \cdot \left[ \left( \ma{H}_0^T \ma{G}_0^{-1} \ma{G}_1^T \right) \odot \ma{\hat{R}}_{S,0} \right]
\\ & + \left[ \ma{H}_1 \odot \ma{\hat{R}}_{S,0} \right] \cdot \left[ \ma{G}_0 \odot \ma{\hat{R}}_{S,0} \right]^{-1}
\cdot \left[ \left( \ma{H}_0^T \ma{G}_0^{-1} \ma{H}_0 \right) \odot \ma{\hat{R}}_{S,0} \right]
\\& \cdot \left[ \left( \ma{G}_0-\ma{H}_0^T \ma{G}_0^{-1} \ma{H}_0 \right) \odot \ma{\hat{R}}_{S,0} \right]^{-1}
\cdot \left[ \left( \ma{H}_0^T \ma{G}_0^{-1} \ma{G}_1^T \right) \odot \ma{\hat{R}}_{S,0} \right]
\\ &-\left[ \ma{H}_1 \odot \ma{\hat{R}}_{S,0} \right] \cdot \left[ \left( \ma{G}_0-\ma{H}_0^T \ma{G}_0^{-1} \ma{H}_0 \right) \odot \ma{\hat{R}}_{S,0} \right]^{-1}
\cdot \left[ \ma{H}_1^T \odot \ma{\hat{R}}_{S,0} \right] \Big\}^{-1}, \end{align}$$

where the matrices $\ma{G}_i, \ma{H}_i$ for $i=0, 1, 2$ are all of size $d \times d$ and given by

\ma{G}_0 & = & {\rm Re}\{\ma{\Psi}^* \cdot \ma{A}^H \cdot \ma{A} \cdot \ma{\Psi}\} \\
\ma{H}_0 & = & {\rm Im}\{\ma{\Psi}^* \cdot \ma{A}^H \cdot \ma{A} \cdot \ma{\Psi}\} \\
\ma{G}_1 & = & {\rm Re}\{\ma{\Psi}^* \cdot \ma{D}^H \cdot \ma{A} \cdot \ma{\Psi}\} \\
\ma{H}_1 & = & {\rm Im}\{\ma{\Psi}^* \cdot \ma{D}^H \cdot \ma{A} \cdot \ma{\Psi}\} \\
\ma{G}_2 & = & {\rm Re}\{\ma{\Psi}^* \cdot \ma{D}^H \cdot \ma{D} \cdot \ma{\Psi}\} \\
\ma{H}_2 & = & {\rm Im}\{\ma{\Psi}^* \cdot \ma{D}^H \cdot \ma{D} \cdot \ma{\Psi}\}.

All nice and good, no problem so far. It was then though said in Section 4 how to generalize this to 2-D, where it was claimed that all we need to do is to replace $\ma{D} \in \mathbb{C}^{M \times d}$ by $\ma{D}_{{\rm 2D}} \in \mathbb{C}^{M \times 2d}$ and $\ma{\hat{R}}_{S,0}$ by $\ma{1}_{2 \times 2} \otimes \ma{\hat{R}}_{S,0}$. Well, the first statement is correct, the second one only partially. Unfortunately this went unnoticed into the TSP2016 paper, where the expression is given for $R$-D.

Why is it wrong? Well, you can see that for $R$-D, the size of $\ma{A}$ is unaffected while $\ma{D}$ goes from having $d$ columns to having $R\cdot d$ columns. Therefore, the size of $\ma{G}_0$ and $\ma{H}_0$ is unaffected ($d\times d$) whereas $\ma{G}_1$ and $\ma{H}_1$ are now $R \cdot d \times d$ and $\ma{G}_2$ and $\ma{H}_2$ are now $R\cdot d \times R\cdot d$. To make the CRB work, the augmentation of of $ \ma{\hat{R}}_{S,0} $ has to be done such that it is consistent with the dimensions of the $\ma{G}_i$ and $\ma{H}_i$.

Concretely, this means that $ \left(\ma{G}_2-\ma{G}_1 \ma{G}_0^{-1} \ma{G}_1^T \right) \odot \ma{\hat{R}}_{S,0} $ changes into $ \left(\ma{G}_2-\ma{G}_1 \ma{G}_0^{-1} \ma{G}_1^T \right) \odot \left(\ma{1}_{R\times R} \otimes \ma{\hat{R}}_{S,0}\right) $, which is the example treated in the paper. However, $ \left( \ma{G}_1 \ma{G}_0^{-1} \ma{H}_0 \right) \odot \ma{\hat{R}}_{S,0} $ becomes $ \left( \ma{G}_1 \ma{G}_0^{-1} \ma{H}_0 \right) \odot \left(\ma{1}_{R \times {\color{red}1}} \otimes \ma{\hat{R}}_{S,0} \right)$ and $ \left( \ma{G}_0-\ma{H}_0^T \ma{G}_0^{-1} \ma{H}_0 \right) \odot \ma{\hat{R}}_{S,0} $ remains unaffected.

Long story short, here is the corrected version of the R-D CRB (equation (15) in TSP2016):

\newcommand{ma}[1]{{\mathbf {#1}}}
\ma{C} = & \frac{\sigma^2}{2N} \Big\{ \left(\ma{G}_2-\ma{G}_1 \ma{G}_0^{-1} \ma{G}_1^T \right) \odot \left(\ma{1}_{R\times R} \otimes \ma{\hat{R}}_{S,0} \right)
\\ & + \left[ \left( \ma{G}_1 \ma{G}_0^{-1} \ma{H}_0 \right) \odot \left(\ma{1}_{R\times 1} \otimes \ma{\hat{R}}_{S,0} \right)\right] \left[ \left( \ma{G}_0-\ma{H}_0^T \ma{G}_0^{-1} \ma{H}_0 \right) \odot \ma{\hat{R}}_{S,0} \right]^{-1}
\\ & \cdot \left[ \left(\ma{H}_1^T- \ma{H}_0^T \ma{G}_0^{-1} \ma{G}_1^T \right) \odot \left(\ma{1}_{1\times R} \otimes \ma{\hat{R}}_{S,0}\right) \right]
\\ & + \left[ \ma{H}_1 \odot \left(\ma{1}_{R\times 1} \otimes \ma{\hat{R}}_{S,0}\right) \right] \cdot \left[ \ma{G}_0 \odot \ma{\hat{R}}_{S,0} \right]^{-1} \cdot \left[ \left( \ma{H}_0^T \ma{G}_0^{-1} \ma{G}_1^T \right) \odot \left(\ma{1}_{1\times R} \otimes \ma{\hat{R}}_{S,0} \right) \right]
\\ & + \left[ \ma{H}_1 \odot \left(\ma{1}_{R\times 1} \otimes \ma{\hat{R}}_{S,0}\right) \right] \cdot \left[ \ma{G}_0 \odot \ma{\hat{R}}_{S,0} \right]^{-1}
\cdot \left[ \left( \ma{H}_0^T \ma{G}_0^{-1} \ma{H}_0 \right) \odot \ma{\hat{R}}_{S,0} \right]
\\& \cdot \left[ \left( \ma{G}_0-\ma{H}_0^T \ma{G}_0^{-1} \ma{H}_0 \right) \odot \ma{\hat{R}}_{S,0} \right]^{-1}
\cdot \left[ \left( \ma{H}_0^T \ma{G}_0^{-1} \ma{G}_1^T \right) \odot \left(\ma{1}_{1\times R} \otimes \ma{\hat{R}}_{S,0} \right) \right]
\\ &-\left[ \ma{H}_1 \odot \left(\ma{1}_{R\times 1} \otimes \ma{\hat{R}}_{S,0}\right) \right] \cdot \left[ \left( \ma{G}_0-\ma{H}_0^T \ma{G}_0^{-1} \ma{H}_0 \right) \odot \ma{\hat{R}}_{S,0} \right]^{-1}
\cdot \left[ \ma{H}_1^T \odot \left(\ma{1}_{1\times R} \otimes \ma{\hat{R}}_{S,0}\right) \right] \Big\}^{-1}. \end{align}$$

The pattern is clear: the “outer” terms get expanded, while the “inner” terms remain unaffected.

We would like to thank Mr. Tanveer Ahmed for noticing the mistake! We sure hope we got it right this time! 🙂

Extended Trigonometric Pythagorean Identities: The Proof

I recently posted on Extended Trigonometric Pythagorean Identities and a “supercharged” version of them, which allows to simplify certain sums of shifted sine functions raised to integer powers. In particular, the claim was that

$$\sum_{n=0}^{N-1} \sin^2\left(x+n\frac{\pi}{N}\right) = \frac{N}{2}$$

or more generally for any integer $k$ and $N\geq k+1$:

$$\sum_{n=0}^{N-1} \sin^{2k}\left(x+n\frac{\pi}{N}\right) =
N \frac{(2k)!}{(k!)^2 2^{2k}} = \frac{N}{\sqrt{\pi}} \frac{\Gamma(k+1/2)}{\Gamma(k+1)} $$

However, in the initial TPI post, I struggled a bit with the proof. It took a while to realize that it is actually quite simple using (a) the algebraic series, i.e.,

$$ \sum_{n=0}^{N-1} q^n = \frac{1-q^N}{1-q}$$

for any $q \in \compl_{\neq 0,1}$ and (b) the fact that $\sin(x) = \frac{1}{2\jmath}\left({\rm e}^{\jmath x} – {\rm e}^{-\jmath x}\right)$. Let us use this relation to prove the following Lemma:

Lemma 1: For any $M \in \mathbb{Z}$, we have

$$ \sum_{n=0}^{N-1}{\rm e}^{\jmath \frac{2\pi}{N} \cdot M \cdot n} =
N & M = k \cdot N, \, k\in \mathbb{Z} \\
0 & {\rm otherwise}.

Proof: The proof is simple by realizing that the sum is in fact an arithmetic series with $q={\rm e}^{\jmath \frac{2\pi}{N} \cdot M}$. Obviously, if $M$ is an integer multiple of $N$ we have $q=1$ and the sum is equal to $N$. Otherwise, by the above identity, the series is equal to

$$\frac{1-{\rm e}^{\jmath 2\pi \cdot M}}{1-{\rm e}^{\jmath \frac{2\pi}{N} \cdot M}}
= \frac{{\rm e}^{\jmath \pi \cdot M}}{{\rm e}^{\jmath \frac{\pi}{N} \cdot M}}\cdot
\frac{{\rm e}^{-\jmath \pi \cdot M}-{\rm e}^{\jmath \pi \cdot M}}{{\rm e}^{-\jmath \frac{\pi}{N} \cdot M}-{\rm e}^{\jmath \frac{\pi}{N} \cdot M}}= {\rm e}^{\jmath \frac{\pi}{N}M(N-1)} \cdot \frac{\sin(\pi M)}{\sin(\frac{\pi}{N}M)} = 0,
since the enumerator is zero (and the denominator is not).

Piece of cake.

Now, we can proceed to prove the TPI for $2k=2$:

\sum_{n=0}^{N-1} \sin^2\left(x+n\frac{\pi}{N}\right)
& = \sum_{n=0}^{N-1}  \left(\frac{1}{2\jmath} {\rm e}^{\jmath(x+n\frac{\pi}{N})}- \frac{1}{2\jmath} {\rm e}^{-\jmath(x+n\frac{\pi}{N})}\right)^2\\
& = -\frac{1}{4}\sum_{n=0}^{N-1} {\rm e}^{2\jmath(x+n\frac{\pi}{N})} + {\rm e}^{-2\jmath(x+n\frac{\pi}{N})} – 2 {\rm e}^{\jmath(x+n\frac{\pi}{N})-\jmath(x+n\frac{\pi}{N})} \\
& = -\frac{1}{4} {\rm e}^{2\jmath x} \sum_{n=0}^{N-1} {\rm e}^{\jmath 2n\frac{\pi}{N}}
-\frac{1}{4} {\rm e}^{-2\jmath x} \sum_{n=0}^{N-1} {\rm e}^{-\jmath 2n\frac{\pi}{N}}
-\frac{1}{4} \sum_{n=0}^{N-1} (-2) \\
& = -\frac{1}{4} \cdot 0 -\frac{1}{4}\cdot 0 -\frac{1}{4}\cdot(-2N) = \frac{N}{2}

where we have used Lemma 1 for $M=1$ and $M=-1$ (which for the Lemma to work requires $M\neq N$ and thus $N\geq 2$). Isn’t that simple? I wonder why I didn’t see it earlier.

Even better yet, this technique allows to extend the proof to other values of $k$. Let’s try $2k=4$:

\sum_{n=0}^{N-1} \sin^4\left(x+n\frac{\pi}{N}\right)
& = \sum_{n=0}^{N-1}  \left(\frac{1}{2\jmath} {\rm e}^{\jmath(x+n\frac{\pi}{N})}- \frac{1}{2\jmath} {\rm e}^{-\jmath(x+n\frac{\pi}{N})}\right)^4\\
& = \frac{1}{16} \sum_{n=0}^{N-1} {\rm e}^{4 \jmath(x+n\frac{\pi}{N})}
-4 {\rm e}^{3\jmath(x+n\frac{\pi}{N}) -\jmath(x+n\frac{\pi}{N})}
+6 {\rm e}^{2\jmath(x+n\frac{\pi}{N}) -2 \jmath(x+n\frac{\pi}{N})} \\ &
-4 {\rm e}^{\jmath(x+n\frac{\pi}{N}) -3\jmath(x+n\frac{\pi}{N})}
+ {\rm e}^{-4 \jmath(x+n\frac{\pi}{N})} \\
& = \frac{1}{16}{\rm e}^{4 \jmath x} \sum_{n=0}^{N-1} {\rm e}^{4 \jmath n\frac{\pi}{N}}
– \frac{4}{16}{\rm e}^{2\jmath x} \sum_{n=0}^{N-1}{\rm e}^{2 \jmath n\frac{\pi}{N}}
+ \frac{6}{16}\sum_{n=0}^{N-1} {\rm e}^{0} \\ &
– \frac{4}{16}{\rm e}^{-2\jmath x} \sum_{n=0}^{N-1}{\rm e}^{-2 \jmath n\frac{\pi}{N}}
+ \frac{1}{16}{\rm e}^{-4 \jmath x} \sum_{n=0}^{N-1} {\rm e}^{-4 \jmath n\frac{\pi}{N}} \\
& = \frac{1}{16} \cdot 0 – \frac{4}{16} \cdot 0 + \frac{6}{16} \cdot N – \frac{4}{16} \cdot 0 + \frac{1}{16} \cdot 0 = \frac{3}{8} N,

where this time we have used Lemma 1 for $M=2, 1, -1, -2$ and thus need $N\geq 3$. This already shows the pattern: The polynomic expansion creates mostly terms with vanishing sums except for the “middle” term where the exponents cancel. The coefficient in front of this term is $\frac{1}{2^{2k}}$ (from the $\frac{1}{2\jmath}$ that comes with expanding the sine) times ${2k \choose k}$ (from the binomial expansion). This explains where the constant $N \cdot \frac{(2k)!}{(k!)^2 2^{2k}}$ comes from.

Formally, we have

\sum_{n=0}^{N-1} \sin^{2k}\left(x+n\frac{\pi}{N}\right) & =
\sum_{n=0}^{N-1} \left( \frac{1}{2\jmath}{\rm e}^{\jmath(x+n\frac{\pi}{N})}
– \frac{1}{2\jmath}{\rm e}^{-\jmath(x+n\frac{\pi}{N})} \right)^{2k} \\
& =
\sum_{n=0}^{N-1} \frac{1}{(2\jmath)^{2k}} \sum_{\ell = 0}^{2k} {2k \choose \ell} (-1)^\ell
{\rm e}^{(2k-\ell) \jmath (x+n\frac{\pi}{N})}{\rm e}^{-\ell \jmath (x+n\frac{\pi}{N})} \\
& =
\sum_{n=0}^{N-1} \frac{(-1)^k}{2^{2k}} \sum_{\ell = 0}^{2k} (-1)^\ell {2k \choose \ell}
{\rm e}^{2(k-\ell) \jmath (x+n\frac{\pi}{N})}\\
& = \frac{(-1)^k}{2^{2k}} \sum_{\ell = 0}^{2k} (-1)^\ell {2k \choose \ell}
{\rm e}^{2(k-\ell) \jmath x} \sum_{n=0}^{N-1}
{\rm e}^{2(k-\ell) \jmath n\frac{\pi}{N}} \\
& = \frac{1}{2^{2k}} {2k \choose k} N,

where in the last step all terms $\ell \neq k$ vanish due to Lemma 1 applied for $M=k, k-1, …, 1, -1, …, -k+1, -k$. This requires $N\geq k+1$.

Eh voila.

Trigonometric Pythagorean Identity, supercharged

You know how they say good things always come back? Well, I recently stumbled over something that reminded me a lot on a post I had made about generalizations of the Trigonometric Pythagorean Identity. In short, the well-known identity $\sin^2(x)+\cos^2(x)=1$ can be generalized to a sum of $N\geq 2$ terms that are uniformly shifted copies of the sine function, which yields

$$\sum_{n=0}^{N-1} \sin^2\left(x+n\frac{\pi}{N}\right) = \frac{N}{2}$$

Well, I now came across a sum of fourth powers of shifted sine functions and much to my initial surprise, these admit very similar simplifications. In fact, it works for any integer power! Look at what I found:

$$\sum_{n=0}^{N-1} \sin^{2k}\left(x+n\frac{\pi}{N}\right) =
N \frac{(2k)!}{(k!)^2 2^{2k}} = \frac{N}{\sqrt{\pi}} \frac{\Gamma(k+1/2)}{\Gamma(k+1)}  \; k \in \mathbb{N}

for $N\geq k+1$. Isn’t this fascinating? No matter to which even power we raise the shifted sines, their sums will always give a constant in the form $c_k \cdot N$ and this constants $c_k$ can be computed analytically.

Here are some examples: sum of squares ($k=1$): $c_1 = 1/2$, sum of fourth powers ($k=2$): $c_2=3/8$, $k=3: 5/16$, $k=4: 35/128$ and so on. Moreover, I think I know how to prove even the “supercharged” version of the TPI for any $k$. I’ll write about it in another blog post.

*Update*: And here is the proof!

*Update2*: Just another small addition: The coefficients $c_k$ satisfy an interesting recurrence relation since you can compute $c_k$ as

$$c_k = \frac{2k+1}{2k+2} c_{k-1}$$

with $c_0 = 1$. This makes clear what structure they actually have: $c_1 = \frac{1}{2}$, $c_2 = \frac{1 \cdot 3}{2 \cdot 4}$, $c_3 = \frac{1 \cdot 3 \cdot 5}{2\cdot 4\cdot 6}$, and so on. Each $c_k$ is equal to the product of the first $k$ odd numbers divided by the product of the first $k$ even numbers. If you like, you can write them with double factorials via

$$c_k = \frac{(2k-1)!!}{(2k)!!}.$$

They are highly related to Wallis’ integrals $W_n$. Maybe this is not too surprising since they are defined as

$$W_n = \int_{0}^{\frac{\pi}{2}} \cos^n(x) {\rm d}x$$

and satisfy

$$W_{2n} = \frac{(2n-1)!!}{(2n)!!} \frac{\pi}{2}.$$

So what the generalized TPI above shows is that the equispaced $N$-term sum delivers somehow the same value as the integral, no matter where we start the sum. Kind of cool I think.

Trigonometric Pythagorean Identity, extended

Here is to another curious and funny identity that has popped up many times and I’ve never quite gotten to find a proof for it:

$$ \sum_{n=0}^{N-1} \sin^2\left( x+ \frac{\pi}{N} n \right) = \frac{N}{2}, \; \forall N \in \mathbb{N} \geq 2$$

The Trigonometric Pythagorean Identity

What’s the connection to good old Pythagoras you ask? Well, let us look at it for $N=2$:

$$\sin^2 \left( x\right) + \sin^2\left( x + \frac{\pi}{2}\right) = 1$$

Since we can think of the cosine as a shifted version of the sine, where the shift is $\pi/2$, i.e., $\cos(x) = \sin(x+\pi/2)$, the last identity reads in fact as:

$$\sin^2 \left( x\right) + \cos^2\left( x \right) = 1$$

This may look familiar, in fact it is often referred to as the Trigonometric Pythagorean Identity (I’ll call it TPI for short). Here is a graphical illustration: On the left-hand side you see the sine and the cosine function, on the right-hand side their squares and the sum of the squares. They add up to a constant.

sin_cos sin_cos_square

Analytical arguments aside what is the link to Pythagoras’ Theorem? Well, there is a nice geometric illustrations of this. Consider a right triangle with one of its angles $\theta$, the sides being $a$ (the adjacent), $b$ (the opposite) and $c$ (the hypotenuse). From Pythagoras Theorem we know that $a^2 + b^2 = c^2$. At the same time we know from the definition of the trigonometric functions that sine and the cosine are related to the ratio between adjacent (opposite) and hypotenuse. In equations:

$$ \sin(\theta) = \frac{b}{c} \\ \cos(\theta) = \frac{a}{c}$$

Squaring and summing gives:

$$ \sin(\theta)^2 + \cos(\theta)^2 = \frac{a^2}{c^2} + \frac{b^2}{c^2} = \frac{a^2+b^2}{c^2} = 1$$

which explains the link to Pythagoras (a more complete version of the argument that also works for obtuse angles can be found on wikipedia).

Extended TPI for N>2

Okay, that was very elementary and maybe even boring stuff. The cool thing is that this works under much more general settings. I have not found a real name of the identity above but you could see it as a straightforward generalization of the TPI. Instead of considering a squared sine and one shifted copy (i.e., summing the shifts 0 and $\pi/2$) you can consider a sum of $N$ shifted copies that still add up to a constant provided that the shifts are chosen uniformly (i.e., all integer multiples of $\pi/N$).

Here is a graphical illustration for $N=3$ and $N=4$:

sin_cos_square_N3 sin_cos_square_N4

Cool stuff, right? Well I think so. However, the actual question of this blog post is, how do we prove this?

Proof idea 1: Decomposing into interleaved sums

This is the most straightforward and I like it a lot for its elegance. It tries to reduce an arbitary $N$ to elementary values of $N$ that have been proven once. It works very nicely for even $N$, where we can reduce to $N=2$. The drawback is that we have to do all other $N$ separately.

Let us start with $N=4$ for simplicity. For $N=4$ the sum looks like this:

$$S = \sin^2\left(x\right) + \sin^2\left(x + \frac{\pi}{4}\right) + \sin^2\left(x + \frac{\pi}{2}\right) + \sin^2\left(x + \frac{3\pi}{4}\right)$$

Actually, the first and the third term look familiar. They represent the case $N=2$ which we assume proven. Let us rearrange the sum by exchanging second and third term:

$$S = \underbrace{\sin^2\left(x\right)  + \sin^2\left(x + \frac{\pi}{2}\right)}_{f_1(x)} + \underbrace{\sin^2\left(x + \frac{\pi}{4}\right) + \sin^2\left(x + \frac{3\pi}{4}\right)}_{f_2(x)}$$

Now, for $f_1(x)$ we know that $f_1(x) = 1, \; \forall x$ from the TPI. The key is to realize that $f_2(x)$ is actually a shifted copy of $f_1(x)$, i.e., $f_2(x) = f_1(x + \pi/4)$, since both arguments just get an “extra” $\pi/4$ to it (remember that $3/4\pi$ is nothing but $\pi/2 + \pi/4$).

Now it’s easy, we have:

$$ S = f_1(x) + f_2(x) = f_1(x) + f_1(x-\pi/4) = 1 + 1 = 2,$$

since $f_1(x) = 1, \; \forall x$.


Does this work for any even $N$? Sure! We always have $f_1(x)$ in there (the first and the $N/2$-th term) and all other terms are $\pi/N$ shifted versions of it. Mathematically:

\begin{align} & \sum_{n=0}^{N-1} \sin^2\left( x+ \frac{\pi}{N} n \right) \\
= & \sum_{n=0}^{N/2-1} \sin^2\left( x+ \frac{\pi}{N} n \right) + \sin^2\left( x+ \pi + \frac{\pi}{N} n \right) \\
= & \sum_{n=0}^{N/2-1} \sin^2\left( x+ \frac{\pi}{N} n \right) + \cos^2\left( x+ \frac{\pi}{N} n \right) \\
= & \sum_{n=0}^{N/2-1} f_1\left(x + \frac{\pi}{N} n\right) \\
= & \sum_{n=0}^{N/2-1} 1 = \frac{N}{2}. \end{align}

Piece of cake.

This is nice but here is the trouble: for odd $N$ it’s not so easy. It already breaks down for $N=3$ since $f_1(x)$ does not even appear there. Even if you prove it for $N=3$, you can use this to prove it for all integer multiples of $3$ but it will not work for $N=5$. In other words, you would have to do this for every prime number separately. Not very elegant.

In essence, in case you were thinking of induction here, this will not work. Increasing $N$ by one changes all terms in the sum so you cannot go from $N$ to $N+1$ (only from $N$ to $2N$).

So, to prove it for arbitrary $N$ we need something else. What is there?

Proof idea 2: Power series

Wikipedia suggests that the original TPI can be proven using the definition of sine and cosine via its power series, i.e.,

\sin(x) & = \sum_{n=0}^\infty \frac{(-1)^n}{(2n+1)!} x^{2n+1} \\
\cos(x) & = \sum_{n=0}^\infty \frac{(-1)^n}{(2n)!} x^{2n}

Based on these, you can find the power series for $\sin^2$ and $\cos^2$, then  sum them and find out that $n=0$ gives $0 + 1 = 1$ and all $n>0$ give $(1-1)^{2n} = 0$.

Oookay, to be honest I haven’t tried this approach for the extended TPI. I can imagine it would work but for sure it would be a lot of work and quite surely far away from being an elegant proof. In highschool, we referred to these as the “crowbar-type” solutions.

It’s one of the typical points where your favorite textbook might simply say: the details of the proof are left as an excercise to the reader. Go ahead and give it a shot if you like… 😉

 Proof idea 3: Differentiating

As usual, writing things down makes the whole thing much more clear and more often than not gives new ideas. I just thought about differentiating the whole sum. If we can show that the differential is zero everywhere we at least know that the sum is constant. We still have to calculate this constant for a complete answer of course.

To calculate the differential let us look at $\sin^2(x)$ for a second. Its differential satisfies a cute relation:

$$\frac{{\rm d} \sin^2(x)}{{\rm d} x} = 2 \sin(x) \cos(x) = \sin(2x).$$

Why cute? Well, look at it for a second. If I differentiate $x^2$ I get $2x$, the 2 goes from the exponent in front of it. If I differentiate $\sin^2(x)$ I get $\sin(2x)$, the 2 goes inside the sine function. But please be careful here, this is not a general rule! It is a pure coincidence, like a little joke made by nature. In fact, it neither works for $n>2$ nor does it work for the cosine, which satisfies

$$\frac{{\rm d} \cos^2(x)}{{\rm d} x} = -2 \sin(x) \cos(x) = -\sin(2x).$$

Now let us turn to our sum $S$. We get

$$ \frac{{\rm d} S}{{\rm d} x} = \sum_{n=0}^{N-1} \sin\left( 2x+ \frac{2\pi}{N} n \right),$$

which we claim should be zero everywhere. This is an interesting one: if you overlap a sine with all its shifted copies (shifts being uniformly chosen from $[0,2\pi)$), the net result is zero. This is something I’ve seen many times before, especially in its relation to complex numbers.

Here is one geometrical interpretation. From Euler’s identity, we have

$${\rm e}^{\jmath x} = \cos(x) + \jmath \sin(x).$$

Therefore, if we write the following sum

$$ \sum_{n=0}^{N-1} {\rm e}^{\jmath (x+\frac{2\pi}{N}n)}
= \sum_{n=0}^{N-1} \cos\left(x+\frac{2\pi}{N}n\right) + \jmath \sum_{n=0}^{N-1} \sin\left(x+\frac{2\pi}{N}n\right),$$

i.e., our desired sum appears in the imaginary part (besides for a factor 2 on the $x$ but this does not matter since our argument applies for any $x$ so it can be rescaled). I am claiming the whole (complex) sum is zero, which shows that our desired sum is zero. Why is that so? Let’s factor out ${\rm e}^{\jmath x}$:

$$ \sum_{n=0}^{N-1} {\rm e}^{\jmath (x+\frac{2\pi}{N}n}) =  {\rm e}^{\jmath x} \underbrace{\sum_{n=0}^{N-1} {\rm e}^{\jmath \frac{2\pi}{N}n}}_z.$$

Now, what is $z$? Imagine a complex plane. Every term in the sum for $z$ is a point on the unit circle, spaced evenly. You can imagine the sum like this: take arrows to all points on the unit circles and add them all together. Find the sum of all these arrows. What is the net direction that remains when we’ve gone in all directions there are evenly? Well, it cannot be any point other than zero. Here is a visualization for it:


The whole thing is completely symmetric so there cannot be any preferred direction. We must have $z=0$, which proves the whole thing.

Of course this is, while being illustrative, a little hand-wavy. There are many more ways to prove $z=0$ more rigorously. I’m not sure which is the most concise and elegant. Right now, I keep thinking about DFTs here, since ${\rm e}^{\jmath \frac{2\pi}{N}n}$ is actually the second row of the $N \times N$ DFT matrix, which makes $z=0$ equivalent to showing that the first and the second row of a DFT matrix are mutually orthogonal. At the same time, ${\rm e}^{\jmath \frac{2\pi}{N}n}$ is the DFT of the sequence $\delta[n-1] = [0,1,0,…,0]$ in which case $z=0$ follows from the fact that the sum of the DFT coefficients is always equal to the first value of the sequence. But that’s just what comes to my mind first, I guess there are easier ways to prove this.

So there you have it, if we differentiate the sum, it’s easy to show that it must be constant. However, this is not the complete proof of the extended TPI yet, we still have to compute the constant. I’m not sure that is easy to do for an arbitrary $N$, is it?

To conclude, so far

So, what do we have? A quite elegant proof for even $N$ that does not generalize to odd $N$, a possible tedious proof idea based on power series, and a sort-of elegant proof that the sum is constant for arbitrary $N$ which still lacks the computation of this constant.

Now I’m curious: do you have better ideas to prove it? Have you come across this or similar identities? Do you know if it has a name and where it has been proven first?


*Update*: I have found a generalization to sine functions raised to any even power $2k$ and also an elegant proof, which also proves the TPI discussed in this post. Check it out if you like.

Widely linear system of equations, revisited

It seems I just cannot stop talking about widely linear equations. Sorry for being to monotonous. My colleague Dominik recently made me aware of the fact that it is possible to solve the widely linear system of equations

$$ \ma{A} \cdot \ma{x} + \ma{B} \cdot \ma{x}^* = \ma{c}$$

that I already visited in an earlier blog post in a much more convenient form. I was suggesting to stack the real and the imaginary parts of both $\ma{x}$ and $\ma{c}$ into long vectors which then transforms the entire system of $N$ complex-valued equations into a system of $2N$ real-valued equations, using real- and imaginary parts of $\ma{A}$ and $\ma{B}$ to construct the coefficients.

It is possible to completely avoid that. Simply conjugate the original equation, this gives you

$$ \ma{A}^* \cdot \ma{x}^* + \ma{B}^* \cdot \ma{x} = \ma{c}^*.$$

Combining both equations in one we can write

$$ \begin{bmatrix} \ma{A} & \ma{B} \\ \ma{B}^* & \ma{A}^* \end{bmatrix} \cdot \begin{bmatrix} \ma{x}  \\ \ma{x}^*  \end{bmatrix} = \begin{bmatrix} \ma{c}  \\ \ma{c}^*  \end{bmatrix}. $$

Therefore, provided the inverse exists, we have

$$ \begin{bmatrix} \ma{x}  \\ \ma{x}^*  \end{bmatrix} = \begin{bmatrix} \ma{A} & \ma{B} \\ \ma{B}^* & \ma{A}^* \end{bmatrix}^{-1} \cdot  \begin{bmatrix} \ma{c}  \\ \ma{c}^*  \end{bmatrix}.$$

This is of course redundant, since we only need to compute $\ma{x}$ (once) and not $\ma{x}$ and $\ma{x}^*$. Instead of simply ditching the last $N$ rows, we can avoid computing them altogether, by applying the rules for inverting two by two block matrices. The final solution then becomes

$$ \ma{x} = \Big(\ma{A} – \ma{B} (\ma{A}^*)^{-1} \ma{B}^*\Big)^{-1} \cdot \ma{c} \; – \ma{A}^{-1} \ma{B} \Big(\ma{A}^* – \ma{B}^* \ma{A}^{-1} \ma{B}\Big)^{-1} \cdot \ma{c}^*.$$

So simple. Why didn’t I see it earlier?