## 4 Optimization for ISMLP
We also document the variations of objective function values with respect to iterations on three datasets in Figure 1. Clearly, the loss decreases as the iterations and inclines become stable after several iterations, which proves that the proposed algorithm can converge within limited iterations. ``` Input: The labeled and unlabeled datasets \(\mathbf{X}_{l}\in\mathbb{R}^{d\times n_{l}}\) and \(\mathbf{X}_{u}\in\mathbb{R}^{d\times n_{u}}\), the similar constraint set \(\mathcal{S}\), \(\lambda\), the number of proxy vectors \(m\), \(\mu\), and the dimensionality of the embedding space p;
1 Initialize \(\mathbf{P}\in\mathbb{R}^{d\times p}\) as a column orthonormal matrix, and setting \(\mathbf{R}\) as the identity matrix \(\mathbf{I}_{p}\);
2 Initialize the set of proxy vectors via the Gaussian mixture model by setting the number of components as \(m\);
3 whilenot convergeddo
4 Fix \(\mathcal{Z}\) to solve \(\mathbf{P}\) and \(\mathbf{R}\) via the Riemannian gradient descent algorithm by using the Equations (19) and (21);
5 for\(k=1\),..., \(m\)do
6 Fix \(\mathbf{P}\) and \(\mathbf{R}\) to solve the \(k\)-th proxy vector \(\mathbf{z}_{k}\) by Equation (29);
7 end for
8
9 end for Output: The projection matrix \(\mathbf{P}\) and low-dimensionality Mahalanobis matrix \(\mathbf{R}\);

#### Time Complexity of ISMLP

In this section, we provide a brief analysis of the time complexity of the proposed ISMLP. Recall that the number of labeled and unlabeled data is \(n_{l}\) and \(n_{u}\), respectively. The dimensionality of the original and the reduced data is denoted as \(d\) and \(p\). The number of proxy vectors is denoted as \(m\). The main procedures of ISMLP consist of the following main steps: (1) Evaluating the loss function; (2) Computing the Euclidean gradient of the loss function with respect to **P** and **R**; (3) Projecting the Euclidean gradient of **P** and **R** to the tangent space and then retracing them back to the manifold; (4) Updating the set of the proxy vectors. * Since the time complexity of solving the inverse of a \(p\times p\) matrix costs \(\mathcal{O}\big{(}p^{3}\big{)}\), evaluating the objective function in Equation (11) takes \(\mathcal{O}\big{(}npd+mnp^{2}+p^{3}\big{)}\). * Computing the Euclidean gradient of the loss function with respect to **P** by using Equation (22) takes \(\mathcal{O}\big{(}mndp^{2}\big{)}\), and computing \(\frac{\partial F}{\partial\textbf{R}}\) via Equation (23) costs \(\mathcal{O}\big{(}mnp^{2}+p^{3}\big{)}\). * According to [37], projecting the Euclidean gradient of the loss function with respect to **P** and **R** by using Equations (17) and (18) costs \(\mathcal{O}\big{(}4 dp^{2}+3p^{3}\big{)}\). Retracting the Riemannian gradient back to the manifold via Equation (21) costs \(\mathcal{O}\big{(}4 dp^{2}+14p^{3}\big{)}\). * Solving all the proxy vectors by using Equation (29) cost \(\mathcal{O}\big{(}d^{3}+m^{2}n_{l}p^{2}\big{)}\), where \(n_{l}\) is the number of labeled data. Considering the usual case of large-scale semi-supervised metric learning is \(d\ll n\), the time complexity of the proposed ISMLP is about \(\mathcal{O}\big{(}mndp^{2}\big{)}\), and the main cost lies in evaluating the Euclidean gradient of **P**. To sum up, the time complexity of the proposed ISMLP has a linear dependence on the number of \(n\); therefore, it can be effectively and efficiently extended to large-scale datasets. ## 5 Experiment

In this section, extensive visual classification and retrieval experiments are conducted to verify the efficacy and efficiency of the proposed ISMLP. Firstly, we provide a detailed description of the datasets and evaluation index, and compared methods used in the experiments. Then, the experimental results are provided. ### Datasets, Evaluation Protocol and Compared Methods

**Datasets:** a total of five datasets are utilized, including MNIST [42], Fashion-MNIST [43], Corel 5K [44], CUB-200 [45], and Cars-196 [46].