3
$\begingroup$

A question bridging math and computer science, I have on the order of 10000 vectors each of a equal but high dimension, say 6 or 7 dimensions. I want to find a given number of 'unique' vectors in the set, the number generally equal to the dimension of the vectors. In math terms I believe I want to find a subset of vectors that has the biggest angle from its neighbours in that sub set. Vector length is also a factor, i.e. a unique but nearly zero length vector is less preferred than one less unique in angle but has a finite length.

An example:

1: [1 2 4 1 5]

2: [1 1 2 1 3]

3: [1 2 4 1 4]

...

9999: [2 1 1 2 2]

10000: [4 5 4 2 1]

vectors 1 and 3 are quite similar, 2 less so, 10000 is most different. I think the dot product and higher order 'angle' is the best measure of uniqueness, though there may be better.

Visually, collapsing the dimension down to 2, the vectors below in black represent the full set, the vectors in red are the subset of seven most unique.

Concept update: 03/05/2018

I have recently stumbled upon the concept of the Latin hypercube, and the higher dimensional mathematics behind it that attempt to find an even spread of higher-dimensional vectors. I don't know exactly how this could be applied, but it has been the closest concept so far. Can anyone see how it might be applicable to the problem?

enter image description here

Improve this question
$\endgroup$
5
  • 5
    $\begingroup$ Welcome to CS.SE! Please edit the question to provide a more careful definition of the problem. What do you mean by "angle from its neighbors"? Do you mean, for each $x \in S$, you compute $a_S(x) = \min \{\text{angle}(x,y) : y \in S, y \ne x\}$, and you want to find $S$ that minimizes $\max \{a_S(x) : x \in S\}$? I wouldn't call that "sorting by uniqueness". What approaches have you considered? Do you have any restrictions on the size of $S$? If not, trivial solutions like taking $S=\emptyset$ seem like they will be optimal. $\endgroup$
    – D.W. ♦
    Jun 16, 2017 at 21:23
  • $\begingroup$ I have considered: 1) brute force techniques, looking at the cosine angle between vector pairs and hunting through a list of vector pairs for the largest angles; 2) breaking up the domain somehow into equal 'slices' originating from the centre and sorting each vector into one of the slices and choosing the best vector in each slice to represent the slice; 3) starting with a single arbitrarily chosen vector and choosing successive vectors each at a making a maximum angle to those that came before. $\endgroup$
    – J Collins
    Jun 17, 2017 at 9:11
  • $\begingroup$ S will be necessarily large as it is a large pool of experimental data, the dimension of each vector represents a sensor in the experiment. with each vector being all sensor readings from a single experiment. $\endgroup$
    – J Collins
    Jun 17, 2017 at 9:13
  • $\begingroup$ Are you looking for a base? $\endgroup$
    – Raphael ♦
    Nov 15, 2017 at 7:23
  • $\begingroup$ Give some more information, that sounds familiar from Engineering Mathematics (that I took in 2001..!) $\endgroup$
    – J Collins
    Nov 15, 2017 at 17:42

1 Answer 1

Reset to default
3
$\begingroup$

I suspect your problem might be NP-hard (by reduction from Clique), so it might be hard to find an efficient algorithm for it.

One heuristic is to use the farthest-point first method, where at each stage you pick the point whose angle to the others already picked is as large as possible. In other words, suppose we have already picked a set $S$ of vectors. Now we find the vector $x$ that maximizes $\min \{\text{angle}(x,s) : s \in S\}$, add it to $S$, and repeat. This most likely won't give the optimal set of vectors, but it might give something that is somewhat close to optimal.

Another possible approach is to use binary search and some kind of clique-finding algorithm. Let $t$ be a threshold. Form an undirected graph $G$ where each vector is a vertex in the graph; and you have an edge $(u,v)$ if the angle between the two vectors $u,v$ is at least $t$. Then if you can find a clique of size $k$ (where $k$ is the desired size of your subset), then you've found a subset of vectors that are all at angle $\ge t$ from each other. Now repeat this, using binary search on $t$ to find the largest $t$ for which you can find a $k$-clique. In this way you might be able to take advantage of methods in the literature for finding $k$-cliques. (For instance, one simple preprocessing step you can do to reduce the size of the graph is: delete any vertex whose degree is less than $k$, and repeat until convergence.)

Improve this answer
$\endgroup$

Your Answer

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

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