Wednesday, December 5, 2018 - 12:00pm to 1:00pm
Location:
8102 Gates Hillman CentersSpeaker:
RUOSONG WANG, Ph.D. Student /RUOSONG%20WANGLp Subspace Sketch
Speaker: Ruosang Wang
Location: GHC 8102
Lp Subspace Sketch
Suppose one is given a d-dimensional subspace, represented as the column span of an $n \times d$ matrix $A$ with $O(\log(nd))$-bit entries, and would like to compress it in an arbitrary way to build a data structure $Q_p$, so that simultaneously for every query x \in \mathbb{R}^d, one has Q_p(x) = (1 \pm \epsilon) \|Ax\|_p. How many bits are required to store Q_p? For p = 2, one can store A^TA using O(d^2\log(nd)) bits, independent of $\epsilon$, so that given a query x, one can output x^T (A^TA) x = \|Ax\|_2^2. However, for p = 1, the size of the smallest data structure known is \widetilde{O}(\epsilon^{-2} d^2), where the \widetilde{O} suppresses \log(nd \epsilon^{-1}) factors. Is the dependence on \epsilo$ necessary?
We show if p \geq 1 is a real number that is {not an even integer} and d = \Omega(\log(1/\epsilon)), then \widetilde{\Omega}(\epsilon^{-2} \cdot d) bits are required. Our result has a number of implications for geometric functional analysis. Our techniques, based on communication complexity, also give alternative proofs of known results in functional analysis, such as the d^{p/2} dimension lower bound for embedding d-dimensional subspaces of L_p into \ell_p.
View post-lecture videos at CMU Youtube Theory channel.