Representative elements of a set I'm looking for the technical name of the following problem.
It sounds like a standard machine learning technique, but I'm not familiar with the field, and can't seem to find it.

Let's say that we have a set of $N$ objects.
Each object is characterized by $k$ properties (real numbers), and is therefore embedded in the property  space $\mathbb{R}^k$. 
We can define a metric $m$ for this space such that two objects $i,j$ are separated by a distance
$$ ||\vec{r}_i - \vec{r}_j||_m = m_1(r_1^{(i)}-r_1^{(j)}) +  m_2(r_2^{(i)}-r_2^{(j)}) + ... $$
where $\{m_\ell\}_{\ell=1,..,k}$ is a set of functions that defines $m$.
I want to identify the  $n \ll N$ objects that are the most representative of the set; i.e. the $n$ objects that will give me a good idea of what are the different "properties regime" of the $N$ objects.
The metric is not necessarily defined a priori and could be learned simultaneously. The simplest approach calls for a straightforward metric, e.g. euclidean distance.

Even if I don't know the name of my problem, I see two naive approaches. Both use the euclidean distance, because I do not know how to choose a proper metric and/or include the choice of metric in the proposed algorithms.


*

*Approach A: apply spectral clustering to the data. Draw one object per cluster, at random.

*Approach B: choose the $n$ objects which maximize the total distance between the $\binom{n}{2}$ pairs of objects.

 A: Approach A is reasonable, but rather than picking a random element, you might want to pick the "most central" point. In a k-means type clustering algorithm, you can pick either the mean of the cluster or the actual data point closest to that mean. In spectral clustering, this becomes something like the Frechét mean, which is harder to find.
Many clustering algorithms support a wide variety of distances you'd like to define.

Approach B is probably not what you want: it'll just pick outliers.
Here's something kind of like that with a similar flavor, though:
use a determinantal point process where the "quality score" is something like, say, a kernel density estimate. That should pick points that are both high-density and far away from one another, which for certain versions of "representative" is kind of like what you're looking for. You could plug in any smoothing kernel you want to model how similar different features are here, and also different distances for determining how different the representatives are.

There's also another approach based on sparse coding.
Here's a pair of papers that do something like this (the first being the basic model, the second extending it to more general forms of data):


*

*Elhamifar, E., Sapiro, G., & Vidal, R. (2012). See All by Looking at A Few: Sparse Modeling for Finding Representative Objects. Computer Vision and Pattern Recognition. (doi, free)

*Elhamifar, E., Sapiro, G., & Vidal, R. (2012). Finding Exemplars from Pairwise Dissimilarities via Simultaneous Sparse Recovery. Advances in Neural Information Processing Systems. (pdf)
Relatedly, you can think of this as a general sparse coding problem where your data dictionary is simply (a subset of) the data itself. That is, you pick a few exemplar data points, and then represent each data point as a sparse linear combination of the others. Depending on the type of data, this might give you representative "parts" of the dataset. Here's a few papers relevant to that:


*

*Sprechmann, P., Ramirez, I., Sapiro, G., & Eldar, Y. C. (2011). C-HiLasso: A Collaborative Hierarchical Sparse Modeling Framework. IEEE Transactions on Signal Processing, 59(9), 4183–4198. (doi, arXiv)

*Esser, E., Möller, M., Osher, S., Sapiro, G., & Xin, J. (2012). A Convex Model for Nonnegative Matrix Factorization and Dimensionality Reduction on Physical Space. IEEE Trans on Image Processing, 21(7), 3239–3252. (doi, arXiv)
I'm just noticing now that Guillermo Sapiro is in common between all these papers. I guess other people have probably worked on the problem too. :)
I also have a class project paper from 2012 on a similar sparse modeling approach to this here, focused more on how to optimize the model since this was for an optimization course. On the very off chance that anyone cares, we did figure out both SAFE and "strong" rules for dropping variables before starting the optimization after that writeup.
All of these approaches use Euclidean distance by default, but the NIPS paper allows for much more general dissimilarities, and my class project and probably some of the others allow kernelization.
A: This is called prototype classification, the simplest method in this class is k-nearest neighbours. 
Another approach is to cluster first, with $n$ clusters, and then pick a representative element per cluster. Commonly used prototypes are the mean and medoid per cluster.
