\begin{thebibliography}{34}
\expandafter\ifx\csname natexlab\endcsname\relax\def\natexlab#1{#1}\fi
\expandafter\ifx\csname url\endcsname\relax
  \def\url#1{{\tt #1}}\fi

\bibitem[Arkadev and Braverman(1966)]{Arkadev}
A.G. Arkadev and E.M. Braverman.
\newblock {\em Computers and Pattern Recognition}.
\newblock Thompson, Washington, D.C., 1966.

\bibitem[Bennett and Mangasarian(1992)]{Bennett}
K.P. Bennett and O.L. Mangasarian.
\newblock Robust linear programming discrimination of two linearly inseparable
  sets.
\newblock {\em Optimization Methods and Software}, 1:\penalty0 23--24, 1992.

\bibitem[Borg and Groenen(1997)]{Borg}
I.~Borg and P.~Groenen.
\newblock {\em Modern Multidimensional Scaling}.
\newblock Springer-Verlag, New York, 1997.

\bibitem[Bradley et~al.(1998)Bradley, Mangasarian, and Street]{Bradley}
P.S. Bradley, O.L. Mangasarian, and W.N. Street.
\newblock Feature selection via mathematical programming.
\newblock {\em INFORMS Journal on Computing}, 10:\penalty0 209--217, 1998.

\bibitem[Burges(1998)]{Burges}
C.J.C. Burges.
\newblock Geometry and invariance in kernel based methods.
\newblock In B.~Sch{\"o}lkopf, C.J.C. Burges, and A.J. Smola, editors, {\em
  Advances in Kernel Methods, Support Vector Learning}. MIT Press, 1998.

\bibitem[Cox and Cox(1995)]{Cox}
T.F. Cox and M.A.A. Cox.
\newblock {\em Multidimensional Scaling}.
\newblock Chapman \& Hall, London, 1995.

\bibitem[Dubuisson and Jain(1994)]{Dubuisson}
M.P. Dubuisson and A.K. Jain.
\newblock Modified hausdorff distance for object matching.
\newblock In {\em 12th International Conference on Pattern Recognition},
  volume~1, pages 566--568, 1994.

\bibitem[Duda et~al.(2001)Duda, Hart, and Stork]{Duda}
R.O. Duda, P.E. Hart, and D.G. Stork.
\newblock {\em Pattern Classification}.
\newblock John Wiley \& Sons, 2001.

