This site contains mathematics courses and book drafts and provides image analysis software. Created and run by Peter Saveliev.

Discrete differential forms

From Intelligent Perception

Jump to: navigation, search

What are discrete differential forms are and why do we need them?

1 How do we approximate continuous processes?

Suppose we have a function, $f$:

Graph of function.png

Suppose also that we know only as a "sampled" function, i.e., we only know its values at, say, 0, 1, 2, 4, 5... Suppose that the derivative, $f'$, of the function is also sampled:

DiscreteForms1.png

For example, $f$ might be the position, $f'$ the velocity. It's like you look at your odometer and speedometer once in a while, so that you measure the position and velocity at equal intervals. Then we have instead two new functions: $g$ and $g'$, which we may call "discrete functions":

DiscreteForms2.png

Then it would make sense if $g'$ was the derivative of $g$, in some way.

But the functions are discrete, so there is no derivative...

Question: How can we establish such a relation between them without actual differentiation?

Answer: We use the Fundamental Theorem of Calculus.

Recall the Riemann integral: $$g(8)-g(0) \stackrel{?}{=} \displaystyle\int_0^8 g'(x) dx.$$ Here the right-hand side is the "displacement".

Meanwhile, in order to integrate, let's turn $g'$ into a step function:

Integrate discrete velocity.png

By example, $$g(8)-g(0) =10$$ but $$\displaystyle\int_0^1 g'(x)dx \approx 0.2+0.4+0.5+0.7+0.8+1+1.7+2.9+4 =12.2.$$ The right-hand side only approximates the integral, so, in general, there is a mismatch.

Then the laws of physics are in danger as they are satisfied only approximately! Just consider the conservation of energy...

Of course, if the sampling is improved by taking more sample values (we look at the dials more often), then the approximation improves and, mathematically, the Riemann sums converge to the Riemann integral.

That's a good news.

However, we still have an issue to deal with.

Question: What about convergence of the approximation of the velocity? Suppose $f_n \rightarrow f$, does it mean that $f'_n \rightarrow f'$?

Answer: No.

As an example, consider the famous Weierstrass function: $$f(x) = \displaystyle\sum_{n=0}^{\infty} a^n cos(b^n \pi x); 0 < a < 1.$$ This series converges uniformly, so $f$ is continuous. But if $b > 1 + \frac{a}{2} \pi$, $f$ is nowhere differentiable. (For another example, consider the issue of lengths of curves in the digital domain.)

To summarize...

  • Any given approximation violates both the laws of calculus and the laws of physics.
  • Improving the approximation won't necessarily capture the process being approximated.

So what do we do?

2 Discrete forms

Idea: build the discrete calculus via discrete differential forms that mimic the continuous forms.

We need a replacement for the derivative then.

What if we choose, for $g'$, secant lines instead of tangent lines?

DiscreteForms3.png

Then

  • $g$ is the sampled $f$, as before, but
  • $g'$ is the slopes on the secant lines.

Observe that the velocity is absent here. It's like we have decided not to look at the odometer at all!

Now the key step: where should $g'$ be defined?

Rather then defining $g'$ at the end point of the intervals: $\{0, 1, 2...\}$, as for $g$, we "expand" $g'$ to the intervals, as a step function (green): $g(x)=0$ on $(0,1)$, $g(x)=1$ on $(1,2)$, etc.

Position and velocity discrete.png

Then the Fundamental Theorem of Calculus works!

Indeed: $$\begin{align*} g(1)-g(0) &= \displaystyle\int_0^1 g'(x) dx {\rm \hspace{6pt} \longrightarrow match!} \\ 0.3 &= 0.3 \end{align*}$$

$$\begin{align*} g(2)-g(1) &= \displaystyle\int_1^2 g'(x) dx {\rm \hspace{6pt} \longrightarrow match!} \\ .4 &= .4 \end{align*}$$

How could it not?..

This is what we end up with:

$g$ $g'$
$\{0, 1, 2, 3\}$ $\{[0,1],[1,2],[2,3]\}$ $\longleftarrow$ the domain
points intervals $\longleftarrow$ nature of the domain
$0$ $1$ $\longleftarrow$ dimension of the domain
$0$-form $1$-form $\longleftarrow$ terminology

There you have it, differential forms!

Let's make a couple of observations about this model.

First, the model of motion is fully realistic as the velocity may remain constant over periods of time.

Second, the motion is captured by the $0$-form that provides the location at every instant of the chosen sequence while we think of the intermediate locations as unknown or unimportant.

Third, the motion can be reconstructed from the $1$-form (and the initial location). One needs this information, no more and no less.

Let's compare these to continuous forms.

Recall that differential forms are multilinear antisymmetric functions on real vectors with real values, parametrized by location in ${\bf R}^n$: $$\varphi =\varphi ^k: {\bf R}^n \times ({\bf R}^n)^k \rightarrow {\bf R}.$$ The examples above suggest that discrete forms should be multilinear antisymmetric functions on integer vectors with integer (or possibly real) values, parametrized by location in ${\bf Z}^n$: $$\varphi =\varphi ^k: {\bf Z}^n \times ({\bf Z}^n)^k \rightarrow {\bf Z}.$$ From this point of view,

