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.


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



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.