Almost Optimal Tensor Sketch

Publication date 3 September 2019

Abstract: We construct a matrix

M i n R^{m o t i m e s d^{c}}

with just

m = O (c, l a m b d a, v a r e p s i l o n^{- 2} e x t p o l y l o g 1 / v a r e p s i l o n d e l t a)

rows, which preserves the norm

| M x |_{2} = (1 p m v a r e p s i l o n) | x |_{2}

of all

x

in any given

l a m b d a

dimensional subspace of

R^{d}

with probability at least

1 - d e l t a

. This matrix can be applied to tensors

x^{(1)} o t i m e s d o t s o t i m e s x^{(c)} i n R^{d^{c}}

in

O (c, m m i n d, m)

time -- hence the name "Tensor Sketch". (Here

x o t i m e s y = e x t a s v e c (x y^{T}) = [x_{1} y_{1}, x_{1} y_{2}, d o t s, x_{1} y_{m}, x_{2} y_{1}, d o t s, x_{n} y_{m}] i n R^{n m}

.) This improves upon earlier Tensor Sketch constructions by Pagh and Pham~[TOCT 2013, SIGKDD 2013] and Avron et al.~[NIPS 2014] which require

m = O m e g a (3^{c} l a m b d a^{2} d e l t a^{- 1})

rows for the same guarantees. The factors of

l a m b d a

,

v a r e p s i l o n^{- 2}

and

l o g 1 / d e l t a

can all be shown to be necessary making our sketch optimal up to log factors. With another construction we get

l a m b d a

times more rows

m = i l d e O (c, l a m b d a^{2}, v a r e p s i l o n^{- 2} (l o g 1 / d e l t a)^{3})

, but the matrix can be applied to any vector

x^{(1)} o t i m e s d o t s o t i m e s x^{(c)} i n R^{d^{c}}

in just

i l d e O (c, (d + m))

time. This matches the application time of Tensor Sketch while still improving the exponential dependencies in

c

and

l o g 1 / d e l t a

. Technically, we show two main lemmas: (1) For many Johnson Lindenstrauss (JL) constructions, if

Q, Q^{'} i n R^{m i m e s d}

are independent JL matrices, the element-wise product

Q x c i r c Q^{'} y

equals

M (x o t i m e s y)

for some

M i n R^{m i m e s d^{2}}

which is itself a JL matrix. (2) If

M^{(i)} i n R^{m i m e s m d}

are independent JL matrices, then

M^{(1)} (x o t i m e s (M^{(2)} y o t i m e s d o t s)) = M (x o t i m e s y o t i m e s d o t s)

for some

M i n R^{m i m e s d^{c}}

which is itself a JL matrix. Combining these two results give an efficient sketch for tensors of any size.

This page was built for publication: Almost Optimal Tensor Sketch