Binary Representation via Jointly Personalized Sparse Hashing

In the following, we use bold uppercase letters (e.g. $Z$) for matrices, bold lowercase letters (e.g. $z$) for vectors, and normal lowercase letters (e.g. z) for scalars. If there are no special instructions, we define the $i$-th row of the matrix $Z$ as $Z_{i\ast }$, the $j$-th column of the matrix $Z$ as $Z_{\ast j}$, the $i$-th element of $Z_{\ast j}$ or the $j$-th element of $Z_{i\ast }$ as $Z_{ij}$. We also denote the transpose of the matrix $Z$ as $Z^T$, and the trace of the matrix $Z$ as $tr\left(Z\right)$ if it is a square matrix. $\parallel Z{\parallel }_2$, $\parallel Z{\parallel }_{2,1}$, and $\parallel Z{\parallel }_F$ represent the $l_2$-norm, $l_{2,1}$-norm, and Frobenius norm of the matrix $Z$, respectively. $Z\otimes H$ denotes the Kronecker product between matrices $Z$ and $H$. In this paper, the training set is denoted as $X=\{x_i{\}}_{i=1}^n$, $x_i\in R^d$, where $n$ is the number of training samples, and $d$ is the dimension of features. The binary codes $B=\{b_i{\}}_{i=1}^m$, $b_i\in R^l$, where $l\ll d$, $l$ is the length of bits, and $m\ll n$, $m$ is the number of anchor points. $I$ is the identity matrix with the size of $l$-by-$l$.

SH (Weiss et al., 2008) aims to extract the discriminative information from the original space to learn binary codes based on the graph theory. With this objective, it minimizes the errors of binary codes between instances with Laplacian graph as follows:

where $l\in R^{1\times l}$ is an all-ones vector, $M_{ij}=exp(-\parallel x_i-x_j{\parallel }^2/{\eta }^2)$, $M\in R^{n\times n}$ is the affinity matrix, $\eta$ is a pre-defined parameter, and $H=\{h_i{\}}_{i=1}^n,h_i\in R^l$ is binary codes of the $i$-th training sample. It is time-consuming to compute $M$ for large-scale datasets. In addition, the information loss between low-dimensional features and binary codes will increase due to the binarization operation.

To reduce the computational complexity in Eq. (1), AGH (Liu et al., 2011) designs a truncated similarity matrix $A\in R^{n\times m}$ between all $n$ instances and $m$ anchor points. The $i$-th element of $A_{\ast j}$ is defined as:

where $c_j\in R^d$ is the $j$-th anchor point; $\left\{i\right\}$ is the index set of $k$ neighboring anchor points of $x_i$, and $\theta$ is a pre-defined parameter. Although AGH has the linear training time for the developed model, it still fails to control the information loss between low-dimensional features and binary codes in the binary representation learning.

To minimize the information loss between low-dimensional feature vectors and binary codes, JSH (Lai et al., 2018) presents $l_{2,1}$-regularized regression formulation, and the objective function can be defined as follows:

where $\alpha$ is the balance parameter, $W\in R^{d\times l}$ is the pairwise weight matrix; $V\in R^{l\times l}$ is the rotation matrix. Although JSH effectively handles the pairwise projection from a high-dimensional space to the Hamming space, the semantics of instances are unknown and motivate our work reported in this paper.

The semantic structure can reflect the intrinsic geometric relationship across different data points within a specific category. The proposed PSH thinks that instances with similar semantic structures should be adaptively projected to the same Hamming space, and vice versa, as shown in Figure 1 (b). For this purpose, one simple yet effective way is to build different personalized subspaces (Weinberger et al., 2009) to capture different semantic structures. Retrieving label information is an expensive process in terms of time, labor and human expertise, and we define semantic structures in a high-dimensional space by pseudo labels produced by K-means. The instances with similar semantic information likely share the same anchor point. Therefore, we derive a set of anchor points $C=\{c_j{\}}_{j=1}^m$ as the training set of PSH and obtaining the following objective function:

