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

### Location:

8102 Gates Hillman Centers### Speaker:

RUOSONG WANG, Ph.D. Student /RUOSONG%20WANG### 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.