"cascaded" cross-correlation

Question

so, first let's do this for the circular correlation case (it might be easier).

let's say we have three real and periodic functions or signals $x(t)$, $y(t)$, $z(t)$ all with period $2 \pi$:

$$ x(t+2\pi) = x(t) \quad \forall t $$ $$ y(t+2\pi) = y(t) \quad \forall t $$ $$ z(t+2\pi) = z(t) \quad \forall t $$

define the cross-correlation between any two, say $x(t)$ and $y(t)$ as

$$ R_{xy}(\tau) \triangleq \frac{1}{2\pi} \int\limits_{-\pi}^{\pi} x(t) y(t+\tau) \ dt $$

let's say that the maximum value of $R_{xy}(\tau)$ occurs at $\tau=\tau_{xy}$

$$ R_{xy}(\tau_{xy}) > R_{xy}(\tau) \quad \forall \tau \in (\tau_{xy},\tau_{xy}+2\pi) $$

(since $x(t)$, $y(t)$, and $z(t)$ are all periodic with period $2 \pi$, so also are any cross-correlation between any pair.)

$$ R_{xy}(\tau_{xy}) = R_{xy}(\tau_{xy} + k \ 2\pi) \quad \forall k \in \mathbb{Z} $$

so here's the question: except for a difference of some multiple of $2\pi$, is

$$ \tau_{xz} = \tau_{xy} + \tau_{yz}$$

or

$$ \tau_{xz} = \tau_{xy} + \tau_{yz} + k \ 2\pi $$ for some integer $k$?

i think this should be true, but it would be nice if it is proved to be so.

Answer 1

I'm afraid your statement isn't true. This can best be seen in a suitable choice of basis, one that simplifies the cross correlation. This basis if of course the shift invariant periodic Fourier basis on your support interval.

Let's label the basis vectors $F_n$ for integer $n$. The cross correlation of two different such basis vectors vanishes, because the vectors are orthogonal and shift invariant: $\langle F_n,F_m \rangle =0$ for $m\neq n$. If we slightly generalize the cross correlation to work for complex signals as in $$\langle A,B \rangle (\tau):=\int_{-\pi}^\pi A^*(t)B(t+\tau)dt$$ and assume normalization of the Fourier basis, then $\langle F_n,F_n \rangle (\tau)=F_n(\tau)$.

With this, we can construct your $x(t)$,$y(t)$ and $z(t)$ signals like follows: $$x(t) := c_{xy} F_{n}(t) + c_{xz} F_{k}(t)$$ $$y(t) := c_{yx} F_{n}(t) + c_{yz} F_{m}(t)$$ $$z(t) := c_{zy} F_{m}(t) + c_{zx} F_{k}(t)$$

with mutually different integer indices $k,m,n$. The complex coefficients $c_{ab}$ for $a,b\in\{x,y,z\}$ can be chosen arbitrarily and independently.

The corresponding correlation functions are:

$$\langle x,y \rangle (\tau) = c^*_{xy} c_{yx} F_n(\tau)$$ $$\langle y,z \rangle (\tau) = c^*_{yz} c_{zy} F_m(\tau)$$ $$\langle x,z \rangle (\tau) = c^*_{xz} c_{zx} F_k(\tau)$$

So each cross correlation function is a complex sinusoid with a phase factor in front. The phase factors and the sinusoids of all three correlation functions can be chosen absolutely independently. If you want to talk about maxima instead of phase factors you can take the whole setup to the reals by either adding the conjugate basis functions or just take the real part of these correlation functions. Either way, you can chose the coefficients to give you any set of maximum lags $\tau_{xy,zy,xz}$ without the requirement of the connection between them you conjectured.

So as requested let's get more explicit. The construction principle that guarantees independence of the three cross correlation functions should be relatively obvious: The orthogonality of the Fourier basis allows us to construct the signals so that the signals $x,y,z$ only overlap pairwise. In other words, the example above demonstrates that there is no transitivity for cross correlations that would allow general statements about $\langle x,z \rangle$ from $\langle x,y \rangle$ and $\langle y,z \rangle$.

The simple construction from above makes them overlap with just one basis function, which is a complex sinusoid. This is probably why the result cannot be immediately seen to apply to the original question. If you want maxima we need to use real numbers, and single real basis functions also do not have a single maximum, so we need to have more than one basis function of overlap between the signals (except for $F_1$, which already only has one maximum per period).

The simplest full example that I can come up with right now and that follows the design principle described above is: $$x(t)=\sin(t)+\cos(4t)+\cos(5t)$$ $$y(t)=\sin(t)+\sin(2t)+\sin(3t)$$ $$z(t)=\sin(2t)+\sin(3t)+\sin(4t)+\sin(5t)$$