where $P_j\in R^{d\times l}$ is a personalized weight matrix for the anchor point $c_j$ and $P=[P_1;P_2;\dots ;P_m]\in R^{md\times l}$. $R\in R^{l\times l}$ is a rotation matrix to minimize quantization errors, driven by ITQ (Gong et al., 2012).

Since the binarization operation for low-dimensional features $R{P}_j^T{c}_j$ and binary codes $b_j$ helps increase the information loss, we consider using the feature sparsity for personalized weight $P_j$ to select important features. Exclusive group lasso (EGL) (Kong et al., 2014, 2016) encourages intra-cluster competition but discourages inter-cluster competition. Inspired by EGL we first impose a $l_{2,1}$-norm regularization on personalized weight $P_j$ for pursuing the sparsity of intra-cluster features. Then, we create a $l_2$-norm term to constrain the non-sparsity of inter-cluster features. This regularization term enables us to perform optimal feature selection for each cluster. However, moderating the personalized weight $P_j$ with a single anchor point $c_j$ may over-fit with a poor generalization ability. Therefore, we force the anchor point $c_j$ to lend certain strengths from its neighboring anchors to learn the personalized weight $P_j$, motivated by the network lasso penalty (Hallac et al., 2015). Finally, we re-write the loss function of PSH as follows:

where ${\lambda }_1$ and ${\lambda }_2$ are balance parameters, $S\in R^{m\times m}$ is the similarity matrix of anchors, and the $i$-th element of $S_{\ast j}$ is defined as follows:

where $\delta$ is a given parameter, and $N_{\psi }\left(c_i\right)$ is the index set of $\psi$ nearest neighbors of the anchor point $c_i$.

As aforementioned, the PSH model shown in Eq. (5) can effectively preserve particular attributes of each cluster from the high-dimensional space into the Hamming space. Instances within the same cluster can be projected by the same personalized weight matrix, resulting in directly maintaining the semantics of instances that correspond to intrinsic structures of data into the Hamming space.

To further improve the representation capacity of binary codes, we also hope to preserve the local neighborhood structure within the cluster in the Hamming space. To this end, we maintain the pairwise similarity via a manifold-based hashing learning method. Since JSH (Lai et al., 2018) can quantify the similarity between each instance and its neighboring anchor points, and greatly reduce the time complexity, we thereby joint Eqs. (3) and (5) to construct the Jointly Personalized Sparse Hashing (JPSH) model. The overall objective function of JPSH is defined as:

where ${\lambda }_3$ is the balance parameter for projected matrix $W$.

In the following, we will discuss how our proposed JPSH learns the binary representation and preserves discriminative information compared with other hashing methods from two aspects.

On the one hand, compared to existing manifold-based hashing methods, such as SH and JSH, our proposed JPSH not only considers local pairwise similarity in the original feature space $X$, but also the intrinsic semantic similarity of the data. In particular, Eq. (3) shows that JSH can effectively reduce the computational complexity using truncated similarity matrix $A$, and avoid information loss via $\parallel W{\parallel }_{2,1}$. Therefore, we maintain local neighborhood structures within each cluster by JSH, as the local structure information in the two clusters (purple points and blue points shown in the Figure 2 (b)). However, JSH has difficulty distinguishing instances with similar features but different semantic information. Comparing Eq. (7) against Eq. (3), we learn a set of personalized weights $P_j(j=1,2,\dots ,m)$ for different anchors $c_j(j=1,2,\dots ,m)$, and employ the $l_{2,1}$-norm sparse constraint on each $P_j$. So, instances with the same pseudo-label can be adaptively mapped to the personalized subspace through the unique projection learning of personalized weights. Therefore, the proposed JPSH can avoid misrepresenting instances of similar features with different semantics by directly retaining the semantic relationship of the original feature space.

