Querying a Matrix through Matrix-Vector Products
作者： Jialin Zhang , David P. Woodruff , Xiaoming Sun , Guang Yang
DOI:
关键词:
摘要: … Let X be an n × m matrix with each row iid drawn from an m-variate normal distribution N (0, Σ). Then the distribution of the m × m random matrix A = XT X is called the Wishart distri…
arxiv.org
acm.org参考文章(39)
Magnús M. Halldórsson, Xiaoming Sun, Mario Szegedy, Chengu Wang, Streaming and communication complexity of clique approximation international colloquium on automata languages and programming. pp. 449- 460 ,(2012) , 10.1007/978-3-642-31594-7_38
David P. Woodruff, Huy L. Nguyen, Yi Li, On sketching matrix norms and the top singular vector symposium on discrete algorithms. pp. 1562- 1581 ,(2014) , 10.5555/2634074.2634188
Andrew McGregor, Kook Jin Ahn, Sudipto Guha, Analyzing graph structure via linear measurements symposium on discrete algorithms. pp. 459- 467 ,(2012) , 10.5555/2095116.2095156
David P. Woodruff, Eric Price, Lower bounds for adaptive sparse recovery symposium on discrete algorithms. pp. 652- 663 ,(2013) , 10.5555/2627817.2627864
Hermann Weyl, Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differentialgleichungen (mit einer Anwendung auf die Theorie der Hohlraumstrahlung) Mathematische Annalen. ,vol. 71, pp. 441- 479 ,(1912) , 10.1007/BF01456804
Ziv Bar-Yossef, D. Sivakumar, Ravi Kumar, Reductions in streaming algorithms, with an application to counting triangles in graphs symposium on discrete algorithms. pp. 623- 632 ,(2002) , 10.5555/545381.545464
Andrew Chi-Chin Yao, Probabilistic computations: Toward a unified measure of complexity 18th Annual Symposium on Foundations of Computer Science (sfcs 1977). pp. 222- 227 ,(1977) , 10.1109/SFCS.1977.24
Anders Björner, László Lovász, Andrew C. C. Yao, Linear decision trees: volume estimates and topological bounds symposium on the theory of computing. pp. 170- 177 ,(1992) , 10.1145/129712.129730
Yi Li, Huy L. Nguyen, David P. Woodruff, Turnstile streaming algorithms might as well be linear sketches symposium on the theory of computing. pp. 174- 183 ,(2014) , 10.1145/2591796.2591812
Haim Avron, Sivan Toledo, Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix Journal of the ACM. ,vol. 58, pp. 1- 34 ,(2011) , 10.1145/1944345.1944349