## 2 Triplet Ordinal Cross Entropy Hashing
### Triplet Ordinal Tensor Graph  
To learn the triplet ordinal relation preserving hashing functions, the first problem is how to efficiently compute the probability distribution of the triplet ordinal relation among the training set in the original space. \begin{table}
\begin{tabular}{c c} \hline \hline
**Notation** & **Description** \\ \hline \(B\) & Compact binary code matrix \\ \(B_{i}\), \(B_{j}\), \(B_{k}\) & The \(i\)-th, \(j\)-th, \(k\)-th column in B \\ \(H(\cdot)\) & Hashing function \\ \(X\) & Data matrix in the Euclidean space \\ \(x_{i}\), \(x_{j}\), \(x_{k}\) & The \(i\)-th, \(j\)-th, \(k\)-th column in \(X\) \\ \(\hat{G}\) & Triplet ordinal graph in the Euclidean space \\ \(\hat{G}\) & Triplet ordinal relation in the Hamming space \\ \(g_{ik}\) & The entry \((i,j,k)\) in G \\ \(\hat{S}\) & Similarity graph \\ \(D\)S & Dissimilarity graph \\ \(N\) & The number of training samples \\ \(L\) & The number of k-means centers \\ \(P(\cdot)\) & Probability distribution function \\ \(d_{h}(\cdot\cdot)\) & Hamming distance function \\ \(M\) & Binary code length \\ \(\mathbf{1}\) & The binary matrix with all values of 1 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The important notations used in this paper. Generally, we select the triplet data (\(x_{i}\), \(x_{j}\), \(x_{k}\)) from the training set to compute their ordinal relation, where the data pair (\(x_{i},x_{j}\)) has a small Euclidean distance value and (\(x_{j}\), \(x_{k}\)) is considered as the dissimilar data pair. However, this mechanism needs to randomly select triplet samples and compare the distance values among all data points. It has a high time complexity and costly memory. Furthermore, it is difficult to define the similar and dissimilar data pairs for the problem without supervised information. In this paper, to solve the above problem, we employ a tensor ordinal graph \(G\) to represent the ordinal relation among the triplet images (\(x_{i}\), \(x_{j}\), \(x_{k}\)). We establish the tensor ordinal graph \(G\) by tensor production and each entry in \(G\) is calculated as \(G(\hat{ij},jk)=S(i,j)\cdot DS(j,k)\). \(S(i,j)\) is the similarity graph as defined in Equation (3). A larger value of \(S(i,j)\) means the data pair (\(x_{i}\), \(x_{j}\)) is more similar. \(DS(i,j)\) is the dissimilarity graph and its value is calculated as \(DS(i,j)=1/S(i,j)\). \[S(i,j)= \begin{cases}0,&i=j\\ e^{-||x_{i}-x_{j}||_{2}^{2}/2\sigma^{2}},&\text{otherwise}\end{cases}  \tag{3}\]  
We further process \(G\) to obey the binary distribution as in Equation (4). \(g_{ijk}\) is the entry of \(G(i,j,k)\). \[ \begin{cases}g_{ijk}=1,&G(i,j,k)>1\\ g_{ijk}=0,&G(i,j,k)\leq 1\end{cases}  \tag{4}\]  
Given \(N\) training samples, the size of the similarity graph and dissimilarity graph is \(N\times N\). The tensor product of the two graphs is shown in Figure 2, and its size is \(N^{2}\times N^{2}\). However, the proposed TOCEH only concerns the relative similarity relationship among the data pairs (\(x_{i}\), \(x_{j}\)) and (\(x_{j}\), \(x_{k}\)). The corresponding elements are marked blue. There are \(N\) rectangles and each rectangle contains \(N\times N\) elements. We pick up these elements and restore them into a matrix with the size of \(N\times N\times N\). Finally, the ordinal relation among any triplet items can be represented by the triplet ordinal graph G, as defined in Equation (5). \[ \begin{cases}S(i,j)>S(k,j),&g_{ijk}=1\\ S(i,j)\leq S(k,j),&g_{ijk}=0\end{cases}  \tag{5}\]  
To illustrate the cases defined in Equation (5), a simple explanation is provided below. For the triplet item (\(x_{i}\), \(x_{j}\), \(x_{k}\)), the value of the (\(j\), \(k\))-th entry is \(G(\hat{ij},k)=S(i,j)\cdot DS(k,j)=S(i,j)/S(k,j)\). If the triplet ordinal relation is \(S(i,j)>S(k,j)\), we have \(G(\hat{ij},k)>1\) and \(g_{ijk}=1\); otherwise,  
Figure 2: The marked elements are picked up to restore in a matrix with the size of \(N\times N\times N\). we have \(G(ij,kj)\leq 1\) and \(g_{ijk}=0\).