# Learning and Compressing: Low-Rank Matrix Factorization for Deep Neural Network Compression
## 3 Algorithm
### CUR Decomposition  
In this subsection, we will briefly introduce the CUR decomposition method. We summarize the overall process of CUR decomposition in Algorithm 1.  
```
0: the weight matrix \(\mathbf{W}\), rank parameter \(r\) and hyperparameter \(c\)
1: Compute the SVD of the \(\mathbf{W}:\mathbf{W}=\mathbf{U}\mathbf{\Sigma}\mathbf{V}^{T}\)
2: Compute the normalized statistical leverage scores with the top \(r\) right singular vectors of \(\mathbf{W}:\pi_{j}=\frac{1}{\zeta}\sum\limits_{\xi=1}^{r}\left(\mathbf{V}_{j}^ {\xi}\right)^{2}\)
3: Compute C by choosing the jth column (\(j\in\left\{\ 1,\ldots,n\right\}\) ) of W based on the probability: \(p_{j}=\min\left\{\ 1,c\pi_{j}\right\}\)
4: Compute R by inputting \(\mathbf{W}^{T}\), \(r\) and \(c\), and repeating step 1-3
5: Compute U : U=\(\mathbf{C}^{+}\mathbf{W}\mathbf{R}^{+}\)
6: Compute \(\mathbf{\Theta}:\mathbf{\Theta}=\mathbf{C}\mathbf{U}\)
7: Return \(\mathbf{\Theta}\)
```  
**Algorithm 1** Pseudocode: CUR decomposition  
Assume that \(\mathbf{W}\) is the \(j\)-th column of weight matrix and can be represented as \(\mathbf{W}^{j}=\sum\limits_{\xi=1}^{R}\mathbf{U}_{\xi}\mathbf{\Sigma}^{\xi} \mathbf{V}_{j}^{\xi}\) using the SVD method (Equation (2)), where \(R=rank(\mathbf{W})\) and \(\mathbf{V}_{j}^{\xi}\) is the \(j\)-th coordinate of the \(\xi\)-th right singular vector. Thus, \(\mathbf{W}^{j}\) can be approximate as a linear combination of the truncated top r left singular vectors and corresponding singular values, denoted as \(\mathbf{W}^{j}\approx\sum\limits_{\xi=1}^{r}\mathbf{U}_{\xi}\mathbf{\Sigma}^{ \xi}\mathbf{V}_{j}^{\xi}\). In the calculation of the normalized statistical leverage scores, it is obvious to prove that \(\pi_{j}\geq 0\) and that \(\sum\limits_{j=1}^{n}\pi_{j}=1\) for all \(j\in\left\{\ 1,\ldots,n\right\}\), and thus that these scores form a probability distribution with \(n\) columns. In conclusion, we calculate the CUR decomposition in three steps. First, we choose columns from the given \(m\times n\) matrix \(\mathbf{W}\) and calculate the normalized statistical leverage scores using the probabilities for all \(j\in\left\{\ 1,\ldots,n\right\}\) with \(c=\mathrm{O}(\frac{r\log r}{c^{2}})\). Secondly, following this procedure (Algorithm 1), we select the rows and columns of matrix \(\mathbf{W}\) to construct the matrices \(\mathbf{C}\) and \(\mathbf{R}\), respectively. Finally, we compute the matrix \(\mathbf{U}=\mathbf{C}^{+}\mathbf{W}\mathbf{R}^{+}\), where \(\mathbf{C}^{+}\) and \(\mathbf{R}^{+}\) is the Moore-Penrose generalized inverse of \(\mathbf{C}\) and \(\mathbf{R}\), respectively. Additionally, the runtime of this CUR decomposition algorithm is dominated by the column and row leverage scores' calculation, and the error analysis of this decomposition method proves that:  
\[\left\|\mathbf{W}-\mathbf{C}\mathbf{U}\mathbf{R}\right\|_{\mathrm{F}}\leq(2 +\varepsilon)\left\|\mathbf{W}\right\|_{\mathrm{F}}, \tag{4}\]  
which is presented clearly in [32].  
In generally, after applying the CUR decomposition algorithm to the matrix \(\mathbf{W}\), we can obtain three matrices: \(\mathbf{C}\in\mathbb{R}^{m\times c}\), \(\mathbf{U}\in\mathbb{R}^{c\times c}\), and \(\mathbf{R}\in\mathbb{R}^{c\times n}\). In other words, we will obtain the compressed matrix \(\mathbf{\Theta}\) by the product of the above three matrices. Suppose that we have a given weight matrix \(\mathbf{W}\) with size of \(m\times n\), we use CUR decomposition (Algorithm 1) to decompose it and obtain two dense layers that satisfy \(\mathbf{D}=\mathbf{C}\in\mathbb{R}^{m\times c}\) and \(\mathbf{E}=\mathbf{U}\mathbf{R}\in\mathbb{R}^{c\times n}\). The total number of parameters in these two dense layers \(\mathbf{D}\) and \(\mathbf{E}\) are \(c\times(m+n)\), and the compression ratio of CUR decomposition is \(\mathrm{O}(\frac{mn}{mc+nc})\). Obviously, \(c\times(m+n)\) will be smaller than \(m\times n\) when \(c\) is significantly smaller than \(\min\left(m,n\right)\).