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 or sketching matrix is a matrix formula_1, where formula_2, such that for any vector formula_3 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 more efficiently. Here formula_10 denotes the Kronecker product, rather than the outer product, though the two are related by a flattening. The speedup is achieved by first rewriting formula_11, where formula_12 denotes the elementwise (Hadamard) product. Each of formula_13 and formula_14 can be computed in time formula_15 and formula_16, respectively; including the Hadamard product gives overall time formula_17. In most use cases this method is significantly faster than the full formula_9 requiring formula_19 time. For higher-order tensors, such as formula_20, 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_21 and formula_22 be two matrices. Then the face-splitting product formula_23 is formula_24 The reason this product is useful is the following identity: where formula_12 is the element-wise (Hadamard) product. Since this operation can be computed in linear time, formula_27 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_28, where formula_29 and formula_30 are independent count sketch matrices and formula_31 is vector convolution. They show that, amazingly, this equals formula_32 – 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_34 is an orthonormal matrix, formula_36 doesn't impact the norm of formula_37 and may be ignored. What's left is that formula_38. 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_40 are formula_52 we get formula_53 which matches the normal Johnson Lindenstrauss theorem of formula_54 when formula_55 is small. The paper also shows that the dependency on formula_56 is necessary for constructions using tensor randomized projections with Gaussian entries. Variations. Recursive construction. Because of the exponential dependency on formula_57 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_57 dimensionality reductions like this only increases formula_55 by a factor formula_63. Fast constructions. The fast Johnson–Lindenstrauss transform is a dimensionality reduction matrix Given a matrix formula_64, computing the matrix vector product formula_65 takes formula_66 time. The "Fast Johnson Lindenstrauss Transform" (FJLT), was introduced by Ailon and Chazelle in 2006. A version of this method takes formula_67 where The matrix-vector multiplication formula_71 can be computed in formula_72 time. If the diagonal matrix  is replaced by one which has a tensor product of formula_52 values on the diagonal, instead of being fully independent, it is possible to compute formula_78 fast. For an example of this, let formula_79 be two independent formula_52 vectors and let formula_68 be a diagonal matrix with formula_82 on the diagonal. We can then split up formula_78 as follows: In other words, formula_85, splits up into two Fast Johnson–Lindenstrauss transformations, and the total reduction takes time formula_86 rather than formula_87 as with the direct approach. The same approach can be extended to compute higher degree products, such as formula_88  Ahle et al. shows that if formula_89 has formula_90 rows, then formula_91 for any vector formula_92 with probability formula_48, while allowing fast multiplication with degree formula_57 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_95. In the case formula_96 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_98 are the data points, formula_99 is the label of the formula_100th point (either −1 or  +1), and formula_101 is the prediction of the class of formula_102. The function formula_103 is the kernel. Typical examples are the radial basis function kernel, formula_104, and polynomial kernels such as formula_105. 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_106 are found, such that formula_107. This allows the above computation to be expressed as where the value formula_109 can be computed in advance. The problem with this method is that the feature space can be very large. That is formula_110. For  example, for the polynomial kernel formula_111 we get formula_112 and formula_113, where formula_114 is the tensor product and formula_115 where formula_116. If formula_117 is already large, formula_68 can be much larger than the number of data points (formula_119) and so the explicit method is inefficient. The idea of tensor sketch is that we can compute approximate functions formula_120 where formula_121 can even be "smaller" than formula_117, and which still have the property that formula_123. 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_124, and we want to find the rows formula_125 with the largest inner products formula_126. We could compute formula_127 and simply look at all formula_128 possibilities. However, this would take at least formula_128 time, and probably closer to formula_130 using standard matrix multiplication techniques. The idea of Compressed Matrix Multiplication is the general identity where formula_114 is the tensor product. Since we can compute a (linear) approximation to formula_133 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_134 from different sources, and using the tensor product formula_135 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.