  Computing a consensus object from a set of given objects is a core problem in
machine learning and pattern recognition. One popular approach is to formulate
it as an optimization problem using the generalized median. Previous methods
like the Prototype and Distance-Preserving Embedding methods transform objects
into a vector space, solve the generalized median problem in this space, and
inversely transform back into the original space. Both of these methods have
been successfully applied to a wide range of object domains, where the
generalized median problem has inherent high computational complexity
(typically $\mathcal{NP}$-hard) and therefore approximate solutions are
required. Previously, explicit embedding methods were used in the computation,
which often do not reflect the spatial relationship between objects exactly. In
this work we introduce a kernel-based generalized median framework that is
applicable to both positive definite and indefinite kernels. This framework
computes the relationship between objects and its generalized median in kernel
space, without the need of an explicit embedding. We show that the spatial
relationship between objects is more accurately represented in kernel space
than in an explicit vector space using easy-to-compute kernels, and demonstrate
superior performance of generalized median computation on datasets of three
different domains. A software toolbox resulting from our work is made publicly
available to encourage other researchers to explore the generalized median
computation and applications.
