# Find representatives of vector-space in set of vectors?

Suppose I have a multi-dimensional vector space $X$, and a collection of $n$ vectors $\{x_i\}_{i=1}^n \subset X$, which are not evenly "spaced-out" in $X$. I am searching for $m<<n$ of these $x_i$ that are good representatives of $X$, or in other words, they are roughly equi-distant to each other.

How can I find these representatives? What algorithm (hopefully with an available implementation in Python) could I use? Would K-Medoids be a good choice?

• What is the dimension of $X$? Commented Aug 12, 2017 at 16:34
• @nicoguaro: Not too large. A couple of dimensions. With current datasets 2 or 4 - but it should be possible to have more dimensions. Commented Aug 12, 2017 at 16:49
• @Make42 How do you define a set of vectors as "good representatives" of a space? Commented Aug 12, 2017 at 20:04
• @Stelios: I mentioned it in the question: roughly equi-distant, so "evenly spaced-out". So they are supposed to cover the whole space. Commented Aug 14, 2017 at 16:06
• If you pick representatives that are “evenly-spaced” you may get a very redundant set of representatives of the space, in the sense that you could use a much smaller set and represent all vectors in the space as linear combinations of the smaller set. You can get such a set with rank-revealing QR, for example. If you can’t use linear combinations of your representative elements then you are not looking for representatives of the vector-space, but representatives of your initial set of vectors. Commented Apr 30, 2021 at 5:20

You can think of each vector as a point in your linear space. As such, we can use a simple quadtree/octree-like algorithm to map your points into boxes, with "nearby" vectors assigned to the same or an adjacent box. With $$n$$ total vectors the vector-to-box map costs $$\mathcal{O} (n\log n)$$, and once this is done you can choose $$m$$ boxes and select the vector closest to the centroid of the box to obtain your "diverse" set of vectors.

Sounds like you want to thin your data where it is dense, and learn the support of your data summarized by data points. If you don't have too many points, you can generate a distance matrix, and prune the points with the closest neighbors. (I don't think this method has a name.)

Otherwise, if you are trying to find the extremal points, then archetypal analysis might be a better direction.

• I do have a lot of points. However, currently I use clustering to find representative points, so I guess your K-nearest neighbor (KNN) idea might not be worse. Bit I am not quite sure yet, what the idea exactly is how to prune the points, without having to recreate the distance matrix over and over again (this might get expensive after a while). Commented Aug 14, 2017 at 16:13
• Btw: Archetypal analysis has been published at arxiv.org/abs/1405.4275 and an implementation from the authors is available at github.com/yuekai/archetypes Commented Aug 14, 2017 at 16:14

Initialize the cluster centers as your subset $V\in X$, where $V=\{x_i\}$. Then run a couple of K-mediods iterations. After that you will see that the certain vectors will come closer, essentially trying to represent similar peaks. It is then possible to merge them.

Another way to do this is mean-shift algorithm, where the modes are being updated (I think you want to find the modes). You start by over-clustering and at a dynamic number of clusters (discovered) that best represents the modes. For discrete data such as yours the medioids variation does exist.

• Mean shift is a good idea, but it is too slow, medoid shift even slower. Commented Apr 10, 2019 at 21:22
• I am not sure I understand your first idea. Did you mean the following? 1) Initialize k-medoids with a relatively large number of instances of $X$, but fewer than elements in $X$ and run k-medoids. 2) Prune medoids that are close to each other. Commented Apr 10, 2019 at 21:23

Another option, in the direction of clustering, could be k-Maxoids clustering:

Another answer could be (Growing) Neural Gas.