# Can we make Tensor Sketch any faster?

For all constants $$\epsilon,\delta>0$$, let $$k=\epsilon^{-2}\log1/\delta$$. We know there exists a linear transformation $$M : \mathbb R^{k^2}\to \mathbb R^{\tilde O(k)}$$, such that for all $$x\in\mathbb R^{k^2}$$ we have $$|\|Mx\|_2-\|x\|_2|\le \epsilon\|x\|_2$$ with probability $$1-\delta$$.

The question is whether there is such a transformation which can be computed in time $$\tilde O(k)$$ for vectors the form $$y_1\otimes y_2=[y_1^2,y_1 y_2,\dots,y_k^2]\in\mathbb R^{k^2}$$, $$y_1,y_2\in\mathbb R^k$$.

(We define $$\tilde O(x) = x(\log x)^{O(1)}$$.)

That is, the embedding should work for any vector in $$\mathbb R^{k^2}$$, but we care about the embedding time of vectors that are known to be simple tensor products. This is known as a Tensor Sketch and has been studied extensively. However, as far as I know, it is still open how fast this can be accomplished, even in the simple case sketched above.

What is known:

(1) Using the Fast JL method on the product, we can compute it in $$\tilde O(k^2)\approx \epsilon^{-4}(\log1/\delta)^2$$ time. (Note that we allow the target dimension to be $$\tilde O(k)$$, slightly bigger than the optimal $$k$$, which is necessary for the best known Fast JL methods.)

(2) Using Sparse JL on the product, we can sketch the vector in time $$\epsilon k^3 = \epsilon^{-5}(\log1/\delta)^3$$.

(3) The analysis in here or here lets us first map the individual vectors with Fast JL into $$\epsilon^{-2}(\log1/\delta)^3$$ dimensions and then take the Hadamard product.

(4) Alternatively, the initial mapping can be done using Sparse JL, in which case we map into $$m=\epsilon^{-2}\log1/\delta+\epsilon^{-1}(\log1/\delta)^2$$ dimensions (again using the analysis of Ahle et al.) using time $$\sim\epsilon m k=\epsilon^{-3}(\log1/\delta)^2+\epsilon^{-2}(\log1/\delta)^3$$. However this is strictly worse than the above method.

In both case (3) and (4), we can make a terminal dimension reduction to the target dimension of $$\tilde O(k)$$ using Fast JL.

Hence the best we know how to do is time $$\approx \epsilon^{-2}(\log1/\delta)^3$$ or $$\epsilon^{-4}(\log1/\delta)^2$$.

I wonder if anyone has an idea for how we can get rid of one or both of the factors $$(\log1/\delta)$$? (Or in the case of method (1), of one or both of the factors $$\epsilon^{-1}$$?)

Even $$\epsilon^{-10}(\log1/\delta)$$ would be quite interesting.

Alternatively we might hope to show that they are necessary? Though, since this would be a time lower bound, rather than an embedding dimension lower bound, it is not clear which model one should choose.

Notes:

• In the case of vectors $$y_1,y_2\in\{-1,1\}^k$$, simply sampling $$\epsilon^{-2}\log1/\delta$$ entries from the tensor product $$y_1\otimes y_2$$ suffices.

• The loss of $$(\log1/\delta)^3)$$ in method (3) seems to have at least one $$(\log1/\delta)$$ more than we would expect from RIP methods. However, the strongest RIP based analysis I know is Jin et al., which gets the same $$\epsilon^{-2}(\log1/\delta)^3$$ dependency.

• The Tensor Sketches mentioned are all "oblivious" in that they apply the same linear transformation to any $$x\in\mathbb R^{k^2}$$, even if it computes it more efficiently for tensor products. There are Tensor Sketch methods which are non-oblivious (such as Wang et al.), but their embedding guarantees are no better.