On the other hand, compared against those multi-stage hashing methods, such as PCA-ITQ and RSSH, we construct the seamless hash objective function Eq. (7). It can avoid suboptimal solutions generated by using multiple independent learning strategies. For example, PCA-ITQ first applies PCA to perform linear dimensionality reduction, and then uses an alternating algorithm for refining the initial orthogonal transformation to reduce quantization errors. RSSH preserves semantic relationships on three subproblems: multi-subspace learning, similarity matrix construction, and semantics preserved hashing. Different from the above methods, we construct personalized weight matrix $P$, pairwise weight matrix $W$ and two rotation matrices $R$ and $V$ in the seamless formulation Eq. (7). Thus, our proposed JPSH can significantly avoid the suboptimal solution, and obtain discriminative hash codes in binary representation learning.

The optimization of Eq. (7) is intractable and non-convex w.r.t all parameters simultaneously. Therefore, we adopt an alternating optimization algorithm to iteratively update all parameters till the algorithm converges to an acceptable settlement.

Update Personalized Weight $P$: First, we update the personalized weight $P$ when $W$, $R$, $V$ and $B$ are fixed. The subproblem of Eq. (7) w.r.t $P$ is:

For the convenience, we devide Eq. (8) into three functions: $F_1\left(P\right)={\sum }_{j=1}^m\parallel b_j-R{P}_j^T{c}_j{\parallel }_2^2$, $F_2\left(P\right)={\lambda }_1{\sum }_{j=1}^m\parallel P_j{\parallel }_{2,1}^2$, $F_3\left(P\right)={\lambda }_2{\sum }_{i,j=1}^m{S}_{ij}\parallel P_i-P_j{\parallel }_F$. We denote $Y=diag(c_1,c_2,\dots ,c_m)$, and $Y\in R^{md\times m}$, where $diag(\cdot )$ is a diagonal function. Since $R{R}^T=I$, the derivative of $F_1\left(P\right)$ w.r.t $P$ can be computed as follows:

According to Refs. (Li et al., 2017a, 2018), we have the derivative of $F_2\left(P\right)$ w.r.t $P$ as follows:

where $K\in R^{md\times md}$ is a diagonal matrix, and the $i$-th diagonal element can be defined as:

where $ϵ$ is a very small constant to ensure the derivative solvable, $I(\cdot )$ is an indicator function, and $I_{ij}=1$ if $P^{i\ast }$ belongs to $P_j$, otherwise $I_{ij}=0$.

The derivative of $F_3\left(P\right)$ w.r.t. $P$ is computed as follows:

where $I_d\in R^{d\times d}$ is an identity matrix. $G\in R^{m\times m}$ is square matrix, and the $i$-th element of $G_{\ast j}$ can be expressed as:

Combining $\partial F_1\left(P\right)/\partial P$, $\partial F_2\left(P\right)/\partial P$ and $\partial F_3\left(P\right)/\partial P$ together, and setting it to be zero, we have a closed-form solution of the personalized weight $P$ as follows:

Update Pairwise Weight $W$: We attempt to update the pairwise weight $W$ when other four parameters are fixed. Removing terms that are irrelevant to $W$, we have the following function as:

According to Ref. (Lai et al., 2018), since the ${\sum }_i{A}_{ij}=1$ and $V{V}^T=I$, the term between $X$ and $X^T$ is an identity matrix. So, the closed-form solution of $W$ is:

where $Q\in R^{d\times d}$ is a diagonal matrix, and the $i$-th element of $Q_{i\ast }$ is:

where $w_{i\ast }$ is the $i$-th row of the pairwise weight $W$.

Update Rotation Matrix $R$: To compute $R$, we fix $P$, $W$, $V$ and $B$, and then solve the following maximization problem:

According to (Zou et al., 2006; Li et al., 2017b), we compute $P^{T}Y{B}^T={\hat{U}}_1{D}_1{\hat{V}}_1^T$ by Singular Value Decomposition (SVD), and the updating scheme of $R$ is described below:

Update Rotation Matrix $V$: To derive the solution of $V$, we fix the other four parameters and re-form the maximization problem as follows:

