# Discrete Semantics-Guided Asymmetric Hashing for Large-Scale Multimedia Retrieval
## 3 The Proposed DSAH Framework
### Optimization  
In this part, we use an alternating strategy to solve the four variables \(\mathbf{B},\mathbf{R},\mathbf{P}_{1},\mathbf{P}_{2}\) in Equation (8), as the four variables are coupled with each other. The problem is split into four steps as follows. Fix \(\mathbf{R},\mathbf{P}_{1},\mathbf{P}_{2}\), update \(\mathbf{B}\). The sub-problem of Equation (8) related to \(\mathbf{B}\) can be formulated as  
\[\underset{\mathbf{B}}{\text{min}} ||(\mathbf{P}_{1}\phi(\mathbf{X}^{(1)}))^{\top}\mathbf{B}-k \mathbf{S}||_{F}^{2}+||(\mathbf{P}_{2}\phi(\mathbf{X}^{(2)}))^{\top}\mathbf{B }-k\mathbf{S}||_{F}^{2}+tr(\mathbf{E}^{\top}\mathbf{D}\mathbf{E}) \tag{9}\] \[+\alpha||\mathbf{B}-0.5\Big{(}\mathbf{P}_{1}\phi(\mathbf{X}^{(1)} )+\mathbf{P}_{2}\phi(\mathbf{X}^{(2)})\Big{)}||_{F}^{2},\] \[s.t.\ \mathbf{B}\in\{-1,1\}^{k\times n}\]  
In the next step, we need to solve the following problem:  
\[\underset{\mathbf{B}}{\text{min}} tr\Big{(}-2k\mathbf{S}\mathbf{B}^{\top}\mathbf{P}_{1}\phi(\mathbf{X}^{(1)} )-2k\mathbf{S}\mathbf{B}^{\top}\mathbf{P}_{2}\phi(\mathbf{X}^{(2)})+\mathbf{B }^{\top}\mathbf{R}\mathbf{D}\mathbf{R}^{\top}\mathbf{B} \tag{10}\] \[-2\mathbf{B}^{\top}\mathbf{R}\mathbf{D}\mathbf{L}-2\alpha\mathbf{ C}\mathbf{B}^{\top}\Big{)}\] \[s.t.\ \mathbf{B}\in\{-1,1\}^{k\times n}\]  
where \(\mathbf{C}=0.5(\mathbf{P}_{1}\phi(\mathbf{X}^{(1)})+\mathbf{P}_{2}\phi( \mathbf{X}^{(2)}))\). As the \(\mathbf{B}\) is the discrete value, it is challenging to directly solve the value of \(\mathbf{B}\). In this solution, we propose an augmented Lagrangian multiplier (ALM) [39] to compute \(\mathbf{B}\). Specifically, we introduce an auxiliary value \(\mathbf{V}\in\{-1,1\}^{k\times n}\) to replace the \(\mathbf{B}\) of second term, i.e., \(\mathbf{B}^{\top}\mathbf{R}\mathbf{D}\mathbf{R}^{\top}\mathbf{B}\). Then, we obtain the following formula:  
\[\underset{\mathbf{B}}{\text{min}} tr\Big{(}-2k\mathbf{S}\mathbf{B}^{\top}\mathbf{P}_{1}\phi(\mathbf{X}^{(1)} )-2k\mathbf{S}\mathbf{B}^{\top}\mathbf{P}_{2}\phi(\mathbf{X}^{(2)})-2\alpha \mathbf{C}\mathbf{B}^{\top} \tag{11}\] \[+\mathbf{B}^{\top}\mathbf{R}\mathbf{D}\mathbf{R}^{\top}\mathbf{V} -2\mathbf{B}^{\top}\mathbf{R}\mathbf{D}\mathbf{L}\Big{)}+\frac{\varsigma}{2}|| \mathbf{B}-\mathbf{V}+\frac{\mathbf{J}_{0}}{\xi}||_{F}^{2},\] \[s.t.\ \{\mathbf{B},\mathbf{V}\}\in\{-1,1\}^{k\times n}\]  
where \(\mathbf{J}_{0}\) measures the gap between \(\mathbf{B}\) and \(\mathbf{V}\). Then, the value of \(\mathbf{B}\) can be solved with a closed-form solution:  
\[ \begin{split}\mathbf{B}&=sgn(2k\mathbf{P}_{1}\phi( \mathbf{X}^{(1)})\mathbf{S}+2k\mathbf{P}_{2}\phi(\mathbf{X}^{(2)})\mathbf{S}+2 \alpha\mathbf{C}-\mathbf{R}\mathbf{D}\mathbf{R}^{\top}\mathbf{V}\\ &+2\mathbf{R}\mathbf{D}\mathbf{L}+\xi\mathbf{V}-\mathbf{J}_{b}). \end{split}  \tag{12}\]  
However, the computational complexity of \(\mathbf{P}_{*}\phi(\mathbf{X}^{(*)})\mathbf{S}|_{s=1}^{2}\) is \(\mathcal{O}(n^{2})\), which is not suitable for large-scale retrieval tasks. To address this problem, we use the label matrix \(\mathbf{L}\in\mathbb{R}^{c\times n}\) to replace the similarity matrix \(\mathbf{S}\in\mathbb{R}^{n\times n}\). Specifically, we let \(\tilde{\mathbf{L}}_{ij}=l_{ij}/||\mathbf{I}_{i}||_{2}\), as the element at the \(i\)-th row and the \(j\)-th column in the matrix \(\mathbf{L}\). Then, the similarity matrix \(\mathbf{S}\) can be rewritten as  
\[\mathbf{S}=2\tilde{\mathbf{L}}^{\top}\tilde{\mathbf{L}}-\mathbf{1}_{n} \mathbf{1}_{n}{}^{\top}, \tag{13}\]  
where \(\mathbf{1}_{n}\) is a vector with all elements being 1. Therefore, we can rewrite the term \(\mathbf{P}_{*}\phi(\mathbf{X}^{(*)})\mathbf{S}|_{s=1}^{2}\) as  
\[\mathbf{P}_{*}\phi(\mathbf{X}^{(*)})\mathbf{S}|_{s=1}^{2}=2\mathbf{P}_{*}\phi (\mathbf{X}^{(*)})\tilde{\mathbf{L}}^{\top}\tilde{\mathbf{L}}-\mathbf{P}_{*} \phi(\mathbf{X}^{(*)})\mathbf{1}_{n}\mathbf{1}_{n}{}^{\top}|_{s=1}^{2}, \tag{14}\]  
which consumes \(\mathcal{O}((q+c)kn)\). _Fix \(\mathbf{B}\), update \(\mathbf{V}\)_. The sub-problem related to \(\mathbf{V}\) can be formulated as  
\[