Tensor sketch

In statistics, machine learning and algorithms, a tensor sketch is a type of dimensionality reduction that is particularly efficient when applied to vectors that have tensor structure. Such a sketch can be used to speed up explicit kernel methods, bilinear pooling in neural networks and is a cornerstone in many numerical linear algebra algorithms.
Mathematical definition.
Mathematically, a dimensionality reduction is a matrix formula_1, where formula_2, such that for any vector formula_3 it holds that
with high probability.
In other words formula_5 preserves the norm of vectors up to a small error.
A Tensor sketch has the extra property that if formula_6 for some vectors formula_7 such that formula_8, the transformation formula_9 can be computed extra efficiently.
Typically formula_10, where formula_11 is the (Hadamard) elementwise product.
Since each of formula_12 and formula_13 can be computed in time respectively formula_14 and formula_15, the computation is much faster than the full formula_9 which would take time formula_17.
For higher-order tensors, such as formula_18 the savings are even more impressive.
History.
The term tensor sketch was coined in 2013 describing a technique by Rasmus Pagh from the same year.
Originally it was understood using the fast Fourier transform to do fast convolution of count sketches.
Later research works generalized it to a much larger class of dimensionality reductions via Tensor random embeddings.
Tensor random embeddings were introduced in 2010 in a paper on differential privacy and were first analyzed by Rudelson et al. in 2012 in the context of sparse recovery.
Avron et al.
were the first to study the subspace embedding properties of tensor sketches, particularly focused on applications to polynomial kernels.
In this context, the sketch is required not only to preserve the norm of each individual vector with a certain probability but to preserve the norm of all vectors in each individual linear subspace.
This is a much stronger property, and it requires larger sketch sizes, but it allows the kernel methods to be used very broadly as explored in the book by David Woodruff.
Tensor random projections.
The face-splitting product is defined as the tensor products of the rows (was proposed by V. Slyusar in 1996 for radar and digital antenna array applications).
More directly, let formula_19 and formula_20 be two matrices.
Then the face-splitting product formula_21 is
formula_22
The reason this product is useful is the following identity:
where formula_11 is the element-wise (Hadamard) product.
Since this operation can be computed in linear time, formula_25 can be multiplied on vectors with tensor structure much faster than normal matrices.
Construction with fast Fourier transform.
The tensor sketch of Pham and Pagh computes
formula_26, where formula_27 and formula_28 are independent count sketch matrices and formula_29 is vector convolution.
They show that, amazingly, this equals formula_30 – a count sketch of the tensor product!
It turns out that this relation can be seen in terms of the face-splitting product as
Since formula_32 is an orthonormal matrix, formula_34 doesn't impact the norm of formula_35 and may be ignored.
What's left is that formula_36.
On the other hand,
Application to general matrices.
The problem with the original tensor sketch algorithm was that it used count sketch matrices, which aren't always very good dimensionality reductions.
In 2020 it was shown that any matrices with random enough independent rows suffice to create a tensor sketch.
This allows using matrices with stronger guarantees, such as real Gaussian Johnson Lindenstrauss matrices.
In particular, we get the following theorem
In particular, if the entries of formula_38 are formula_50 we get formula_51 which matches the normal Johnson Lindenstrauss theorem of formula_52 when formula_53 is small.
The paper also shows that the dependency on formula_54 is necessary for constructions using tensor randomized projections with Gaussian entries.
Variations.
Recursive construction.
Because of the exponential dependency on formula_55 in tensor sketches based on the face-splitting product, a different approach was developed in 2020 which applies
We can achieve such an formula_5 by letting
With this method, we only apply the general tensor sketch method to order 2 tensors, which avoids the exponential dependency in the number of rows.
It can be proved that combining formula_55 dimensionality reductions like this only increases formula_53 by a factor formula_61.
Fast constructions.
The fast Johnson–Lindenstrauss transform is a dimensionality reduction matrix
Given a matrix formula_62, computing the matrix vector product formula_63 takes formula_64 time.
The "Fast Johnson Lindenstrauss Transform" (FJLT), was introduced by Ailon and Chazelle in 2006.
A version of this method takes
formula_65
where
The matrix-vector multiplication formula_69 can be computed in formula_70 time.
If the diagonal matrix is replaced by one which has a tensor product of formula_50 values on the diagonal, instead of being fully independent, it is possible to compute formula_76 fast.
For an example of this, let formula_77 be two independent formula_50 vectors and let formula_66 be a diagonal matrix with formula_80 on the diagonal.
We can then split up formula_76 as follows:
In other words, formula_83, splits up into two Fast Johnson–Lindenstrauss transformations, and the total reduction takes time formula_84 rather than formula_85 as with the direct approach.
The same approach can be extended to compute higher degree products, such as formula_86
Ahle et al. shows that if formula_87 has formula_88 rows, then formula_89 for any vector formula_90 with probability formula_46, while allowing fast multiplication with degree formula_55 tensors.
Jin et al., the same year, showed a similar result for the more general class of matrices call RIP, which includes the subsampled Hadamard matrices.
They showed that these matrices allow splitting into tensors provided the number of rows is formula_93.
In the case formula_94 this matches the previous result.
These fast constructions can again be combined with the recursion approach mentioned above, giving the fastest overall tensor sketch.
Data aware sketching.
It is also possible to do so-called "data aware" tensor sketching.
Instead of multiplying a random matrix on the data, the data points are sampled independently with a certain probability depending on the norm of the point.
Applications.
Explicit polynomial kernels.
Kernel methods are popular in machine learning as they give the algorithm designed the freedom to design a "feature space" in which to measure the similarity of their data points.
A simple kernel-based binary classifier is based on the following computation:
where formula_96 are the data points, formula_97 is the label of the formula_98th point (either −1 or +1), and formula_99 is the prediction of the class of formula_100.
The function formula_101 is the kernel.
Typical examples are the radial basis function kernel, formula_102, and polynomial kernels such as formula_103.
When used this way, the kernel method is called "implicit".
Sometimes it is faster to do an "explicit" kernel method, in which a pair of functions formula_104 are found, such that formula_105.
This allows the above computation to be expressed as
where the value formula_107 can be computed in advance.
The problem with this method is that the feature space can be very large. That is formula_108.
For example, for the polynomial kernel formula_109 we get formula_110 and formula_111, where formula_112 is the tensor product and formula_113 where formula_114.
If formula_115 is already large, formula_66 can be much larger than the number of data points (formula_117) and so the explicit method is inefficient.
The idea of tensor sketch is that we can compute approximate functions formula_118 where formula_119 can even be "smaller" than formula_115, and which still have the property that formula_121.
This method was shown in 2020 to work even for high degree polynomials and radial basis function kernels.
Compressed matrix multiplication.
Assume we have two large datasets, represented as matrices formula_122, and we want to find the rows formula_123 with the largest inner products formula_124.
We could compute formula_125 and simply look at all formula_126 possibilities.
However, this would take at least formula_126 time, and probably closer to formula_128 using standard matrix multiplication techniques.
The idea of Compressed Matrix Multiplication is the general identity
where formula_112 is the tensor product.
Since we can compute a (linear) approximation to formula_131 efficiently, we can sum those up to get an approximation for the complete product.
Compact multilinear pooling.
Bilinear pooling is the technique of taking two input vectors, formula_132 from different sources, and using the tensor product formula_133 as the input layer to a neural network.
In the authors considered using tensor sketch to reduce the number of variables needed.
In 2017 another paper takes the FFT of the input features, before they are combined using the element-wise product.
This again corresponds to the original tensor sketch.