【1】Exploiting Linear Structure Within Convolutional Networks for Efficient Evaluation -- NIPS2014

文章地址: https://arxiv.org/pdf/1404.0736.pdf
代码地址: https://cs.nyu.edu/~denton/compress_conv.zip
Contribution.

1. A collection of generic methods to exploit the redundancy inherent in deep CNNs.
2. Showing empirical speedups on convolutional layers by a factor of 2-3x and a reduction of parameters in fully connected layers by a factor of 5-10x.

Monochronmatic Convolution Approximation.
Let $W\in \mathbb{R}^{C\times X \times Y \times F} (96,7,7,3)$W∈RC×X×Y×F(96,7,7,3)
For every output feature $f$f, consider the matrix $W_f \in \mathbb{R}^{C\times (XY)}$Wf​∈RC×(XY)
Find the SVD, $W_f = U_fS_fV_f^{T}$Wf​=Uf​Sf​VfT​, where $U_f \in \mathbb{R}^{C\times C }(3,3), S_f \in \mathbb{R}^{C\times XY}(3,7\times 7 =49), V_f \in \mathbb{R}^{XY\times XY}(49,49)$Uf​∈RC×C(3,3),Sf​∈RC×XY(3,7×7=49),Vf​∈RXY×XY(49,49).
We can take the rank 1 approximation of $W_f$Wf​, $\tilde{W}_f = \tilde{U}_f\tilde{S}_f\tilde{V}_f^{T}$W~f​=U~f​S~f​V~fT​, where $\tilde{U}_f\in \mathbb{R}^{C\times 1}, \tilde{S}_f\in \mathbb{R}, \tilde{V}_f\in \mathbb{R}^{1\times XY}$U~f​∈RC×1,S~f​∈R,V~f​∈R1×XY.

Further clustering the $F$F left singular vectors, $\tilde{U}_f$U~f​ into $C&#x27;$C′ clusters, $C&#x27;&lt;F$C′<F. (Kmeans)
$\tilde{W}_f =U_{c_f}\tilde{S}_f\tilde{V}_f^T$W~f​=Ucf​​S~f​V~fT​, where $U_{c_f}\in\mathbb{R}^{C\times 1}$Ucf​​∈RC×1 is the cluster center for cluster $c_f$cf​.

Biclustering Approximation.
Let $W\in \mathbb{R}^{C\times X \times Y \times F}$W∈RC×X×Y×F, $W_C\in\mathbb{R}^{C\times (XYF)}$WC​∈RC×(XYF), $W_F\in\mathbb{R}^{(CXY)\times F}$WF​∈R(CXY)×F.
Clustering rows of $W_C$WC​ into $G$G clusters.
Clustering columns of $W_F$WF​ into $H$H clusters.
Then we get $H\times G$H×G sub-tensors $W(C_i, :, :,F_j),W_S\in\mathbb{R}^{\frac{C}{G}\times(XY)\times{\frac{F}{H}}}$W(Ci​,:,:,Fj​),WS​∈RGC​×(XY)×HF​
Each sub-tensor contains similar elements, and thus is easier to fit with a low-rank approximation.

1. Outer product decomposition ($rank-K$rank−K)
   $W^{k+1}\leftarrow W^k-\alpha \otimes \beta\otimes \gamma$Wk+1←Wk−α⊗β⊗γ
   where $\alpha\in \mathbb{R}^C,\beta\in\mathbb{R}^{XY},\gamma\in\mathbb{R}^{F}$α∈RC,β∈RXY,γ∈RF
2. SVD decomposition
   For $W\in\mathbb{R}^{m\times n k}$W∈Rm×nk,$\tilde{W}\approx\tilde{U}\tilde{S}\tilde{V}^T$W~≈U~S~V~T.
   W can be compressed even further by applying SVD to $\tilde{V}$V~.
   Use $K_1$K1​ and $K_2$K2​ to denote the rank used in the first and second SVD.

Settings.