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}$$


$$ \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.

  • $\begingroup$ i s'pose it would be sufficient to prove that if $\tau_{xy}=0$ and $\tau_{yz}=0$, then $\tau_{xz}=0$ (all $\pm k \ 2\pi$). $\endgroup$ – robert bristow-johnson Sep 23 '14 at 1:24
  • $\begingroup$ Is the location of each crosscorrelation (global) maximum unique in $[0,2\pi)$ or are there multiple global maxima (repeated periodically) in $[0,2\pi)$? If the latter, which location should be used? $\endgroup$ – Dilip Sarwate Sep 23 '14 at 22:51
  • $\begingroup$ it's unique in $[0, 2\pi)$ (or i might prefer putting the principal value in $[-\pi, \pi)$). that's what i meant by "equality occurs only at $\tau_{xy}+k2\pi$ for any integer $k$." $\endgroup$ – robert bristow-johnson Sep 24 '14 at 14:24

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$:

Crosscorrelation between x and y

$\langle y,z \rangle$:

Crosscorrelation between y and z

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

Crosscorrelation between x and z

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.

  • $\begingroup$ okay, Jazz, i'm looking this over. there was a reason i chose $2\pi$ for the period, because i suspected we might express this with Fourier series and it looked like a handy choice. can you please look at the modified answer (using elements in a Hilbert space) that i just wrote and see if you can see where that takes a wrong turn? i'm gonna look this over and after i'm convinced (and i think i will be), the bounty rep goes to you. but please look at that answer below and tell me where it is barking up the wrong tree. BTW, is the basis for $F_n(t)$, explicitly $$ F_n(t) \triangleq e^{j n t} $$? $\endgroup$ – robert bristow-johnson Sep 25 '14 at 21:25
  • $\begingroup$ Jazz, i would like it if you were more explicit about the basis functions (how are they defined?) and more explicit about how $x(t)$, $y(t)$, and $z(t)$ get defined to be real valued and, then, how the $\tau_{xy}$, $\tau_{yz}$, and $\tau_{xz}$ values are determined from this. or show how $x(t)$, $y(t)$ and $z(t)$ can be defined so that their correlation is maximum at $\tau=0$ and the resulting maximum for the correlation between $x(t)$ and $z(t)$ is not at $\tau=0$. still missing pieces. $\endgroup$ – robert bristow-johnson Sep 25 '14 at 23:02
  • $\begingroup$ I'll add what you think is missing. I didn't want to spell out every detail but just point you into the direction of the argument. Also, the complex conjugate on $A$ is the standard convention, not $B$ like you commented in your edit. In general in a complex Hilbert space the opening angle always goes with the conjugate, because it's the "bra" dual of the actual vector space "ket". $\endgroup$ – Jazzmaniac Sep 26 '14 at 8:04
  • $\begingroup$ Also, I have deliberately not spelled out the basis functions, because their representation depends on the domain we are in. The example I added uses continuous time, so I could explicitly write the basis functions. $\endgroup$ – Jazzmaniac Sep 26 '14 at 8:57
  • $\begingroup$ yes, you're right about the convention of which argument gets complex conjugated. and you satisfied my requirement about an explicit counter-example. so, the bounty is yours. i dunno what else i have to do other than check-mark your answer. if your 1542 doesn't get bumped up to 1842+, at least by the end of the bounty period, we need to find someone to complain to. thanks, Jazz. you earned it. $\endgroup$ – robert bristow-johnson Sep 26 '14 at 12:50

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)$.

  • $\begingroup$ Actually, to be fair, my answer above is just a shorter version of the answer given by Jazz $\endgroup$ – dave_mc Sep 28 '14 at 10:35
  • $\begingroup$ If two crosscorrelations are identically $0$, their maxima can be taken to be any value one likes, and so all that would be necessary is to claim that $\tau_{yz}$, say, has the right value to make $\tau_{xy}+\tau_{yz}$ work out to be the same as $\tau_{zx}$ (or is it $-\tau_{zx}$?) $\endgroup$ – Dilip Sarwate Sep 28 '14 at 16:12
  • $\begingroup$ yeah, but dave, it was quicker to the point. if your answer had preceded Jazz, i think the bounty would be yours. so this delay gets "propagated" inasmuch as the same sinusoidal components (which are members of the set of basis functions) are propagated. this answer is short and sweet and more direct, but i dunno how the bounty gets awarded (being that the bounty is still "open"). $\endgroup$ – robert bristow-johnson Sep 28 '14 at 17:21
  • $\begingroup$ yeah, but @DilipSarwate, even though i was not clear about that in the question, i didn't intend for any of the $R_{xy}(\tau)$ functions to be identically zero. but, i do understand how that fact is used by dave and Jazz to construct inputs that have a cross-correlations that are mutually independent. and the intention was to have $$\tau_{xy} + \tau_{yz} = \tau_{xz}$$ or $$\tau_{xy} + \tau_{yz} + \tau_{zx} = 0$$. $\endgroup$ – robert bristow-johnson Sep 28 '14 at 17:26

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}$$


$$ 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.

  • $\begingroup$ again, i think it is sufficient to prove that if $R_{xy}(\tau)$ is maximum when $\tau=0$ and if $R_{yz}(\tau)$ is maximum when $\tau=0$, then $R_{xz}(\tau)$ is maximum when $\tau=0$. if we can prove that, i think the main point is proved. and these all can be proved by showing if $Q_{xy}(\tau)$ is minimum when $\tau=0$ and $Q_{yz}(\tau)$ is minimum when $\tau=0$, then $Q_{xz}(\tau)$ is minimum when $\tau=0$. if we can prove that, we proved the whole thing. $\endgroup$ – robert bristow-johnson Sep 24 '14 at 17:07

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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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