We use SVD to solve the problem $W^{T}XA{B}^T={\hat{U}}_2{D}_2{\hat{V}}_2^T$, and then retain the solution of $V$ as follows:

Update Binary Codes $B$: Finally, we update the parameter $B$ when others have been fixed and solve the optimization problem as follows:

Thus, the solution to $B$ is:

where $sgn(\cdot )$ is a sign function.

With the above handling, the pseudo codes of our proposed JPSH method is summarized in Algorithm 1.

After having optimized the overall objective function of JPSH, we perform similarity prediction based on four parameters $P$, $W$, $R$ and $V$. More specifically, for each query instance $\hat{x}$, we first find the personalized weight $P_j$ corresponding to the anchor point $c_j$ using the minimum Euclidean distance, for the query instance $\hat{x}$. Then, we joint the personalized weight $P_j$, pairwise weight $W$, and two rotation matrices $R$ and $V$ to learn discriminative binary codes $\hat{b}$, that is: $\hat{b}=sgn(R{P}_j^T{c}_j+V{W}^T\hat{x})$.

Observing $\hat{b}=sgn(R{P}_j^T{c}_j+V{W}^T\hat{x})$, we can find that each hash code $\hat{b}$ is constrained by $R{P}_j^T{c}_j$ and $V{W}^T\hat{x}$. The first term $R{P}_j^T{c}_j$ transforms the anchor $c_j$ corresponding to $\hat{x}$ by the personalized weight matrix $P_j$. Since the personalized weight matrices are different for different clusters, the hash codes $\hat{x}$ generated by the first trem have the semantic separability. From Eq. (7), we can observe that the pairwise weight matrix $W$ is produced under the constraints of pairwise similarity matrix $A$. Thus, the second trem $V{W}^T\hat{x}$ reflects the local neighborhood structures among data. Integrating the first term $R{P}_j^T{c}_j$ and the second term $V{W}^T\hat{x}$ into the program of producing $\hat{b}$, we can obtain the binary codes fused the semantic and pairwise similarities.

The proposed method and the comparative ones are evaluated on the following four datasets, and some example images of each dataset are shown in Figure 3. MNIST (LeCun et al., 1998) contains 70,000 handwritten digit images from 10 classes in total. Each image is re-shaped to a 784-dimensional feature vector. We construct the testing set by randomly selecting 100 images per class, and the remaining images are composed as the training set (Lin et al., 2018). CIFAR-10 (Krizhevsky et al., 2009) consists of 60,000 tiny images of 10 classes. Following (Hu et al., 2018), 512-dimensional GIST features (Oliva and Torralba, 2001) are retrieved. We randomly select 100 images per class to form the testing set, and the remaining 5900 images per class form the training set. NUS-WIDE (Chua et al., 2009) is a real-world dataset containing 269,648 images related to 81 ground truth concepts. We pick the most 21 frequent concepts for evaluation. For each category, 100 images are randomly sampled to form the testing set, and 100,000 images from the remaining images form the training set. 4096-dimensional CNN features (Krizhevsky et al., 2017) are firstly extracted, and then 1000-dimensional PCA features are generated to represent each image. FLICKR25K (Huiskes and Lew, 2008) is also a real-world dataset including 25,000 images of 24 categories. We randomly select 1000 images to form the testing set, and 19,015 images for the training set (Dong et al., 2021). Following the setting of NUS-WIDE, we extract 1000-dimensional PCA features to represent each image.

