Co-Occuring Directions Sketching for Approximate Matrix Multiply
作者： Etienne Marcheret , Vaibhava Goel , Youssef Mroueh
DOI:
关键词:
摘要: We introduce co-occurring directions sketching, a deterministic algorithm for approximate matrix product (AMM), in the streaming model. show that co-occuring achieves better error bound AMM than other randomized and approaches AMM. Co-occurring gives $1 + \epsilon$ -approximation of optimal low rank approximation product. Empirically our outperforms competing methods AMM, small sketch size. validate empirically theoretical findings algorithms
arxiv.org参考文章(12)
Michael B. Cohen, Jelani Nelson, David P. Woodruff, Optimal approximate matrix product in terms of stable rank arXiv: Data Structures and Algorithms. ,(2015)
J. Misra, David Gries, Finding Repeated Elements Science of Computer Programming. ,vol. 2, pp. 143- 152 ,(1982) , 10.1016/0167-6423(82)90012-0
Harold Hotelling, Relations Between Two Sets of Variates Springer Series in Statistics. ,vol. 28, pp. 162- 190 ,(1992) , 10.1007/978-1-4612-4380-9_14
Petros Drineas, Ravi Kannan, Michael W. Mahoney, Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication SIAM Journal on Computing. ,vol. 36, pp. 132- 157 ,(2006) , 10.1137/S0097539704442684
Tamas Sarlos, Improved Approximation Algorithms for Large Matrices via Random Projections foundations of computer science. pp. 143- 152 ,(2006) , 10.1109/FOCS.2006.37
Edo Liberty, Simple and deterministic matrix sketching knowledge discovery and data mining. pp. 581- 588 ,(2013) , 10.1145/2487575.2487623
Inderjit S. Dhillon, Co-clustering documents and words using bipartite spectral graph partitioning knowledge discovery and data mining. pp. 269- 274 ,(2001) , 10.1145/502512.502550
David P. Woodruff, Sketching as a Tool for Numerical Linear Algebra ,(2014)
Kaiming He, Xiangyu Zhang, Shaoqing Ren, Jian Sun, Deep Residual Learning for Image Recognition computer vision and pattern recognition. pp. 770- 778 ,(2016) , 10.1109/CVPR.2016.90
Mina Ghashami, Amey Desai, Jeff M. Phillips, Improved Practical Matrix Sketching with Guarantees european symposium on algorithms. pp. 467- 479 ,(2014) , 10.1007/978-3-662-44777-2_39