4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.