For the proposed JPSH, the test range of parameters ${\lambda }_1$, ${\lambda }_2$ and ${\lambda }_3$ is $\{0,1,\dots ,{10}^5,{10}^6\}$, the test range of parameter $k$ is $[3,5,7,10,20]$, and the test range of parameter $m$ is $[100,200,\dots ,1000]$. Based on the test results, we empirically set $k=7$, $m=800$, ${\lambda }_1={\lambda }_2=1$ and ${\lambda }_3=10$ on MNIST and CIFAR-10, and set $k=5$, ${\lambda }_1={\lambda }_2=10$ and ${\lambda }_3={10}^5$ on NUS-WIDE and FLICKR25K, while $m=1000$ for NUS-WIDE, and $m=500$ for FLICKR25K. In addition, we set $\psi =7$ in Eq. (6) for MNIST and CIFAR-10 datasets, and set $\psi =5$ for FLICKR25K and NUS-WIDE datasets. We test the system with different lengths of codes ranged in the set of $[8,16,32,64,96,128]$. As for the evaluation, five standard evaluation metrics, i.e. mean Average Precision (mAP), the mean average precision of the top 100 testing samples (Pre@100), Precision-Recall curve, precision vs. top-N positions (Precision@N) curve, and recall vs. top-N positions (Recall@N) curve, are used to evaluate the performance. All results shown here are produced with Hamming radius 2, being the average of 10 run times. The baseline methods used in this evaluation are under no domain adaption assumption. The baseline methods consist of 10 state-of-the-art unsupervised hashing methods: LSH (Datar et al., 2004), SH (Weiss et al., 2008), PCA-ITQ (Gong et al., 2012), SP (Xia et al., 2015), SGH (Jiang and Li, 2015), OEH (Liu et al., 2016), OCH (Liu et al., 2018), JSH (Lai et al., 2018), CH (Weng and Zhu, 2020) and RSSH (Tian et al., 2020). All hashing methods are examined using Matlab on a PC with 3.6GHz and 64G RAM.

To analyze the roles of pairwise and semantic similarities played in JPSH, we perform ablation studies on the CIFAR-10 and FLICKR25K datasets. The experimental results are depicted in Table 1. From this table, we have three clear observations: Firstly, JPSH achieves better performance than JSH and PSH. The reason is that JPSH learns and creates a seamless hash function, jointly considering pairwise and semantic similarities. Compared to JSH, the proposed JPSH considers further the semantics of instances corresponding to the intrinsic geometric structures. In addition, the JPSH retains the superior performance of the traditional manifold hashing method JSH comparsed with the PSH. Secondly, closely looking at JSH and PSH, we observe that PSH performs worse than JSH. One possible reason is that pseudo labels determined by K-means cannot accurately represent the semantic information of the high-dimensional data, comparing to the ground truths. Third, only taking PSH into consideration, we discover that PSH can achieve decent performance, especially on real-world FLICKR25K dataset. This verifies that the proposed PSH can retain the semantic similarity of the high-dimensional space into the Hamming space in a certain extent, without any manually tagged labels. Overall, these well-designed studies exhibit the effectiveness of combining JSH-based pairwise and PSH-based semantic similarity to a seamless formulation.

For the MNIST dataset, the first two rows in Table 1 illustrate the mAP and Pre@100 of our proposed JPSH and the baselines with different hash bits. Figure 4 (a, b, c) show the Precision-Recall curve, Precision@N and Recall@N curves on 64 bits, respectively. Going through these results, we have the following observations: (1) JPSH consistently outperforms all baselines in all cases on this dataset with large gaps, demonstrating its effectiveness on the binary representation in dealing with similarity search tasks. (2) Compared against the second-best method JSH, our proposed method improves $23.76\%$ and $8.63\%$ at least for mAP and Pre@100, respectively. This shows that JPSH outperforms the standard manifold-based hashing method JSH, and generates more discriminative binary codes by jointly learning semantic and pairwise similarities in the Hamming space. (3) RSSH shows better performance than manifold-based hashing methods in low hash bits but worse than JPSH. This indicates that semantic preservation helps to learn the discriminative information, especially that for our proposed method. (4) Figure 4 (a, b, c) show that JPSH achieves consistent performance improvement in terms of Precision-Recall curve, Precision@N and Recall curves on 64 bits, indicating the effectiveness of our JPSH.