The base indices that overlap between the signals are $1$ for $xy$, $2$ and $3$ for $yz$, and finally $4$ and $5$ for $xz$. The latter have a phase shift introduced to realise your requirement. The overlaps group adjacent basis functions so that we have a single guaranteed maximum.

At this point it's probably easier to inspect the resulting correlation functions graphically.

First, $\langle x,y \rangle$:

$\langle y,z \rangle$:

and finally the independent third pair $\langle x,z \rangle$:

The maxima of the first two cross correlations are clearly at $\tau=0$, while the third pair correlates best at some $\tau>0$.

This example works in both discrete and continuous time, as it only uses properties of the Fourier basis that are realised in both domains.

Answer 2

We can easily create three real, $2\pi$-periodic signals that have zero cross correlation with each other, simply by ensuring they contain no common frequency components. For example:

$$a(t) = a_1 \sin t + a_2 \sin 2t \\ b(t) = b_1 \sin 3t + b_2 \sin 4t \\ c(t) = c_1 \sin 5t + c_2 \sin 6t $$

Now, I can construct $x(t)$, $y(t)$ and $z(t)$ as follows:

$$x(t) = a(t) + b(t) \\ y(t) = b(t) + c(t) \\ z(t) = c(t) + a(t-\tau_{xz}) $$

These functions will have the property that $\tau_{xy}=0$, $\tau_{yz}=0$, and $\tau_{zx}$ will take on whatever value we chose when we constructed $z(t)$.

Answer 3

if you don't like the language of the metric spaces (i am not sure i do either), another way to look at this is besides defining the cross correlation:

$$ R_{xy}(\tau) \triangleq \frac{1}{2\pi} \int\limits_{-\pi}^{\pi} x(t) y(t+\tau) \ dt $$

