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.

Let $X$ be a set of $n$ points in $\mathbb{R}^3$ and $f_m$ be the Fréchet mean, i.e.:

$$ f_m= \arg \min_{p \in M} \sum_{i=1}^n w_id^2(p,x_i) $$

where $(\mathbb{R}^3,d)$ is a complete metric space, $d$ a distance function (Euclidean $d_E$, log-Euclidean $d_{log}$, Riemannian $d_R$) between any two points and $w$ a weight function.

$$ d_E(x_i,x_j)= \| x_i - x_j\| $$

$$ d_{log}(x_i,x_j)= \| \log(x_i) - \log(x_j)\| $$

$$ d_R(x_i,x_j)= \| \log(x_i^{-1/2}x_jx_i^{-1/2})\| $$

How could I solve this problem? Maybe by Gradient Descent?

share|improve this question
    
If the points are in $\mathbb R^3$, what does $(M,d)$ have to do with the problem? –  user31373 Jun 5 '12 at 14:50
    
You are right. It is $(\mathbb{R}^3,d)$ –  no_name Jun 5 '12 at 15:00
    
OK, is $d(x,y)$ the Euclidean distance $\sqrt{(x_1-y_1)^2+\dots+(x_n-y_n)^2}$ or someone else? –  user31373 Jun 5 '12 at 15:01
    
I was vague bacause I would like to analize the differences between Euclidean, log-Euclidean, and Riemannian metric. –  no_name Jun 5 '12 at 15:14

1 Answer 1

In the case $d=d_E$ you have $f_m=\sum w_i x_i$ (assuming $\sum w_i=1$, which can always be achieved by scaling the weights). Proof: for any $x\in\mathbb R^3$

$$\sum w_i\|x-p_i\|^2 = \sum w_i\|x-f_m+f_m-x_i\|^2 \\= \|x-f_m\|^2 + \sum w_i\|f_m-x_i\|^2 + 2\sum w_i\langle x-f_m, f_m-x_i\rangle$$ In the last term we move summation into the bracket to get $$\sum w_i\langle x-f_m, f_m-x_i\rangle=\langle x-f_m, f_m-\sum w_ix_i\rangle=0$$ Thus, $$\sum w_i\|x-p_i\|^2 =\|x-f_m\|^2+\sum w_i\|f_m-x_i\|^2\ge \sum w_i\|f_m-x_i\|^2 $$ QED

Also, if your metric is of the form $d(x,y)=\|\Phi(x)-\Phi(y)\|$ where $\Phi\colon\mathbb R^3\to\mathbb R^3$ is some invertible map, then $f_m=\Phi^{-1}(\sum w_i \Phi(x_i))$.

share|improve this answer
    
Thank you. This is pretty reasonable for Euclidean metric. It should be a "weighted" centroid. Could I use the same procedure with $d_{log}$ and $d_R$? –  no_name Jun 6 '12 at 10:30
1  
@no_name If you can write them in the form given in the last paragraph of my answer, then yes. Otherwise, unlikely. Unfortunately, I don't understand your formulas for either metric: how do you take the logarithm of a vector, for example? –  user31373 Jun 6 '12 at 15:09

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.