\relax 
\bibstyle{plainnat}
\catcode`"\active
\citation{Dubuisson}
\citation{Jain}
\citation{Jacobs}
\select@language{polish}
\@writefile{toc}{\select@language{polish}}
\@writefile{lof}{\select@language{polish}}
\@writefile{lot}{\select@language{polish}}
\select@language{english}
\@writefile{toc}{\select@language{english}}
\@writefile{lof}{\select@language{english}}
\@writefile{lot}{\select@language{english}}
\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{175}}
\citation{Scholkopf}
\citation{Vapnik}
\citation{Scholkopf1}
\citation{Scholkopf0}
\citation{Scholkopf1}
\citation{Goldfarb2}
\citation{Duin2}
\citation{Pekalska2}
\citation{Arkadev}
\citation{Duin3}
\citation{Duin4}
\citation{Dubuisson}
\citation{Jacobs}
\citation{Tversky}
\citation{Jacobs}
\@writefile{toc}{\contentsline {section}{\numberline {2}On dissimilarity measures}{177}}
\newlabel{sec:compactness}{{2}{177}}
\citation{Duin2}
\citation{Pekalska2}
\citation{Young}
\citation{Borg}
\citation{Cox}
\citation{Borg}
\citation{Greub}
\citation{Borg}
\@writefile{toc}{\contentsline {section}{\numberline {3}Linear embedding of dissimilarities}{178}}
\newlabel{sec:embed}{{3}{178}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.1}Embedding of Euclidean distances}{178}}
\newlabel{Bis0}{{1}{178}}
\newlabel{eigen}{{2}{178}}
\newlabel{Xis}{{3}{178}}
\citation{Borg}
\citation{Gower}
\citation{Gower2}
\citation{Cox}
\citation{Gower}
\citation{Goldfarb1}
\citation{Goldfarb2}
\citation{Greub}
\newlabel{Covis}{{4}{179}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.2}Embedding of non-Euclidean distances}{179}}
\newlabel{Dnewis}{{5}{179}}
\citation{Goldfarb2}
\citation{Goldfarb1}
\citation{Goldfarb2}
\citation{Scholkopf0}
\citation{Scholkopf}
\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces An example on the usefulness of disregarding the negative eigenvalues. Assume that the theoretical, original data is a perfect line, however due to the measurement process, somewhat distorted, as observed in the first plot. The distance kernel $D$ is computed with distances $d_{ij} = ||\unhbox \voidb@x \hbox {\relax \mathversion  {bold}$x$}_i - \unhbox \voidb@x \hbox {\relax \mathversion  {bold}$x$}_j||^{1.004}$, which is nearly Euclidean. During the embedding process $16$ eigenvalues are revealed, where $14$ are negative (the largest negative in magnitude equals $-0.042$). This would suggest a possible $16$-dimensional configuration, however, one significant positive eigenvalue indicates that the `real' intrinsic dimensionality of the data is $1$ (for an Euclidean distance and a perfect line, the embedded configuration is $1$-dimensional). The second plot shows the projection onto first two dimensions (the configuration is retrieved up to a rotation). The last plot presents the projection onto the 1st and the 3rd dimensions, where the 3rd dimension corresponds to the largest (in magnitude) negative eigenvalue (how the embedding is done in such a case is explained by Formula \ref  {Xpsis}). Notice how a tiny change of both the theoretical data and the Euclidean distance of a very simple problem enlarges the number of retrieved dimensions, from $1$, in the perfect case, to $16$. }}{180}}
\newlabel{fig:line}{{1}{180}}
\newlabel{Xpsis}{{8}{180}}
\newlabel{Covpis}{{9}{180}}
\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces A pseudo-Euclidean space $R^{(1,1)}$, where $d^2(\unhbox \voidb@x \hbox {\relax \mathversion  {bold}$x$},\unhbox \voidb@x \hbox {\relax \mathversion  {bold}$y$}) = (\unhbox \voidb@x \hbox {\relax \mathversion  {bold}$x$} - \unhbox \voidb@x \hbox {\relax \mathversion  {bold}$y$})^T M (\unhbox \voidb@x \hbox {\relax \mathversion  {bold}$x$} -\unhbox \voidb@x \hbox {\relax \mathversion  {bold}$y$})$. Here, the length of any vector of the form $[x_1\ \pm x_1]^T$, is zero. The orthogonal vectors are mirrored w.r.t. the lines $x_2=x_1$ or $x_2=-x_1$, e.g. $\delimiter "426830A OA,OC\delimiter "526930B = 0$. Vector $\unhbox \voidb@x \hbox {\relax \mathversion  {bold}$v$}$ defines the plane $\unhbox \voidb@x \hbox {\relax \mathversion  {bold}$v$}^T M \unhbox \voidb@x \hbox {\relax \mathversion  {bold}$x$}=0$ in this space. Vector $\unhbox \voidb@x \hbox {\relax \mathversion  {bold}$w$} = M \tmspace  +\thinmuskip {.1667em} \unhbox \voidb@x \hbox {\relax \mathversion  {bold}$v$}$, a `flipped' version of $\unhbox \voidb@x \hbox {\relax \mathversion  {bold}$v$}$, describes the plane as if in an Euclidean space, i.e. it is perpendicular. This explains that in any pseudo-Euclidean space, the inner product operation can be seen as an Euclidean operation where one vector is `flipped' by $M$. In general, distances can be of any sign, e.g.: $d^2(A,C) = d^2(F,G) = 0$, $d^2(A,B) = 1$, $d^2(B,C) = -1$, $d^2(D,A) = -8$, $d^2(F,A) = 21$ and $d^2(E,C) = 8$. }}{181}}
\newlabel{fig:R11}{{2}{181}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.3}Embedding new points}{181}}
\newlabel{Bnewis}{{10}{181}}
\newlabel{Mis}{{11}{181}}
\citation{Goldfarb2}