nips nips2013 nips2013-206 nips2013-206-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Dimitris Achlioptas, Zohar S. Karnin, Edo Liberty
Abstract: We consider the problem of selecting non-zero entries of a matrix A in order to produce a sparse sketch of it, B, that minimizes A B 2 . For large m n matrices, such that n m (for example, representing n observations over m attributes) we give sampling distributions that exhibit four important properties. First, they have closed forms computable from minimal information regarding A. Second, they allow sketching of matrices whose non-zeros are presented to the algorithm in arbitrary order as a stream, with O 1 computation per non-zero. Third, the resulting sketch matrices are not only sparse, but their non-zero entries are highly compressible. Lastly, and most importantly, under mild assumptions, our distributions are provably competitive with the optimal offline distribution. Note that the probabilities in the optimal offline distribution may be complex functions of all the entries in the matrix. Therefore, regardless of computational complexity, the optimal distribution might be impossible to compute in the streaming model. 1
[AHK05] Sanjeev Arora, Elad Hazan, and Satyen Kale. Fast algorithms for approximate semidefinite programming using the multiplicative weights update method. In Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on, pages 339–348. IEEE, 2005. [AHK06] Sanjeev Arora, Elad Hazan, and Satyen Kale. A fast random sampling algorithm for sparsifying matrices. In Proceedings of the 9th international conference on Approximation Algorithms for Combinatorial Optimization Problems, and 10th international conference on Randomization and Computation, APPROX’06/RANDOM’06, pages 272–279, Berlin, Heidelberg, 2006. Springer-Verlag. [AKV02] Noga Alon, Michael Krivelevich, and VanH. Vu. On the concentration of eigenvalues of random symmetric matrices. Israel Journal of Mathematics, 131:259–267, 2002. [AM01] Dimitris Achlioptas and Frank McSherry. Fast computation of low rank matrix approximations. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 611–618. ACM, 2001. [AM07] Dimitris Achlioptas and Frank Mcsherry. Fast computation of low-rank matrix approximations. J. ACM, 54(2), april 2007. [AW02] Rudolf Ahlswede and Andreas Winter. Strong converse for identification via quantum channels. IEEE Transactions on Information Theory, 48(3):569–579, 2002. [Ber07] Aleˇ Berkopec. Hyperquick algorithm for discrete hypergeometric distribution. Journal of Discrete s Algorithms, 5(2):341–347, 2007. [CR09] Emmanuel J Cand` s and Benjamin Recht. Exact matrix completion via convex optimization. Foune dations of Computational mathematics, 9(6):717–772, 2009. [CT10] Emmanuel J Cand` s and Terence Tao. The power of convex relaxation: Near-optimal matrix come pletion. Information Theory, IEEE Transactions on, 56(5):2053–2080, 2010. [d’A08] Alexandre d’Aspremont. Subsampling algorithms for semidefinite programming. arXiv preprint arXiv:0803.1990, 2008. [DKM06] Petros Drineas, Ravi Kannan, and Michael W. Mahoney. Fast monte carlo algorithms for matrices; approximating matrix multiplication. SIAM J. Comput., 36(1):132–157, July 2006. [DZ11] Petros Drineas and Anastasios Zouzias. A note on element-wise matrix sparsification via a matrixvalued bernstein inequality. Inf. Process. Lett., 111(8):385–389, 2011. [FK81] Z. F¨ redi and J. Koml´ s. The eigenvalues of random symmetric matrices. Combinatorica, 1(3):233– u o 241, 1981. [GT09] Alex Gittens and Joel A Tropp. Error bounds for random matrix approximation schemes. arXiv preprint arXiv:0911.4108, 2009. [Juh81] F. Juh´ sz. On the spectrum of a random graph. In Algebraic methods in graph theory, Vol. I, a II (Szeged, 1978), volume 25 of Colloq. Math. Soc. J´ nos Bolyai, pages 313–316. North-Holland, a Amsterdam, 1981. [NDT09] NH Nguyen, Petros Drineas, and TD Tran. Matrix sparsification via the khintchine inequality, 2009. [NDT10] Nam H Nguyen, Petros Drineas, and Trac D Tran. Tensor sparsification via a bound on the spectral norm of random tensors. arXiv preprint arXiv:1005.4732, 2010. [PCI 07] J. Philbin, O. Chum, M. Isard, J. Sivic, and A. Zisserman. Object retrieval with large vocabularies and fast spatial matching. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2007. [Rec11] Benjamin Recht. A simpler approach to matrix completion. J. Mach. Learn. Res., 12:3413–3430, December 2011. [RV07] Mark Rudelson and Roman Vershynin. Sampling from large matrices: An approach through geometric functional analysis. J. ACM, 54(4), July 2007. [Sty11] Will Styler. The enronsent corpus. In Technical Report 01-2011, University of Colorado at Boulder Institute of Cognitive Science, Boulder, CO., 2011. [Tro12a] Joel A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics, 12(4):389–434, 2012. [Tro12b] Joel A Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics, 12(4):389–434, 2012. [Wig58] Eugene P. Wigner. On the distribution of the roots of certain symmetric matrices. Annals of Mathematics, 67(2):pp. 325–327, 1958. 9