\bibitem[Duin(1999)]{Duin3}
R.P.W. Duin.
\newblock Compactness and complexity of pattern recognition problems.
\newblock In {\em International Symposium on Pattern Recognition 'In Memoriam
  Pierre Devijver'}, pages 124--128, Royal Military Academy, Brussels, 1999.

\bibitem[Duin(2000)]{Duin2}
R.P.W. Duin.
\newblock Classifiers in almost empty spaces.
\newblock In {\em 15th International Conference on Pattern Recognition},
  volume~2, pages 1--7, Barcelona (Spain), 2000.

\bibitem[Duin and P\eob{}kalska(2001)]{Duin4}
R.P.W. Duin and E.~P\eob{}kalska.
\newblock Complexity of dissimilarity based pattern classes.
\newblock In {\em SCIA}, 2001.

\bibitem[Duin et~al.(1999)Duin, P\eob{}kalska, and Ridder]{Duin1}
R.P.W. Duin, E.~P\eob{}kalska, and D.~de Ridder.
\newblock Relational discriminant analysis.
\newblock {\em Pattern Recognition Letters}, 20\penalty0 (11-13):\penalty0
  1175--1181, 1999.

\bibitem[Fukunaga(1990)]{Fukunaga}
K.~Fukunaga.
\newblock {\em Introduction to Statistical Pattern Recognition}.
\newblock Acad. Press, 1990.

\bibitem[Goldfarb(1984)]{Goldfarb1}
L.~Goldfarb.
\newblock A unified approach to pattern recognition.
\newblock {\em Pattern Recognition}, 17:\penalty0 575--582, 1984.

\bibitem[Goldfarb(1985)]{Goldfarb2}
L.~Goldfarb.
\newblock A new approach to pattern recognition.
\newblock In L.N. Kanal and A.~Rosenfeld, editors, {\em Progress in Pattern
  Recognition}, volume~2, pages 241--402. Elsevier Science Publishers B.V.,
  1985.

\bibitem[Gower(1982)]{Gower2}
J.C. Gower.
\newblock Euclidean distance geometry.
\newblock {\em Mathematical Scientist}, 7:\penalty0 1--14, 1982.

\bibitem[Gower(1986)]{Gower}
J.C. Gower.
\newblock Metric and euclidean properties of dissimilarity coefficients.
\newblock {\em Journal of Classification}, 3:\penalty0 5--48, 1986.

\bibitem[Graepel et~al.(1999{\natexlab{a}})Graepel, Herbrich, Bollmann-Sdorra,
  and Obermayer]{Graepel2}
T.~Graepel, R.~Herbrich, P.~Bollmann-Sdorra, and K.~Obermayer.
\newblock Classification on pairwise proximity data.
\newblock In {\em Advances in Neural Information System Processing 11}, pages
  438--444, 1999{\natexlab{a}}.

\bibitem[Graepel et~al.(1999{\natexlab{b}})Graepel, Herbrich, Sch{\"o}lkopf,
  Smola, Bartlett, M{\"u}ller, Obermayer, and Williamson]{Graepel1}
T.~Graepel, R.~Herbrich, B.~Sch{\"o}lkopf, A.~Smola, P.~Bartlett, K.R.
  M{\"u}ller, K.~Obermayer, and R.~Williamson.
\newblock Classification on proximity data with {LP}-machines.
\newblock In {\em International Conference on Artificial Neural Networks},
  pages 304--309, 1999{\natexlab{b}}.

\bibitem[Greub(1975)]{Greub}
W.~Greub.
\newblock {\em Linear Algebra}.
\newblock Springer-Verlag, 1975.

\bibitem[Jacobs et~al.(2000)Jacobs, Weinshall, and Gdalyahu]{Jacobs}
D.W. Jacobs, D.~Weinshall, and Y.~Gdalyahu.
\newblock Classification with non-metric distances: Image retrieval and class
  representation.
\newblock {\em IEEE Transactions on Pattern Analysis and Machine Intelligence},
  22\penalty0 (6):\penalty0 583--600, 2000.

\bibitem[Jain and Zongker(1997)]{Jain}
A.K. Jain and D.~Zongker.
\newblock Representation and recognition of handwritten digits using deformable
  templates.
\newblock {\em IEEE Transactions on Pattern Analysis and Machine Intelligence},
  19\penalty0 (12):\penalty0 1386--1391, 1997.

\bibitem[P\eob{}kalska and Duin(2001)]{Pekalska2}
E.~P\eob{}kalska and R.P.W. Duin.
\newblock Automatic pattern recognition by similarity representations.
\newblock {\em Electronic Letters}, 37\penalty0 (3):\penalty0 159--160, 2001.

\bibitem[Sch{\"o}lkopf(1997)]{Scholkopf1}
B.~Sch{\"o}lkopf.
\newblock {\em Support vector learning}.
\newblock PhD thesis, Verlag, Munich, 1997.

\bibitem[Sch{\"o}lkopf(2000)]{Scholkopf}
B.~Sch{\"o}lkopf.
\newblock The kernel trick for distances.
\newblock In {\em Neural Information Processing Systems}, Vancouver, British
  Columbia, Canada, 2000.

\bibitem[Sch{\"o}lkopf et~al.(1999)Sch{\"o}lkopf, Smola, and
  M{\"u}ller]{Scholkopf0}
B.~Sch{\"o}lkopf, A.~Smola, and K.-R. M{\"u}ller.
\newblock Kernel principal component analysis.
\newblock In B.~Sch{\"o}lkopf, C.J.C. Burges, and A.J. Smola, editors, {\em
  Advances in Kernel Methods, Support Vector Learning}, pages 327--352. MIT
  Press, Cambridge, MA, 1999.

\bibitem[Sch{\"o}lkopf et~al.(2000)Sch{\"o}lkopf, Smola, Williamson, and
  Bartlett]{Scholkopf3}
B.~Sch{\"o}lkopf, A.J. Smola, R.~Williamson, and P.L. Bartlett.
\newblock New support vector algorithms.
\newblock {\em Neural Computation}, 12:\penalty0 1207--1245, 2000.

\bibitem[Sebastian et~al.(2001)Sebastian, Klein, and Kimia]{Kimia}
T.B. Sebastian, P.N. Klein, and B.B. Kimia.
\newblock Recognition of shapes by editing shock graphs.
\newblock In {\em International Conference on Computer Vision}, page to appear,
  2001.

\bibitem[Smola et~al.(1999)Smola, Friess, and Sch{\"o}lkopf]{Smola}
A.J. Smola, T.T. Friess, and B.~Sch{\"o}lkopf.
\newblock Semiparametric support vector and linear programming machines.
\newblock In M.J. Kearns, S.A. Solla, and D.A. Cohn, editors, {\em Advances in
  Neural Information Processings Systems 11}, pages 585--591, Cambridge,MA,
  1999. MIT Press.

\bibitem[Tversky(1977)]{Tversky}
A.~Tversky.
\newblock Features of similarity.
\newblock {\em Psychological Review}, 84\penalty0 (4):\penalty0 327--352, 1977.

\bibitem[Vapnik(1995)]{Vapnik}
V.~Vapnik.
\newblock {\em The Nature of Statisticsal Learning}.
\newblock Springer, N.Y., 1995.

\bibitem[Wahba(1999)]{Wahba}
G.~Wahba.
\newblock Support vector machines, reproducing kernel hilbert spaces and the
  randomized {G}{A}{C}{V}.
\newblock In B.~Sch{\"o}lkopf, C.J.C. Burges, and A.J. Smola, editors, {\em
  Advances in Kernel Methods, Support Vector Learning}, pages 69--88. MIT
  Press, Cambridge, MA, 1999.

\bibitem[Wilson and Garris(1992)]{nist}
C.L. Wilson and M.D. Garris.
\newblock Handprinted character database 3.
\newblock Technical report, National Institute of Standards and Technology,
  February 1992.

\bibitem[Young and Householder(1938)]{Young}
G.~Young and A.S. Householder.
\newblock Discussion of a set of points in terms of their mutual distances.
\newblock {\em Psychometrika}, 3:\penalty0 19--22, 1938.

\end{thebibliography}