we can define this "distance measure" (it's actually the ASDF, Average Squared Difference Function, a variant of the AMDF or Average Magnitude Difference Function):

$$ Q_{xy}(\tau) \triangleq \frac{1}{2\pi} \int\limits_{-\pi}^{\pi} \left( x(t) - y(t+\tau) \right)^2 \ dt \ge 0 $$

then neat thing is that delaying $y(t)$ by $\tau$, doesn't change its power or "norm". so this is true:

$$\begin{align} Q_{xy}(\tau) & = \frac{1}{2\pi} \int\limits_{-\pi}^{\pi} \left( x(t) - y(t+\tau) \right)^2 \ dt \\ & = \frac{1}{2\pi} \int\limits_{-\pi}^{\pi} x^2(t) + y^2(t+\tau) - 2 x(t)y(t+\tau) \ dt \\ & = \frac{1}{2\pi} \int\limits_{-\pi}^{\pi} x^2(t) \ dt + \frac{1}{2\pi} \int\limits_{-\pi}^{\pi} y^2(t+\tau) \ dt - 2 \frac{1}{2\pi} \int\limits_{-\pi}^{\pi} x(t)y(t+\tau) \ dt \\ & = \frac{1}{2\pi} \int\limits_{-\pi}^{\pi} x^2(t) \ dt + \frac{1}{2\pi} \int\limits_{-\pi}^{\pi} y^2(t) \ dt - 2 \frac{1}{2\pi} \int\limits_{-\pi}^{\pi} x(t)y(t+\tau) \ dt \\ & = R_{xx}(0) + R_{yy}(0) - 2 R_{xy}(\tau) \\ \end{align}$$

or

$$ R_{xy}(\tau) = \frac{R_{xx}(0) + R_{yy}(0)}{2} - \frac{1}{2} Q_{xy}(\tau) $$

again, because spinning $y(t)$ by a time of $\tau$ does not change its power (which is $R_{yy}(0)$), $R_{xy}(\tau)$ is maximized when $Q_{xy}(\tau)$ is minimized. so we are at the same place we are in the other answer. not yet complete, but this is the direction i am going with it.

Answer 4

i'm gonna start answering the question. actually, i am exploring an answer.

so, first, think of this in terms of an Inner Product Space or Hilbert Space (but in this case there are no complex conjugates that those familiar with Hilbert Spaces might miss).

let $\mathbf{x}$ be the point or element in that space that is fully defined by the real and periodic function $x(t)$ where $x(t+2\pi)=x(t) \quad \forall t$. if i remember correctly Hilbert Spaces are also Normed Linear Spaces (Banach Spaces).

there's an inner product

$$ \langle \mathbf{x}, \mathbf{y} \rangle \triangleq \int\limits_{-\pi}^{\pi} x(t) y(t) \ dt$$

a norm

$$ \| \mathbf{x} \| = \sqrt{ \langle \mathbf{x}, \mathbf{x} \rangle } $$ $$ \| \mathbf{x} \|^2 = \langle \mathbf{x}, \mathbf{x} \rangle $$

which is the distance that $\mathbf{x}$ is from the $\mathbf{0}$ element.

there are distance metrics between two points. the more general distance function is

$$ \begin{align} \| \mathbf{x}-\mathbf{y} \| & = \sqrt{\| \mathbf{x}-\mathbf{y} \|^2} \\ & = \sqrt{ \langle \mathbf{x}-\mathbf{y}, \mathbf{x}-\mathbf{y} \rangle } \\ & = \sqrt{ \langle \mathbf{x}, \mathbf{x}-\mathbf{y} \rangle - \langle \mathbf{y}, \mathbf{x}-\mathbf{y} \rangle } \\ & = \sqrt{ \langle \mathbf{x}, \mathbf{x} \rangle + \langle \mathbf{y}, \mathbf{y} \rangle - 2 \langle \mathbf{x}, \mathbf{y} \rangle } \\ & = \sqrt{ \| \mathbf{x} \|^2 + \| \mathbf{y} \|^2 - 2 \langle \mathbf{x}, \mathbf{y} \rangle } \\ \end{align}$$

what this means is that, as long as the norms of $\mathbf{x}$ and $\mathbf{y}$ remain constant, the distance between $\mathbf{x}$ and $\mathbf{y}$ is minimized when the inner product between the two is maximized. and vise versa.

so now let's generalize $\mathbf{x}$ or $\mathbf{y}$ or $\mathbf{z}$ a little more. the point $\mathbf{x}$ corresponds to the periodic $x(t)$ and $\mathbf{y}$ corresponds to $y(t)$. another point in this Hilbert space, we'll call $\mathbf{x}(\tau)$ corresponds to the periodic function $x(t+\tau)$, and naturally $\mathbf{y}(\tau)$ corresponds to $y(t+\tau)$. so as $\tau$ moves from $0$ to $2\pi$, $\mathbf{y}(\tau)$ traces out a curve (what we used to call a parametric line curve) in this Hilbert space that is a closed curve, because $\mathbf{y}(2\pi) = \mathbf{y}(0) = \mathbf{y}$.

note that no matter what real value $\tau$ is,

$$ \| \mathbf{y}(\tau) \| = \| \mathbf{y} \| . $$

which means that all of the points on this closed curve are equal distance from the origin $\mathbf{0}$ no matter what $\tau$ is. and the same is true for $\mathbf{x}(\tau)$ and $\mathbf{z}(\tau)$.

now, without loss of generality, i think we can assume that $\tau_{xy}$ and $\tau_{yz}$ are zero, for which we then have to prove that $\tau_{xz}=0$ ($\pm k 2 \pi$, which i'm not gonna worry about). that means that the distance that $\mathbf{x}(0)$ is from $\mathbf{y}(0)$ is less than the distance $\mathbf{x}(0)$ is from $\mathbf{y}(\tau)$ for any other $\tau \ne k 2 \pi$.

but this curve $\mathbf{x}(\tau)$ is parallel in some sense to the curve $\mathbf{y}(\tau)$ because we know that $\mathbf{x}(\tau_1)$ is closest to the point $\mathbf{y}(\tau_1)$ and $\mathbf{x}(\tau_2)$ is closest to the point $\mathbf{y}(\tau_2)$ for any values of $\tau_1$ and $\tau_2$ for the same reason that $\mathbf{x}(0)$ is closest to the point $\mathbf{y}(0)$.

the same can be said of the curves $\mathbf{y}(\tau)$ and $\mathbf{z}(\tau)$ because of the assumption $\tau_{yz}=0$ which means that the distance that $\mathbf{y}(0)$ is from $\mathbf{z}(0)$ is less than the distance $\mathbf{y}(0)$ is from $\mathbf{z}(\tau)$ for any other $\tau \ne k 2 \pi$.

so, somehow, in a formal manner, can't we say that if $\mathbf{y}(0)$ is the element of $\mathbf{y}(\tau)$ closest to $\mathbf{x}(0)$ and $\mathbf{z}(0)$ is the element of $\mathbf{z}(\tau)$ that is closest to $\mathbf{y}(0)$, doesn't this mean that $\mathbf{z}(0)$ is the element of $\mathbf{z}(\tau)$ closest to $\mathbf{x}(0)$??

can we make this into a decent proof?

as you can see, i am willing to pay some bounty to whomever can help me formalize this (or to persuasively disprove my reasoning above).