Pruning is an efficient model compression technique to remove redundancy in the connectivity of deep neural networks (DNNs). A critical problem to represent sparse matrices after pruning is that if fewer bits are used for quantization and pruning rate is enhanced, then the amount of index becomes relatively larger. Moreover, an irregular index form leads to low parallelism for convolutions and matrix multiplications. In this paper, we propose a new network pruning technique that generates a low-rank binary index matrix to compress index data significantly. Specifically, the proposed compression method finds a particular finegrained pruning mask that can be decomposed into two binary matrices while decompressing index data is performed by simple binary matrix multiplication. We also propose a tile-based factorization technique that not only lowers memory requirements but also enhances compression ratio. Various DNN models (including conv layers and LSTM layers) can be pruned with much fewer indices compared to previous sparse matrix formats while maintaining the same pruning rate.
The paper addresses the problem of reducing the computational complexity of neural network pruning. Main idea is to compute a low-rank approximation of the binary index matrix used to represent the structure of the pruned network. In the considered setup, the binary index matrix is the (sparse) boolean matrix associated with the nonzero network's weights. As low-rank decomposition of binary matrices is a hard problem, the authors propose a method to approximate the solution by computing a more standard non-negative matrix factorization. 
This is a nice problem and the proposed approach is interesting  but I would tend to reject the paper. The main problem, in my opinion, is a substantial lack of theoretical justifications.  What are the intuitive motivations for considering the proposed method? It is hard to understand why the approach should be preferred to others.  The idea of converting the binary low-rank factorization problem into a real-valued non-negative factorization problem is interesting but 
could have been better justified (from an intuitive/theoretical and computational perspective). For example, why is it convenient to convert a hard matrix factorization problem (BMF) into another hard matrix factorization problem (NMF). 
An empirical or theoretical analysis of the algorithm's computational complexity would help in this sense.
Also, it is not completely clear what is the relationship of the proposed approach with the neural network framework. Would the impact of the paper increase if presented as a method for binary matrix factorization without links to neural networks pruning? Perhaps a quantitative comparison between gains associated with sparse matrix storage versus other computational costs (related to training or pruning) would help to better collocate the proposed approach in the deep learning framework.
Questions:
- The general idea of approximating BMF with NMF is interesting and could be investigated independently and more deeply. Have the problem and the proposed solution appeared before in the matrix factorization literature (without connections to neural network pruning )?
- Is there any intuitive justification of why thresholding the matrix before and after the factorization leads to consistent results?
- The cost of the proposed approach seems to depend on the rank. Could such explicit dependence be estimated quantitatively and compared with the computational complexity of solving the problem (BMF) directly? 
- In the experiments, the value of the pruning objective seems to decrease as the rank of the factorization increases. Is this an expected result? What is even less clear to me is the behaviour of the test accuracy. Is it normal for the pruned network accuracy to increase with sparsity? And why does the performance look independent from the rank?