# Understand rough path iterated integral and how to compute it numerically?

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?

$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 or the documents linked from this.)

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$.

• Thanks, after all these days, finally one answer!My problem is, I can understand the integral representation, but I have no idea how to compute it numerically? Any suggestion? – Jedi Jun 2 '15 at 7:42
• I have added specific working in the piecewise linear case, which is the obvious case where it can be calculated numerically. – JeremyR Jun 2 '15 at 13:35
• Better way to explain this is to use the Hopf algebra in context of rough paths theory see for example this paper arxiv.org/pdf/math/0610300.pdf – Zbigniew Nov 14 '16 at 11:17
• May I request to show a numerical example for one dimensional case. Say N=3 and points are (1,5),(2,9) and (3,4). – Creator Aug 6 '18 at 22:41
• Do you mean the length of the upper index should never be less than one? In this way I'm using ellipses, (j_1,...,j_h) is the empty tuple when h=0. Similar to the way \sum_{i=1}^0 doesn't sum anything. – JeremyR Aug 9 '18 at 8:37