Sampling based succinct matrix approximation

This work furnishes a sharper bound of exponential form to the L2 norm of an arbitrary shaped random matrix. On the basis of this bound, a non-uniform sampling method is developed for approximating a matrix with a sparse binary one. Both time and storage loads of matrix computations can hereby be relieved with limited loss of information. The sampling and quantizing approaches are naturally combined together in the approximation. Furthermore, this method is pass-efficient because the whole process can be completed within one pass over the input matrix. The sampling method demonstrated an impressive capability of providing succinct and tight approximations (data reduction) for input matrices in the experimental evaluation on a large data set.