Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider the set $\mathcal{L}^2(\mathbb{R})$, where two functions $f$ and $g$ are said to be equal, if they agree almost everywhere. I would like to define a distance/similarity measure and would like to study its properties such as whether it would along with this set, forms a metric space.

Let $f$,$g$ be two functions on this set. We define a normalized cross correlation function as $$h(x) = \frac{\int \limits_{-\infty}^{\infty}f(t)g(t+x)\mathrm dt}{\int \limits_{-\infty}^{\infty}f(t)^2\mathrm dt \int \limits_{-\infty}^{\infty}g(t)^2\mathrm dt}$$

and our distance measure is given as $$d(f,g) = \frac{1}{\sup_x |h(x)|} - 1.$$

What I am interested to know is whether this set along with this distance measure qualifies as a metric space and also whether it has any interesting properties.

Modification (as it doesnt sound interesting in this current form) I hope its ok in this special case.

First we define an equivalence class and then modify the metric (infact would like to call it a similarity rather than metric and disacuss its properties and ask whether it would be modified to a metric if necessary)

Equivalence class :

Let $f$ be a function and we define its equivalence class as $\{kf_{\theta}\}$, $\require{enclose} \enclose{horizontalstrike}{$\theta \in [0,\pi]}$, $\theta \in [-\pi,\pi], k \in \mathbb{R}\setminus \{0\}$ and $$f_{\theta} = f \cos(\theta) + f_h \sin(\theta)$$ where $f_h$ is the hilbert transform of $f$.

Similarity measure (metric)

let $$h(x) = \frac{\int \limits_{-\infty}^{\infty}f(t)g(t+x)\mathrm dt}{\sqrt{\int \limits_{-\infty}^{\infty}f(t)^2\mathrm dt \int \limits_{-\infty}^{\infty}g(t)^2\mathrm dt}}.$$

Now define $$H(x) = \sqrt{h(x)^2 + h_h(x)^2}$$ where $h_h(x)$ is the hilbert transform of $h(x)$.

and our similarity measure is given as $$ s(f,g) = \sup_x H(x). $$

Define metric as $$d(f,g) =-\log(s(f,g)).$$

Is $d(f,g)$ a metric in the usual sense? Does this form a metric space?

PS : We assume sufficient regularity requirements on this space for the Hilbert transform to exist.

share|improve this question
    
I think you may need more restrictions than just $L^2$: How would you define distance from, say $f = 0$? –  user61527 Sep 25 '13 at 4:44
    
@T.Bongers : Looks like we have to exclude $f=0$ from this set. –  Rajesh D Sep 25 '13 at 4:45
    
Do you want the square root in the denominator? Otherwise, $d(f,f)\ne0$. –  robjohn Sep 25 '13 at 14:33
    
If you do include the square root in the denominator, we get $d(f,-f)=0$. –  robjohn Sep 25 '13 at 14:36
1  
How about $d(f,2f)$? Should it be zero? If you are going to normalise in your definition of $h$ you really should just work with functions with unit $L^2$ norm instead. This simplifies your notation and gets rid of the conformal degree of freedom. –  Willie Wong Oct 10 '13 at 12:04

2 Answers 2

up vote 6 down vote accepted

There are many, many things wrong with your question. The below may not completely answer/fix them (since I am not sure about your motivations), but should at least get you started on the right track.

The starting point for you seems to be the correlation

$$ \int f(t) g(t+x) \mathrm{d}t $$

By the Cauchy-Schwarz inequality, we have

$$ \left| \int f(t) g(t+x) \mathrm{d}t\right| \leq \|f\|_2 \|g\|_2 \tag{*}$$

