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 M ∈ R k × d {\displaystyle M\in \mathbb {R} ^{k\times d}} , where k < d {\displaystyle k<d} , such that for any vector x ∈ R d {\displaystyle x\in \mathbb {R} ^{d}}
| ‖ M x ‖ 2 − ‖ x ‖ 2 | < ε ‖ x ‖ 2 {\displaystyle |\|Mx\|_{2}-\|x\|_{2}|<\varepsilon \|x\|_{2}}
with high probability. In other words, M {\displaystyle M} preserves the norm of vectors up to a small error. A tensor sketch has the extra property that if x = y ⊗ z {\displaystyle x=y\otimes z} for some vectors y ∈ R d 1 , z ∈ R d 2 {\displaystyle y\in \mathbb {R} ^{d_{1}},z\in \mathbb {R} ^{d_{2}}} such that d 1 d 2 = d {\displaystyle d_{1}d_{2}=d} , the transformation M ( y ⊗ z ) {\displaystyle M(y\otimes z)} can be computed more efficiently. Here ⊗ {\displaystyle \otimes } denotes the Kronecker product, rather than the outer product, though the two are related by a flattening. The speedup is achieved by first rewriting M ( y ⊗ z ) = M ′ y ∘ M ″ z {\displaystyle M(y\otimes z)=M'y\circ M''z} , where ∘ {\displaystyle \circ } denotes the elementwise (Hadamard) product. Each of M ′ y {\displaystyle M'y} and M ″ z {\displaystyle M''z} can be computed in time O ( k d 1 ) {\displaystyle O(kd_{1})} and O ( k d 2 ) {\displaystyle O(kd_{2})} , respectively; including the Hadamard product gives overall time O ( d 1 d 2 + k d 1 + k d 2 ) {\displaystyle O(d_{1}d_{2}+kd_{1}+kd_{2})} . In most use cases this method is significantly faster than the full M ( y ⊗ z ) {\displaystyle M(y\otimes z)} requiring O ( k d ) = O ( k d 1 d 2 ) {\displaystyle O(kd)=O(kd_{1}d_{2})} time. For higher-order tensors, such as x = y ⊗ z ⊗ t {\displaystyle x=y\otimes z\otimes t} , 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.
… excerpt ends here. Continue reading the full article.
