Wednesday, December 5, 2018 - 12:00pm to 1:00pm

Location:

Speaker:

Lp 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.

Event Website:

For More Information, Contact:

Keywords: