The lp-Subspace Sketch Problem with Applications to Non-Embeddability

：李翼助理教授
：2019-06-05 15:30
：实验楼108

       Speaker：Dr. Yi Li

                        Nanyang Technological University

       Title:  The lp-Subspace Sketch Problem with Applications to Non-Embeddability

       Time：5 June 2019,15:30

Location：实验楼108

Abstract:  Consider the classical problem of finding the smallest n such that any d-dimensional subspace of L_p(0,1) can be (1+eps)-embedded into (R^n,||.||_p). We show that when p>=1 is not an even integer d >=Clog(1/eps), it is necessary that n >= C'/(eps^2 polylog(1/eps)), which is the optimal dependence on eps up to polylogarithmic factors, extending the previously known best eps-dependence of 1/eps^{2-o(1)} for p = 1 to a general p. The proof uses techniques in communication complexity by studying the following \ell_p-subspace sketch problem. There are two players Alice Bob. Alice has the subspace sends a message to Bob such that Bob can approximate the ell_p norm of any vector in the subspace. We show that the message length needs to be at least d/(eps^2 polylog(1/eps)) bits, from which the embedding dimension lower bound follows.

      Speaker Introduction：Assistant professor in the Divison of Mathematial Sciences at Nanyang Technological University. Previously, he was a postdoc at Harvard University, a postdoc at the Max-Planck Institute for Informatics in Saarbruecken, Germany a research fellow at the Simons Institute for the Theory of Computing, Ph. D. in Computer Science Engineering, University of Michigan. Research Interests: Algorithms for massive data sets, data streaming algorithms; Low-distortion metric embeddings; Compressive sensing signal processing; Theoretical computer science.

 联系人：  张文教授