For the CIFAR-10 dataset, mAP and Pre@100 are reported in the third and fourth rows of Table 1, and Figure 4 (d, e, f) show the Precision-Recall curve, Precision@N and Recall@N curves based on 64 bits, respectively. From these results, we have the observations similar to those of MNIST: (1) Compared with all baselines, JPSH achieves the best results of 16 to 128 bits in terms of mAP and Pre@100, demonstrating that JPSH can learn discriminative binary codes by maintaining semantic structures in different personalized subspaces. (2) Of 8 bits, PCA-ITQ achieves the best performance. However, the performance of JPSH and PCA-ITQ is very close, whilst JPSH is competitive to the other methods. (3) In Figure 4 (d, e, f), JPSH matches the best baseline in terms of Precision-Recall curve and Recall@N curve, but little low than RSSH on Precision@N. It is worth noting that JPSH ourperforms JSH in terms of Precision@N and Recall@N curves. This indicates that PSH can help to map instances within the same cluster to the same Hamming space in a certain extent.

For the NUS-WIDE dataset, we report the results of mAP and Pre@100 in the fifth and sixth rows of Table 1. The Precision-Recall, Precision@N, and Recall@N curves are shown in Figure 4 (g, h, i). Regarding those results, we have similar observations to the above cases: (1) JPSH also outperforms all baselines in all cases in terms of mAP on this real-world dataset. It significantly surpasses all baselines of low hash bits (8 to 32 bits) in terms of Pre@100, and little lower than JSH of high hash bits (64 to 128 bits). As a whole, these results demonstrate the effectiveness and robustness of the semantic- and pairwise-preserving scheme used in JPSH. (2) From Figure 4 (g, h, i), we witness that JPSH has a consistent improvement compared with all baselines. This justifies that our proposed JPSH discovers more discriminative structural information in binary representation learning.

For the FLICKR25K dataset, the last two rows of Table 1 show results of mAP and Pre@100, and curves of Precision-Recall, Precision@N and Recall@N are shown in Figure 4 (j, k, l). Again, we have observations similar to the above three datasets: (1) JPSH obtains the best results compared with all baselines in terms of mAP and Pre@100, demonstrating the effectiveness and robustness of our proposed JPSH in the binary representation learning process. (2) Figure 4 (j, k, l) show that our proposed JPSH outperforms all compared methods in terms of Precision-Recall and Recall@N curves, slightly lower than some compared methods in terms of Precision@N curve. Furthermore, JPSH is always better than JSH in Figure 4 (k). Therefore, our JPSH can learn better representative binary codes for similarity search.

In JPSH, we use pseudo labels to distinguish different clusters, and then map instances within the same cluster to the same Hamming space. In order to verify that our JPSH indeed maintains a certain semantic similarity, the training set of PSH is replaced by random samples called JPSH${}_0$. The results of mAP and Pre@100 between JPSH${}_0$ and JPSH are shown in Fig 5 and Fig 6, respectively. From those figures, we can observe that the mAP and Pre@100 of JPSH${}_0$ are obviously below that of JPSH, particularly in CIFAR-10 and NUS-WIDE datasets. These results indicate that K-means is good for extracting discriminative information with exploring the semantic structures. Moreover, our proposed JPSH successfully retains those structures into the Hamming space, and JPSH${}_0$ can not be.

As shown in Figure 7, to study the sparsity of JPSH, we depict the visualization of personalized weight matrix $P$ processed by $sign$ function with size $16\times 784$, $32\times 784$ and $64\times 784$. It can be seen that each matrix contains some green columns that are equal to zero due to the sparsity constraint of $\parallel P_j{\parallel }_{2,1}$. It means that those corresponding features are ignored in a projection operation. Thus, we can eliminate some redundant features for binary representation learning. For example, the first column of matrices in Figure 7 (a), (b) and (c) are all the zero vector, which means that the first feature of data is malfunction to distinguish the differences between data. Another benefit of sparsity lies in that it can increase the interpretability of the JPSH model. We can know that which features provide the discriminative information, while those features do not. Therefore, the sparsity of $\parallel P_j{\parallel }_{2,1}$ works in our JPSH model.

