报告题目：mining big data with recapitulated randomness

报告人：张凯 博士

主持人：浦剑

报告时间：2017年5月5号(周五) 14:00—15:30

报告地点：中北校区数学馆西113

报告人介绍：

       Kai zhang received the PhD degree in computer science from the Hong Kong University of Science and Technology, Hong Kong, in 2008. Then, he joined the Life Science Division, Lawrence Berkeley National Laboratory, Berkeley, CA. He is currently a research staff member with NEC Laboratories America, Inc., Princeton, NJ. He will be joining Temple University as a tenure-track faculty this fall. His current research interests include large scale machine learning, matrix approximation, sparse learning, and applications in bioinformatics, time series, and complex networks.

报告摘要：

       Matrix low-rank decomposition plays a fundamental role in modern scientific computing and optimization algorithms. Randomized algorithms recently received tremendous amount of interest in computing partial approximate factorization with theoretic performance guarantees. However, the need to manipulate the entire input matrix still imposes severe memory and computational bottlenecks. In this talk we find an interesting underlying relation between matrix sketching and lossy data compression, based on which a cascaded bilateral sampling framework is devised to sketch an $m/times n$ matrix in only $/O{(m+n)}$ time and space. The proposed frame accesses only a small number of matrix rows and columns, which significantly improves the memory footprint. Meanwhile, by sequentially teaming two rounds of sketching procedures and upgrading the sampling strategy from uniform sampling to more sophisticated, encoding-orientated clustering, significant algorithmic boosting is achieved to uncover more granular structures in the data. Empirical results on numerical simulations and a wide spectrum of real-world, large-scale matrices show that by taking only linear time and space, the accuracy of our method rivals those state-of-the-art randomized algorithms consuming a quadratic amount of resources.