\section{Introduction}

Euclidean distances are found in many real-world applications including fields from engineering to psychology \cite{journal:Leeuw}. For example, in sensor network localization, some pairs of sensors can communicate each other by sending and receiving  signals, which allows them to estimate their distances \cite{journal:Biswas}. Another example is the molecular conformation problem, in which some pairs of atoms are connected and the distances between them can be estimated using nuclear magnetic resonance experiments \cite{journal:Havel}. Other interesting examples and references can be found in \cite{journal:Dokmanic, journal:Liberti, journal:Billinge}.  \\
\indent Due to several reasons, in many situations we cannot access all the pairwise distances and, therefore, it becomes necessary to estimate those missing data. This problem is known as the \emph{Matrix Completion Problem} \cite{inbook:Candes1}.\\
\indent In many applications, the matrices to be completed are low-rank ones, that is, the minimum between the number of rows and the number of columns is much larger than the rank of the matrix. For instance, in molecular conformation problem, we may be interested in the coordinates of thousands of atoms (points in $\mathbb{R}^3$). This leads us to a Euclidean distance matrix with rank at most $5$, which is very low comparing to the number points \cite{journal:Dokmanic}.\\
\indent The \emph{Matrix Completion Problem} has attracted the attention in many areas of science and several advances have been obtained. One of the most important results in this field was achieved by Cand\`es and Recht \cite{inbook:Candes1}, who proved that it is possible to perfectly recover most low-rank matrices from what appears to be an incomplete set of entries.\\
\indent Based on this result, some algorithms have been proposed to recover a low-rank matrix. Cai et al \cite{journal:Cai} proposed a first-order singular value thresholding algorithm addressing problems in which the optimal solution has low rank. Mazumder et al \cite{journal:Mazumder} presented another algorithm, called Soft-Impute, which uses the singular value decomposition to find successive approximations through a regulator parameter. Krislock \cite{PhDthesis:Krislock} considers semidefinite facial reduction to complete low-rank Euclidean distance matrices.\\
\indent In this paper, we propose a novel completion approach. The rationale behind our method, which bears a resemblance to the soft-impute algorithm, is that the rank of a EDM, obtained from points in $\mathbb{R}^k$, is at most $k + 2$ and does not depend on the number of points. Therefore, differently from the soft-impute algorithm, our proposal takes the rank of the target matrix into account in order to calculate, for each iteration, the regulator parameter, which is paramount for the algorithm convergence. More specifically, we propose a way to calculate the regulator parameter, for each iteration, based on the most recent approximation. This apparently naive modification has been proved to be highly efficient, allowing to recover incomplete EDMs with high precision. For example, we were able to recover random EDMs with more than one thousand rows and up to $90\%$ of missing data, obtaining absolute error less than $10^{-8}$.  We have performed massive computational experiments that confirm the efficiency of our approach to recover missing data in EDMs, besides requiring a smaller number of iterations when compared to other competitive state-of-art technique, as the soft-impute.

\indent The rest of this paper is organized as follows. In Section $2$, we set the notation and provide a brief background on EDMs. In Section $3$, we introduce the matrix completion problem and present the soft-impute algorithm proposed by Mazumder et al \cite{journal:Mazumder}. In the same section, we present our contributions, defining a new way to choose the regulator parameter of soft-impute. In Section $4$, we present and discuss numerical experiments. Finally, we conclude the paper in Section $5$.

\section{Notations and preliminaries}

In this section, we shall define our notations and also present a short review of some important linear algebra results that are central for this paper.

Let $X=\left[x_1\,\,x_2\,\, \ldots \,\,x_n \right],\,\,\,x_i\in\mathbb{R}^k$, be a matrix whose columns represent $n$ points in a Euclidean $k-$dimensional space. The  distance-square $\left(d_{ij}\right)$ between any two points in $\mathbb{R}^k$ is defined by:
{\small{
\begin{equation}
\label{dist}
  d_{ij}=\|x_i-x_j\|^2_2 \triangleq \langle x_i-x_j\,,\,x_i-x_j\rangle = x_i^Tx_i -2x_i^Tx_j +x_j^Tx_j = \|x_i\|_2^2+\|x_j\|_2^2-2x_i^Tx_j.
\end{equation}
}}
\begin{defn
The matrix $D=\left[d_{ij}\right]\in \mathbb{R}^{n\times n}$, whose elements represent the square of the distances between $n$ points in $\mathbb{R}^k$ is called \emph{Euclidean Distance Matrix}, denoted by $edm(X)$.
\end{defn}

\begin{defn
The matrix $G=X^TX\in\mathbb{R}^{n\times n}$, whose elements represent the inner products between $n$ points in $\mathbb{R}^k$ is called \emph{Gram matrix} associated to $X$.
\end{defn}
According to (\ref{dist}), we can show that
\begin{equation}\label{edm}
  D \triangleq \textbf{1}\left(diag\left(X^TX\right)\right)^T-2X^TX+diag\left(X^TX\right)\textbf{1}^T,
\end{equation}
where \emph{\textbf{1}} represents the column vector of all elements equal to 1 and \emph{diag(A)} represents the column vector of the diagonal elements of $A$.

\begin{teor}\label{rankG}
  The rank of the Gram matrix associated to $X$ is at most $k$.
\end{teor}

\begin{proof}
  Since $X$ has $k$ rows, we know that $rank(X)\leq k$. From the properties
  \begin{itemize}
    \item $rank(AB)\leq\min(rank(A),\,rank(B))$
  \end{itemize}
  and
  \begin{itemize}
    \item $rank(A)=rank(A^T)$,
  \end{itemize}
 we concluded that
  $$rank(X^TX)=rank(X^TX)\leq\min(rank(X^T),\,rank(X))=rank(X)\leq k.$$
\end{proof}

\begin{teor}\label{rankD}
  The rank of the $edm(X)$ is at most $k+2$.
\end{teor}

\begin{proof}
   By Theorem \ref{rankG}, the rank of $X^TX$ is at most $k$. On the other hand, either $\textbf{1}diag(X^TX)^T$ or $diag(X^TX)\textbf{1}^T$ are matrices with rank equal to $1$.\\
   Therefore, from $rank(A+B)\leq rank(A)+rank(B)$ and by (\ref{edm}), we obtain that: $$rank(edm(X))\leq1+k+1=k+2.$$
\end{proof}

The Singular Value Decomposition (SVD) of a matrix $A$ is an important result for this work and it may be stated as the following \cite{inbook:Golub}:

\begin{teor}[Singular Value Decomposition]
Let $A\in\mathbb{R}^{n\times m}$ be a matrix with rank $r$. Then, $A$ can be written in the form
\begin{equation}\label{svd}
  A = U\Sigma V^T,
\end{equation}
where $U\in\mathbb{R}^{n\times n}$ and $V\in\mathbb{R}^{m\times m}$ are orthogonal matrices and $\Sigma\in\mathbb{R}^{n\times m}$ is given by
\begin{equation}\label{Sigma}
  \Sigma=\left[
           \begin{array}{ll}
             \Sigma_1 & 0_{r\times(m-r)} \\
             0_{(n-r)\times r} & 0_{(n-r)\times(m-r)} \\
           \end{array}
         \right],
\end{equation}
with $\Sigma_1=diag\{\sigma_1,\ldots,\sigma_r\}$.
\end{teor}
The decomposition (\ref{svd}) is called \emph{singular value decomposition} of $A$. The columns of $U$ are orthonormal  vectors, called \emph{right singular vectors} of $A$, and the columns of $V$ are also orthonormal, called \emph{left singular vectors} of $A$. $\sigma_k$ is called \emph{singular value}.

\section{Problem description and proposed model}

\subsection{Low-rank matrix completion}

Let $D$ be a Euclidean Distance Matrix (EDM), for which only a subset of its entries are available. Is it possible to guess the missing positions? How many entries are necessary to recover exactly the EDM? Is there an efficient way to compute the missing distances? This paper aims to answer these questions.

In general, the problem of estimating missing data matrix is known as the \textit{matrix completion problem} and has been intensively studied in the area of signal processing \cite{inbook:Candes1} and, more recently, attracted the attention in many other fields \cite{inbook:Candes2}.

In the context of Euclidean Distances, the matrix completion problem can be formulated as follows. Let $D$ be a EDM associated to a set of points $X = \{x_1,\,x_2,\ldots,\,x_n\}$, where $x_i\in\mathbb{R}^k$. Suppose that only a subset of its entries are available, say $\{ d_{ij}: (i,j) \in \Omega \}$, where $\Omega$  is a subset of the complete set of entries of $D$. The goal is to determine a complete EDM, $\hat{D} = [\hat{d}_{ij}]$,  such that  $\hat{d}_{ij}=d_{ij}, \ \forall \ (i,j) \in \Omega$. Additionally, the elements of the recovered matrix $\hat{D}$ must also satisfy the requirements of a EDM (non-negativity, symmetry, and triangular inequality).

The unknown elements in matrix $\hat{D}$ may be considered as variables of an optimization problem, defined by
\begin{equation}\label{minank}
    \begin{array}{ll}
      \emph{minimize} & \emph{rank($\hat{D}$)} \\
      \emph{subject to}\,\,\,   & \sum\limits_{(i,\,j)\in\Omega}(d_{ij}-\hat{d}_{ij})^2\leq\delta, \\
    \end{array}
\end{equation}
\noindent where $\delta$ is a tolerance for the known positions.\\

Unfortunately, the formulation expressed in (\ref{minank}) is not practical since the problem is non-convex and the solution through exact methods is computationally hard \cite{journal:Vandenberghe}. To overcome this difficulty, some relaxed versions of the problem  have been proposed \cite{inbook:Candes1, PhDthesis:Fazel} exploring the nuclear norm of $\hat{D}$. One of this approach is the following formulation:

\begin{equation}\label{minnuclear}
    \begin{array}{ll}
      \emph{minimize} & \|\hat{D}\|_* \\
      \emph{subject to}\,\,\,  & \sum\limits_{(i,\,j)\in\Omega}(d_{ij}-\hat{d}_{ij})^2\leq\delta, \\
    \end{array}
\end{equation}

\noindent where $\|\hat{D}\|_*$ is the nuclear norm of $\hat{D}$ (the sum of the singular values of $\hat{D}$).\\

Mazumder et al \cite{journal:Mazumder} consider an equivalent version of the problem (\ref{minnuclear}) in the Lagrangian form:
\begin{equation}\label{Lagrange}
    \begin{array}{cl}
      \emph{minimize} & \dfrac{1}{2}\sum\limits_{(i,\,j)\in\Omega}(d_{ij}-\hat{d}_{ij})^2+\lambda\|\hat{D}\|_*,
    \end{array}
\end{equation}

\noindent where $\lambda$ is a regularization parameter that controls the nuclear norm of the minimizer $\widehat{X}_\lambda$ of (\ref{Lagrange}). The authors show that there is a binary relation between $\delta\geq0$  and $\lambda\geq0$ on the active domains of each of these parameters.\\
\indent In the same paper, \cite{journal:Mazumder}, it is proposed a heuristic approach to solve the problem. The authors present a method called \emph{Soft-impute} that exploits the SVD factorization of the incomplete matrix. A pseudo-code is presented in  Algorithm $1$, where $S_{\lambda}(X)=U\Sigma_\lambda V^T,$
 with $\Sigma_\lambda=diag[(\sigma_1-\lambda)_+,\ldots,\,(\sigma_r-\lambda)_+]$  $\left(U\Sigma V^T\right.$ denotes the singular value decomposition of $\left.X\right)$, $\Sigma=diag[\sigma_1,\ldots,\,\sigma_r]$, $t_+=\max(t,\,0)$, $r=rank(X)$, $\|\cdot\|_F$ is the Frobenius norm $\left(\|A\|_F=\sqrt{\sum\limits_{i=1}^n\sum\limits_{j=1}^m|a_{ij}|^2}\right)$ and
 $$P_\Omega(X)(i,\,j)=\left\{
                         \begin{array}{ll}
                           X_{i,j}, & \hbox{if}\quad (i,\,j)\in\Omega \\
                           0, & \hbox{if}\quad (i,\,j)\notin\Omega
                         \end{array}.
                       \right.
 $$

\begin{algorithm}
\caption{- Soft-Impute \cite{journal:Mazumder}}
\begin{itemize}
  \item Input: matrix with missing data, $D\in\mathbb{R}^{n\times n}$, and a tolerance $\epsilon>0$.
\end{itemize}
\begin{enumerate}
  \item Inicialize $X^{old}=0$.
  \item Choose a decreasing sequence of scalars: $\lambda_1,\,\lambda_2,\ldots,\,\lambda_K$.
  \item For $i=1$ to $K$ do:
  \begin{enumerate}
    \item Calcule $X^{new}\rightarrow S_{\lambda_i}(P_\Omega(D)+P_\Omega^\perp(X^{old}))$.
    \item If $\dfrac{\|X^{new}-X^{old}\|_F^2}{\|X^{old}\|_F^2}<\epsilon$, exit.
    \item Do $X^{old}\leftarrow X^{new}$.
  \end{enumerate}
\end{enumerate}
\begin{itemize}
    \item Output: $X^{new}$.
\end{itemize}
\end{algorithm}

We propose a more specific formulation focused on Euclidean Distance Matrices. The idea is to exploit the properties of an EDM (the fact of its rank is at most $k+2$) to obtain some additional advantages in the optimization problem. We want to estimate the matrix $\hat{D}$ by solving the following optimization problem:
\begin{equation}
\label{fixed-rank}
    \begin{array}{ll}
      \emph{minimize } & \displaystyle \sum\limits_{(i,\,j)\in\Omega}(d_{ij}-\hat{d}_{ij})^2 \\
      \emph{subject to}\,\,\,  & \mbox{rank}(\hat{D}) = k+2. \\
    \end{array}
\end{equation}

Since there is not a straightforward formula for $\mbox{rank}(\hat{D})$ as a function of the variables $\hat{d}_{ij}$, we propose a heuristic approach to solve (\ref{fixed-rank}) based on a modification in the Soft-impute Algorithm. The resulting method is called the \textit{Fixed-Rank Soft-Impute} and it is described in the next section.

\subsection{Fixed-Rank Matrix Completion}

There are two main difficulties to apply Algorithm $1$ to solve the formulation (\ref{fixed-rank}) -- actually to solve any problem where the rank of $D$ it is a prior information. The first difficult is that the parameter $\lambda$ is defined outside of the loop, implying that it is insensitive to the convergence that occurs inside the loop. The second difficulty is that there is no specific details about the choice of the parameter $\lambda$. In \cite{journal:Mazumder}, the authors mention a \textit{warm starts}, but without presenting any concrete way of obtaining the values of $\lambda$. In our experiments, we realized that convergence of Algorithm $1$ seems to be very sensitive on the choice of $\lambda$ which motivate us to propose a new way of approach.

The new way to calculate the regulator parameter was also thought out to overcome the second difficult on the use of  Algorithm $1$ to solve (\ref{fixed-rank}). Since now we know the rank of the target matrix, let say rank$(X)=r$, we propose to compute the values of $\lambda$, in each iteration, as
\begin{equation}
\label{new_lambda}
\lambda=\beta\sigma_{r+1},
\end{equation}
where $\beta\in(0,1)$ and $\sigma_{r+1}$ is the $(r+1)$th singular value of the matrix $P_\Omega(D)+P_\Omega^\perp(X^{old})$, where $X^{old}$ is the most recent approximation.

\indent The idea is to link the parameter $\lambda$ with the most recent approximation of $X$ and leave its calculation automatically. Since we wish to converge to a matrix $X$, such that rank$(X) = r$, we should have only $r$ singular values greater than zero. Thus, the singular value $\sigma_{r+1}$ give us a valuable information about how far we are from the solution and, therefore, we can calibrate the step size of the next iteration.

The only exogenous parameter we have now is the value of $\beta \in (0,1)$, that may be adjusted to control the rate of decreasing the singular values in each iteration of the method. The big is $\beta$ the fast is the way of decreasing the singular values in each iteration. Some matrices are very sensitive on the rate of decreasing of the less significant singular values and Algorithm $2$ may lead to a rank $r$ matrix without achieving the tolerance $\epsilon$. In this case, we suggest to try a smaller value for $\beta$ and so running a more slowly decreasing.

We summarize our approach in the following algorithm:

\begin{algorithm}[H]
\caption{- Fixed-Rank Soft-Impute}
\begin{itemize}
  \item Inputs: a matrix with missing data, $D\in\mathbb{R}^{n\times n}$, the rank $r$ of the target matrix $X$ and a tolerance $\epsilon>0$.
\end{itemize}
\begin{enumerate}
  \item Inicialize $X^{old}=0$.
  \item Choose a initial value to $\lambda$ ($\lambda=\lambda_0$).
  \item For $i=1$ to $K$ do:
  \begin{enumerate}
    \item Calcule $X^{new}\rightarrow S_{\lambda}(P_\Omega(D)+P_\Omega^\perp(X^{old}))$.
    \item Set $\lambda=\beta\sigma_{r+1}$, with $\beta\in(0,1)$.
    \item If $\dfrac{\|X^{new}-X^{old}\|_F^2}{\|X^{old}\|_F^2}<\epsilon$, exit.
    \item Do $X^{old}\leftarrow X^{new}$.
  \end{enumerate}
\end{enumerate}
\begin{itemize}
    \item Output: $X^{new}$.
\end{itemize}
\end{algorithm}

We remark that there is no additional cost to obtain $\lambda$, since the SVD is calculated in step 3(a). The apparently naive modification on the calculation of $\lambda$ has been proved to be highly efficient, allowing us to recover incomplete EDMs with high precision, even in the case where less than $5\%$ of the positions of $D$ are known. In the next section, we present some results of computational experiments we have performed using Algorithm 2.

The tests performed were based on a random generation of distance matrices and random deletion of a percentage $p$ of their elements. The original matrix $D$ was maintained for comparison purposes. We used the relative error, defined by $er = \dfrac{\|D -\hat{D}\|_F^2}{\|D\|_F^2}$, where $||A||_F$ represents the Frobenius norm of matrix $A$. We also compute the maximum error $(max\_err)$ between two corespondent elements, i.e.  $max\_err  = max|d_{ij}-\hat{d}_{ij}|$, which is a very rigorous criteria of convergence.

\section{Numerical results}

We have implemented the methods in Matlab language and performed the tests using a microcomputer with Windows-$64$ bits, Intel Core i-$5$, $2430M$ CPU, $2.40$GHz and $4$GB of RAM. \\
\indent We considered two classes of matrices. In order to test Algorithm 2 in a general context, we generated $n\times n$ matrices of rank $r$ according to the form $M=M_LM^*_R$, where $M_L$ and $M_R$ are $n\times r$ independent matrices, having i.i.d. Gaussian entries, as done in \cite{journal:Cai}. Another class is the main interest of this paper. We generated random points in $\mathbb{R}^k$ and then calculated the correspondent EMD. In both cases, we deleted a percentage $p$ of his entries, uniformly at random. All results presented are averages of $10$ simulations. \\
\indent In order to set a good choice for the parameter $\beta$, we performed a set of warm up simulations varying $\beta$ in the interval $(0,\,1)$ and then choosing the most appropriated value for each type of test. Figure \ref{beta} shows the results of these simulations for EDMs, suggesting that, for this case, we may consider $\beta \approx 0.8$.
\begin{figure}[H]
  \centering
  \includegraphics[scale=.3 ]{fig1}
  \caption{{\scriptsize{Number of iterations (average) versus beta. We made $100$ simulations, using $100\times 100$ EDMs associated to points in $\mathbb{R}^2$, with $40\%$ of missing data.}}}
  \label{beta}
\end{figure}

In Table \ref{tab3}, we present a comparison between results obtained with Algorithm $2$, for the case of random matrices of form $M=M_LM^*_R$, and results presented in \cite{journal:Cai} for the same size of matrices and percentage of deletion.\\

\begin{table}[H]{\scriptsize{
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
\multicolumn{3}{|c|}{} & \multicolumn{6}{c|}{Results}\tabularnewline
\hline
\multicolumn{3}{|c|}{Unknow matrix
} & \multicolumn{3}{c|}{Results by \cite{journal:Cai} } & \multicolumn{3}{c|}{Our approach}\tabularnewline
\hline
size ($n\times n$) & rank ($r$) & $|\Omega|/n^{2}$ & time ($s$) & \# iter  & relative error & time ($s$) & \# iter  & relative error\tabularnewline
\hline
\multirow{3}{*}{$1000\times1000$} & $10$ & $0.12$ & $23$ & $117$ & $1.64\times10^{-4}$ & $226$ & $386$ & $9.95\times10^{-5}$\tabularnewline
\cline{2-9}
 & $50$ & $0.39$ & $193$ & $114$ & $1.59\times10^{-4}$ & $73.2$ & $103$ & $9.93\times10^{-5}$\tabularnewline
\cline{2-9}
 & $100$ & $0.57$ & $501$ & $129$ & $1.68\times10^{-4}$ & $129$ & $79$ & $9.68\times10^{-5}$\tabularnewline
\hline
\end{tabular}
\caption{{\scriptsize{Comparison between our approach and Cai et al in \cite{journal:Cai}, for a  $1000\times1000$ matrix.}}}
\label{tab3}
}}
\end{table}

In Table \ref{tab5}, we show the advantage of our approach. With the same parameters  used in Table \ref{tab3}, we set the tolerance $\epsilon = 10^{-10}$. We can see that, in the worst case, we were able to recover $D$ with $7$ correct decimal places ($max\_error \leq 10^{-8}$), showing the high accuracy of our approach.

\begin{table}[H]{\scriptsize{
  \centering
  \begin{tabular}{|c|c|c|c|c|c|c|}
    \hline
    \multicolumn{3}{|c|}{$Unknow\ matrix$} & \multicolumn{4}{|c|}{$Results$}\tabularnewline
    \hline
    \hline
    $size\ (n\times n)$ & $rank\ (r)$ & $|\Omega|/n^{2}$ & $relative\ error$ & $max\ error$ & $\#\ iter$ & $time\ (s)$\tabularnewline
    \hline
    \multirow{3}{*}{$1000\times1000$} & $10$ & $0.12$ & $9.83\times10^{-11}$ & $1.18\times10^{-9}$ & $1084$ & $1003.2$\tabularnewline
    \cline{2-7}
     & $50$ & $0.39$ & $9.72\times10^{-11}$ & $8.16\times10^{-9}$ & $244$ & $238.2$\tabularnewline
    \cline{2-7}
     & $100$ & $0.57$ & $9.35\times10^{-11}$ & $1.94\times10^{-8}$ & $201$ & $192.6$\tabularnewline
    \hline
\end{tabular}
  \caption{{\scriptsize{$1000\times1000$ matrix completion performed by our approach, setting tolerance equal to $10^{-10}$.}}}
  \label{tab5}
  }}
\end{table}

Now, we focus on EDM's. We generated points in $\mathbb{R}^k$, according to a uniform distribution  and then compute the corresponding EDM $D$. For each experiment we deleted a percentage $p$ of the entries of $D$, uniformly at random, and we applied Algorithm $2$ to recover the missing data.

Table \ref{tab2} shows numerical results of tests performed with EMD's obtained from random generation. We varied the number of points generated, the space dimension, the percentage of deletion, and we fixed the tolerance (relative error) equal to $10^{-8}$.\\

\begin{table}[H]{\scriptsize{
\centering

\begin{tabular}{|c|c|c|c|c|c|}
\hline
\# Points (n) & Dimension (d) & Rank (r) & Deletion (\%) & \# Iteration  & Maximum error\tabularnewline
\hline
\hline
$500$ & $10$ & $12$ & $50$ & $61$ & $2.76\times10^{-7}$\tabularnewline
\hline
$1000$ & $3$ & $5$ & $70$ & $82$ & $7.11\times10^{-8}$\tabularnewline
\hline
$2000$ & $10$ & $12$ & $70$ & $86$ & $2.45\times10^{-7}$\tabularnewline
\hline
$5000$ & $50$ & $52$ & $50$ & $44$ & $1.27\times10^{-6}$\tabularnewline
\hline
$5000$ & $200$ & $202$ & $50$ & $74$ & $8.32\times10^{-6}$\tabularnewline
\hline
$5000$ & $50$ & $52$ & $80$ & $193$ & $1.61\times10^{-6}$\tabularnewline
\hline
$5000$ & $3$ & $5$ & $90$ & $201$ & $1.24\times10^{-4}$\tabularnewline
\hline
$10000$ & $100$ & $102$ & $80$ & $187$ & $3.40\times10^{-6}$\tabularnewline
\hline
\end{tabular}

\caption{{\scriptsize{Performance of Algorithm $2$ varying some parameters such as the number of points generated, the space dimension, and the percentage of random deletion. For every experiment we fixed the tolerance (relative error) equal to $10^{-8}$.}}}
\label{tab2}
}}
\end{table}

According to these results, we can see that Algorithm $2$ was able to recover missing data with very high accuracy. Additionally, Table \ref{tab2} shows us that we can recover matrices with not so small rank. We recovered, for instance, matrices with rank equal to $100$ and $200$ with a very good accuracy. \\

For the results presented in Table \ref{tab6}, we fixed $n = 1000$ points in dimension $r = 8$ and we varied the percentage of deletion of data: $p \in \{10, 20,\ldots, 90\}$.

\begin{table}[H]
  \centering
  {\scriptsize{
  \begin{tabular}{|c|c|c|c|c|}
\hline
\multirow{2}{*}{Deletion (\%)} & \multicolumn{4}{c|}{Computational results}\tabularnewline
\cline{2-5}
 & $time\ (s)$ & $\#\ iter$ & $relative\ error$ & $max\ error$\tabularnewline
\hline
$10$ & $10.2$ &$24$ & $5.73\times10^{-13}$ & $7.67\times10^{-12}$\tabularnewline
\hline
$20$ & $9$ & $35$ & $6.04\times10^{-13}$ & $1.31\times10^{-11}$\tabularnewline
\hline
$30$ & $17.4$ & $43$ & $5.04\times10^{-13}$ & $7.22\times10^{-12}$\tabularnewline
\hline
$40$ & $18.6$ & $58$ & $6.79\times10^{-13}$ & $8.35\times10^{-12}$\tabularnewline
\hline
$50$ & $27$ & $75$ & $8.53\times10^{-13}$ & $9.43\times10^{-12}$\tabularnewline
\hline
$60$ & $38.4$ & $110$ & $9.08\times10^{-13}$ & $1.72\times10^{-11}$\tabularnewline
\hline
$70$ & $69$ & $184$ & $9.18\times10^{-13}$ & $1.32\times10^{-11}$\tabularnewline
\hline
$80$ & $170.4$ & $430$ & $9.42\times10^{-13}$ & $2.05\times10^{-11}$\tabularnewline
\hline
$90$ & $367.8$ & $1000$ & $2.91\times10^{-07}$ & $3.30\times10^{-06}$\tabularnewline
\hline
\end{tabular}
}}
  \caption{{\scriptsize{Performance of Fixed Rank Soft Impute. Results of a simulation with an EDM associated to 1000 points in $\mathbb{R}^8$, with random deletion $p \in \{10, 20,\ldots, 90\}$, a maximum number of iteration of 1000 and tolerance equal to $10^{-12}$.}}}
  \label{tab6}
\end{table}

As expected, as the percentage of the missing data increases, the algorithm needs more iterations to converge. Even so, in all cases we were able to achieve at error maximum up to $10^{-6}$ with less than 1000 iterations in a few minutes of calculation.\\

We also varied the size of EDMs, using points in $\mathbb{R}^5$ and deleting $p=70\%$ of the data, to see how our approach behaves. We summarized the results in Table \ref{tab7}.

\begin{table}[H]
  \centering
  {\scriptsize{
  \begin{tabular}{|c|c|c|c|c|}
\hline
\multirow{2}{*}{$\# points$ ($n$)} & \multicolumn{4}{c|}{Computational results}\tabularnewline
\cline{2-5}
 & $time\ (s)$ & $\#\ iter$ & $relative\ error$ & $max\ error$\tabularnewline
\hline
$200$ & $10.8$ & $473$ & $9.72\times10^{-09}$ & $5.61\times10^{-08}$\tabularnewline
\hline
$500$ & $16.2$ & $165$ & $9.33\times10^{-09}$ & $8.17\times10^{-08}$\tabularnewline
\hline
$1000$ & $29.4$ & $108$ & $9.13\times10^{-09}$ & $1.05\times10^{-07}$\tabularnewline
\hline
$2000$ & $149.4$ & $83$ & $8.16\times10^{-09}$ & $8.46\times10^{-08}$\tabularnewline
\hline
\end{tabular}
}}
  \caption{{\scriptsize{Performance of Fixed Rank Soft Impute. Results of a simulation with a EDM associated to $n$ points $(n\in\{200,\ 500,\ 1000,\ 2000\})$ in $\mathbb{R}^5$, with random deletion of $70\%$ of data, a maximum number of iteration of 1000 and tolerance equal to $10^{-08}$.}}}
  \label{tab7}
\end{table}

We can note that, for a fixed percentage of missing data, the number of required iterations decreases when the size of the EMD grows. As we can see, in all cases tested, our approach has been proved to be an efficient way to recover missing data in EDMs, outperforming other competitive state-of-art technique. Finally, we have performed some examples with EDMs related to 5000 random points in $\mathbb{R}^3$ and considered $p=0.98$ of missing data. In these cases, our approach was able to recover the exact matrix with absolute error smaller than $10^{-7}$.

\section{Conclusions}

We proposed the application of low-rank matrix completion approach to estimate missing data in Euclidean distance matrices (EDMs). We presented a specific formulation of the matrix completion and proposed an algorithm based on singular value decomposition. Computational results indicate that our approach is efficient to estimate missing positions in matrices whose rank is known a priori. We were able to recover matrices from a few percentage of entries, with very  high accuracy. The method presented here can also be used for other applications in matrix completion when the rank of the target matrix is know.

\section*{Acknowledgements}

The authors would like to thank the Brazilian research agencies CAPES, CNPq, and FAPESP for their financial support.


\section{Introduction}

In recent years, style transfer, as an interesting application of deep neural networks (DNNs), has increasingly attracted attention among the research community. Existing studies either apply an iterative optimization mechanism~\cite{Gatys} or directly learn a feed-forward generator network to force the output image to be with target style and target contents~\cite{johnson,ulyanov}. A set of losses are accordingly proposed for the transfer network, such as the pix-wise loss~\cite{isola}, the perceptual loss~\cite{johnson,zhang2017multi}, and the histogram loss~\cite{wilmot}. Recently, several variations of generative adversarial networks (GANs)~\cite{liu2016,Zhu2017} are introduced by adding a discriminator to the style transfer network which incorporates adversarial loss with transfer loss to generate better images. However, these studies aim to explicitly learn the transformation from a certain source style to a given target style, and the learned model is thus not generalizable to new styles, i.e. retraining is needed for transformations of new styles which is time-consuming.

\begin{figure}[!tbp]
\setlength{\abovecaptionskip}{-2pt}
\centering
\hspace{-5pt}
\includegraphics[height=1.0in,width=3.3in]{net1.pdf}
\caption{The framework of the proposed {\em EMD} model.}
\label{fig:framework1}
\vspace{-15pt}
\end{figure}

\begin{table*}[!t]\footnotesize{}
    \centering
    \caption{Comparison of {\em EMD} with existing methods.}
    \begin{tabular}{c|c|c|c|c}
    \hline
        Methods &  Data format & Generalizable to new styles? & Requirements for new style transfer & What the model learned? \\
    \hline Pix2pix~\cite{isola} & paired & \multirow{8}{3.2cm}{The learned model can only transfer images to styles which appeared in the training set. For new styles, the model has to be retrained.}
    & \multirow{6}{4cm}{Retrain on a lot of training images for a source style and a target style.}  & \multirow{6}{4.5cm}{The translation from a certain source style to a specific target style.}\\
    \cline{1-2} CoGAN~\cite{liu2016} &  unpaired &  & & \\
    \cline{1-2} CycleGAN~\cite{Zhu2017} &  unpaired  & &  \\
    \cline{1-2} Rewrite~\cite{rewrite} &  paired  &  & &\\
    \cline{1-2} Zi-to-zi~\cite{zitozi} & paired  &  & &\\
    \cline{1-2} AEGN~\cite{lyu} & paired  &   & & \\
    \cline{1-2} \cline{4-5} Perceptual~\cite{johnson} & unpaired  &  &  \multirow{2}{4cm}{Retrain on many input content images and one style image.} &
    \multirow{2}{4.5cm}{Transformation among specific styles.}\\
    \cline{1-2} StyleBank~\cite{chen2017} & unpaired  &  & & \\
    \hline  Patch-based~\cite{chen2016fast} & unpaired  & \multirow{3}{3.2cm}{The learned model can be generalized to new styles.}  & \multirow{3}{4cm}{One or a small set of style/content reference images.} & The swap of style/content feature maps. \\
    \cline{1-2} \cline{5-5} AdaIn~\cite{Huang_2017_ICCV} & unpaired & & & The transferring of feature statistics. \\
    \cline{1-2} \cline{5-5} EMD & triplet &  &  & The feature representation of style/content. \\

    \hline
    \end{tabular}%
    \vspace{-10pt}
  \label{tab:comp_methods}%
\end{table*}%

In this paper, we propose a novel generalized style transfer network which can extend well to new styles or contents. Different from existing supervised style transfer methods, where an individual transfer network is built for each pair of style transfer, the proposed network represents each style or content with a small set of reference images and attempts to learn separate representations for styles and contents. Then, to generate an image of a given style-content combination is simply to mix the corresponding two representations. This learning framework allows simultaneous style transfer among multiple styles and can be deemed as a special `multi-task' learning scenario. Through separated style and content representations, the network is able to generate images of all style-content combination given the corresponding reference sets, and is therefore expected to generalize well to new styles and contents.
To our best knowledge, the study most resembles to ours is the bilinear model proposed by Tenenbaum and Freeman~\cite{Tenenbaum}, which obtained independent style and content representations through matrix decomposition. However, it usually requires an exhaustive enumeration of examples for accurate decomposition of new styles and contents, which may not be readily available for some styles/contents.

