计算机软件新技术国家重点实验室

摘 要：

In the subspace sketch problem one is given an n x d matrix A with O(log(nd)) bit entries, and would like to compress it in an arbitrary way to build a small space data structure Q_p, so that for any given x in R^d, with probability at least 2/3, one has Q_p(x) = (1\pm \epsilon)\|Ax\|_p, where the randomness is over the construction of Q_p. The central question is: How many bits are necessary to store Q_p?

 A major open question is the dependence on the approximation factor \epsilon. We show if p >= 0 is not a positive even integer and d = Omega(log(1/\epsilon)), then \tilde{\Omega}(ϵ^{−2}d) bits are necessary. On the other hand, if p is a positive even integer, then there is an upper bound of O(d^p log(nd)) bits independent of \epsilon. As a corollary of our main lower bound, we obtain the first near-tight bound on the epsilon-dependence for embedding subspaces of L_p(0,1) in functional analysis.

报告人简介:

Yi Li is an assistant professor in the Division of Mathematical Sciences at Nanyang Technological University in Singapore. He was graduated from University of Michigan, Ann Arbor in 2013. His research interests lie in the area of sublinear-time algorithms, algorithms for massive datasets and low-distortion metric embeddings.

李翼 新加坡南洋理工大学

时间：5月28日  15:00-16:00

地点：计算机科学技术楼224室