The "signature" of rough path theory is defined by iterated integral as  

$s(k)=\int\_{0 \le u\_1 \le \cdots \le u\_k \le t} \mathrm{d}X\_{u\_1} \otimes \cdots \otimes \mathrm{d}X\_{u\_k}$  

 in witch $X(t)$ is a $d$ dimensional rough path.
I'm new to tensor calculus, and still in struggle to figure out what the above equation actually means, and further more, to implement it numerically? 


Let me make the problem more specific:


* 1) $X(t)$ is a $d$ dimensional rough path, which will be represented by a matrix with $d$ rows and $N$ columns, each column is actually $X(t\_k)$;
* 2) $s(k)$ is a sequence of size $d^k-1$, of which each element is actually an integral of the following form:
 $s^{(j\_1,j\_2,...j\_k)}=\int\_{0 \le u\_1 \le \cdots \le u\_k \le t} \mathrm{d}x\_{j\_1}(u\_1)\mathrm{d}x\_{j\_2}(u\_2)\cdots\mathrm{d}x\_{j\_k}(u\_k)$, $j\_k\in(1,...,d)$


What confuses me is what $s^{(j\_1,j\_2,...j\_k)}$ actually means? And, since $X(t)$ is a $d\*N$ matrix, how come integrate along one dimension affect the integration along another dimension?



Understand rough path iterated integral and how to compute it numerically?
$s(k)$ is made of $d^k$ numbers. They are labelled by the k-tuple $(j\_1,j\_2,\dots j\_k)$ - and there are $d^k$ possibilities. 
For example, if $d$ is 3 and $k$ is 2, there are 9 values: $s^{(1,1)}$, $s^{(3,2)}$ etc.


For a concrete example, the value of $s^{(2,3)}$ is the integral $\int\_{0<u\_1<u\_2<t}\,dx\_2(u\_2)dx\_3(u\_1)$ or $\int\_0^t\int\_0^{u\_1}x\_2'(u\_2)x\_3'(u\_1)\,du\_2\,du\_1$ . I think you are using $x$ and $X$ for the same thing - the function from $[0,t]$ to $\mathbb{R}^d$ which defines the path. The numbers in the subscripts of $x$ in the integral determine which component of $s(k)$ is being calculated.


Let's say the path is piecewise linear between $N$ points, where $N>1$, and is specified as a $d \times N$ matrix $M$. $M$ is enough to calculate the signature - we don't need to know the exact speed the path is traversed, we don't need $t$ or $X$. Then let the signature of the straight path from the $i$th point to the $(i+1)$th point be $a\_i$. For any $k$, and any $(j\_1,\dots,j\_k)$, we know that the value of $(a\_i)^{(j\_1,\dots,j\_k)}$ is $\frac1{k!}\prod\_{h=1}^k(M\_{j\_h,i+1}-M\_{j\_h,i})$ by explicitly doing the integrals. 


Let the signature of the whole of the path from the first point up to the $(i+1)$th point be $b\_i$. We can calculate the value of $b\_i$ "up to level $K$" (i.e. for all tuples $(j\_1,\dots,j\_k)$ with $k\le K$) cumulatively in $i$, from the fact that $b\_1=a\_1$ and Chen's identity, which says that, for each $k$, and any $(j\_1,\dots,j\_k)$, $(b\_{i+1})^{(j\_1,\dots,j\_k)}=\sum\_{h=0}^k(b\_i)^{(j\_1,\dots\,j\_h)}(a\_{i+1})^{(j\_{h+1},\dots,j\_k)}$ . We then get the signature of the whole path, $b\_{N-1}$, up to level $K$.




---


Edit 2018 to add a specifically requested explicit example. (Note that we are still using some of the notation of the original question, which may not be the friendliest to read. Newcomers to the signature may prefer [this](https://arxiv.org/abs/1603.03788) or the documents linked from [this](https://github.com/bottler/iisignature).)


Consider the two-dimensional path from $(1,5)$ straight to $(2,9)$ straight to $(3,4)$. We have $N=3$ and $d=2$. Let's calculate its signature up to level $K=2$.


We have the following $a\_1^{()}=1$, $a\_1^{(1)}=1$, $a\_1^{(2)}=4$, $a\_1^{(11)}=\frac12$, $a\_1^{(12)}=a\_1^{(21)}=2$, $a\_1^{(22)}=8$.
Also we calculate $a\_2^{()}=1$, $a\_2^{(1)}=1$, $a\_2^{(2)}=-5$, $a\_2^{(11)}=\frac12$, $a\_2^{(12)}=a\_2^{(21)}=-\frac52$, $a\_2^{(22)}=\frac{25}{2}$.
We have $b\_1=a\_1$.
With Chen's identity we calculate $b\_2^{()}=b\_1^{()}a\_2^{()}=1$, $b\_2^{(1)}=b\_1^{()}a\_2^{(1)}+b\_1^{(1)}a\_2^{()}=2$, $b\_2^{(2)}=b\_1^{()}a\_2^{(2)}+b\_1^{(2)}a\_2^{()}=-1$,
$b\_2^{(11)}=b\_1^{()}a\_2^{(11)}+b\_1^{(1)}a\_2^{(1)}+b\_1^{(11)}a\_2^{()}=2$, $b\_2^{(12)}=b\_1^{()}a\_2^{(12)}+b\_1^{(1)}a\_2^{(2)}+b\_1^{(12)}a\_2^{()}=-\frac{11}{2}$, $b\_2^{(21)}=b\_1^{()}a\_2^{(21)}+b\_1^{(2)}a\_2^{(1)}+b\_1^{(21)}a\_2^{()}=\frac72$, $b\_2^{(22)}=b\_1^{()}a\_2^{(22)}+b\_1^{(2)}a\_2^{(2)}+b\_1^{(22)}a\_2^{()}=\frac{1}{2}$.
The signature we are aiming for is $b\_2$.


