Oleg Zabluda's blog
Saturday, April 01, 2017
 
Exploiting Linear Structure Within Convolutional Networks for Efficient Evaluation (2014) Emily Denton, Wojciech...
Exploiting Linear Structure Within Convolutional Networks for Efficient Evaluation (2014) Emily Denton, Wojciech Zaremba, Joan Bruna, Yann LeCun, Rob Fergus
"""
3.2.1 Matrix Decomposition

Matrices are 2-tensors which can be linearly compressed using the Singular Value Decomposition. If W ∈ R^m×k is a real matrix, the SVD is defined as W = USV, where U ∈ R^m×m, S ∈ R^m×k, V ∈ R^k×k. S is a diagonal matrix with the singular values on the diagonal, and U, V are orthogonal matrices. If the singular values of W decay rapidly, W can be well approximated by keeping only the t largest entries of S, resulting in the approximation W˜ = U˜S˜V˜, where U˜ ∈ R^m×t, S˜ ∈ R^t×t, V˜ ∈ R^t×k. Then, for I ∈ R^n×m, the approximation error || IW˜ − IW|| ≤ s_{t+1}|| I || , and thus is controlled by the decay along the diagonal of S.Now the computation IW˜ can be done in O(nmt + nt2 + ntk), which, for sufficiently small t is significantly smaller than O(nmk).
"""
https://arxiv.org/abs/1404.0736
https://arxiv.org/abs/1404.0736

Labels:


- posted by Oleg Zabluda @ 7:41 PM | permalink | | | technorati | bloglines | feedster
| |

Home

Powered by Blogger