where $\|\cdot\|_2$ denotes the $L^2$ norm. The Cauchy-Schwarz (and in general, Hölder's) inequality is known to be sharp (see, for example, Hardy-Littlewood-Polya); that is to say that equality in (*) is attained if and only if $$f(t) = C g(t+x)\tag{**}$$ where $C$ is any scalar.

This means that for your modified $h(x)$, you have that $|h(x)| = 1$ if and only if there is some constant $C$ such that $f$ and $g$ are related by (**), and in general $|h(x)| \leq 1$.

This also means that if you want to define some sort of metric of the form $$ d(f,g) = F(\sup_{x} h ) $$ where $F(1) = 0$, you need to quotient out by all symmetries which makes $d(f,g) = 0$ when $f \neq g$.


With these all said, this means that the only reasonable space on which any semblance of $d(f,g)$ can satisfy the requirement that $d(f,g) = 0 \iff f = g$ would be if you take the underlying space to be

$$ L^2 / \sim $$

where the equivalence relation is that $f \sim g$ if (**) holds for some constants $C$ and $x$. If you do this you will find the zero function somewhat lonely and isolated, so it is perhaps best to start with $L^2 \setminus \{0\}$ instead.

In other words, you should be looking at the projective space associated to the vector space $L^2$, with the additional identification that translations of functions are identified. Now, projective Hilbert spaces are quite well studied in the context of quantum mechanics (see, for example, this MO discussion), but we needn't go in that direction.


So I propose the following modification of your definitions.

Underlying set: Let $M$ be the set of $(L^2(\mathbb{R};\mathbb{C}) \setminus\{0\} )/ \sim$ such that $f\sim g$ iff there exists $(C,x)$ such that (**) holds.

Similarity measure: Let

$$ h(f,g) = \sup_{x} \frac{\left|\int \overline{f}(t) g(t+x) \mathrm{d}x\right|}{\|f\|_2\|g\|_2} $$

One easily checks that this is independent of the representative in the equivalence class $[f]\in M$. By the sharpness of the Cauchy-Schwarz inequality, we have that $h(f,g) = 1 \iff [f] = [g]$. Otherwise $h(f,g) \in [0,1)$. (Note that $h(f,g) = 0$ is possible: choose $f,g$ such that their Fourier transforms $\hat{f},\hat{g} \in C^\infty_0(\mathbb{R};\mathbb{C})$ with disjoint support. Spatial translations and absolute scaling do not change the frequency support, so by Parseval $h(f,g) = 0$. This in particular means that neither of the definitions for $d$ in your original post are good, since you run into problems with $\frac{1}{0}$ or $\log 0$ not being real numbers.)

Now clearly $h(f,g)$ is symmetric. So in order to get a "metric" on the space $M$, it suffices to find a function $F: [0,1] \to \mathbb{R}$ such that

  1. $F(1) = 0$
  2. $F|_{[0,1)} > 0$
  3. For $d(f,g) = F\circ h(f,g)$, the triangle inequality is satisfied.

Since we are essentially working with the unit sphere in a Hilbert space, inspired by the Law of Cosine a reasonable choice seems to be $F = \arccos$ with the usual branch. This trivially satisfies the first two requirements.

The third requirement we check using the sum of angle formulae for $\cos$ which implies

$$ \arccos A + \arccos B = \arccos (A B - \sqrt{(1-A^2)(1-B^2)}) \tag{***}$$

Where given our choice of $A,B\in [0,1]$ we have that $AB\in [0,1]$ and $\sqrt{(1-A^2)(1-B^2)}\in [0,1]$, we have that the argument $(A B - \sqrt{(1-A^2)(1-B^2)}) \in [-1,1]$, and thus (*) holds for the branch of $\arccos$ such that its image of $[-1,1]$ is $[0,\pi]$ and is strictly decreasing.

Now, let $A = h(f_1,g)$ and $B = h(f_2,g)$. Since $h$ is independent of representative, assume $f_1,f_2,g$ all have unit $L^2$ norm.

Then we note that $$ \langle f_1,f_2\rangle = \langle f_1,g\rangle\langle f_2,g\rangle + \langle f_1 - \langle f_1,g\rangle g, f_2 - \langle f_2,g\rangle g\rangle $$ so by Cauchy-Schwarz on the last term $$ \langle f_1,f_2 \rangle \geq \langle f_1,g\rangle\langle f_2,g\rangle - \sqrt{ (1 - \langle f_1,g\rangle^2)(1 - \langle f_2,g\rangle^2)} $$ Taking the sup over translations this implies $$ h(f_1,f_2) \geq A B - \sqrt{(1-A^2)(1-B^2)} \tag{****}$$

Combining this with the formula (*) and using the monotonicity of $\arccos$, we obtain $$ \arccos h(f_1,g) + \arccos h(f_2,g) \geq \arccos h(f_1,f_2) $$ which is precisely the triangle inequality $$ d(f_1,f_2) \leq d(f_1,g) + d(f_2,g) $$

share|improve this answer
    
I fully agree with your suggestion to consider $$ L^2 / \sim $$, that the translations be identified. In the second part of your answer, you raise the question of $d(f,g) = \infty$, that is similarity being zero and then taking a logarithm of it introduces infinity. The example you have given is choose f,g such that their Fourier transforms f^,g^∈C∞0(R;C) with disjoint support. Does it violate with "PS : We assume sufficient regularity requirements on this space for the Hilbert transform to exist."..., –  Rajesh D Oct 10 '13 at 16:41
    
If it does not violate, then I'd like like to impose differentiability or such regularity requirements and make $d(f,g) = \infty $ to become impossible. I'd like to mention that the equivalence class I have defined in my question (fcos(theta) + fhsin(theta), is very important and i'd like to proceed in that direction. I don't want to go with simply correlation. –  Rajesh D Oct 10 '13 at 16:41
1  
@RajeshD: The Hilbert transform is a Fourier multiplier. Thus if $f,g$ have disjoint Fourier support, both the $h$ and $h_h$ in your "modified" version will return 0. One can even choose $f,g$ to be Schwartz class. So neither regularity nor Hilbert transform will save you from the problem of $d(f,g) = \infty$. –  Willie Wong Oct 11 '13 at 7:32
    
Hi Willie : Is the negative square of your metric $-d(f,g)^2$ a conditionally positive defnite kernel? Its important for me to know as if it turns out, I can have an isometric embedding of this metric space into a Hilbert space. –  Rajesh D Jan 20 '14 at 2:42
    
No idea (in fact I am not familiar with your terminology "conditionally positive definite kernel", especially in this context). –  Willie Wong Jan 20 '14 at 8:44

Willie, you just gave me everything I could dream, that too in mathematically brilliant way! (subject to the validity of what follows). All I have to do is replace $\log$ with $\arccos$ in my modified question and ofcourse identify translations. I'll try and explain briefly below by summarizing everything.

Consider $L^2(\mathbb{R}) \setminus \{0\}$ and impose the following equivalence class on this.

Equivalence class $@$

Let $f$ be a function and we define its equivalence class as $@ = \{kf_{\theta}(x+\tau)\}$, $\theta \in [-\pi,\pi], k \in \mathbb{R}\setminus \{0\}$,$\tau \in \mathbb{R}$ and $$f_{\theta}(x) = f(x) \cos(\theta) + f_h(x) \sin(\theta)$$ where $f_h(x)$ is the hilbert transform of $f(x)$.

Lets us denote this set together with this equivalence class as $R = (L^2(\mathbb{R}) \setminus \{0\})/@$.

(All I did is apart from what is in the question, I have identified translations).

Now we define metric just as in the question except replacing $\log$ with $\arccos$. Just to summarize...

Given $f,g \in R$, let $$h(x) = \frac{\int \limits_{-\infty}^{\infty}f(t)g(t+x)\mathrm dt}{\sqrt{\int \limits_{-\infty}^{\infty}f(t)^2\mathrm dt \int \limits_{-\infty}^{\infty}g(t)^2\mathrm dt}}.$$

Now define $$H(x) = \sqrt{h(x)^2 + h_h(x)^2}$$ where $h_h(x)$ is the hilbert transform of $h(x)$.

and our similarity measure is given as $$ s(f,g) = \sup_x H(x). $$

Define metric as $$d(f,g) = \arccos(s(f,g)).$$

Willie with his proposition of his metric on his set $M$, has just proved that the above defined set $R$ with metric $d(f,g)$ is indeed a metric space.

How? We just have to move from $R$ to $M$ (Willie's space, see his answer for definition) (Hilbert space with translations identified and zero element removed) by replacing object $f$ by $F(x) = f(x) + if_h(x)$. Thats it!

If we denote Willie's cosine metric on $M$ as $w$, then given any $f,g \in R$, we create objects $F,G \in M$ given as $F(x) = f(x) + if_h(x), G(x) = g(x) + ig_h(x)$.

Now it can be seen that $$d(f,g) = w(F,G)$$ Hence $(R,d)$ is a metric space.

Please correct me wherever I am wrong!

PS : If I had the power, I'd would like give Willie's answer a thousand upvotes! (as gratitude) .

PS : I have been using $\log$ in all my experiments, but now I replace it with $\arccos$ (I'd like to call this Willie's cosine metric). If the results are physically useful and If by chance I get to publish it, I'd like to quote this Q&A and give credit to Willie, robjohn and all others who have commented on this.

share|improve this answer
    
@Willie ; I definitely expect lot of mistakes in my post, so please correct me if I am wrong. –  Rajesh D Oct 11 '13 at 15:15
    

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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