PDA

View Full Version : Vector with minimal angle to a set of vectors


Obelus
Oct5-11, 02:04 AM
Let \mathbb X be a set of mean-shifted vectors \mathbf X_1, \mathbf X_2, \ldots, \mathbf X_k in \mathbb R^n. By mean-shifted, I mean that \text{Mean}(\mathbf X_i) = 0 \forall i \in {0, \ldots, k}. I want to find a vector \mathbf T \in \mathbb R^n that maximizes the function

f(\mathbf T) = \sum \limits_{\mathbf X \in \mathbb X} \big ( cos(\theta_{\mathbf X, \mathbf T}) \big )^2 = \sum \limits_{\mathbf X \in \mathbb X} \big ( \frac{\mathbf X \cdot \mathbf T}{||\mathbf X|| \cdot ||\mathbf T||} \big )^2

(Edit: maximizing this f does not actually get what I want. Instead, I want to maximize the geometric mean of the correlations - see my followup posts).

In other words, I want to find a vector \mathbf T that has a small angle \theta to each \mathbf X \in \mathbb X. (Actually there must be infinitely many solutions, since any linear transformation of \mathbf T is also a solution).

My real motivation is statistical: this is equivalent to finding a vector that has a high Pearson correlation coefficient with all the vectors in \mathbb X.

I can use numerical algorithms to optimize f, but I would prefer to find a closed-form solution. This problem is part of a larger algorithm that I am trying to speed up, and it spends most of its time trying to find T. Is a closed-form solution possible? Or is this problem similar to an existing problem, which I can adapt?

If k=2, the solution should just be to rotate \mathbf X_1 halfway to \mathbf X_2, using some multidimensional rotation as discussed in this thread (http://forums.xkcd.com/viewtopic.php?f=17&t=29603). Perhaps this rotation concept could be extended to find the "rotational average" of \mathbb X, if that makes sense?

Any help towards finding a closed-form solution to this problem would be appreciated.

Obelus
Oct5-11, 11:16 AM
Actually, I just realized that f in my previous post is not exactly what I want to maximize. I want T to be equally and maximally close to all vectors in \mathbb X, so maximizing the minimum correlation with T would be better:

f = \displaystyle{\mathop{\mbox{min}}_{\mathbf X \in \mathbb X}} \big ( \frac{\mathbf X \cdot \
\mathbf T}{||\mathbf X|| \cdot ||\mathbf T||} \big )^2

However, this makes f non-differentiable, so perhaps using the generalized mean formula (http://mathoverflow.net/questions/35191/a-differentiable-approximation-to-the-minimum-function) would work:

f = \big ( \frac{1}{|\mathbb X|}\sum\limits_{\mathbf X \in \mathbb X} \frac{\mathbf X \cdot \
\mathbf T}{||\mathbf X|| \cdot ||\mathbf T||} \big )^{\frac{1}{k}}

for k \rightarrow - \infty.

Obelus
Oct5-11, 12:02 PM
Argh, actually that's not what I want either. If one vector in \mathbb X is very different from the others, it will pull \mathbf T towards it too much. Instead, I think I want to maximize the geometric mean, or the limit as k \rightarrow 0 of the generalized mean.

Sorry I keep changing my mind. Basically, I want \mathbf T to be a good angular approximation of all the vectors in \mathbb X.