We discuss the sensitivity of our JPSH over parameters ${\lambda }_1$, ${\lambda }_2$, ${\lambda }_3$, $k$ and $m$. The setting ranges of the corresponding parameters are described in Section 4.2. As an example, Figure 8 (a, b, c) show the sensitivity of the ${\lambda }_1$, ${\lambda }_2$ and ${\lambda }_3$ on the FLICKR25K dataset with 64 bits. Figure 8 (a) and (b) show that the mAPs are over 0.71 within a large wide ranges w.r.t ${\lambda }_1$ and ${\lambda }_2$. In addition, the mAPs fluctuated within a certain range indicate the terms of ${\sum }_{j=1}^m\parallel P_j{\parallel }_{2,1}^2$ and ${\sum }_{i,j=1}^m{S}_{ij}\parallel P_i-P_j{\parallel }_F$ can influence the performance of the JPSH. We set ${\lambda }_1$ and ${\lambda }_2$ as 10 for the FLICKR25K dataset because of the relatively higher and more stable performance. From Figure 8 (c), mAPs exceed 0.69 in the range of $\{0,1,\dots ,{10}^5\}$, and when ${\lambda }_3$ equals to ${10}^5$, the mAP surpasses 0.72. Therefore, we set the best ${\lambda }_3={10}^5$ for the FLICKR25K dataset. In addition, Figure 8 (d) shows mAPs versus $k$ and $m$ on the FLICKR25K dataset with 64 bits, suggesting that the JPSH is not sensitive to $k$ and $m$, either. The sensitivity analysis of ${\lambda }_1$, ${\lambda }_2$, ${\lambda }_3$, $k$ and $m$ on MNIST, CIFAR-10 and NUS-WIDE datasets is similar with that on the FLICKR25K dataset.

Figure 8 (e) and (f) show the convergence curves of our JPSH method on CIFAR-10 and FLICKR25K datasets with 32 bits. The objective function of the JPSH is well converging, and quickly converges to an optimal solution within 20 iterations in all datasets. From Figure 8 (e), we witness that the objective loss function values settle after 4 iterations. Thus, we set the time iteration of our JPSH for CIFAR-10 dataset as $T=4$. Analogously, based on Figure 8 (f), we set $T=10$ for FLICKR25K dataset. For MNIST and NUS-WIDE datasets, we empirically set iteration times to be $T=10$ and $T=5$, respectively.

The overall training time complexity of the JPSH is mainly composed by three parts: (1) the building of matrix $S$, which the computational complexity is $O\left(mm\right)$; (2) the time-consuming of computing matrix $A$ is $O\left(nm\right)$; (3) For each iteration, the computational complexity of Eq. (14) is $O(m^3{d}^3+m^3{d}^2+m^{2}dl+md{l}^2)$; of Eq. (16) is $O(d^3+n{d}^2+mnd+mdl+d{l}^2)$; of performing SVD on rotation matrices $R$ and $V$ both are $O\left(l^3\right)$; and of Eq. (23) is $O(md{l}^2+m^{2}dl+d{l}^2+ndl+mnl)$. Generally, due to the length of binary codes $l$ and anchor points $m$ are usually smaller, the total computational complexity of our JPSH is $O(T{d}^3+Tn{d}^2)$. It is linear with the number of training samples. Note that the whole computational process is mainly based on matrix multiplications, which can be computed in parallel for accelerations. It is reasonably efficient on the binary representation learning. To quantitatively compare the computational complexity, we evaluate the training time-consumation of OEH, RSSH and JPSH on CIFAR-10 dataset in terms of 32, 64 and 96 bits. Table 3 shows the time complexity and running times of OEH, RSSH and JPSH. Obviously, we could find that JPSH needs much less time than the multi-stage hashing method RSSH while little higher than OEH. It is noted that the JPSH yields higher mAP values than OEH, which are shown in Table 2. Therefore, the time cost of our proposed JPSH model is acceptable.