As shown in Figure~\ref{fig:framework1}, the proposed style transfer network, denoted as {\em EMD} thereafter, consists of a style encoder, a content encoder, a mixer, and a decoder. Given a set of reference images, the style/content encoder leverages the conditional dependence of styles and contents to learn style/content representations. The mixer then combines the corresponding style and content representations using a bilinear model. The decoder finally generates the target images based on the combined representations. Each training example for the proposed network is provided as a triplet $<$$\mathcal{R}_{S_i}$, $\mathcal{R}_{C_j}$, $I_{ij}$$>$, where $I_{ij}$ is the target image of style $S_i$ and content $C_j$. $\mathcal{R}_{S_i}$ and $\mathcal{R}_{C_j}$ are respectively the style and content reference sets, each consisting of $r$ random images of the corresponding style $S_i$ and content $C_j$. The entire network is trained end-to-end with a weighted $L1$ loss measuring the difference between the generated images and the target images.
As it is difficult to validate the decomposition of style and content for images, we here use the character typeface transfer as a special case of style transfer to validate the proposed method. Extensive experiment results have demonstrated the effectiveness and robustness of our method for style transfer.
The main contributions of our study are summarized as follows.
\begin{itemize}
\item We propose a generalized style transfer network which is able to generate images of any unseen style/content given a small set of reference images.
\item The network decomposes an image into separate style and content representations, taking advantages of the conditional dependence of contents and styles.
\item This learning framework allows simultaneous style transfer among multiple styles and can be deemed as a special `multi-task' learning scenario.
\end{itemize}

\begin{figure*}[!tbp]
\setlength{\abovecaptionskip}{-2pt}
\centering
\includegraphics[height=2.5in,width=7in]{net2.pdf}
\caption{The detailed architecture of the proposed generalized {\em EMD} model for style transfer.}
\label{fig:framework2}
\vspace{-5pt}
\end{figure*}

\section{Related Work}

\textbf{Neural Style Transfer.} DeepDream~\cite{mordvintsev} may be the first attempt to generate artistic work using Convolution Neural Networks (CNNs). Then Gatys et. al successfully applied CNNs to neural style transfer~\cite{Gatys}. They generate the target image by optimizing a noise image iteratively using a pretrained network, which is time-consuming. Therefore, many studies have been done for finding a way to directly learn a feed-forward generator network. Johnson et. al proposed a perceptual loss function to help neural style transfer~\cite{johnson}. Ulyanov et. al proposed a texture network for both texture synthesis and style transfer~\cite{ulyanov}. Further, Chen et. al proposed the stylebank to represent each style by a convolution filter, which can simultaneously learn numerous styles~\cite{chen2017}. For arbitrary neural style transfer, \cite{chen2016fast} proposed a patch-based method to replace each content feature patch with the nearest style feature. Further, \cite{Huang_2017_ICCV} proposed a faster method based on adaptive instance normalization which performed style transfer in the feature space by transferring feature statistics.

\textbf{Image-to-Image Translation.} Image-to-image translation is to learn the mapping from the input image to output image, such as from edges to real objects. Pix2pix~\cite{isola} used a conditional GAN based network which needs paired data for training. However, paired data are hard to collect in many applications. Therefore, some methods with no need for paired data are proposed. Liu and Tuzel proposed the coupled GAN (CoGAN)~\cite{liu2016} for learning a joint distribution of two domains by a weight sharing way. Later, Liu~\cite{liu2017} extended the CoGAN to unsupervised image-to-image translation problem. Some other studies~\cite{Bousmalis,Shrivastava,Taigmand} encourage the input and output to share certain content even though they may differ in style by enforcing the output to be close to the input in a predefined metric space, such as class label space and so on. Recently, Zhu et. al proposed the cycle-consistent adversarial network (CycleGAN)~\cite{Zhu2017} which performs well for many vision and graphics tasks.

\textbf{Character Style Transfer.} Most existing studies take character style transfer as an image translation task. The ``Rewrite" project uses a simple traditional flavour top-down CNNs structure and can transfer a typographic font to another stylized typographic font~\cite{rewrite}. As the improvement version, the ``zi-to-zi" project can transfer multiple styles by assigning each style an one-hot category label and training the network by a supervised way~\cite{zitozi}. The recent work ``From A to Z" also adopts a supervised method and assigns each character an one-hot label~\cite{upchurch}. Lyu et. al proposed an auto-encoder guided GAN network (AEGN) which can synthesize calligraphy images with specified style from standard Chinese font images~\cite{lyu}.

However, most of the methods reviewed above can only transfer styles in the training set and the network must be retrained for new styles. In contrast, the proposed {\em EMD} network can generate images with novel styles/contents given only a small set of reference images. We present a comparison of the methods in Table~\ref{tab:comp_methods}.

\section{Generalized Style Transfer Model}

In this section, we present the details of the proposed generalized style transfer model {\em EMD}. The whole model is an encoder-decoder network which consists of four subnets: $\textsl{Style Encoder}$, $\textsl{Content Encoder}$, $\textsl{Mixer}$ and $\textsl{Decoder}$, as shown in Figure~\ref{fig:framework2}. First, the $\textsl{Style/Content Encoder}$  extracts style/content representations given style/content reference images. Next, the $\textsl{Mixer}$ integrates the style feature and content feature and the combined feature is then fed into the $\textsl{Decoder}$. Finally, the $\textsl{Decoder}$ generates the image with the target style and content.

\subsection{Encoder Network}
To achieve the generation of images with arbitrary style and content, it is crucial to separate the style and content explicitly. The $\textsl{Style Encoder}$ and $\textsl{Content Encoder}$ are designed for this purpose. They both have the same architecture, consisting of a series of Convolution-BatchNorm-LeakyReLU down-sampling blocks which yield 1$\times$1 latent feature representations of the input style/content reference images. The first convolution layer is with $5\times5$ kernel and stride 1 and the rest are with $3\times3$ kernel and stride 2. All ReLUs are leaky, with slope 0.2.

The input to the $\textsl{Style Encoder}$ and $\textsl{Content Encoder}$ are style reference set $\mathcal{R}_{S_i}$ and content reference set $\mathcal{R}_{C_j}$, respectively. $\mathcal{R}_{S_i}$ consists of $r$ reference images with the same style $S_i$ but different contents ${C_{j_1},C_{j_2},\ldots,C_{j_r}}$
\begin{equation}
\mathcal{R}_{S_i} = \{I_{ij_1}, I_{ij_2}, \ldots, I_{ij_r} \},
\end{equation}
where $I_{ij}$ represents the image with style $S_i$ and content $C_j$.

Similarly, $\mathcal{R}_{C_j}$ is for content $C_j$ $(j=1,2,\ldots,m)$ and consists of $r$ reference images with the same content $C_j$ but different styles ${S_{i_1},S_{i_2},\ldots,S_{i_r}}$
\begin{equation}
\mathcal{R}_{C_j} = \{I_{i_1j}, I_{i_2j}, \ldots, I_{i_rj} \}.
\end{equation}
The $r$ reference images are concatenated in the channel dimension to feed in to the encoders. This allows the encoders to capture the common characteristics among images of the same style/content.

\subsection{Mixer Network}
With the style representations and content representations obtained by the $\textsl{Style Encoder}$ and $\textsl{Content Encoder}$, we combine the two factors by the $\textsl{Mixer}$ which is a bilinear model. The bilinear models are two-factor models with the mathematical property of separability: their outputs are linear in either factor when the other is held constant, which has been demonstrated that the influences of two factors can be efficiently separated and combined in a flexible representation that can be naturally generalized to unfamiliar factor classes~\cite{Tenenbaum}, such as new styles. Furthermore, the bilinear model has also been successfully used in zero-shot learning as a compatibility function to associate visual representation and auxiliary class text description~\cite{changpinyo,frome,xian}. The learned compatibility function can be seen as the shared knowledge and transferred to new classes. Here, we take the bilinear model to integrate styles and contents together and the combination function can be formulated as
\begin{equation}
F_{ij} = S_i\textbf{W}C_j,
\end{equation}
where $\textbf{W}$ is a tensor with size $R\times K \times B$, $S_i$ is the $R$-dimensional style feature and $C_j$ is the $B$-dimensional content feature. $F_{ij}$ can be seen as the $K$-dimensional feature vector of image $I_{ij}$ which will be taken as the input of the $\textsl{Decoder}$ to generate the image with style $S_i$ and content $C_j$.

\subsection{Decoder Network}

The image generator is a typical decoder network which is symmetrical to the encoder and maps the combined feature representation to the output image with target style and content. The $\textsl{Decoder}$ roughly follows the architectural guidelines set forth by Radford et. al~\cite{Radford} and consists of a series of Deconvolution-BatchNorm-ReLU up-sampling blocks except the last layer which only contains the deconvolution layer. Other than the last layer which uses 5$\times$5 kernels and stride 1, all deconvolution layers use 3$\times$3 kernels and stride 2. The outputs are transformed into $0\sim 1$ by the sigmoid function.

In addition, since the stride convolution in $\textsl{Style Encoder}$ and $\textsl{Content Encoder}$ is detrimental to spatial information extraction, we adopt the skip-connection which has been commonly used in semantic segmentation tasks~\cite{jegou,long,ronneberger} to refine the segmentation using spatial information from different resolutions. Here, based on the fact that though the content inputs and outputs differ in appearances, they share the same structure, we concatenate the input feature map of each up-sampling block with the corresponding output of the symmetrical down-sampling block in $\textsl{Content Encoder}$ to allow the $\textsl{Decoder}$ to learn back the relevant structure information lost during the down-sampling process.

\subsection{Loss Function}

Given a set of training examples $\mathcal{D}_t$, the training objective is defined as
\begin{alignat}{3}
\theta = \argmin_{\theta} \sum_{I_{ij} \in \mathcal{D}_t} L(\hat{I}_{ij},I_{ij}|\mathcal{R}_{S_i},\mathcal{R}_{C_j}),
\label{eq:model}
\end{alignat}
where $\theta$ represents model parameters, $\hat{I}_{ij}$ is the generated image and $L(\hat{I}_{ij},I_{ij}|\mathcal{R}_{S_i},\mathcal{R}_{C_j})$ is the generation loss which can be written as
\begin{equation}
L(\hat{I}_{ij},I_{ij}|\mathcal{R}_{S_i},\mathcal{R}_{C_j}) = W^{ij}_{st}\times W^{ij}_b \times ||\hat{I}_{ij} - I_{ij}||.
\end{equation}
We use pixel-wise L1 loss as our generation loss for character typeface transfer problem rather than L2 loss since L1 loss tends to yield sharper and cleaner images~\cite{isola,lyu}.

$W^{ij}_{st}$ and $W^{ij}_b$ are two weights for target image $I_{ij}$ which are added to alleviate the imbalance in the target set induced by the random sampling. In each learning iteration, the size and thickness of target images in the target set may vary greatly and the model will be optimized mainly for target images containing characters which have more pixels and cause more losses, such as those big and thick characters. Moreover, models trained using L1 loss may pay more attention to blacker characters and perform poorly on images with lighter characters. To alleviate these imbalance, we add these two weights on the generation loss: $W^{ij}_{st}$ about the size and thickness of characters, and $W^{ij}_b$ about the darkness of characters.

As for $W^{ij}_{st}$, we first calculate the number of black pixels, i.e. pixels covered by the characters. Then $W^{ij}_{st}$ is defined as the reciprocal of the number of black pixels in each target image
\begin{equation}
W^{ij}_{st} = 1/N_b^{ij},
\end{equation}
where $N_b^{ij}$ is the number of black pixels of target image $I_{ij}$.

As for $W^{ij}_b$, we calculate the mean value of black pixels for each target image and set a softmax weight
\begin{equation}
W^{ij}_b = \frac{exp(\textrm{mean}_{ij})}{\sum_{I_{ij}\in \mathcal{D}_t}exp(\textrm{mean}_{ij})},
\end{equation}
where $\textrm{mean}_{ij}$ is the mean value of the black pixels of the target image $I_{ij}$.

\section{Experiments}
In this section, we evaluate the proposed network for Chinese Typeface transfer problem. We first introduce the data set we used followed by the implementation details. Finally, we present our experimental results.

\begin{figure}[!t]
\setlength{\abovecaptionskip}{-2pt}
\centering
\hspace{-5pt}
\includegraphics[height=1.5in,width=3.3in]{train.pdf}
\caption{The illustration of data set partition, target images selection and reference set construction (best viewed in color).}
\label{fig:train}
\vspace{-10pt}
\end{figure}

\begin{figure}[!t]
\centering
\setlength{\abovecaptionskip}{5pt}
\hspace{-6pt}
\subfigure{
\begin{minipage}{0.24\textwidth}{\vspace{-5pt}
\begin{minipage}{0.12\textwidth}TG:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-10s-10c-test1-157-targets.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O1:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_20000-10s-10c-test1-157-outputs.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O2:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_50000-10s-10c-test1-157-outputs.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O3:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_100000-10s-10c-test1-157-outputs.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O4:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-10s-10c-test1-157-outputs.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O5:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_500000-10s-10c-test1-157-outputs.png}
\end{minipage}
\unskip\ \hrule\
\\
\begin{minipage}{0.12\textwidth}TG:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-10s-10c-test3-14-targets.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O1:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_20000-10s-10c-test3-14-outputs.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O2:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_50000-10s-10c-test3-14-outputs.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O3:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_100000-10s-10c-test3-14-outputs.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O4:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-10s-10c-test3-14-outputs.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O5:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_500000-10s-10c-test3-14-outputs.png}
\end{minipage}
}
\end{minipage}
}
\vspace{-5pt}
\unskip\ \vrule\
\hspace{-3pt}
\subfigure{
\begin{minipage}{0.21\textwidth}{\vspace{-5pt}
\includegraphics[width=1.5in,height=0.21in]{results_300000-10s-10c-test2-157-targets.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_20000-10s-10c-test2-157-outputs.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_50000-10s-10c-test2-157-outputs.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_100000-10s-10c-test2-157-outputs.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_300000-10s-10c-test2-157-outputs.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_500000-10s-10c-test2-157-outputs.png}
\unskip\ \hrule\
\\
\includegraphics[width=1.5in,height=0.21in]{results_300000-10s-10c-test4-14-targets.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_20000-10s-10c-test4-14-outputs.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_50000-10s-10c-test4-14-outputs.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_100000-10s-10c-test4-14-outputs.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_300000-10s-10c-test4-14-outputs.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_500000-10s-10c-test4-14-outputs.png}

}
\end{minipage}
}
\caption{Generation results for $D_1$, $D_2$, $D_3$, $D_4$ (from upper left to lower right) with different training set size. TG: Target image, O1: Output for $N_{t}$=20k, O2: Output for $N_{t}$=50k, O3: Output for $N_{t}$=100k, O4: Output for $N_{t}$=300k, O5: Output for $N_{t}$=500k. In all cases, $r$=10.}
\label{fig:train-size}
\vspace{-15pt}
\end{figure}

\subsection{Data Set}
To evaluate the proposed {\em EMD} model with Chinese Typeface transfer tasks, we construct a data set which contains 832 fonts (styles) and each font has 1732 commonly used Chinese characters (contents). All images are $80\times 80$ pixels. We randomly select 75\% of the styles and contents as known styles and contents (i.e. 624 train styles and 1299 train contents) and leave the rest 25\% as novel styles and contents (i.e. 208 novel styles and 433 novel contents). The entire data set is therefor partitioned into four subsets as shown in Figure~\ref{fig:train}: $D_1$, images with known styles and contents namely train styles and contents, $D_2$, images with known styles but novel contents, $D_3$, images with known contents but novel styles, and $D_4$, images with both novel styles and novel contents. The four data sets represent different levels of style transfer challenges.

\subsection{Implementation Details}
In our experiment, the output channels of convolution layers in the $\textsl{Style Encoder}$ and $\textsl{Content Encoder}$ are 1, 2, 4, 8, 8, 8, 8, 8 times of $C$ respectively, where $C$=64. And for the $\textsl{Mixer}$, we set $R$=$B$=$K$ in our implementation. The output channels of the first seven deconvolution layers in $\textsl{Decoder}$ are 8, 8, 8, 8, 4, 2, 1 times of $C$ respectively. We set the initial learning rate as 0.0002 and train the model end-to-end with the Adam optimization method until the output is stable.

In each experiment, we first randomly sample $N_{t}$ target images with known content and known styles as training examples. We then construct the two reference sets for each target image by randomly sampling $r$ images of the corresponding style/content. Figure~\ref{fig:train} provides an illustration of target images selection and reference set construction. Each row represents one style and each column represents a content. The target images are represented by randomly scattered red ``x" marks. The reference images for the target image are selected from corresponding style/content, shown as the orange circles for the style reference images and green circles for content reference images. When testing, taking D4 as an example, each target image in D4 can be generated with $r$ style/content reference images. The style reference images can be randomly sampled from images with target style in D3 and the content reference images are randomly sampled from images with target content in D2.

\begin{figure}[!t]
\centering
\setlength{\abovecaptionskip}{-15pt}
\hspace{-7pt}
\subfigure{
\begin{minipage}{0.24\textwidth}{\vspace{-5pt}
\begin{minipage}{0.12\textwidth}TG:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-10s-10c-test1-24-targets.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O1:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-5s-5c-test1-24-outputs.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O2:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-10s-10c-test1-24-outputs.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O3:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-15s-15c-test1-24-outputs.png}
\end{minipage}
\vspace{3pt}\\
\begin{minipage}{0.12\textwidth}TG:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-10s-10c-test1-37-targets.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O1:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-5s-5c-test1-37-outputs.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O2:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-10s-10c-test1-37-outputs.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O3:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-15s-15c-test1-37-outputs.png}
\end{minipage}
\unskip\ \hrule\
\\
\begin{minipage}{0.12\textwidth}TG:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-10s-10c-test3-16-targets.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O1:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-5s-5c-test3-16-outputs.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O2:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-10s-10c-test3-16-outputs.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O3:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-15s-15c-test3-16-outputs.png}
\end{minipage}
\vspace{3pt}\\
\begin{minipage}{0.12\textwidth}TG:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-10s-10c-test3-123-targets.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O1:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-5s-5c-test3-123-outputs.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O2:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-10s-10c-test3-123-outputs.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O3:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-15s-15c-test3-123-outputs.png}
\end{minipage}
}
\end{minipage}
}
\hspace{1pt}
\unskip\ \vrule\
\hspace{-3pt}
\subfigure{
\begin{minipage}{0.21\textwidth}{\vspace{-5pt}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-10s-10c-test2-24-targets.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-5s-5c-test2-24-outputs.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-10s-10c-test2-24-outputs.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-15s-15c-test2-24-outputs.png}\vspace{3pt}\\
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-10s-10c-test2-37-targets.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-5s-5c-test2-37-outputs.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-10s-10c-test2-37-outputs.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-15s-15c-test2-37-outputs.png}
\unskip\ \hrule\
\\
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-10s-10c-test4-16-targets.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-5s-5c-test4-16-outputs.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-10s-10c-test4-16-outputs.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-15s-15c-test4-16-outputs.png}\vspace{3pt}\\
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-10s-10c-test4-123-targets.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-5s-5c-test4-123-outputs.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-10s-10c-test4-123-outputs.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_ref_num-15s-15c-test4-123-outputs.png}

}
\end{minipage}
}
\caption{The impact of the number of reference images on the generation of images in $D_1$, $D_2$, $D_3$, $D_4$, respectively (from upper left to lower right). TG: Target image, O1: Output for $r$=5, O2: Output for $r$=10, O3: Output for $r$=15. In all cases, $N_{t}$=300k.}
\vspace{-15pt}
\label{fig:ref-num}
\end{figure}

\subsection{Experimental Results}

In this section, we present the experimental results. First, we analyze the influence of some factors influencing the model performance. Then, we validate the separation of style and content. Finally, we compare the proposed method with some baseline networks to prove the effectiveness of our method.

\subsubsection{Influence of the Training Set Size }
To evaluate the influence of the training set size on style transfer, we conduct experiments for $N_{t}$=20k, 50k, 100k, 300k and 500k. The generation results for $D_{1}$, $D_{2}$, $D_{3}$ and $D_{4}$ are shown in Figure~\ref{fig:train-size}. As we can see, the larger the training set, the better the performance, which is consistent with our intuition. The generated images with $N_{t}$=300k and 500k are clearly better than images generated with $N_{t}$=20k, 50k and 100k. Besides, the performance of $N_{t}$=300k and $N_{t}$=500k is close which implies that with more training images, the network performance tends to be saturated and $N_{t}$=300k is enough for good results. Therefore, we take $N_{t}$=300k for the following experiments.

\begin{figure}[!tpb]
\centering
\setlength{\abovecaptionskip}{-10pt}
\hspace{-7pt}
\subfigure{
\begin{minipage}{0.24\textwidth}{\vspace{-5pt}
\begin{minipage}{0.12\textwidth}TG:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_connection-connection-test1-16-targets.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O1:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_connection-no_connection-test1-16-outputs.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O2:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_connection-connection-test1-16-outputs.png}
\end{minipage}
\vspace{3pt}\\
\begin{minipage}{0.12\textwidth}TG:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_connection-connection-test1-232-targets.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O1:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_connection-no_connection-test1-232-outputs.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O2:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_connection-connection-test1-232-outputs.png}
\end{minipage}
\unskip\ \hrule\
\\
\begin{minipage}{0.12\textwidth}TG:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_connection-connection-test3-58-targets.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O1:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_connection-no_connection-test3-58-outputs.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O2:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_connection-connection-test3-58-outputs.png}
\end{minipage}
\vspace{3pt}\\
\begin{minipage}{0.12\textwidth}TG:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_connection-connection-test3-197-targets.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O1:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_connection-no_connection-test3-197-outputs.png}
\end{minipage}\\
\begin{minipage}{0.12\textwidth}O2:\end{minipage}
\begin{minipage}{0.15\textwidth}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_connection-connection-test3-197-outputs.png}
\end{minipage}
}
\end{minipage}
}
\hspace{1pt}
\unskip\ \vrule\
\hspace{-3pt}
\subfigure{
\begin{minipage}{0.21\textwidth}{\vspace{-5pt}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_connection-connection-test2-16-targets.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_connection-no_connection-test2-16-outputs.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_connection-connection-test2-16-outputs.png}\vspace{3pt}\\
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_connection-connection-test2-232-targets.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_connection-no_connection-test2-232-outputs.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_connection-connection-test2-232-outputs.png}
\unskip\ \hrule\
\vspace{2pt}
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_connection-connection-test4-58-targets.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_connection-no_connection-test4-58-outputs.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_connection-connection-test4-58-outputs.png}\vspace{3pt}\\
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_connection-connection-test4-197-targets.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_connection-no_connection-test4-197-outputs.png}\\
\includegraphics[width=1.5in,height=0.21in]{results_300000-comparison_connection-connection-test4-197-outputs.png}

}
\end{minipage}
}
\caption{The impact of the skip-connection on generation of images in $D_1$, $D_2$, $D_3$, $D_4$, respectively (from upper left to lower right). TG is the target image, O1 and O2 are outputs of models without and with skip-connection. In all cases $N_{t}$=300k, $r$=10.}
\vspace{-18pt}
\label{fig:connection}
\end{figure}

\subsubsection{Influence of the Reference Set Size}
In addition, we conduct experiments with different number of reference images. Figure~\ref{fig:ref-num} displays the image generation results of $N_{t}$=300k with $r$=5, $r$=10 and $r$=15 respectively. From the figure, we can observe that with more reference images, characters are generated better in details. Besides, characters generated with $r$=5 are overall okay, meaning that our model can generalize to novel styles using only a few reference images. The generation results of $r$=10 and $r$=15 are close, therefore we take $r$=10 in our other experiments. Intuitively, more reference images will support more information about strokes and styles of characters and the common points in the reference sets will be more obvious. Therefore, given $r>1$, our model can achieve co-learning of images with the same style/content. Moreover, with $r>1$ we can learn more images at once which will improve the efficiency but if we split the $<$r, r, 1$>$ triplets to be $r^2$ $<$1, 1, 1$>$ triplets, the time will increase nearly $r^2$ times under the same condition.

\subsubsection{Effect of the Skip-connection}

To evaluate the effectiveness of the skip-connection during image generation, we compare the results with and without skip-connection in Figure~\ref{fig:connection}. As shown in the figure, images in $D_1$ are generated best, next is $D_3$ and last is $D_2$ and $D_4$, which conforms to the difficulty level and indicates that novel contents are more challenging to extract than novel styles. For known contents, models with and without skip-connection perform closely but for novel contents, images generated with skip-connection are much better in details. Besides, the model without skip-connection may generate images of novel characters to be similar characters which it has seen before. This is because the structure of novel characters is more challenging to extract and the structure information losing during down-sampling will lead the model to generate blurry even wrong characters. However, with content skip-connection, the location and structure information lost will be recaptured by the $\textsl{Decoder}$ network.

\begin{figure}[!t]
\centering
\setlength{\abovecaptionskip}{-10pt}
\includegraphics[height=1.7in,width=3.3in]{style_val.pdf}
\caption{Validation of pure style extraction. CR: the content reference set, TG: the target image, O1, O2 and O3 are generated by CR and three different style reference sets SR1, SR2 and SR3.}
\vspace{-10pt}
\label{fig:vali-style}
\end{figure}

\begin{figure}[!t]
\centering
\setlength{\abovecaptionskip}{-2pt}
\includegraphics[height=1.7in,width=3.3in]{content_val.pdf}
\caption{Validation of pure content extraction. SR: the style reference set, TG: the target image, O1, O2 and O3 are generated using SR but three different content reference sets CR1, CR2 and CR3.}
\vspace{-15pt}
\label{fig:vali-content}
\end{figure}

\begin{figure*}[!t]
\centering
\setlength{\abovecaptionskip}{-15pt}
\hspace{-20pt}
\subfigure{
\begin{minipage}{0.42\textwidth}{\vspace{-10pt}
\begin{minipage}{0.17\textwidth}Source:\end{minipage}
\begin{minipage}{0.38\textwidth}
\includegraphics[width=2.4in,height=0.25in]{comparison_baselines-source-source3.png}
\end{minipage}\\
\begin{minipage}{0.17\textwidth}Pix2pix:\end{minipage}
\begin{minipage}{0.38\textwidth}
\includegraphics[width=2.4in,height=0.25in]{comparison_baselines-pixtopix-500-area2-373_generate.png}
\end{minipage}\\
\begin{minipage}{0.17\textwidth}AEGN:\end{minipage}
\begin{minipage}{0.38\textwidth}
\includegraphics[width=2.4in,height=0.25in]{comparison_baselines-calligraphy-500-area2-373_generate.png}
\end{minipage}\\
\begin{minipage}{0.17\textwidth}Zitozi:\end{minipage}
\begin{minipage}{0.38\textwidth}
\includegraphics[width=2.4in,height=0.25in]{comparison_baselines-zitozi-500-area2-373_generate.png}
\end{minipage}\\
\begin{minipage}{0.17\textwidth}C-GAN:\end{minipage}
\begin{minipage}{0.38\textwidth}
\includegraphics[width=2.4in,height=0.25in]{comparison_baselines-cyclegan-500-area2-373_generate.png}
\end{minipage}\\
\begin{minipage}{0.17\textwidth}EMD:\end{minipage}
\begin{minipage}{0.38\textwidth}
\includegraphics[width=2.4in,height=0.25in]{comparison_baselines-my-area2-373-outputs.png}
\end{minipage}\\
\begin{minipage}{0.17\textwidth}Target:\end{minipage}
\begin{minipage}{0.38\textwidth}
\includegraphics[width=2.4in,height=0.25in]{comparison_baselines-my-area2-373-targets.png}
\end{minipage}
}
\end{minipage}
\unskip\ \vrule\
\begin{minipage}{0.35\textwidth}{\vspace{-5pt}
\begin{minipage}{0.38\textwidth}
\includegraphics[width=2.4in,height=0.25in]{comparison_baselines-source-source1.png}
\end{minipage}\\
\begin{minipage}{0.38\textwidth}
\includegraphics[width=2.4in,height=0.25in]{comparison_baselines-pixtopix-500-area2-277_generate.png}
\end{minipage}\\
\begin{minipage}{0.38\textwidth}
\includegraphics[width=2.4in,height=0.25in]{comparison_baselines-calligraphy-500-area2-277_generate.png}
\end{minipage}\\
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.4in,height=0.25in]{comparison_baselines-zitozi-500-area2-277_generate.png}
\end{minipage}\\
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.4in,height=0.25in]{comparison_baselines-cyclegan-500-area2-277_generate.png}
\end{minipage}\\
\begin{minipage}{0.35\textwidth}
\includegraphics[width=2.4in,height=0.25in]{comparison_baselines-my-area2-277-outputs.png}
\end{minipage}\\
\begin{minipage}{0.35\textwidth}
\includegraphics[width=2.4in,height=0.25in]{comparison_baselines-my-area2-277-targets.png}
\end{minipage}\\
}
\end{minipage}
\unskip\ \vrule\
\begin{minipage}{0.45\textwidth}{\vspace{-15pt}
\begin{minipage}{0.15\textwidth}L1 loss\end{minipage}
\begin{minipage}{0.15\textwidth}RMSE\end{minipage}
\begin{minipage}{0.15\textwidth}PDAR\end{minipage}\vspace{7pt}\\
\begin{minipage}{0.15\textwidth}0.0105\end{minipage}
\begin{minipage}{0.15\textwidth}0.0202\end{minipage}
\begin{minipage}{0.15\textwidth}0.17\end{minipage}\vspace{7pt}\\
\begin{minipage}{0.15\textwidth}0.0112\end{minipage}
\begin{minipage}{0.15\textwidth}0.0202\end{minipage}
\begin{minipage}{0.15\textwidth}0.3001\end{minipage}\vspace{7pt}\\
\begin{minipage}{0.15\textwidth}0.0091\end{minipage}
\begin{minipage}{0.15\textwidth}\textbf{0.0184}\end{minipage}
\begin{minipage}{0.15\textwidth}0.1659\end{minipage}\vspace{7pt}\\
\begin{minipage}{0.15\textwidth}0.0112\end{minipage}
\begin{minipage}{0.15\textwidth}0.02\end{minipage}
\begin{minipage}{0.15\textwidth}0.3685\end{minipage}\vspace{7pt}\\
\begin{minipage}{0.15\textwidth}\textbf{0.0087}\end{minipage}
\begin{minipage}{0.15\textwidth}\textbf{0.0184}\end{minipage}
\begin{minipage}{0.15\textwidth}\textbf{0.1332}\end{minipage}\\
}
\end{minipage}
}
\vspace{-10pt}
\caption{Comparison of image generation for known styles and novel contents. Equal number of image pairs with source and target styles are used to train the baselines.}
\label{fig:com-area2}
\vspace{-15pt}
\end{figure*}

\subsubsection{Validation of Style and Content Separation}

Separating style and content is the key feature of the proposed {\em EMD} model. To validate the clear separation of style and content, we combine one content representation with style representations from a few disjoint style reference sets for one style and check whether the generated images are the same. For better validation, the content reference sets and style reference sets are all for novel styles and contents and we generate images with novel style and novel content. Similarly, we combine one style representation with content representations from a few disjoint content reference sets. The results are displayed in Figure~\ref{fig:vali-style} and Figure~\ref{fig:vali-content}, respectively. As shown in Figure~\ref{fig:vali-style}, the generated O1, O2 and O3 are similar though the style reference sets used are different, demonstrating that the $\textsl{Style Encoder}$ extracts accurate style representations since the only one thing the three style reference sets share is the style. Similar results can be found in Figure~\ref{fig:vali-content}, showing that the $\textsl{Content Encoder}$ extracts accurate content representations.

\subsubsection{Comparison with Baseline Methods}
In this subsection, we compare our method with the following baselines for character style transfer.
\begin{itemize}
    \item Pix2pix~\cite{isola}: Pix2pix is a conditional GAN based image translation network, which also adopts the skip-connection to connect encoder and decoder. Pix2pix is optimized by L1 distance loss and adversarial loss.
 \item Auto-encoder guided GAN (AEGN)~\cite{lyu}: AEGN consists of two encoder-decoder networks, one for image transfer and another acting as an auto-encoder to guide the transfer to learn detailed stroke information.
\item Zi-to-zi~\cite{zitozi}: Zi-to-zi is proposed for Chinese typeface transfer which is based on the encoder-decoder architecture followed by a discriminator. In discriminator, there are two fully connected layers to predict the real/fake and the style category respectively.
\item CycleGAN (C-GAN)~\cite{Zhu2017}: CycleGAN consists of two mapping networks which translate images from style A to B and from style B to A, respectively and construct a cycle process.
\end{itemize}

\begin{figure*}[!t]
\centering
\setlength{\abovecaptionskip}{-10pt}
\hspace{-20pt}
\subfigure{
\begin{minipage}{0.45\textwidth}{
\begin{minipage}{0.26\textwidth}Source:\end{minipage}
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-source-source2.png}
\end{minipage}\\
\begin{minipage}{0.26\textwidth}Pix2pix-300:\end{minipage}
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-pixtopix-300-166_generate.png}
\end{minipage}\\
\begin{minipage}{0.26\textwidth}Pix2pix-500:\end{minipage}
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-pixtopix-500-area4-166_generate.png}
\end{minipage}\\
\begin{minipage}{0.26\textwidth}Pix2pix-1299:\end{minipage}
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-pixtopix-1299-166_generate.png}
\end{minipage}\\
\begin{minipage}{0.26\textwidth}AEGN-300:\end{minipage}
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-calligraphy-300-166_generate.png}
\end{minipage}\\
\begin{minipage}{0.26\textwidth}AEGN-500:\end{minipage}
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-calligraphy-500-area4-166_generate.png}
\end{minipage}\\
\begin{minipage}{0.26\textwidth}AEGN-1299:\end{minipage}
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-calligraphy-1299-166_generate.png}
\end{minipage}\\
\begin{minipage}{0.26\textwidth}Zitozi-300:\end{minipage}
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-zitozi-300-166_generate.png}
\end{minipage}\\
\begin{minipage}{0.26\textwidth}Zitozi-500:\end{minipage}
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-zitozi-500-area4-166_generate.png}
\end{minipage}\\
\begin{minipage}{0.26\textwidth}Zitozi-1299:\end{minipage}
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-zitozi-1299-166_generate.png}
\end{minipage}\\
\begin{minipage}{0.26\textwidth}C-GAN-300:\end{minipage}
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-cyclegan-300-166_generate.png}
\end{minipage}\\
\begin{minipage}{0.26\textwidth}C-GAN-500:\end{minipage}
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-cyclegan-500-area4-166_generate.png}
\end{minipage}\\
\begin{minipage}{0.26\textwidth}C-GAN-1299:\end{minipage}
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-cyclegan-1299-166_generate.png}
\end{minipage}\\
\begin{minipage}{0.26\textwidth}EMD-10:\end{minipage}
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-my-area4-166-outputs.png}
\end{minipage}\\
\begin{minipage}{0.26\textwidth}Target:\end{minipage}
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-my-area4-166-targets.png}
\end{minipage}\\
}
\end{minipage}
\unskip\ \vrule\
\begin{minipage}{0.33\textwidth}{\vspace{-5pt}
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-source-source4.png}
\end{minipage}\\
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-pixtopix-300-14_generate.png}
\end{minipage}\\
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-pixtopix-500-area4-14_generate.png}
\end{minipage}\\
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-pixtopix-1299-14_generate.png}
\end{minipage}\\
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-calligraphy-300-14_generate.png}
\end{minipage}\\
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-calligraphy-500-area4-14_generate.png}
\end{minipage}\\
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-calligraphy-1299-14_generate.png}
\end{minipage}\\
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-zitozi-300-14_generate.png}
\end{minipage}\\
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-zitozi-500-area4-14_generate.png}
\end{minipage}\\
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-zitozi-1299-14_generate.png}
\end{minipage}\\
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-cyclegan-300-14_generate.png}
\end{minipage}\\
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-cyclegan-500-area4-14_generate.png}
\end{minipage}\\
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-cyclegan-1299-14_generate.png}
\end{minipage}\\
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-my-area4-14-outputs.png}
\end{minipage}\\
\begin{minipage}{0.44\textwidth}
\includegraphics[width=2.3in,height=0.25in]{comparison_baselines-my-area4-14-targets.png}
\end{minipage}
}
\end{minipage}
\unskip\ \vrule\
\begin{minipage}{0.40\textwidth}{\vspace{-22pt}
\begin{minipage}{0.15\textwidth}L1 loss\end{minipage}
\begin{minipage}{0.15\textwidth}RMSE\end{minipage}
\begin{minipage}{0.15\textwidth}PDAR\end{minipage}\vspace{7pt}\\
\begin{minipage}{0.15\textwidth}0.0109\end{minipage}
\begin{minipage}{0.15\textwidth}0.0206\end{minipage}
\begin{minipage}{0.15\textwidth}0.1798\end{minipage}\vspace{7pt}\\
\begin{minipage}{0.15\textwidth}0.0106\end{minipage}
\begin{minipage}{0.15\textwidth}0.0202\end{minipage}
\begin{minipage}{0.15\textwidth}0.1765\end{minipage}\vspace{7pt}\\
\begin{minipage}{0.15\textwidth}0.01\end{minipage}
\begin{minipage}{0.15\textwidth}0.0196\end{minipage}
\begin{minipage}{0.15\textwidth}0.1531\end{minipage}\vspace{7pt}\\
\begin{minipage}{0.15\textwidth}0.0117\end{minipage}
\begin{minipage}{0.15\textwidth}0.02\end{minipage}
\begin{minipage}{0.15\textwidth}0.3951\end{minipage}\vspace{7pt}\\
\begin{minipage}{0.15\textwidth}0.0108\end{minipage}
\begin{minipage}{0.15\textwidth}0.02\end{minipage}
\begin{minipage}{0.15\textwidth}0.2727\end{minipage}\vspace{7pt}\\
\begin{minipage}{0.15\textwidth}0.0105\end{minipage}
\begin{minipage}{0.15\textwidth}0.0196\end{minipage}
\begin{minipage}{0.15\textwidth}0.26\end{minipage}\vspace{7pt}\\
\begin{minipage}{0.15\textwidth}0.0091\end{minipage}
\begin{minipage}{0.15\textwidth}0.0187\end{minipage}
\begin{minipage}{0.15\textwidth}0.1612\end{minipage}\vspace{7pt}\\
\begin{minipage}{0.15\textwidth}\textbf{0.009}\end{minipage}
\begin{minipage}{0.15\textwidth}0.0185\end{minipage}
\begin{minipage}{0.15\textwidth}0.1599\end{minipage}\vspace{7pt}\\
\begin{minipage}{0.15\textwidth}\textbf{0.009}\end{minipage}
\begin{minipage}{0.15\textwidth}\textbf{0.0183}\end{minipage}
\begin{minipage}{0.15\textwidth}0.1624\end{minipage}\vspace{7pt}\\
\begin{minipage}{0.15\textwidth}0.0143\end{minipage}
\begin{minipage}{0.15\textwidth}0.0215\end{minipage}
\begin{minipage}{0.15\textwidth}0.5479\end{minipage}\vspace{7pt}\\
\begin{minipage}{0.15\textwidth}0.0126\end{minipage}
\begin{minipage}{0.15\textwidth}0.0203\end{minipage}
\begin{minipage}{0.15\textwidth}0.4925\end{minipage}\vspace{7pt}\\
\begin{minipage}{0.15\textwidth}0.0128\end{minipage}
\begin{minipage}{0.15\textwidth}0.0203\end{minipage}
\begin{minipage}{0.15\textwidth}0.4885\end{minipage}\vspace{7pt}\\
\begin{minipage}{0.15\textwidth}\textbf{0.009}\end{minipage}
\begin{minipage}{0.15\textwidth}0.0186\end{minipage}
\begin{minipage}{0.15\textwidth}\textbf{0.1389}\end{minipage}
}

\end{minipage}
}
\vspace{-10pt}
\caption{Comparison of image generation for novel styles and contents given $r$=10. The baseline methods are trained with 300, 500, 1299 image pairs respectively.}
\vspace{-15pt}
\label{fig:com-area4}
\end{figure*}

For comparison, we use the font Song as the source font which is simple and commonly used and transfer it to target fonts. Our model is trained with $N_{t}$=300k and $r$=10 and as an average, we use less than 500 images for each style. We compare our method with baselines on generating images with known styles and novel styles, respectively. For novel style, the baselines is re-trained from scratch.

\textbf{Known styles as target style.} Taking known styles as the target style, baselines are trained using the same number of paired images as the images our model used for the target style. The results are displayed in Figure~\ref{fig:com-area2} where CycleGAN is denoted as C-GAN for simplicity. We can observe that for known styles and novel contents, our method performs much better than pix2pix, AEGN and CycleGAN and close to or a little better than zi-to-zi. This is because pix2pix and AEGN usually need more samples to learn a style as Lyu did in~\cite{lyu}. CycleGAN performs poorly and it only generates part of characters or some strokes, which may be because it learns the domain mappings and without the domain knowledge, it may perform poorly. Zitozi performs well since it learns multiple styles at the same time and the contrast among different styles helps the model learn styles better.

For quantification analysis, we calculate the L1 loss, Root Mean Square Error (RMSE) and the Pixel Disagreement Ratio (PDAR)~\cite{Zhu2017} between generated images and target images. PDAR is the number of pixels with different values in the two images divided by the total image size after image binaryzation. We conduct experiments for 10 randomly sampled styles and the average results are displayed at the last three columns in Figure~\ref{fig:com-area2} and the best performance is bold. We can observe that our method performs best and achieves the lowest L1 loss, RMSE and PDAR.

\textbf{Novel styles as target style.} Taking novel styles as the target style, we test our model to generate images of novel styles and contents given $r$=10 style/content reference images without retraining. As for baselines, retraining is needed. Here, we conduct two experiments for baselines. One is that we first pretrain a model for each baseline method using the training set our method used and then fine-tune the pretrained model with the same 10 reference images as our method used. The results show that all baseline methods preform poorly and it is unfeasible to learn a style by fine-tuning on only 10 reference images. Thus, we omit the experiment results here.

The other setting is training the baseline model from scratch. Since it is unrealistic to train baseline models with only 10 samples, we train them using 300, 500, 1299 images of the target style respectively. Here we use 1299 is because the number of train contents is 1299 in our data set. The results are presented in Figure~\ref{fig:com-area4}. As shown in the figure, the proposed {\em EMD} model can generalize to novel styles from only 10 style reference images but other methods need to be retrained with more samples. The pix2pix, AEGN and CycleGAN perform worst even learned on all 1299 training images, which demonstrates that these three methods are not effective for character style transfer especially when the training data are not enough. With only 10 style reference images, our model performs better than zi-to-zi-300 namely zi-to-zi model learned with 300 examples for each style, close to zi-to-zi-500 and a little worse than zi-to-zi-1299. This may be because zi-to-zi learns multiple styles at the same time and learning with style contrast helps model learning better.

The quantitative comparison results including L1 loss, RMSE and PDAR are shown at the last three columns of Figure~\ref{fig:com-area4} and we can observe that though given only 10 style reference images, our method performs better than all pix2pix, AEGN and CycleGAN models and zi-to-zi-300, and close to zi-to-zi-500 and zi-to-zi-1299, which demonstrates the effectiveness of our method.

In conclusion, these baseline methods require many images of source styles and target styles to learn, which may hard to collect for some styles. Besides, the learned baseline model can only transfer styles appearing in train set and for new styles, they have to be retrained which is time-consuming. But our method can generalize to novel styles given only a few reference images. In addition, baseline models can only use images of target styles. However, since the proposed {\em EMD} model learns feature representations instead of transformation among specific styles, it can leverage images of any styles and make the most of existing data.

\section{Conclusion and Future Work}
In this paper, we propose a generalized style transfer network named {\em EMD} which could generate images with new styles and contents given only a few style and content reference images. The main idea is that from these reference images, the $\textsl{Style Encoder}$ and $\textsl{Content Encoder}$ could extract style and content representations, respectively. Then the extracted style and content representations will be mixed by a $\textsl{Mixer}$ to generate images with target styles and contents. To separate style and content, we leverage the conditional dependence of styles and contents given an image. This learning framework allows simultaneous style transfer among multiple styles and can be deemed as a special `multi-task' learning scenario. Then the learned encoders and mixer will be taken as the shared knowledge and transferred to new styles and contents. We evaluate the proposed method on Chinese Typeface transfer task and extensive experiments demonstrate its effectiveness.

In our study, the learning process consists of a series of image generation tasks and we try to learn a model which can generalize to novel but related tasks by learning a high-level strategy, namely learning the feature representations. This resembles to ``learning-to-learn" program. In the future, we will explore more about ``learning-to-learn" and integrate it with our framework.

\section*{Acknowledgment}
The work is partially supported by the High Technology Research and Development Program of China 2015AA015801, NSFC 61521062, STCSM 15DZ2270400.

{\small
\bibliographystyle{ieee}