= All-subsequence embedding kernel
{title2=$K(x,y)=\sum_u\phi_u(x)\phi_u(y)$}
Here $\phi_u(x)$ counts increasing position embeddings of the word $u$ as a <subsequence> of $x$. Counting embeddings retains repeated-letter multiplicities. The empty word has one embedding in every string. Prefix <dynamic programming> computes this <positive-semidefinite kernel> by $F(i,j)=F(i-1,j)+F(i,j-1)-F(i-1,j-1)+\mathbf1_{\{x_i=y_j\}}F(i-1,j-1)$ with boundary values one. The <time complexity> is $O(|x||y|)$ arithmetic operations, and rolling rows require $O(\min(|x|,|y|))$ integer cells. Counting pairs of position subsets bounds output bit length by $O(|x|+|y|)$.
Back to article page
