## 3 Information-Theoretic Large-Scale Semi-Supervised Metric Learning via Proxies
### Joint Dimensional Reduction and Metric Learning  
One can combine the labeled part and the entropy regularization to finish the objective function of ISMLP. However, when the dimensionality of the feature is large, adopting PGD technology to solve ISMLP will encounter high time complexity. To solve this issue, inspired by the hierarchical way to build the Mahalanobis matrix [37], we propose to decompose \(\mathbf{M}\) as the following form:  
\[\mathbf{M}=\mathbf{PRP}^{T}, \tag{10}\]  
where \(\mathbf{P}\in\text{St}(p,d)\), and \(\mathbf{R}\in\mathcal{S}_{++}^{p}\). In the experiment, \(p\) is usually much smaller than \(d\); therefore, the running time can be significantly reduced. The decomposition form can be understood as first projecting the original feature into a lower embedding space, then using \(\mathbf{R}\) to learn the weight and correlations in the embedding space. Following the common practice in dimensionality reduction, we require \(\mathbf{P}\) to be a column-orthogonal matrix, namely \(\mathbf{P}^{T}\mathbf{P}=\mathbf{I}_{p}\).  
Integrating the Equations (8)-(10) to finish the objective function of ISMLP, we obtain:\[\begin{split}\min_{\mathbf{P},\mathbf{R},\mathcal{Z}}-\frac{1}{| \mathcal{S}|}&\sum_{\big{(}\mathbf{x}_{i},\mathbf{x}_{j}\big{)} \in\mathcal{S}}\log\Biggl{(}\frac{\exp\bigl{(}-d_{\mathbf{M}}^{2}\big{(} \mathbf{x}_{i},p\big{(}\mathbf{x}_{j}\big{)}\big{)}\bigr{)}}{\sum_{i=1}^{n} \exp\bigl{(}-d_{\mathbf{M}}^{2}\big{(}\mathbf{x}_{i},\mathbf{z}_{j}\big{)} \bigr{)}}\Biggr{)}\\ &-\frac{\lambda}{n_{u}}\sum_{i=n_{l}+1}^{n}\sum_{k=1}^{m}q_{ik} \text{log}q_{ik}+\mu r(\mathbf{R},\mathbf{R}_{0})\\ &\text{s.t. }\mathbf{M}=\mathbf{PR}^{\mathsf{T}},\mathbf{P}\in\text{ St}(p,d),\ \mathbf{R}\in\mathcal{S}_{++}^{p}\end{split} \tag{11}\]  
where \(r:\mathcal{S}_{++}^{p}\times\mathcal{S}_{++}^{p}\rightarrow\mathbb{R}_{+}\) denotes the regularization term concerning \(\mathbf{R}\). Here, we aim to keep \(\mathbf{R}\) to be close to a prior matrix \(\mathbf{R}_{0}\) and propose to utilize the Burg divergences [38]:  
\[r(\mathbf{R},\mathbf{R}_{0})=\text{Tr}\Bigl{(}\mathbf{R}\mathbf{R}_{0}^{-1} \Bigr{)}-\text{logdet}\Bigl{(}\mathbf{R}\mathbf{R}_{0}^{-1}\Bigr{)}-p. \tag{12}\]  
In our experiments, we set \(\mathbf{R}_{0}\) as \(\mathbf{I}_{p}\) for simplicity.  
\(\lambda>0\) and \(\mu>0\) are two hyper-parameters that control the importance of the entropy regularization term and the structural prior of \(\mathbf{M}\), respectively. \(p\) is the dimensionality of the latent space. The proposed ISMLP jointly learns the decomposition forms of the Mahalanobis matrix \((\mathbf{P},\mathbf{R})\) and multiple proxy vectors \(\mathcal{Z}\). Maximizing Equation (11) will push the labeled data moving toward their corresponding proxy vectors, which will assign the unlabeled data a high probability.  
Since the first part can be considered as minimizing the entropy of the labeled data and maximizing that of the unlabeled data. These two parts can be naturally combined together in a meaningful way. Instead of directly building the probabilistic model via the pairwise Mahalanobis distance as SERAPH did, ISMLP takes advantage of the proxy vectors to convert the semi-supervised metric learning into \(m\) class distribution optimization. The merits of the ISMLP lie in two folds; on the one hand, the proposed IMSLP is more robust than SERAPH, and can cope well with the outlier in the dataset; on the other hand, the time complexity of the algorithm can be significantly reduced.