3
$\begingroup$

Given a set of vectors $S = \{v_1, v_n, ..., v_n\}$, $v_i \in \mathbb{R}^m $. Now I want to find a binary vector $ t \in \{0, 1\}^m $ to minimize $ \sum_{i=1}^n \text {distance} (t, v_i)$.

Specifically, $t$ is a vector in $\mathbb{R}^m $ but with every component being 0 or 1. The distance computation here is not limited to Euclidean distance. So I want to know if there is a generized optimization solution for this question.

Thank you in advance for any assistance or guidance!

$\endgroup$

1 Answer 1

4
$\begingroup$

I think it strongly depends on the used distance.

  • If the distance is decomposable, i.e. the contribution of each vector component to the distance can be isolated (for instance, Squared Euclidean Distance $d(x,y)=\sum_{i=0}^m (x_i-y_i)^2$, or, more generally, $\ell_p$-distances, also Hamming distance, etc), it becomes quite easy and you can do it in time linear with respect to the vector length ($O(n\cdot m)$) by just computing that component's contribution on the whole dataset and then taking the minimum between the two cases ($0$ and $1$) for each component of the binary vector.

  • On the other hand, if we have a non-decomposable distance, for instance dynamic time warping (DTW) or Frechet distance, this is not possible and I'd say that, in the most general case, you can't probably do better than trying all the possible binary vectors, which is exponential in time with respect to the number of components of the vector: $O\bigl(n\cdot 2^m \cdot f(m)\bigr)$, where $f(m)$ is the cost of computing the distance between two vectors of length $m$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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