Now observe that given a point $a \in {\bf Z}^n$ on the grid, $k$ vectors $v_1,...,v_k \in {\bf Z}^n$ of length $1$ will define a (possibly degenerate) $k$-cell. Therefore, we can think, informally, of a discrete (cubical) $k$-form as a continuous differential form, the coefficients of which are

  • constant on open $k$-cells and
  • undefined elsewhere.

The former condition indicates that the discrete forms change abruptly as you move from cell to cell. Think of it as if instead of $x dx$ you have $1 dx$ on one cell, $2 dx$ on the next etc.

Recall this about smooth forms in ${\bf R}^3$:

$0$-forms: a function $A$
$1$-forms: $\varphi = A dx + B dy + C dz$, the dot product $(A,B,C) \cdot (dx,dy,dz)$ (only $A dx + B dy$ in ${\bf R}^2$)
$2$-forms: $\varphi = A dx \hspace{1pt} dy + B dy \hspace{1pt} dz + C dz \hspace{1pt} dx$ (only $A dx \hspace{1pt} dy$ in ${\bf R}^2$)
$3$-forms: $\varphi = A dx \hspace{1pt} dy \hspace{1pt} dz$ (only $0$ in ${\bf R}^2$)

Now, discrete forms are no different except there will be restrictions on $A, B, C$: they are constant on the cells.

The multilinearity can be seen as $\varphi(\lambda a)=\lambda \varphi(a)$. This identity in the case of discrete forms uses the idea of multiples (and even linear combinations) of cells. They are called "chains".

3 Geometric interpretation

What is the main difference?

The grid: the Euclidean space is divided into small, disjoint parts. Within each of the piece, the form is unchanged, i.e., it's just a number.

In dimension $1$, these parts are: points and intervals.

  • $...,-3,-2,-1,0,1,2,3...$ are the $0$-cells;
  • $...,(-2,-1),(-1,0),(0,1),(1,2),(2,3),...$ are the $1$-cells.

In dimension $2$, these parts are: points, intervals, and squares ("pixels").

DiscreteFormGridDim2.png

Specifically, in dimension 2 we have:

  • $0$-cells: $\{(0,0)\}, \{(0,1)\}, \ldots,$
  • $1$-cells: $(0,1) \times 0$, $0 \times (0,1),\ldots,$
  • $2$-cells: $(0,1) \times (0,1),\ldots.$

The main thing to remember:

A cubical $k$-form is defined on $k$-cells, only.

As follows:

DiscreteKFormKCell.png

Consider these examples of forms below. Notice how each cell is assigned two symbols: one is its name (a latter) and the other is the value of the form at that location (a number): $f(A)=5$.

space: defined on: graphical representation (letters are the names of the cells): algebra:
${\bf R}^1$ $0$-cells ExamplesDiscreteFormsDim10Cell.png ... $0$-form $\varphi$ $\varphi(A)=3$, $\varphi(B)=5, \ldots$
${\bf R}^1$ $1$-cells ExamplesDiscreteFormsDim11Cell.png ... $1$-form $\psi$ $\psi(a)=5$, $\psi(b)=3, \ldots$
${\bf R}^2$ $0$-cells ExamplesDiscreteFormsDim20Cell.png ... $0$-form $\varphi$ $\varphi(A)=0$, $\varphi(B)=1, \ldots$
${\bf R}^2$ $1$-cells ExamplesDiscreteFormsDim21Cell.png ... $1$-form $\psi$ $\psi(a)=1$, $\psi(c)=8, \ldots$
${\bf R}^2$ $2$-cells ExamplesDiscreteFormsDim22Cell.png ... $2$-form $\theta$ $\theta(\alpha)=3$, $\theta(\beta)=5, \ldots$

Note that in the "algebra" column we no longer interpret the discrete forms as defined on points of each cell (constant) but simply as defined on each cell itself. This is called the cochain representation discussed later.

This is how we can connect this definition to the traditional representation of continuous differential forms. We use integral theorems for evaluation of the forms on each cell of appropriate dimension. For example, for $1$-forms on the plane we use the Fundamental Theorem of Calculus:

  • Given $\psi(a)=1$, then $\psi=1 dx$ on $a$ since $\int_a 1 dx=1$;
  • Given $\psi(c)=8$, then $\psi = 8 dy$ on $c$ since $\int_c 8 dy=8$;
  • etc.

We can even interpret this form in the old notation $$\psi = A dx + B dy,$$ where $A,B$ are functions defined on $1$-cells.

In the above table, complexes are given in the main column with cells double labelled: the names of cells and the corresponding values. Then these relations are written algebraically in the last column.

These are examples of $0$-, $1$-, and $2$-forms in Excel:

Forms in Excel.png