# Learning and Compressing: Low-Rank Matrix Factorization for Deep Neural Network Compression
## 3 Algorithm
### Optimization Algorithm  
In this section, we mainly focus on optimizing DNN model compression based on the low-rank CUR decomposition technique. We first introduce the solution of the objective function of Equation (5), and then give the incorporate process of CUR decomposition and ranks auto-selection. The detailed solution process is shown in Algorithm 2. ```
1:the weight matrices \(\{\ \mathbf{W}_{k}\}\) and compression cost functions \(\text{C}_{k}(r_{k})\) in \(k\)-th layer, hyperparameter \(\lambda\) and \(\mu_{0}\)
2:Train the weight matrices of the DNN model: \(\mathbf{W}=\{\ \mathbf{W}_{k}\}\ \leftarrow\arg\min_{\mathbf{W}}L(\mathbf{W})\)
3:Initialize ranks and Lagrange multipliers at each layer: \(\{\ \mathbf{r}_{k}\}\ =0\), \(\{\ \mathbf{M}_{k}\}\ =0\)
4:for\(\mu=\mu_{0}<\mu_{1}<...<\infty\)do
5:for\(k=1,2,...,K\)do
6: Compute \(\mathbf{\Theta}_{k}\) from \(\mathbf{W}_{k}\) using Algorithm 1
7:endfor
8: Solve the learning step:\(\mathbf{W}\leftarrow\underset{\mathbf{W}}{\operatorname{argmin}}\ L(\mathbf{W})+\frac{\mu}{2}\Big{\|}\mathbf{W}-\mathbf{\Theta}-\frac{1}{ \mu}\mathbf{M}\Big{\|}_{\text{F}}^{2}\)
9:for\(k=1,2,...,K\)do
10: Solve the compressing step: \[\mathbf{\Theta}_{k},\mathbf{r}_{k}\leftarrow\underset{\mathbf{\Theta}_{k},r_{k} }{\operatorname{argmin}}\lambda\text{C}_{k}(r_{k})+\frac{\mu}{2}\Big{\|} \mathbf{W}_{k}-\mathbf{\Theta}_{k}-\frac{1}{\mu}\mathbf{M}_{k}\Big{\|}_{\text{ F}}^{2}\]
11:endfor
12: Update Lagrange multipliers \(\mathbf{M}\leftarrow\mathbf{M}-\mu(\mathbf{W}-\mathbf{\Theta})\)
13:endfor
14:Return\(\mathbf{W},\mathbf{\Theta},r\)
```  
**Algorithm 2** Pseudocode: optimization framework  
In DNNs, we assume that the network has \(K\) layers, and \(W_{k}\) represents the weight matrix in the \(k\)-th layer (\(k\in\{\ 1,\ldots,K\}\) ). In order to solve Equation (5), we introduce the ALM to convert the constrained optimization into an unconstrained optimization. Under iterations, we can solve Equation (5)ALM by introducing the Lagrange multiplier vector \(\mathbf{M}\). Then the Equation (5) can be rewritten as follows:  
\[ \begin{split}&\min_{W,\Theta,r}L(\mathbf{W})+\lambda C(r)-\mathbf{M} ^{T}\sum\limits_{k=1}^{K}\left(\mathbf{W}_{k}-\mathbf{\Theta}_{k}\right)+\frac {\mu}{2}\sum\limits_{k=1}^{K}\left\|\mathbf{W}_{k}-\mathbf{\Theta}_{k}\right\| _{F}^{2},\\ &\text{s.t}\quad\text{rank}(\mathbf{\Theta}_{k})=r_{k}\leq R_{k}, k=1,...,K\end{split}  \tag{7}\]  
where \(\mu\) is penalty parameter and its value should be non-negative, \(\mathbf{M}\) is Lagrange multiplier which has the same dimension as \(\mathbf{W}\). For Equation (7), it can be alternately optimized by updating Lagrange multiplier while driving \(\mu\rightarrow\infty\). In Algorithm 2, this algorithm has two sets per layer in the \(k\)-th layer: \(\left\{\ \mathbf{W}\right\}\) in the learning step, and \(\left\{\ \mathbf{\Theta}\right\}\) with rank \(\left\{\ r\right\}\) determined in each compressing step. We first initialize the weight matrix by directly computing the classification loss and then divide the solution into two separated steps: the learning step and compression step. The former step is a regular learning step (training process) of a cross-entropy loss function plus a quadratic regularization penalty, which drives the matrices \(\mathbf{W}_{k}\) towards the low-rank approximation matrices \(\mathbf{\Theta}_{k}\), and the form is as follows:  
\[\min_{\mathbf{W}}L(\mathbf{W})+\frac{\mu}{2}\left\|\mathbf{W}-\mathbf{\Theta} -\frac{1}{\mu}\mathbf{M}\right\|_{F}^{2},\text{s.t.rank}(\mathbf{\Theta}_{k})= r_{k}\leq R_{k},k=1,...,K \tag{8}\]  
Based on the learning step, we can use stochastic gradient descent (SGD) to optimize Equation (8) for training on large-scale datasets and high-dimensional weight matrices.