text:
# Is there a function whose total variation is unbounded but its restricted variation (mesh converging to zero) is bounded?

Suppose $$f$$ is a bounded function on $$[a,b]$$, its total variation is defined to be $$\mathrm{Var}(f) = \sup_{\tau} \sum_{i=1}^{n} |f(x_{i})-f(x_{i-1})|.$$ Furthermore, if $$f$$ is continuous on $$[a,b]$$, it can be proved that $$\mathrm{Var}(f) = \lim_{|\tau|\to 0}\sum_{i=1}^{n} |f(x_{i})-f(x_{i-1})|,$$ where $$|\tau|$$ denotes the mesh of the partition $$\tau$$.

When $$f$$ is discontinuous, can anyone give a counterexample to the above equality, that is the total variation cannot always be calculated by letting the mesh approaching zero?

• If the limit exists then it is equal to the total variation. I don't know if there is an example where the limits does not exist. Apr 5, 2019 at 12:07
• The question asked in the title is different that the one in the main formulation.
– Hayk
Apr 17, 2019 at 15:59

To see that the limit and supremum in question might produce difference results define $$f:[0,1]\to[0,1]$$ as $$f(x) = \begin{cases} 0, &\text{ if } \ x \neq 1/2, \\ 1, &\text{ if } \ x = 1/2. \end{cases}$$ Clearly $$\mathrm{Var}(f) = 2$$, but any partition of $$[0,1]$$, with diameter however small, will result in $$0$$ variance-sum unless it includes the point $$1/2$$ in the partition of $$[0,1]$$.
• @C.Davide, if I understand you correctly, there cannot be a counterexample that is partition independent. This is because the $\sup$ itself is realized on a partition with diameter approaching to $0$. Indeed, notice that $\sup$ is a limit of some sequence of partitions. But for any partition of $[a,b]$ adding more points to it can only increase the variation-sum. Hence, WLOG, we may assume that the sequence of partitions realizing the $\sup$ has diameter converging to $0$. Thus, there is at least one sequence of partitions (meshes) with decaying diameter, that coincides with the $\sup$.

format: plain


text:
Top

# Pythagorean Identities

Pythagorean Identities are identities that are derived from the Pythagorean theorem. There are three important Pythagorean Identities.

sin2 x + cos2 x = 1

tan2 x + 1 = sec2 x

cot2x + 1 = csc2 x

We can derive all these trigonometric identities from any one of the others using simple algebraic equations.

 Related Calculators Pythagorean Calculator Pythagorean Triples Calculator Trig Identities Calculator

## Pythagorean Identities Proof

Proof of Pythagorean identities is given below:

Identity 1: sin$^2$x + cos$^2$x = 1

Proof:

In a Right-Angle Triangle ABC, let AC be the hypotenuse, AB be the opposite side, and BC be the adjacent side.

Then, sin x = $\frac{\text{opp}}{\text{hyp}}$ => $\frac{AB}{AC}$

cos x = $\frac{\text{adj}}{\text{hyp}}$ => $\frac{BC}{AC}$

Now,

sin2x + cos2x = $\frac{AB^2}{AC^2} + \frac{BC^2}{AC^2}$

= $\frac{AB^2 + BC^2}{AC^2}$

= $\frac{AC^2}{AC^2}$
[Using Pythagorean theorem ]

= 1

Therefore, sin2x + cos2x = 1.

Hence proved.

Identity 2: tan2x + 1 = sec2x

Proof:

Let us consider Identity 1, sin2x + cos2x = 1

Dividing the equation by cos2x,

$\frac{\sin^2x}{\cos^2x} + \frac{\cos^2x}{\cos^2x} = \frac{1}{\cos^2x}$

tan2x + 1 = sec2x

Hence proved.

Identity 3: 1 + cot2x = csc2x

Proof:

Let us consider Identity1, sin2x + cos2x = 1

Dividing the equation by sin2x,

$\frac{\sin^2x}{\sin^2x} + \frac{\cos^2x}{\sin^2x} = \frac{1}{\sin^2x}$

1 + cot2x = csc2x

Hence proved.

## Solving Pythagorean Identities

Given below are some of the examples in solving pythagorean identities.

### Solved Examples

Question 1:

In a triangle ABC, we have that sin X = $\frac{4}{5}$, what is the value of cos x?

Solution:

We have the basic trigonometric identity:

sin2 x + cos2 x = 1

In our case, we know sin x = $\frac{4}{5}$, so we replace in the previous equation to get:

cos2 x = 1 - $(\frac{4}{5})^2$

cos2 x = 1 - $\frac{16}{25}$ = $\frac{9}{25}$

cos x = $\frac{3}{5}$.

Question 2:

If csc x = $\frac{5}{3}$ and tan x = $\frac{3}{4}$, find the values of remaining trigonometric functions, using Pythagorean identity.

Solution:

Given:
csc x = $\frac{5}{3}$ and tan x = $\frac{3}{4}$

Step 1: We know, cot$^2$x + 1 = csc$^2$x

cot$^2$x + 1 = $(\frac{5}{3})^2$

cot$^2$x + 1 = $\frac{25}{9}$

cot$^2$x = $\frac{25}{9}$ - 1 = $\frac{16}{9}$

cot x = $\frac{4}{3}$

Step 2: tan$^2$x + 1 = sec$^2$x

$(\frac{3}{4})^2$ + 1 = sec$^2$x

$\frac{9}{16}$ + 1 = sec$^2$x

$\frac{25}{16}$ = sec$^2$x

or sec x = $\frac{5}{4}$

Step 3: sin x = $\frac{1}{csc\ x}$ = $\frac{1}{\frac{5}{3}}$ = $\frac{3}{5}$

=> sin x = $\frac{3}{5}$

Step 4: sin$^2$x + cos$^2$x = 1

$(\frac{3}{5})^2$ + cos$^2$x = 1

$\frac{9}{25}$ + cos$^2$x = 1

cos$^2$x = 1 - $\frac{9}{25}$ = $\frac{16}{25}$

cos x = $\frac{4}{5}$

## Pythagorean Identities Problems

Below are some solved examples using Pythagorean identities.

### Solved Examples

Question 1: Simplify the expression (1 - cos2x) (csc x) to a single trigonometric function.
Solution:

We know sin2x + cos2x = 1, 1 - cos2x = sin2x and cscx = $\frac{1}{\sin x}$

So, the function becomes, (sin2 x)$\frac{1}{\sin x}$ = sin x

=> (1 - cos2x) (csc x) = sinx

Question 2: Solve by using trigonometric functions : $\frac{\csc a \cos^2 a}{1 + \csc a}$
Solution:
$\frac{\csc a \cos^2 a}{1 + \csc a}$ =$\cos^2a$ $\frac{\frac{1}{\sin a}}{1 + \frac{1}{\sin a}}$ [ csc (a) = $\frac{1}{\sin(a)}$ ]

= $\frac{\cos^2a}{\sin a + 1}$

= $\frac{1 - \sin^2a}{\sin a + 1}$ [ Here, $cos^2a = 1 - sin^2a$ ]

= $\frac{(1 - \sin a)(1 + \sin a)}{\sin a + 1}$

= 1 - $\sin a$

Question 3: In a triangle ABC, we have that cos Y = $\frac{5}{13}$, what is the values of sin Y?
Solution:

We have the basic trigonometric identity, Sin2 A + cos2 A = 1

In our case, we know cos Y = $\frac{5}{13}$

sin2 Y = 1 - $(\frac{5}{13})^2$

sin2 Y = 1 - $\frac{25}{169}$ = $\frac{144}{169}$

sin Y = $\pm$ $\sqrt{\frac{144}{169}}$ = -$\frac{12}{13}$.

(Because cos Y is +ve, lies in lV quadrant. Value of sin Y is -ve in this quadrant.
)

 Related Topics Math Help Online Online Math Tutor
*AP and SAT are registered trademarks of the College Board.


text:
# Why should I avoid the For loop in Mathematica?

Some people advise against the use of For loops in Mathematica. Why? Should I heed this advice? What is wrong with For? What should I use instead?

• This comes up so often, I wanted to have something to link to. As always on StackExchange, other answers are welcome. – Szabolcs Jan 2 '17 at 14:40
• As, still, someone not that fluent in Mathematica, and a longtime programmer (mostly C), this was the most useful question/answer I've read - and I have read a bunch of these! Thanks to both the questioner and the responder. – Jack Adams Jan 3 '17 at 21:45
• Related (my own self Q&A): Alternatives to procedural loops and iterating over lists in Mathematica: "Explicit loops are often counterproductive in Mathematica, not only taking more keystrokes, but also more execution time. They are also, in my opinion, more prone to mistakes." – Mr.Wizard Jan 5 '17 at 9:30

If you are new to Mathematica, and were directed to this post, first see if you can use Table to solve your problem.

I have often told people, especially beginners, to avoid using For in favour of Do. The following is my personal opinion on why using For is harmful when learning Mathematica. If you are a seasoned Mathematica user, you won't find much to learn here. My biggest argument against For is that it hinders learning by encouraging error-prone, hard to read, and slow code.

For mimics the syntax of the for loop of C-like languages. Many beginners coming from such languages will look for a "for loop" when they start using Mathematica. Unfortunately, For gives them lots of ways to shoot themselves in the foot, while providing virtually no benefits over alternatives such as Do. Settling on For also tends to delay beginners in discovering more Mathematica-like programming paradigms, such as list-based and functional programming (Table, Map, etc.)

I want to make it clear at the beginning that the following arguments are not about functional vs procedural programming. Functional programming is usually the better choice in Mathematica, but procedural programming is also clearly needed in many situations. I will simply argue that when we do need a procedural loop, For is nearly always the worst choice. Use Do or While instead.

### Use Do instead of For

The typical use case of For is iterating over an integer range. Do will do the same thing better.

• Do is more concise, thus both more readable and easier to write without mistakes. Compare the following:

For[i=1, i <= n, i++,
f[i]; g[i]; h[i]
]

Do[ f[i]; g[i]; h[i], {i, n} ]

In For we need to use both commas (,) and semicolons (;) in a way that is almost, but not quite, the opposite of how they are used in C-like languages. This alone is a big source of beginner confusion and mistakes (possibly due to muscle memory). , and ; are visually similar so it is hard to spot the mistake.

• For does not localize the iterator i. A safe For needs explicit localization:

Module[{i},
For[i=1, i <= n, i++, ...]
]

A common mistake is to overwrite the value of a global i, possibly defined in an earlier input cell. At other times i is used as a symbolic variable elsewhere, and For will inconveniently assign a value to it.

In Do, i is a local variable, so we do not need to worry about these things.

• C-like languages typically use 0-based indexing. Mathematica uses 1-based indexing. for-loops are typically written to loop through 0..n-1 instead of 1..n, which is usually the more convenient range in Mathematica. Notice the differences between

For[i=0, i < n, i++, ...]

and

For[i=1, i <= n, i++, ...]

We must pay attention not only to the starting value of i, but also < vs <= in the second argument of For. Getting this wrong is a common mistake, and again it is hard to spot visually.

• In C-like languages the for loop is often used to loop through the elements of an array. The literal translation to Mathematica looks like

For[i=1, i <= n, i++,
doSomething[array[[i]]]
]

Do makes this much simpler and clearer:

Do[doSomething[elem], {elem, array}]

• Do makes it easy to use multiple iterators:

Do[..., {i, n}, {j, m}]

The same requires a nested For loop which doubles the readability problems.

### Transitioning to more Mathematica-like paradigms

A common beginner-written program that we see here on StackExchange collects values in a loop like this:

list = {};
For[i=1, i <= n, ++i,
list = Append[list, i^2]
]

This is of course not only complicated, but also slow ($O(n^2)$ complexity instead of $O(n)$). The better way is to use Table:

Table[i^2, {i, n}]

Table and Do have analogous syntaxes and their documentation pages reference each other. Starting out with Do makes the transition to Table natural. Moving from Table to Map and other typical functional or vectorized (Range[n]^2) constructs is then only a small step. Settling on For as "the standard looping construct" leaves beginners stuck with bad habits.

Another very common question on StackExchange is how to parallelize a For loop. There is no parallel for in Mathematica, but there is a ParallelDo and more importantly a ParallelTable. The answer is almost always: design the computation so that separate steps of the iteration do not access the same variable. In other words: just use Table.

### More general versions of For

For is of course in some ways more flexible than Do. It can express a broader range of iteration schemes. If you need something like this, I suggest just using While instead.

When we see for, we usually expect either a simple iteration through an integer range or through an array. Doing something else, such as modifying the value of the iterator in the loop body is unexpected, therefore confusing. Using While signals that anything can happen in the loop body, so the readers of the code will watch out for such things.

### When is For appropriate?

There are some cases when For is useful. The main example is translating code from other languages. It is convenient to be able to translate analogous for loops, and not have to think about what may be broken by immediately translating to a Do or a Table (e.g. does the loop modify the iterator in the body?). Once the translated code works fine, it can be rewritten gradually.

There are existing questions on this, which also discuss other cases:

### Summary

The problem with For is that it hinders learning and makes it very easy for beginners to introduce mistakes into their code.

If you are new to Mathematica, my advice is to forget that For exists, at least for a while. You can always accomplish the very same things with Do and While—use them instead. Very often you will be able to replace Do with a Table or even a vectorized expressions. This will help you learn to write effective Mathematica code faster.

If you are unsure about a use of For, then ask yourself: do I see a reason why For is clearly better here than Do or While? If not, don't use it. If yes, you may have found one of the rare good use cases.

• @Feyre It is, in several ways. And the jump from Table to vectorized computation is quite straightforward—another reason to use Do, which then leads to Table, which then leads to the paradigm you show. But there is only so much space in one post. I wrote this up so I can link to it when people ask why they are told to avoid For. – Szabolcs Jan 2 '17 at 15:05
• +1, but one nit. I've never understood how Table is considered more inline with a "functional" paradigm than For. There are obvious utilities with using Table/Do over For, but other languages have used similar forms for years, usually expressed as ForEach and c++ has gotten in on the act via the ranged for. – rcollyer Jan 2 '17 at 16:37
• Avoid For, Do is better. Avoid Do, Table is better. Avoid Table, Range^2 is better. When is it good enough? – DepressedDaniel Jan 2 '17 at 18:45
• @DepressedDaniel when our computations become fast enough to solve the most basic problems in Ramsey Theory ;) let's start with $R(5,5)$ and work from there... – Brevan Ellefsen Jan 2 '17 at 19:05
• "For does not localize the iterator i" -- that alone for me is a sufficient argument to avoid For. All the rest are good points, but mostly about style / readability whereas this one actually breaks the functional pattern (I strive to have as few assignments as possible in general) and may lead to hard-to-find bugs (as opposed to simple typo's that Mathematica will tell you about). – CompuChip Jan 3 '17 at 13:17

Illustration of the timings required to compute the squares i^2 from i=1 to i=10^n for n=1, 2, ..., 7 with the use of For, While, Do, Table, and Range.

for = Table[
Module[{i},
For[i = 1, i <= 10^n, i++, i^2] // AbsoluteTiming // First
]
, {n, 1, 7}]

while = Table[
Module[{i},
i = 1; While[i <= 10^n, i^2; i++] // AbsoluteTiming // First
]
, {n, 1, 7}]

do = Table[Do[i^2, {i, 10^n}] // AbsoluteTiming // First, {n, 1, 7}]

table = Table[
Table[i^2, {i, 10^n}]; // AbsoluteTiming // First, {n, 1, 7}]

range = Table[Range[10^n]^2; // AbsoluteTiming // First, {n, 1, 7}]

(By the way, look how concise are the codes of Do, Table and Range compared to For and While.)

The timings for 10^7 squares (i.e., n=7):

Last /@ {for, while, do, table, range}

{7.32907, 8.23668, 2.44558, 0.132735, 0.036395}

And a plot (vertical axis in log-scale):

ListLogPlot[{for, while, do, table, range}, Frame -> True,
PlotRange -> All, Joined -> True, ImageSize -> 400,
FrameLabel -> {"n", "Log[AbsoluteTiming] (sec)"},
PlotLabels -> {"For", "While", "Do", "Table", "Range"}]

Do is about $3\times$ faster than For/While; for this particular application, one could (and should) employ Table/Range, which are two orders of magnitude faster than For.

• Not sure that's a fair comparison, because: (1) Do, for example, throws away everything calculated (returning Null) whereas Table, for example, actually returns the list of squares; and (2) calculating i^2 is relatively trivial and misleadingly magnifies the effect of the looping construct used. – murray Jan 2 '17 at 16:51
• @murray I've made it a community wiki; feel free to improve. – corey979 Jan 2 '17 at 16:53
• @murray In general, you are right: one of the things the benchmark shows is the performance of the looping construct itself, as i^2 is so fast. In more typical uses it is the speed of looping that is negligible compared to the loop body. But there's more here: Table is fast because of auto-compilation. Auto-compilation is possible because of the functional nature of Table: each element of the table is computed independently of the others and usually without side effects. – Szabolcs Jan 3 '17 at 11:32
• @murray In contrast, each evaluation done by Do will have side effects, otherwise it would be pointless. Usually, that side effect is changing the same global variable (e.g. accumulating a sum), which makes the evaluations non-independent. Thus Do does not auto-compile. Similarly, Table is immediately parallelizable while Do isn't. My original answer wasn't simply about performance. There's much more to it: readability, manageability, etc. But I think it is true that using For can significantly hinder performance. Of course this applies to Mathematica only, not other languages. – Szabolcs Jan 3 '17 at 11:32
• +1 for actual science, even if a microbenchmark-y one – user11734 Jan 3 '17 at 14:40

The functional paradigm, exemplified by this code:

Map[(#^2) &, Range[10^7]] // AbsoluteTiming

will usually result in the fastest execution because it takes advantage of the architecture of the machine. Both the CPU and the memory are optimized for sequential access, so when you pass a function over a list of data to transform that data, the code stays in one place, taking advantage of locality (no code-cache misses), and the data is accessed as one continuous stream of bytes. The above line of code takes 0.281 seconds to complete on my computer, while the line below ran for well over an hour and only produced a list 1,190,218 elements long:

out = {};
For[i = 1, i <= 10^7, ++i, AppendTo[out, i^2]] // AbsoluteTiming

• The fastest way is in fact using array arithmetic (i.e. "vectorization"): Range[10^7]^2. Map needs to evaluate Mathematica code for each element, which is slower than handling the entire array with a low-level implementation. To be precise, Map will auto-compile #^2&, which gives a considerable speedup. But it is still not competitive with parallelized array arithmetic that makes use of SIMD instructions. – Szabolcs Apr 5 '17 at 16:59
• But generally you are correct. If this were not something that can be expressed with basic vector arithmetic, then Map would be a good way. It is only purely numerical operations on packed arrays that will benefit for vectorization. – Szabolcs Apr 5 '17 at 17:31


text:
# Example of fancy table using TikZ package

Can anyone share me several fancy table templates? I want to make this thread like a reference so that each time I need a template, I could just go here. If you can, please provide a screenshot for illustrative purpose. Thanks in advance ;)

-
have you tried googling? this one pops up readily: texblog.net/latex-archive/graphics/tikz-table –  prettygully Sep 11 '11 at 6:29
Yeah, I found these two tables. However my goal is not just two, I want the whole collection so that I can look it up later. –  Chan Sep 11 '11 at 20:45

Here's an example which I wrote for my TeX blog. It defines a matrixtable environment which uses the TikZ matrix of nodes feature.

\documentclass[svgnames]{beamer}
[top=blue!1,bottom=blue!30]
\usepackage{tikz}
\usetikzlibrary{matrix}
\newcommand*\up{\textcolor{YellowGreen}{$\blacktriangle$}}
\newcommand*\down{\textcolor{Red}{$\blacktriangledown$}}
\newcommand*\const{\textcolor{darkgray}{\textbf{--}}}
\newenvironment{matrixtable}[4]{%
\begin{tikzpicture}[matrix of nodes/.style={
execute at begin cell=\node\bgroup\strut,
execute at end cell=\egroup;}]
\matrix (m) [matrix of nodes,top color=blue!20,
bottom color=blue!80,draw=white,
nodes={draw,top color=blue!10,bottom color=blue!35,
draw,inner sep=2pt,minimum height=3.1ex},
column sep=1ex,row sep=0.6ex,inner sep=2ex,
rounded corners,column 1/.style={minimum width=#1},
column 2/.style={minimum width=#2},
column 3/.style={minimum width=#3},
column 4/.style={minimum width=#4}]}%
{;\end{tikzpicture}}
\begin{document}
\begin{frame}[fragile,bg=lightgray]
\begin{center}
\begin{matrixtable}{1.2cm}{2.4cm}{1.2cm}{0.6cm}{
1 & Ubuntu    & 2114 & \down  \\
2 & Fedora    & 1451 & \up    \\
3 & Mint      & 1297 & \const \\
4 & OpenSUSE  & 1228 & \up    \\
5 & Debian    & 910  & \down  \\
6 & Mandriva  & 907  & \up    \\
7 & PCLinuxOS & 764  & \up    \\
8 & Puppy     & 738  & \up    \\
9 & Sabayon   & 671  & \up    \\
10 & Arch      & 625  & \down  \\
}
\end{matrixtable}
\end{center}
\end{frame}
\end{document}

-
The table looks awesome, Stefan! Great work! –  Paulo Cereda Sep 11 '11 at 10:05

The table from my answer to coloring every other row of a table, with vertical lines is not extremely fancy, but could come in useful in some cases:

\documentclass{article}
\usepackage{tikz}
\usetikzlibrary{matrix}
\begin{document}

\tikzset{
table/.style={
matrix of nodes,
row sep=-\pgflinewidth,
column sep=-\pgflinewidth,
nodes={
rectangle,
draw=black,
align=center
},
minimum height=1.5em,
text depth=0.5ex,
text height=2ex,
nodes in empty cells,
%%
every even row/.style={
nodes={fill=gray!20}
},
column 1/.style={
nodes={text width=2em,font=\bfseries}
},
row 1/.style={
nodes={
fill=black,
text=white,
font=\bfseries
}
}
}
}

\begin{tikzpicture}

\matrix (first) [table,text width=6em]
{
& Monday   & Tuesday & Wednesday & Thursday & Friday\\
1   & A & B & C & D & E \\
2   & F & G & H & J & K \\
3   & A & B & C & D & E \\
4   & F & G & H & J & K \\
};

\end{tikzpicture}
\end{document}

-
Thanks a lot, your table is so elegant ;). –  Chan Sep 11 '11 at 20:46
Wait, why I find that in the first row, the texts are not really centred. Did you notice that? –  Daniel May 10 '13 at 19:04

Another example, which combines a tabularx environment with a TikZ picture, drawing on its background layer.

\documentclass{beamer}
\usetheme{default}
\usepackage{amsmath}
\usepackage{tabularx}
\usepackage{booktabs}
\usepackage{colortbl}
\usepackage{tikz}
\usetikzlibrary{calc}
\pgfdeclarelayer{background}
\pgfdeclarelayer{foreground}
\pgfsetlayers{background,main,foreground}
[top=blue!1,bottom=blue!30]
\newcommand*\up{\textcolor{green}{%
\ensuremath{\blacktriangle}}}
\newcommand*\down{\textcolor{red}{%
\ensuremath{\blacktriangledown}}}
\newcommand*\const{\textcolor{darkgray}%
{\textbf{--}}}
\begin{document}
\begin{frame}[bg=lightgray]
\textbf{\Large Linux distribution ranking,
26th August 2009}
\begin{center}
\begin{tikzpicture}
\node (tbl) {
\begin{tabularx}{.6\textwidth}{cXrcc}
\arrayrulecolor{purple}
\textbf{Rank} & \textbf{Distribution} &
\textbf{Hits} & \\
1 & Ubuntu\rule{0pt}{2.5ex}  &  2114 & \down \\
\midrule
2 & Fedora & 1451 & \up \\
\midrule
3 & Mint & 1297 & \const \\
\midrule
4 & OpenSUSE & 1228 & \up \\
\midrule
5 & Debian & 910 & \down \\
\midrule
6 & Mandriva & 907 & \up \\
\midrule
7 & PCLinuxOS & 764 & \up \\
\midrule
8 & Puppy & 738 & \up \\
\midrule
9 & Sabayon & 671 & \up \\
\midrule
10 & Arch & 625 & \down \\[0.5ex]
\end{tabularx}};
\begin{pgfonlayer}{background}
\draw[rounded corners,top color=red,bottom color=black,
draw=white] ($(tbl.north west)+(0.14,0)$)
rectangle ($(tbl.north east)-(0.13,0.9)$);
\draw[rounded corners,top color=white,bottom color=black,
middle color=red,draw=blue!20] ($(tbl.south west) +(0.12,0.5)$) rectangle ($(tbl.south east)-(0.12,0)$);
\draw[top color=blue!1,bottom color=blue!20,draw=white]
($(tbl.north east)-(0.13,0.6)$)
rectangle ($(tbl.south west)+(0.13,0.2)$);
\end{pgfonlayer}
\end{tikzpicture}
\end{center}
\small
Data by DistroWatch.com, spanning over the last 6 months,
hits per day.
\end{frame}
\end{document}

-
I use fancy chapter from texblog.net/latex-archive/layout/fancy-chapter-tikz, the chapter is in example memoir chapter style (documentation 2010) too and I customize some. the result is great. thanks Stefan Kottwitz. –  Verly Sep 11 '11 at 12:43
@Stefan Kottwitz: Many thanks, great one ;) –  Chan Sep 11 '11 at 20:45
@Stefan Kottwitz: IMHO that one is the best of the examples. But maybe you could change the text color of the head, because black text on red to black color gradient is unreadable. –  Schweinebacke Nov 8 '11 at 9:02


text:
# Tag Info

Plane curves are continuous (or smooth) functions $\gamma\colon I\to\mathbb R^2$ from a real interval to the plane. Sometimes also the image $\gamma(I)$ is called curve.


text:
What happens at this part in the key schedule of a Speck...?

I am trying to figure out the process behind the Speck block cipher. I understand how XOR works (Exclusive-or) when you take 2 strings of bits and you want to XOR them together.

However, in the key schedule of the cipher, there is a point where XOR takes place but I don t understand what is being XORed.

For example, in the key schedule in the link, the result of the binary addition is being XOR d with 0?

Can someone explain what this means? Thanks.

• It is round counter Sep 9, 2018 at 15:01

It's very simple: In the key schedule, the exclusive-or step after the addition is done with the round counter, and the round counter starts at $0$ rather than $1$.
So for round number $0$, the first exclusive-or is done with the value $0$. In the next round, the exclusive-or is done with the value $1$, and so forth.


text:
# Why are Euler's equations of motion coupled? Physical explanation

I have a problem with one of my study questions for an oral exam:

Euler’s equation of motion around the $z$ axis in two dimensions is $I_z\dot{\omega}_z = M_z$, whereas it in three dimensions is $I_z\dot{\omega}_z =-(I_y-I_x)\omega_x\omega_y+M_z$, assuming that the $xyz$ coordinate systems is aligned with the principal axis. Why does Euler’s equation of motion for axis $z$ contain the rotational velocities for axes $x$ and $y$?

How can one explain this physically? I mean I can derive Euler's equation of motion, but how can I illustrate that the angular velocities are changing in 3 dimensions?

## 2 Answers

As explained on Wikipedia, the nice tensor form of the equations is $$\mathbf{I} \cdot \dot{\boldsymbol\omega} + \boldsymbol\omega \times \left( \mathbf{I} \cdot \boldsymbol\omega \right) = \mathbf{M}$$ This reduces to your equations if one diagonalizes the tensor of the moment of inertia $I$ and labels the diagonal entries etc.

The three components are mixed with each other because quantities like $\vec\omega$ and $\vec M$ are really associated with rotations in space and rotations around the axis $x,y,z$ don't commute with each other – unlike translations. Translations commute with each other which is why the 3 components in $\vec F=m\vec a$ don't mix with each other.

For example, take the Earth, rotate it by 90 degrees around the $x$ axis, then 90 degrees around $y$ axis, then you rotate back by 90 degrees but first around $x$ axis again, so that you aren't undoing the $y$ rotation immediately, but then you undo the $y$ rotation, too. You don't get back where you have been: instead, you end up rotating the Earth around the $z$ axis. We say that rotations form the group $SO(3)$ which is non-abelian, $gh\neq hg$. The moment of force wants to rotate the rigid body around an axis but because it was already rotating around another axis given by $\vec \omega$ and the rotations don't commute with each other, the effect of the moment of force also influences the "remaining third" component.

A natural way to write the vectors $\vec \omega, \vec M$ is actually an "antisymmetric tensor" – they're "pseudovectors", not actual vectors. At any rate, when you correctly derive the equations, you should reproduce what Euler got.

• It might be good (although this is a very old question and the OP may already have done Nobel-earning work by now!) to point out that the $\boldsymbol\omega \times \left( \mathbf{I} \cdot \boldsymbol\omega \right)$ term is in fact the commutator $[\boldsymbol\omega ,\, \left( \mathbf{I} \cdot \boldsymbol\omega \right)]$ in the Adjoint representation, thus making the comparison with $\vec{F}=m\,\vec{a}$ precise. – WetSavannaAnimal Mar 11 '17 at 10:14
• What kind of a commutator? What is the algebra you are working with? Is your comment more than just the confusing renaming of the cross product as a "commutator"? – Luboš Motl Mar 11 '17 at 16:13
• Sorry to cause confusion. What I mean: if your using the Adjoint representation of $SU(2)$ to analyze rotations, then of course your rotation of $X\in\mathfrak{su}(2)$ is $X\mapsto \gamma\,X\,\gamma^{-1}$. So now let $X(t),\,Y(t) \in\mathfrak{su}(2)$ stand for spatial vectors in two relatively rotating frames linked by $\gamma(t)\in SU(2)$, then $Y=\gamma\,X\,\gamma^{-1}$ and $\dot{Y} = \gamma\,\left(\dot{X} + [\Omega,\,X]\right)\,\gamma^{-1}$, where $\Omega =\gamma^{-1}\,\gamma\in\mathfrak{su}(2)$ is the bivector representing the instantaneous angular velocity. $\dot{X} + [\Omega,\,X]$ ... – WetSavannaAnimal Mar 12 '17 at 0:09
• ... is of course the usual cross product formula $\mathrm{d}_t \mapsto \mathrm{d}_t + \omega\times$ for time derivatives in relatively rotating frames.Do the same thing for the Euclidean group's Adjoint representation, and the corresponding commutator term is nontrivial for rotations but vanishes for translations. Sorry to cause confusion: my supervisor Prof. John Stillwell was fond of calling $\mathfrak{su}(2)$ the cross product algebra for this reason and I'm not sure how widespread that is. More abstractly, although renaming the cross product a commutator would be confusing and .... – WetSavannaAnimal Mar 12 '17 at 0:23
• ...although that's not what I mean here, it wouldn't be too outlandish: the cross product is an abstract Lie bracket, in being billinear, skew-symmetric, and fulfilling the Jacobi identity. Construct a matrix representation thereof (always exists by these properties alone by Ado's theorem, but dead easy to write down from the cross product definition), exponentiate and the cross product thus defines $SO(3)$. – WetSavannaAnimal Mar 12 '17 at 0:26

If you are familiar aircraft flight dynamics, then please remember an aerobatic maneuver so called "Immelmann turn". Let us take x,y and z axis for longitudinal, lateral and vertical coordinate axes fixed to the aircraft. Then, if we pull control a stick and let the aircraft turn in vertical plane around the y axis and turn the stick to the right or left and make a rolling motion around the x axis at the same time. When the both two angular motion accomplished 180 degree turn, then the aircraft flies in the opposite direction before this maneuver. This means that the aircraft turned 180 degree around the z axis. This is my interpretation of the Euler equation of rigid body motion.


text:
Taylor Series Approximation

Homework Statement

Hi!

I have a couple of problems on Taylor Series Approximation.

For the following equations, write out the second-order Taylor‐series approximation.
Let x*=1 and, for x=2, calculate the true value of the function and the approximate value given by the Taylor series approximation.

f(x)=(x0.5-1)/0.5
f(x)=(x-1)2

The Attempt at a Solution

I was able to do the approximation at x=1 for the first problem. However, for the second problem, the second derivative yields a constant meaning that I cannot plug in x=1. What should I do in this case?

I do not understand the following direction:

"for x=2, calculate the true value of the function and the approximate value given by the Taylor series approximation."

P.S. I am sorry - I don't know how to paste formulas within this message, thus, I have to attach a Word document.

Attachments

• First Problem.doc
118.5 KB · Views: 132
• Second Problem.doc
78 KB · Views: 143

have you learned about binomial series? If you have you can solve the second problem with it without even thinking much if you know about binomial series and just get the right answer that way.

(1 + x)^p = summation from k=0 to ∞ of (p chose k)x^k

wait nvm i don't think that will work
oh actually ya i think you can manipulate it so that way it will

oh my bad you want the power series not taylor series...
so than just do from k=0 to k=2

sorry i forgot how to do the Taylor series and just recalled the summation for (1+x)^p as a power series. You get to the point were you just do these problems so much it's just best to remeber some of the easier ones...

I'm kinda rusty on this stuff lol

look up power series of (1+x)^p as a power series and just do from k=0 to k=2
you can also just put the equation in wolfram alpha to get the answer =O
note that you still have to figure out why the answer is correct =P

P.S. I think there's some other way to do this that I forgot about

but if f(x)=constant
then f(2) = constant
it's not a problem

Last edited:
Ray Vickson
Homework Helper
Dearly Missed

Homework Statement

Hi!

I have a couple of problems on Taylor Series Approximation.

For the following equations, write out the second-order Taylor‐series approximation.
Let x*=1 and, for x=2, calculate the true value of the function and the approximate value given by the Taylor series approximation.

f(x)=(x0.5-1)/0.5
f(x)=(x-1)2

The Attempt at a Solution

I was able to do the approximation at x=1 for the first problem. However, for the second problem, the second derivative yields a constant meaning that I cannot plug in x=1. What should I do in this case?

I do not understand the following direction:

"for x=2, calculate the true value of the function and the approximate value given by the Taylor series approximation."

P.S. I am sorry - I don't know how to paste formulas within this message, thus, I have to attach a Word document.

Why do you say you can't plug in x = 1 in the second case? What prevents you from substitution x = 1 in the formula f''(x) = 2 (for all x)?

RGV

Why do you say you can't plug in x = 1 in the second case? What prevents you from substitution x = 1 in the formula f''(x) = 2 (for all x)?

RGV

So you mean that given that f"(x)=2, I can say that f"(1)=2?

Yes.
You may imagine it by thinking it is 2 independently by x.

Ray Vickson
Homework Helper
Dearly Missed
So you mean that given that f"(x)=2, I can say that f"(1)=2?

Of course. That is what we mean when we say f''(x) = 2 for all x. It holds for x = 1 or x = 943.76/sqrt(pi) or x = 10 million, or whatever.

RGV

Oh, I see. Thanks.

Do you know how do I calculate the true value of the function and the approximate value given by the Taylor series approximation for x=2?

Mark44
Mentor
Oh, I see. Thanks.

Do you know how do I calculate the true value of the function and the approximate value given by the Taylor series approximation for x=2?

You're given the formulas for both functions, and you presumably have your Taylor polynomials. Just evaluate these functions at the appropriate values.

I got it! Thanks!


text:
# 7 Convolution and Autocorrelation#

# import all python add-ons etc that will be needed later on
%matplotlib inline
import numpy as np
import matplotlib.pyplot as plt
from sympy import *
init_printing()                      # allows printing of SymPy results in typeset maths format
plt.rcParams.update({'font.size': 14})  # set font size for plots

## Motivation and concept#

Instruments measure everything: for example, mass, energy, number of particles, wavelength of light, voltage, current, and images. However, every instrument distorts the data to a greater or lesser extent, and obviously we try to make these distortions insignificant but this is not always possible. In cases when a detector may not respond quickly enough to an event, when very wide slits have to be used in a spectrometer to detect a weak signal, or an electronic circuit does not respond in a linear manner to the input voltage, a distortion to the data is unavoidable. The effect is to convolute the ideal response, as defined by the physics behind the experiment, with the instrumental response. Fortunately Fourier transforms can usually be used to unravel the effect of convolution, however, in some circumstances this may not be possible.

## 7.1 Examples#

(i) To be specific, suppose that the lifetime of electronically excited atoms or molecules is to be measured by exciting them with a pulse of light and their fluorescence measured as it decays with time. This fluorescence could be observed with a photodiode or photomultiplier, whose output voltage is measured with an oscilloscope. Before doing this experiment, two questions have to be answered;

(a) Is the laser used to excite the molecules of short enough duration that the molecules or atoms can be excited quickly enough before any significant number can decay back to the ground state?

(b) Is the detection equipment (photodiode, oscilloscope) used able to respond quickly enough to measure the decaying fluorescence properly?

Figure 24. Top: A signal representing the ideal response of an experiment to a sudden impulse. Middle: The actual stimulation used in the experiment represented as the instrument response. Bottom: The measured signal, the convolution of the two upper curves.

If either one or both of these conditions cannot be met, then the data will be distorted by the relatively slow response of the instrument. The convolution curve in fig 24 shows how this distortion affects some data. In this figure, the top curve is the ideal decay of the excited state, but it could represent any ideal response. This behaviour would be observed if the molecules could be excited with an infinitesimally narrow laser pulse and measured with a photo-detector with an unlimited time response. The second curve is the actual shape of the laser pulse, and/or detector response, and is the ‘instrument response’ drawn on the same timescale. Clearly, this has a width and a rise and decay time that is not so very different to that of the ideal response. The lower curve is the convolution of the ideal response with the instrument response, and is what would be measured experimentally and clearly has characteristics of both curves. A log plot of the data would show that only at long times does the convoluted response have the same slope as the ideal one. It makes no difference if the instrument response consists of a slow ‘driving force’ for the experiment, in this case a long-lived light-pulse, or a slowly responding detector or both, because the effect producing the convolution is the same. Fortunately, convolution can be calculated easily and rapidly using Fourier transforms.

Figure 25. The convolution of a narrow spectral line with a wide slit in a spectrometer.

(ii) As a second example, consider measuring the width or position of one particular spectral line, such as from a star or a sample of molecules in the lab. The spectrometer has slits on its entrance and exit and these, with the number of grooves in the grating, control the resolution of the spectrometer. Typically, this is $$0.1$$ nm/mm of slit width for a moderately good spectrometer and 1 nm/mm for a general purpose one. If the slits cannot be closed to more than $$0.1$$ mm, then the resolution of the general purpose instrument will be approximately 0.1 nm and a narrow spectral line will appear to have this value even it is many times narrower. This is because the grating is rotated while measuring the spectrum and the spectral line is swept across the slits. The effect is to sequentially place a spectral line at all possible points, and hence wavelengths, across the slit. A signal is recorded at all these wavelengths rather than being measured only at its proper one, and the response measured is the convolution of the ideal width of the spectral line with the instrument response, which is the finite width of the slit. In many instruments, a CCD camera measures all wavelengths simultaneously, and a slit is not needed nor is the grating scanned. However, the same reasoning applies because the individual elements of the camera have a finite width, which therefore act as individual slits.

(iii) A final use of convolution is to smooth data. Because convoluting one function with another involves integration, this has the effect of summing or averaging. The rolling or moving average method (Section 10.4) is in effect a convolution, and effectively smooths spiky data.

## 7.2 How convolution works#

In the next sections, a convolution will be calculated by direct summation and by a Fourier transform. Convolution is related to the auto- and cross-correlations and these will also be described. How to go about estimating the true response from the convoluted response in real, that is experimental data, i.e. reversing the effects of convolution, is discussed in chapter 13 on numerical methods. This is usually done using iterative, non-linear least-squares methods, (See 13.6.7), because when using real data, which always contains noise, it is found that reverse transforming the convolution often results in a calculated ideal response that is so noisy as to be useless.

Figure 26. Curves show the instrument response (red), made up as a series of impulses (dotted), which produce a response ($$w$$) at each point on its profile any a few of which are shown. These are then added together in this time delayed manner, to produce the convoluted response.

To understand how convolution works, suppose that the overall instrument response is made up of a series of $$\delta$$-function impulses. These can be infinitesimally narrow light pulses that excite a molecule. Suppose these impulses are made at ever shorter time intervals, then the effect is that of smoothly exciting the molecule. Each of the impulses elicits an ideal response but because there are many of them, their responses must be added together. The result is the convolution; the effect is shown in Fig. 26. It is always assumed in the convolution that the response is linear with the impulse, which simply means that doubling the impulse doubles the response and so forth.

The light pulses occur at each point in the dashed curve, Fig. 26. The response from each impulse is the decaying solid curve. To calculate the overall response at any given point along the x-axis, the effect of all previous impulses must be added into the calculation. Suppose that the pulse exciting the sample has a shape given by some function $$f$$, the ideal experimental response $$w$$, and the convolution $$C$$. The terms can be written down at each time if it is assumed, for the present, that the impulses are discrete and the data is represented as a series of points at times $$1, 2, 3$$, and so forth; $$f$$(6), for example, represents the value of $$f$$ at the sixth time position. The first point of the impulse is $$f$$(1) and this produces the response

$\displaystyle f (1)[w(1) + w(2) + w(3) + \cdots]$

The second and third impulses produce

$$\displaystyle f(2)[w(1) + w(2) + w(3) + \cdots]$$ and $$f(3)[w(1) + w(2) + w(3) + \cdots]$$.

The convolution is the sum of these terms at times 1, 2, 3, and so on therefore;

\begin{split}\displaystyle\begin{align} C(1)& = f (1)w(1)\\ C(2)& = f (1)w(2) + f (2)w(1)\\ C(3) &= f (1)w(3) + f (2)w(2) + f (3)w(1)\\ C(4)& = f (1)w(4) + f (2)w(3) + f (3)w(2) + f (4)w(1)\\ \end{align}\end{split}

These sums are shown in Fig. 27 by adding the products of $$f$$ and $$w$$ vertically. Clearly, only where both $$f$$ and $$w$$ are not zero, will this product have a value. The symmetry in these sums soon becomes apparent, each being the product of one series running to the right, and the other to the left; for instance, look at $$C$$(4). The name convolution arises from just this effect; the word also means ‘folded’ and this is shown in the form of the series where each function is folded back onto the other. Convolution is also the distribution of one function in accordance with a ‘law’ specified by another function (Steward 1987) because the whole of one function $$w$$, is multiplied with each ordinate of the other $$f$$, and the results added. The ideal response (the ‘one function’) is distributed, i.e. spread out according to the law or shape of the driving function $$f$$.

Figure 27. Diagram showing the notation used to calculate a convolution.

## 7.3 Convolution by summation#

Written as a summation, the convolution at point $$k$$ is

$\displaystyle C(k) = \sum_{i=0}^k f(i)w(k - i ) \qquad\tag{32}$

This sum evaluates just one point; to calculate the whole convolution, the index $$k$$ must now be varied from 1 to $$n$$, which is the number of data points, making a double summation. One reason Fourier transforms are used to calculate convolutions is that the fast Fourier transform algorithm, FFT, is far quicker on the computer than calculating the convolution as a double summation, particularly for a large number of data points.

The algorithm to calculate the summation has a double loop to calculate all values of $$k$$ and to perform the summation in eqn. 32. The two functions used are those that produced Fig. 24, which are $$\displaystyle f(t) = e^{-t/100}$$ and $$\displaystyle w(t) = e^{-(t-100)^2/1000}$$, and $$2^{10}$$ points will be also be used to mimic the data produced by an instrument.

First, because the data is discrete, arrays $$f$$ and $$w$$ are made; to hold the data points. Then two loops are made, one changes $$k$$ from 1 to $$n$$ the and inside one calculates $$C(k)$$. The indices are arranged as in equation 32. The variable $$s$$ accumulates the sum as the inner do loop progresses. This is a relatively slow calculation because of the double loop.

# algorithm convolution by double summation
#---------------------------
def do_convolution(f,w):   # f and w are arrays
# Sigma f(n-m)g(m) ;   c(0) = f(0)w(0),    c(1) =  f(0)w(1) + f(1)w(0)  etc
n = len(f)
c = [0.0 for i in range(n)]
for k in range(n):
s = 0.0
for i in range(k):
s = s + f[i]*w[k-i]
pass
c[k] = s
return c
#---------------------------

n = 2**10
f = [ np.exp(-i/100.0)  for i in range(n)]
w = [ np.exp(-(i-100)**2/1e3) for i in range(n)]
t = [i for i in range(n)]

C = do_convolution(f,w)
mxc  = max(C)         # use to normalse
plt.plot(t,C/mxc,color='red',label='C , convolution '+r'$f\otimes w$')
plt.plot(t,f,color='black',label='f(x)')
plt.plot(t,w,color='blue',label='w(x)')
plt.xlim([0,n])
plt.legend()
plt.show()

## 7.4 Convolution by Fourier transform#

The convolution can also become an integral, by supposing that the points are separated by an infinitesimal amount, and therefore, the change $$sum \rightarrow \int$$ is allowable. The integral form of the convolution at time $$u$$, is

$\displaystyle C(u)=\int_{-\infty}^\infty f(t)w(u-t)dt \qquad\tag{33}$

which represents the response at time $$u$$ to an impulse delivered at time $$t$$. The limits to the integral are often represented as $$\pm \infty$$. If the signal is zero at times less than zero, then the lower limit can be made zero.

The convolution integral is frequently written as,

$\displaystyle C(t) = f (t) \otimes w(t) \qquad \text{ or } \qquad C = f \otimes w \qquad\tag{34}$

The convolution is performed by Fourier transforming functions $$f$$ and $$w$$ separately, multiplying the transforms together and then inverse transforming. The symbol $$\otimes$$ represents all these calculations because the result is returned in the time domain. Sometimes, the convolution is written only as a conversion into the frequency domain as

$\displaystyle f(t)\otimes w(t) = \sqrt{2\pi} F(\omega)W(\omega)$

where $$F$$ and $$W$$ are the respective fourier transforms of $$f$$ and $$w$$, $$\omega$$ being angular frequency. Thus convolution in ‘normal’ space is multiplication in ‘Fourier’ space.

If $$T$$ represents the Fourier transform and $$T^{-1}[\cdots]$$ the inverse transform the convolution is formally written as

$\displaystyle C = T^{-1}[\,T( f )T(w)\,] \qquad\tag{35}$

which is the same as equation 34. If the equations describing $$f$$ and $$w$$ are known, an exponential and a Gaussian for example, then

$$\quad$$(a) the Fourier transform integral of each function is calculated as described in Section 6,

$$\quad$$(b) these are multiplied together and

$$\quad$$(c) the inverse transform integral calculated.

The result of these three operations is the convolution of the two functions in other words

$$\quad$$(1) the convolution of two functions is the transform of the product of their individual transforms: $$\displaystyle T[\,T( f )\cdot T(w)\,]$$.

Other statements are also true

$$\quad$$(2) The transform of a convolution is the product of the transforms: $$T^{-1}[f(t)\otimes w(t)]=T(f)\cdot T(w)$$.

$$\quad$$(3) The transform of a product is the convolution of the transforms: $$T(f\cdot w)=T(f)\otimes T(w)$$.

$$\quad$$(4) The product of two functions is the reverse transform of the convolution of their transforms: $$f\cdot w=T^{-1}[ T(f)\otimes T(w) ]$$.

### Proof of convolution as transform#

The proof that the convolution is a product of transforms starts with the definition in eqn 33 the transform is made and the order of integration is changed. (The limits are removed for clarity and are $$u,t \pm \infty$$ and replaced with the variable). The first step is to convert $$w$$ into its fourier transform, which introduces another integral

$\displaystyle \int_{u}\int_{t} f(t)w(u-t)\,dt \,e^{-i\omega u} du =\int_{t}f(t)\left[\int_{u} w(u-t)e^{-i\omega u} du \right]\,dt$

changing $$s= u-t$$ and rearranging

$\displaystyle \int_{t}f(t)\left[\int_{s} w(s)e^{-i\omega (s+t)} ds\right]\,du =\int_{-\infty}^\infty f(t)e^{-i\omega t}dt\int_{-\infty}^\infty w(s)e^{-i\omega s} ds \equiv F(\omega)W(\omega)$

which shows that the convolution is the product of the fourier transforms in transform space. Note that the $$t$$ and $$u-t$$ in the convolution have both become frequency in the transformed equation. Note also that $$s$$ is a dummy variable as it is the integration variable, any other symbol could be used, $$t$$ for example as long as it does not conflict with another.

As an example, consider convoluting a square pulse with two delta functions. Their convolution will produce two square pulses centred on the two delta functions, because, as the pulse is swept past the two deltas, only at their overlap will their product have a finite value. Three stages of the convolution are shown at the top of Fig. 28, and the result is shown below this.

Figure 28. Convolution as Fourier transforms.

Next, the convolution is evaluated using Fourier transforms. The transforms of the two delta functions and the pulse have already been calculated, and are shown in Fig. 29. This product of the two transforms is then reverse transformed and two square pulses are produced.

This last convolution is, incidentally, another way of describing the interference due to a double slit, and if many delta functions are used then this describes the effect of a diffraction grating on light waves.

The data needed in a convolution is frequently a list of numbers because it comes from an experiment and in this case a numerical method has to be used to do the transform, which is then called a Discrete Fourier Transform. This is described further in Section 9, but here is an example some code to illustrate convolution using discrete Fourier transforms.

Figure 29. Left: The two waveforms are the Fourier transform of a square pulse (top) and two delta functions (lower). When these are multiplied together and reverse transformed two pulses are produced which is the convolution of the delta functions and the single square pulse. The same method has been used to make Fig. 24, even though the functions differ.

### Shifting a wavepacket: $$T(f\cdot w)=T(f)\otimes T(w)$$: Products and transforms#

As an illustration that the transform of a product is the convolution of the transforms we examine a wavepacket which has the form of a complex exponential modified by a gaussian envelope, fig 29a. A femtosecond laser pulse could have this time profile, a vibrational wavepacket this shape with bond extension $$x$$. The wavepacket is

$\displaystyle f(t)= e^{ikx}e^{-x^2/2\sigma^2}$

where $$\sigma$$ is the variance of the envelope. You can see that this function is the product of an exponential and a Gaussian. Its fourier transform is therefore the convolution of the transform of these two functions. The exponential has the transform (see table 6.7) $$\delta(k-k_0)$$ and the Gaussian $$\sigma e^{-\sigma^2k^2/2}$$.

The convolution and hence transform is

$\displaystyle \int_{-\infty}^\infty \sigma e^{-\sigma^2k^2/2}\delta(k-k_0) dk = \sigma e^{-\sigma^2(k-k_0)^2/2}$

and because the delta function is everywhere zero except at $$k=k_0$$ the integral need not be performed as one value only is selected and the result written down. This shows that the transform is also a gaussian but shifted by an amount $$k_0$$ as shown in figure 29a.

Figure 29a. A Gaussian wavepacket shifted by convolution with the $$\delta$$ function $$\delta(k-k_0)$$ in $$k$$ space. The various widths are shown as red lines. The left hand panel shows the function in ‘real’ $$x$$ space, the right hand one in transform $$k$$ space. The constants used were $$\sigma=1,k_0=10$$.

### Code example of convolution by fourier transform#

# convolution by fourier transform

n = 2**10
f = [ np.exp(-i/100.0) for i in range(n)]
w = [ np.exp(-(i-100)**2/1e3) for i in range(n)]
t = [i for i in range(n)]

F = np.fft.rfft(f)        # use rfft as input in only real
W = np.fft.rfft(w)
C = np.fft.irfft(F*W)

mxc  = max(C)         # use to normalse

plt.plot(t,C/mxc,color='red',label='C , convolution '+r'$f\otimes w$')
plt.plot(t,f,color='black',label='f')
plt.plot(t,w,color='blue',label='w')
plt.plot()
plt.xlim([0,n])
plt.legend()
plt.show()

## 7.5 A warning and a Solution#

Finally a warning about using Fourier transforms to perform convolution. The transform assumes that the function being transformed is periodic, this means that if the signal is not of the same size, such as zero, at its start and end there is a frequency associated with changing from end to start so that this will appear as an artifact in the convolution. THis occurs because the transform assumes that the signal is periodic. This does not arise in the case of the summation method and even though this may be slower to calculate, it is more robust. The difference is shown in the next figure 29b. On the left is shown the summation based convolution calculation using an exponential, with lifetime of 10000, and a Gaussian and on the right using the Fourier transform method. All is not lost, however, because by padding the data with zeros to double its length the correct result can be obtained.

Figure 29b. The figure shows the difference between the correct convolution done by summation ( red curve left ) and the artefact introduced by using the Fourier method ( red curve right ) this is produced when the functions are not the same size, preferably zero, at the start and end of the data.

## 8 Autocorrelation and Cross-Correlation#

A correlation is a function that measures the similarity of one set of data to another. A cross-correlation is formed if the data are dissimilar, an autocorrelation if there is only one set of data. The data might be a voltage from a detector, it might be an image or residuals from fitting a set of data. In Fig. 30 part of a noisy sinusoidal curve is shown in black and labelled 1. The second curve (2, red) is displaced only a little from the first and is clearly only slightly different; the third (3, grey) which is displaced by more is clearly different from the first as it is positive at large $$x$$ when the first curve is negative. The right-hand figure shows the autocorrelation of the curve (1) shown on the left, and as this is an oscillating curve, the autocorrelation also oscillates but eventually reaches zero. The oscillation is a result of the fact that a sinusoidal curve is similar to itself after each period, and the autocorrelation measures this similarity by increasing and decreasing. The autocorrelation is also less noisy that the data because it involves summing or integrating over many data points.

A random signal with an average of zero will have an autocorrelation that averages to zero at all points except the first, whereas the autocorrelation of an exponential and similar functions will be not be zero, but decay away in some manner. The autocorrelation is a likened to a measure of the ‘memory’ a function has, that is, how similar one part of the data is with an earlier or later part. A zero average random signal has no memory because it is random, and each point is independent of its predecessor; this is not true of any other signal. The correlation is therefore a process by which we can compare patterns in data. In data analysis, the residuals, which are the difference between the data and a fitted function, should be random if the fit is correct; the shape of the autocorrelation is therefore a way of testing this.

Figure 30. A sketch showing the first $$120$$ points of a set of noisy data of $$250$$ points. The data is still somewhat similar to itself when displaced by only a few points but much less so, when displaced by many, dashed grey curve. The autocorrelation of all the data is shown on the right. Notice also how as autocorrelation integrates the data, the noise is reduced.

## 8.1 Applications#

In ultra-fast (femtosecond) laser spectroscopy, autocorrelations are used to measure the length of the laser pulse because no electronic device is fast enough to do this, as they are limited to a time resolution of a few tens of picoseconds at best, but laser pulses can be less than $$10$$ fs in duration. In single molecule spectroscopy, the correlation of the number of fluorescent photons detected in a given time interval is used to determine the diffusion coefficient of the molecules. In the study of the electronically excited states of molecules, the correlation of time resolved spectra, recorded as the molecule moves on its potential energy surface, is a measure of excited state and solvent dynamics. Perhaps the most important application is in FTIR spectroscopy.

The signal from an FTIR spectrometer is the autocorrelation of the infra-red radiation because in this instrument one arm of the (Michaelson) interferometer is moved relative to the other thus changing i.r. radiation’s pathlength. The two beams interfere on the detector forming the autocorrelation, see section 5.2 and figure 12. More details are given shortly in section XX.

Two dimensional cross correlation is used in imaging for example to identify a particular feature by correlating two images. High spots in the correlation show where the images have similarities.

## 8.2 Calculating the correlation#

The correlation function is similar to, but different from, convolution. The autocorrelation is always symmetrical about zero displacement or lag, the cross-correlation is not. In the convolution the two functions $$f$$ and $$w$$ are folded on one another, the first point of $$f$$ multiplying the last of $$w$$ and so on, until the last point of $$f$$ multiplies the first of $$w$$, equation 31. In the auto- and cross-correlation, one function is also moved past the other and the sum of the product of each term is made but with the indices running in the same direction, both increasing.

A cross-correlation is shown in Fig. 31 using a triangle $$w$$ and a rectangle $$f$$, each with a base line, and for clarity, defined with only six points. The first term in auto- or cross-correlation $$A$$ occurs when point $$f$$(6) overlaps with $$w$$(1), when $$f$$ is to the far left of $$w$$. The position at $$-5$$ to the left is shown in the figure as $$A$$(-5). The middle term in the correlation is at zero displacement, or lag, and there is total overlap of the two shapes and the correlation is at a maximum. The figure on the right shows the last overlap, consisting of just one point in common between the two shapes. There are six terms in the summation of $$A$$(0) down to one in each of $$A$$(-5) and $$A$$(5). The zero lag term is

$\displaystyle A(0) = f (1)w(1) + f (2)w(2) + \cdots + f (6)w(6)$

The next term has one point displacement between $$f$$ and $$w$$ and five terms are summed,

$A(1) = f (1)w(2) + f (2)w(3) + f (3)w(4) + f (4)w(5) + f (5)w(6)$

With two points displaced, there are four terms

$\displaystyle A(2) = f (1)w(3) + f (2)w(4) + f (3)w(5) + f (4)w(6)$

and so forth for the other terms. The last overlap is

$\displaystyle A(5) = f (1)w(6) \qquad\tag{36}$

On the negative side, the indices are interchanged, $$f$$ for $$w$$ and vice versa, and the first (far left) term is $$A(-5) = f (6)w(1)$$ and similarly for the other terms. There are 11 terms in all or, in general $$2n - 1$$, for data of $$n$$ points. In an autocorrelation, $$f$$ and $$w$$ are the same function and therefore the autocorrelation must be symmetrical and only terms from zero to five are needed, the others being known by symmetry.

Figure 31. A pictorial description of cross-correlation of the signals (functions) $$w$$ a traingle and $$f$$ a ‘top-hat’ or rectangle.

The formula for the autocorrelation for $$n$$ data points is

$\displaystyle A_a(k)=\sum_{i=0}^{n-k}f(i)f(k+i) \qquad k=0,1,\cdots \rightarrow \cdots n \qquad\tag{37}$

where the first value of the displacement $$k$$ is zero, and the last $$n$$, and both functions are now labelled $$f$$. Very often the autocorrelation is normalized; this means dividing by $$\sum f(i)^2$$,

$\displaystyle A_a(k)=\frac{\sum\limits_{i=0}^{n-k}f(i)f(k+i)}{\sum f(i)^2} \qquad\tag{38}$

These last two formulae produce just half of the autocorrelation. To produce the full correlation, symmetrical about zero lag, the mirror image of equation (37) must be added as points $$-n \to -1$$ to the left-hand part of the data.

The cross-correlation uses a similar formula

$\displaystyle A_c(k)=\sum\limits_{i=0}^{n-k} f(i)w(k+i) \qquad k=-n+1,\cdots 0, \cdots n-1 \qquad\tag{39}$

but now $$k$$ always ranges from $$-n + 1 \to n - 1$$. This distinction is crucial, otherwise the whole of the cross-correlation is not calculated.

In calculating a correlation as a summation with a computer, as with a convolution, each term in the correlation is a sum, so this means that two nested ‘loops’ are needed to calculate the whole function; one loop sums each individual term, the other calculates the sum, $$A(k)$$.

Some authors define the correlation up to a maximum of $$n$$ in the summation, not $$n - k$$. There is, however, a pitfall in doing this because, if the correlation is not zero above half the length of the data, then this folds round and what is calculated is the sum of the correlation plus its mirror image. The way to avoid this is to add $$n$$ zeros to the data and the summation continued until $$2n$$. This should be done routinely if Fourier transforms are used to calculate the correlation.

Correlations and convolution are not restricted to digitized data but apply also to normal functions. Written as an integral, the cross-correlation of a real, i.e. not complex, function is

$\displaystyle A_c(u) =\int_{-\infty}^{\infty}f(t)w(u+t)dt \qquad\tag{40}$

and the autocorrelation of $$f$$,

$\displaystyle A_a(u) =\int_{-\infty}^{\infty}f(t)f(u+t)dt \qquad\tag{41}$

Notice that the sign in the second term is positive in the correlation but negative in a convolution, equation (33). Some authors multiply by a normalising term $$1/\sqrt{2\pi}$$ to the autocorrelation but we shall ignore this constant as in most applications it is not usually necessary to know it. The autocorrelation is an even function thus

$\displaystyle A_a(u)=A_a(-u)$

and if the function contains a complex number, then the conjugate is always placed on the left,

$\displaystyle A_a(u) =\int_{-\infty}^{\infty}f(t)^*f(u+t)dt \qquad\tag{41}$

The normalised autocorrelation is

$\displaystyle G(u) = \frac{\int\limits_{-\infty}^{\infty}f(t)^*f(u+t)dt}{\int\limits_{-\infty}^{\infty}f(t)^2dt} =\frac{\langle f(t)\,f(u+t)\rangle}{\langle f(t)^2\rangle} \qquad\tag{42}$

and the bracket notation indicates that these are average value. The denominator is the normalization term and is also the value of the numerator with $$u = 0$$.

If $$f(x)$$ is complex then it is conventional to write

$\displaystyle A_a(u)=\int_{-\infty}^\infty f(t)f^*(u-t)dt\qquad\text{or}\qquad \displaystyle A_a(u)=\int_{-\infty}^\infty f^*(t)f(u+t)dt$

where * indicates the complex conjugate.

## 8.3 Comparison with convolution and a fourier transform.#

The convolution and correlation are very closely related , the convolution integral has the form

$\displaystyle C(u)= \int f(t)w(u-t)dt \qquad \text{convolution}$

whereas the correlation is

$\displaystyle A_c(u)=\int f(t)w(u+t)dt\qquad \text{correlation}$

and as with a convolution, an autocorrelation can be represented as a fourier transform. To show this start by replacing $$f$$ and $$w$$ by their transforms which we call $$g$$ and $$h$$ respectively, and to be general suppose that $$f$$ and $$w$$ are complex then the change is $$f\to f^*$$ which is its complex conjugate.

$\displaystyle A_c(u)=\int_{-\infty}^\infty \left[\int_{-\infty}^\infty g^*(\omega)e^{i\omega t} d\omega\right]\left[ \int h(\omega' ) e^{-i\omega'(t+ u)}d\omega'\right]dt$
$=\int_{-\infty}^\infty \int_{-\infty}^\infty \int_{-\infty}^\infty g^*(\omega)h(\omega')e^{i\omega t} e^{-i\omega'(t+ u)}dt d\omega d\omega'$
$=\int_{-\infty}^\infty \int_{-\infty}^\infty g^*(\omega)h(\omega')\int_{-\infty}^\infty e^{-i(\omega'-\omega) t}dt e^{-i\omega'u} d\omega d\omega'$

the integral in $$dt$$ is the delta function $$\delta(\omega'-\omega)$$ which is zero unless $$\omega=\omega'$$ which leaves one integral

$A_c(u)=\int_{-\infty}^\infty g^*(\omega)h(\omega)e^{-i\omega u} d\omega$

In the case of an autocorrelation $$f=w$$ and

$\displaystyle A_a(u)= \int_{-\infty}^\infty f(t)f(u+t)dt =\int_{-\infty}^\infty |g(\omega)|^2 e^{-i\omega u} d\omega$

which is the Wiener-Khinchin Theorem described shortly. This shows us that the square of the absolute value of the fourier transform of $$f$$ is its autocorrelation.

## 8.4 Examples#

### (i) Periodic function#

If the function is periodic then the integration limits should cover one period. The normalized autocorrelation of a cosine $$A\cos(2\pi\nu t + \varphi)$$, where the period is $$T = 1/\nu$$ and $$\varphi$$ is the phase, is calculated as

$\displaystyle G(u) = \frac{\int\limits_0^T \cos(2\pi\nu t+\varphi)\cos(2\pi \nu (u+t)+\varphi)dt}{\int\limits_0^T \cos^2(2\pi \nu t+\varphi)dt}$

and the result will be independent of the phase. Note that we could also use $$\omega =2\pi \nu$$ as the frequency, which to use is a matter of preference. The normalisation integral is a standard one and can be looked up or converted to an exponential form to simplify integration. The result is $$\displaystyle \int_0^T \cos(2\pi t/T+\varphi)^2dt = T/2$$. The other integral can similarly be calculated. Using SymPy, this is

t, phi, T, u = symbols('t, phi, T, u',positive =True)

f01 = cos(2*pi*t/T+phi)*cos(2*pi*t/T+phi+2*pi*u/T )

G = integrate(f01,(t,0,T),conds='none')    # slow calculation
simplify(G)

from which it is seen that the normalised autocorrelation is also a cosine $$\displaystyle G(u) = \cos\left(2\pi \frac{u}{T}\right)$$. If the initial cosine is written as $$\cos(\omega t + \varphi)$$ then the period is $$T = 2\pi/\omega$$.

If the trigonometric function is a complex exponential $$\displaystyle Ae^{-i(\omega t+\varphi)}$$ rather than a sine or cosine then the complex conjugate of the function is taken in both of the autocorrelation integrals. The normalization could not be simpler $$\int_0^Tdt = T$$. The correlation is also a very straightforward integral;

$\displaystyle G(u)=\frac{1}{T}\int\limits_0^T e^{-i\omega t+\varphi}e^{i\omega (u+t)+\varphi}dt =\frac{1}{T}\int\limits_0^T e^{i\omega u}dt=e^{i\omega u}$

Using the Euler relationship, $$\displaystyle e^{-i\theta} = \cos(\theta) + i \sin(\theta)$$, the real or imaginary parts of the function give the cosine or sine result respectively.

### (ii) aperiodic function#

If the function is not periodic, then the limits must be determined by the function being used. The normalized autocorrelation $$A(u)$$ of the function $$f(t) = e^{-at}$$, when $$t \ge 0$$ and $$f (t) = 0$$ when $$t \lt 0$$, will be calculated, and also its full width at half-maximum, fwhm. The integration limits can be changed from those in equation (42) because the function is zero for $$t \lt 0$$ and the lower limit can be zero. The normalization, using equation (42), is

$\displaystyle \int_{-\infty}^{\infty} f(t)^2dt=\int_0^\infty e^{-2at}dt = \frac{1}{2a}$

and the autocorrelation

$\displaystyle \int_{-\infty}^{\infty} f(t)f(u+t)dt=\int_0^\infty e^{-at}e^{-a(u+t)}dt =e^{-au}\int_0^\infty e^{-2at}dt=\frac{e^{-au}}{2a}$

Importantly, the autocorrelation must be an even function because it is symmetrical thus it is $$\displaystyle A(u) = \frac{e^{-a|u|}}{ 2a}$$ therefore, the value of $$u$$ must always be positive. The normalised autocorrelation is $$\displaystyle A(u)=e^{-a|u|}$$. The $$|u|$$ does not follow from the mathematics; it is imposed by our knowledge of symmetry of the function.

As a check, at $$u = 0,\, A(0) = 1$$, which is correct and the function is even or symmetrical about its y-axis, or, $$u = 0$$. The fwhm is calculated when $$\displaystyle A(u_h) = 0.5 = e^{-a|u_h|}$$ or $$\displaystyle |u_h|=a^{-1}\ln(2)$$ and thus fwhm is $$\displaystyle 2a^{-1}\ln(2)$$. This is twice as wide in this instance as the initial function.

### (iii) Laser pulses#

The duration of a short laser pulse is often measured as an autocorrelation with an optical correlator. If the intensity profile $$I$$ of the short laser pulse is a Gaussian centred at zero $$\displaystyle I = e^{-2(t/a)^2}$$, it is possible to calculate the width of its normalized autocorrelation. If the calculated autocorrelation shape is compared with an experimentally measured one, an estimation of the laser pulse’s duration can be made. The optical correlator to do this measurement is a Michelson interferometer; the path length in one arm is changed relative to the other so that one pulse is moved past the other in time. The pulses are combined in a frequency doubling crystal, and a u.v. signal is detected only when the pulses overlap.

To achieve this, the doubled frequency, which is in the ultraviolet part of the spectrum, is separated from the fundamental wavelength by a filter. The size of the signal vs the distance the mirror moves, which is proportional to time, is the autocorrelation see Fig. 32.

Figure 32. Schematic of an optical autocorrelator used to measure the duration of pico- and femtosecond laser pulses.

The pulse is centred at zero delay and (theoretically) extends from $$-\infty$$ to $$\infty$$, which are the integration limits of the autocorrelation, equation (42). The autocorrelation integral is

$\displaystyle A(u)=\int\limits_{-\infty}^{\infty} e^{-t^2/a^2}e^{-(u+t)^2/a^2}dt = a\sqrt{\frac{\pi}{2}} e^{-u^2/(2a^2)}$

and the calculation with SymPy is

t, u, a =symbols('t u a',positive=True)
f01= exp(-(t/a)**2)*exp(-((u+t)**2)/a**2)
G= simplify(integrate(f01, (t,-oo,oo), conds='none'))    # oo is infinity
G.doit()

The normalization integration can be looked up but need not be worked out because it is the value of autocorrelation when $$u$$ = 0. The normalization equation is therefore $$\displaystyle \int e^{-2t^2/a^2}dt=a\sqrt{\pi /2}$$. The normalized autocorrelation $$G(u)$$ is also a Gaussian, with a value $$\displaystyle G(u)=e^{-u^2/(2a^2)}$$. The fwhm of this function is calculated when $$G(u)=1/2$$ and is $$a\sqrt{2\ln(2)}$$ and that of the original pulse is $$a\sqrt{\ln(2)}$$ therefore, the autocorrelation is $$\sqrt{2} \approx$$ 1.414 times wider than the pulse. Knowing this factor provides a convenient way of measuring the duration of a short laser pulse assuming it has a Gaussian profile.

### (iv) Goodness of data fitting#

The randomness or otherwise of the autocorrelation of the residuals obtained from fitting real data to a model (theory) is important when determining the ‘goodness of fit’. The function is now a set of data points not an equation. The data in Fig. 33 shows the autocorrelation of a random sequence of values where the mean is 0 (left) and $$1/2$$ (right). When the mean is zero, only the first point has a value not essentially zero. When the mean is $$1/2$$, there is a correlation between each point, and this decreases as the separation between points increases. Since the mean is $$1/2$$ (or any value not zero), this means that each point is related to all the others, because, besides random fluctuations, they all have the same underlying value. Their correlation becomes less the further they are separated.

The normalized autocorrelation of any line $$y$$ = constant, is a sloping straight line starting at $$1$$ and ending at $$0$$. This is to be expected, because at zero displacement the line is overlapped with itself, whereas at the maximum displacement, only one term remains, see equation (36), and this value is small. In Fig. 33, the random noise has a large correlation at zero displacement because the whole trace must be perfectly correlated with itself; its value is 1 but only because the autocorrelation is normalized.

In calculating the autocorrelation of residuals from a set of fitted data, the mean value of the data is always subtracted first to prevent this sloping effect on the autocorrelation shown on the right of Fig. 9.33. Of course, if after doing this the autocorrelation is still sloping, then it clearly is not equally distributed about zero and the model used to describe the data may not be correct.

The autocorrelation calculation is shown below.

# Algorithm: Autocorrelation
#-----------------------
def do_autoc(f,w):       # Autocorrelation ac(k)= sum_i=0^{n-k} f(i)w(k+i) /norm
n = len(w)
ac = [0.0 for i in range(n)]
sf = sum([f[i]**2 for i in range(n)])
sw = sum([w[i]**2 for i in range(n)])
normfw = np.sqrt(sf*sw)
for k in range(n-1):
s = 0.0
for i in range(n-k):
s = s + f[i]*w[k+i]
ac[k] = s

return ac/normfw
#----------------------

fig1= plt.figure(figsize=(8.0,4.0))

n = 250
s = [ np.random.rand() for i in range(n)]
t0= [i for i in range(n)]

ss = sum(s)/n                       # get average
s0 = [s[i] - ss for i in range(n)]  # subtract average

ax0.plot(t0, do_autoc(s0,s0),color='blue') #  (S0, S0) is autocorrelation
ax0.axhline(0,color='black',linewidth=1)
ax0.set_xlabel('x')
ax0.set_title('autocorrelation, av = 0')
ax0.set_yticks([-0.5,0.0,0.5,1])

ax1.plot(t0, do_autoc(s,s),color='blue')
ax1.axhline(0,color='black',linewidth=1)
ax1.set_xlabel('x')
ax1.set_title('autocorrelation, av = 0.5')
ax1.set_yticks([-0.5,0.0,0.5,1])
plt.tight_layout()

plt.show()

Fig. 33 Normalized autocorrelations of $$250$$ random numbers with an average of $$0$$ (left) and an average of $$1/2$$ (right). Only the right-hand half of the autocorrelation is calculated and plotted. The left-hand part is the exact mirror image.

## 8.5 Autocorrelation of fluctuating and noisy signals#

The autocorrelation of noise is now considered, and in the next section this will lead to understanding the shape of a spectroscopic transition and this is illustrated with NMR. Any experimental measurement is accompanied by noise. When measuring the properties of single atoms, molecules, or photons, considerable fluctuations in their measured values are expected and many events have to be averaged to obtain a precise result. The measured property might be energy, velocity, the number of photons in a given period measured by a photodiode, or the current in a transistor or diode when this is so small that discrete charge events are recorded. This latter noise is called shot noise. If you could hear shot noise, the effect would be rather similar to the sound of heavy rain falling on a car’s roof.

There is thermal noise in all resistors in electrical circuits that causes fluctuations in the current. These fluctuations are caused by the thermal motion of the many electrons as they pass through the inhomogeneous material forming the body of the resistor. The frequency of the noise measured on an oscilloscope is determined by the frequency with which the circuitry responds and therefore depends on the capacitance, resistance, and inductance. This generally produces noise with a spread of frequencies of about equal amplitude, except for multiples of mains frequency and those of switched-mode power supplies, and is called white noise. At low frequencies, the amplitude of the noise increases in direct proportion to $$1/f$$ where $$f$$ is frequency and is therefore called ‘$$1/f$$’ noise. The origin of $$1/f$$ noise is not fully understood.

On the macroscopic scale, random noise also accompanies experimental measurements. Measuring the amount of any of the many trace gases, such as CO$$_2$$, IO$$_2$$, and NOx, in the atmosphere using optical techniques is an inherently noisy process. This is due to the continuous and erratic motion of air packets along the line of sight during the measurement and from one measurement to another. The frequency of the noise is, however, mostly limited to the speed at which the air changes.

In the laboratory, all sorts of noise sources can affect an experiment; mostly these are due to voltage or current ripple in DC power supplies. In sensitive laser experiments, noise can be caused by dust particles in the air, vibrations of the building and from the air flow coming from air conditioning units. Atomic force microscopes have in the past needed to be suspended inside a sound proof box by elastic bungee ropes, to avoid adding noise to the measurements from the vibrations of the building and from nearby traffic.

In an attempt to reduce noise a Fourier transform and an autocorrelation of the signal will provide information about the frequencies present, and how quickly they change, or alternatively, how long the noise persists, and hence the possible source. The transform can also be used to remove noise as illustrated in Section 10.

Suppose that the noise on a measurement is represented by some fluctuating signal $$f(t)$$, the frequency of which is determined by the nature of the experiment and by the measuring apparatus. This signal will be represented by a general Fourier series similar to that in Section 1.1 but where $$T$$ is the period over which a measurement is made and the summation starts from zero as this makes the resulting equations simpler,

$\displaystyle f(t)=\sum\limits_{n=0}^\infty a_n\cos \left(\frac{2\pi n t}{T}\right)+\sum\limits_{n=0}^\infty b_n\sin\left(\frac{2\pi n t}{T}\right)$

Following Davidson (1962, chapter 14), the time average of $$f$$ and $$f^2$$ is the respective integral divided by the time interval $$T$$. The average $$\langle f \rangle$$ is zero because the noise is random, but the average of $$f^2$$ is not; the integral is

$\displaystyle \langle f^2 \rangle =\frac{1}{T}\int\limits_0^T\left [\sum\limits_{n=0}^\infty a_n\cos \left(\frac{2\pi n t}{T}\right)+\sum\limits_{n=0}^\infty b_n\sin\left(\frac{2\pi n t}{T}\right) \right]^2 dt$

which simplifies considerably because of the orthogonality of the cosine integrals such as $$\displaystyle \int \cos(2\pi \frac{nt}{T})\sin(2\pi \frac{mt}{T})dt=0$$, $$n$$ and $$m$$ being integers, and the result is very simple;

$\displaystyle \langle f^2\rangle = \frac{1}{2}\sum_n(a_n^2+b_n^2)$

This expression can also represent the average of many measurements if the coefficients $$a$$ and $$b$$ themselves represent average values. This means that the ergodic hypothesis (or ergodic condition) applies, i.e. for a stationary system each part comprising the ensemble (of particles) will pass through all values accessible to it, given a sufficiently long time. Thus the time average is the same for all parts of the ensemble. This also means that the time average is the equivalent to the ensemble average. To explain further; the word ‘stationary’ means that there is no preferred origin for the measurement, thus any time period over which measurements are made is just as good as any other. The ensemble average is taken over all coordinates of a system at a fixed time. The time average considers just a part of the ensemble averaged over a sufficiently long time. If the ergodic hypothesis applies these averages are equal.

The variance (the square of the standard deviation) on the signal is $$\sigma^2=\langle f^2\rangle - \langle f\rangle^2$$ and in this case the standard deviation is $$\sqrt{\langle f^2\rangle}$$ and is the determined only by the amplitudes $$a$$, $$b$$ of the noise. The energy in the noise is $$a^2 + b^2$$.

The autocorrelation of $$f(x)$$ is

$\displaystyle A(u) =\langle f(t)f(u+t)\rangle =\frac{1}{T}\int_0^Tf(t)f(t+u)dt$

which looks quite complicated when the substitution for $$f$$ is made. However, using the formulas for $$\sin(A + B), \cos(A + B)$$ and the orthogonality rules, a remarkably simple result is produced:

$\displaystyle A(u)=\frac{1}{2}\sum_n\left(a_n^2+b_n^2\right)\cos\left(\frac{2\pi nu}{T} \right) \qquad\tag{43}$

which is an oscillating signal that will repeat itself with a period $$T$$.

## 8.6 Wiener–Khinchin relations#

The autocorrelation (equation (43)) is related to the energy or power in a given signal. For example, with electromagnetic radiation the energy is the square of the amplitude $$E$$ of the electric field, the field is given by the constants $$a$$ and $$b$$ thus $$a^2 + b^2$$ represents the energy. This is also true of a sound wave in a fluid where the energy is proportional to the square of the oscillating pressure. There are other examples; the power dissipated in a resistor is proportional to the current squared and the kinetic energy of a molecule is proportional to the square of the velocity. Thus, in general if the signal is $$f$$, $$\langle f^2\rangle$$ represents the average energy or power. The period $$T$$ (equation (43)) is somewhat arbitrary and can reasonably take on any value; therefore, it is possible to define $$n/T \equiv \nu_n$$ as a frequency. The amount of power $$P$$ in a small frequency interval from $$\nu$$ to $$\nu + \nu + \delta \nu$$ is therefore $$\displaystyle P(\nu)d\nu = \frac{1}{2}\left(a_\nu^2 + b_\nu^2\right)$$ and the autocorrelation can be written as an integral over frequencies rather than a summation over index $$n$$. This effectively means that there are so many terms in the sum that it can be changed into an integral without any significant error, and doing this produces the autocorrelation;

$\displaystyle A(u)=\int_{v=0}^\infty P(\nu)\cos(2\pi\nu u)d\nu \qquad\tag{44}$

Comparing this equation with a Fourier transform equation, the power spectrum is

$\displaystyle P(\nu) = 4\int_{u=0}^\infty A(u)\cos(2\pi\nu u)d\nu \qquad\tag{45}$

and these two equations are known as the Wiener - Khinchin relationships: the power spectrum $$P(\nu)$$ and autocorrelation $$A(u)$$ form a Fourier transform pair. Very often the transform pair involve time and frequency, in which case the changes $$u\to t$$ and $$P(\nu) \to J(\nu)$$ are commonly made. In NMR and other spectroscopies $$J(\omega)$$ is called the spectral density.

The power spectrum is proportional to what we would normally observe in a spectroscopic experiment, as the change in the signal vs frequency. The width of the signal is determined by the autocorrelation and this is determined by the noise. If the noise is due to a random process then it is often found that the autocorrelation decays exponentially as $$\displaystyle e^{-t/\tau}$$ with rate constant $$k=1/\tau$$. In this case the power spectrum $$J(\nu)$$ is

$\displaystyle J(\nu) =4\int_{u=0}^\infty e^{-u/\tau}\cos(2\pi \nu u)du = \frac{4\tau}{1+(2\pi\nu \tau)^2} \qquad\tag{46}$

and the integral is most easily evaluated by converting the cosine to its exponential form.

The nature of the random processes contributing to the power spectrum is now considered using NMR as an example. The nuclear spin angular momentum in a molecule remains in fixed precessing motion governed by the external magnetic field, but the molecules themselves also undergo random rotational diffusion due to thermal agitation when in solution. This random motion causes the nuclear spin to experience a fluctuating magnetic field in addition to the applied external field. Therefore, those nuclei undergoing NMR transitions experience this fluctuating field and its effect is to return the nuclear spin population to equilibrium with a lifetime called T1 (Sanders & Hunter 1987; Levitt 2001). The timescale of these fluctuations is of the order of tens of picoseconds because this is the timescale of molecular rotation. ( Translational diffusion is far slower ). The molecular rotation rate constant and hence frequency is similar to that of the NMR transition frequency (Larmor frequency) and therefore rotational diffusion can greatly influence the return to equilibrium of the nuclear spins and can dominate both the T1 and T2 decay processes. Loss of spin coherence is characterized by the lifetime T2.

Molecular translational diffusion is far slower than rotation and so causes magnetic field fluctuations at a far lower frequency than the NMR transition and is therefore less important for T1 processes. Similarly, vibrational motion is too high to influence the NMR transition. Large molecules in a viscous solvent have a sluggish response and a small rotational diffusion coefficient, and long rotational relaxation times, and vice versa. However, while different solvents and molecules of different sizes will change the frequency of the random magnetic field fluctuations, the timescale remains comparable to that of the NMR transition. In proteins, while overall rotation can be slow, approximately tens of nanoseconds, faster local motion of residues called ‘wobbling in a cone’ motion still occurs.

The autocorrelation of rotational diffusion can be shown to be an exponentially decaying function with a lifetime $$\tau$$ proportional to the reciprocal of the rotational diffusion coefficient. Fig. 34 shows the spectral density calculated for different rotational relaxation times. The coupling of the magnetic field fluctuations is most effective when $$1/2\pi\tau$$ is close to the Larmor frequency and therefore molecules of different sizes will be affected differently.

When plotted on a linear scale the spectral density of a slowly decaying exponential autocorrelation, equation 46, is a narrow function centred at zero frequency, whereas the rapidly decaying autocorrelation has the same shape but is wide. Zero frequency here means the transition frequency, see fig 34. The line-width is a consequence of the time-energy or time-frequency uncertainty, causing a wide spectral line when processes are rapid and vice versa. When plotted on a linear - log scale the power spectrum is constant over a wide range of low frequencies, and this is called ‘white noise’. It rapidly decreases, centred about the frequency $$1/2\pi\tau$$ as is shown in the figure. If the noise were completely random, the power spectrum would be constant at all frequencies.

The Weiner - Khinchin theorem also shows that the autocorrelation of the signal $$f$$ is the squared modulus of its Fourier transform $$g(k)$$. Apart from a constant of proportionality, this is

$\displaystyle A_a(u) =\int_{-\infty}^\infty f^*(t)f(u+t)dt = T[|g(t)|^2]$

Because the squared modulus of the Fourier transform is produced, the autocorrelation has lost all phase information so it is not possible to invert or reverse $$g(k)$$ to produce the original function $$f$$. Thus, in the NMR case, it is not possible to measure the spectral density, which is proportional the shape of the NMR transition, and then work backwards to obtain the function that produced this shape. All that can be done is to generate a model of the interactions, such as rotational diffusion, and, for example, by a non-linear, least-squares method fit this theoretical model to the data.

Figure 34. Left: Power spectra (or spectral density) vs. frequency for a signal that has an exponential autocorrelation function, the decay lifetimes of the exponentials are from $$1 \to 100$$ ps. The density of the fluctuation in the noise is almost constant at lower frequencies and this is called ‘white noise’.

## 8.7 FTIR supplement#

An overview of the FTIR spectrometer was given in section 5.2 and a schematic shown in figure 12. Here we discuss how the instrument measures the spectrum even though both beams pass through the sample and a single detector is used. This is unlike the situation in a uv-vis spectrophotometer where the light is split and passes separately through a sample and a reference cell and the signals from two detectors compared.

Recall that the FTIR instrument is a Michelson interferometer in which the input beam is made parallel and has a round cross-section as it passes through the instrument. This beam contains all wavelengths, its amplitude is divided at the beam splitter, and finally recombined onto a single detector whose output produces ‘fringes’ as one arm moves relative to the other. If $$d$$ is the difference in distance travelled by the beams they arrive at the detector at times separated by a delay of $$\tau=d/c$$ seconds. The detector measures the intensity $$I$$ which is the complex square of the amplitude of any wave $$f^*f = |f|^2$$. If the i.r. radiation is hypothetically monochromatic with frequency $$\omega_0$$ as the mirror is translated the detector measures a sinusoidally varying signal as the pathlength $$\tau$$ varies because the i.r. waves become in and out of phase with one another.

The amplitude or field is $$f=ae^{i\omega_0 t}$$ at frequency $$\omega_0$$ ($$\equiv 2\pi \nu_0$$) and at the detector the fields at time $$t$$ and $$t+\tau$$ are recombined as

$\displaystyle I(\tau)=\beta \int |f(t)+f(t+\tau)|^2dt \qquad\tag{46a}$

where $$\beta$$ is the product of reflectivity and transmission of the beam splitter. The signal is averaged at each time delay $$\tau$$ for a small time $$t_m$$, say a second. Expanding out (and ignoring limits for clarity) gives

\begin{split}\displaystyle \begin{align}I(\tau)/\beta &= \int\; \Big(f^*(t)+f^*(t+\tau)\Big) \Big( f(t)+f(t+\tau) \Big)\;dt\\&=\int f^*(t)f(t)dt+\int f^*(t)f(t+\tau)dt +\int f(t)f^*(t+\tau)dt +\int f^*(t+\tau)f(t+\tau)dt\end{align}\end{split}

The first and last integrals are just the average intensity which is constant, for example

$\displaystyle \int_0^{t_m} f^*(t+\tau)f(t+\tau)dt=a^2\int_0^{t_m} e^{-i\omega_0((t+\tau)}e^{+i\omega_0((t+\tau)} dt=a^2t_m$

The other integrals are autocorrelations

\begin{split}\displaystyle \begin{align}\int_0^{t_m} f^*(t)f(t+\tau)+ f(t)f^*(t+\tau) dt &= a^2\int_0^{t_m}e^{-i\omega_0 t}e^{i\omega_0 (t+\tau)}+e^{+i\omega_0 t}e^{-i\omega_0 (t+\tau)}dt\\ &=a^2t_m (e^{i\omega_0 \tau}+e^{-i\omega_0 \tau})\end{align}\end{split}

making

$\displaystyle I(\tau)= (2+e^{i\omega_0 \tau}+e^{-i\omega_0 \tau})C$

collecting the constants as $$C=a^2\beta t_m$$. As $$\displaystyle 2\cos(\omega_0\tau)=e^{i\omega_0 \tau}+e^{-i\omega_0 \tau}$$, then

$\displaystyle I(\tau)=C (1+\cos(\omega_0\tau) )$

which shows the sinusoidal variation on top of a constant signal. Recall that as $$\tau =d/c$$ the time delay is equivalent to a distance moved by the interferometer.

Molecules naturally have many vibrational and rotational transitions, think of the HCl rotational/vibration spectrum for example, and therefore the field at the detector will be the sum of many different frequencies, we call this distribution $$B(\omega)$$, which is the spectrum we hope to measure, and therefore

$\displaystyle I(\tau) =\int_0^\infty B(\omega)(1+\cos(\omega\tau) )d\omega$

where the constant is absorbed into $$B$$ and the integral is added because the detector measures all frequencies $$\omega$$ at the same time. At zero delay $$\tau=0,\, I(0)=2\int B(\omega)d\omega$$ which is a constant and shows that at time zero twice the total signal is measured. After rearranging

$I(\tau)- I(0)/2=\int_0^\infty B(\omega)\cos(\omega\tau) d \omega$

This is a fourier cosine transform and can be reverse transformed to give

$\displaystyle B(\omega) = \int_0^\infty \left(I(\tau)-\frac{I(0)}{2}\right)\cos(\omega\tau)d\tau\qquad\tag{46b}$

which is the basic equation for FTIR and is the cosine fourier transform of $$(I(\tau)-I(0)/2)$$ where $$I(\tau)$$ is the intensity the detector measures at delay time $$\tau$$. As $$\tau$$ changes this function will oscillate up and down as the phase between the two arms changes due to both pathlength change and absorption in the sample. How the transform extracts a signal is explained earlier in the chapter, see 6.4. To see that this equation is a fourier transform recall that $$\displaystyle 2\cos(\omega\tau)=e^{i\omega \tau}+e^{-i\omega \tau}$$. The integration ranges from $$0\to \infty$$ which in practice is the distance that becomes $$\approx 500\to \approx 4000\; \mathrm{cm^{-1}}$$. Note that for each frequency $$\omega$$ the integration on the right has to be performed. Normally this will be done numerically using a fast four transform FFT.

At very long times there can no longer be any correlation between the two arms and the signal remaining is due to that of the two separate arms, the constant terms from eqn 46a, making the long time value $$I(0)/2$$.

So far we have tried to explain how the fourier transfer picks out transition frequencies but their magnitudes are also obtained and this is more subtle because both beams pass through the sample and contain the same frequencies. It is obvious that any absorption will affect the i.r. beam’s intensity, but both beams pass through the sample and are equally affected. The reason that the absorption magnitude can be measured is that the phase of the combined wave (one from each arm) is determined by the relative magnitude of each transition. This happens because the absorption of amplitude $$a_i$$ of a wave of frequency $$\omega_i$$ contributes to the sum $$\sum_i a_ie^{i\omega_i \tau}=a_0\sum_i e^{i\omega_i \tau+i\varphi_i}$$ and so the phase of the autocorrelation vs. $$\tau$$ is changed. This is shown in figure 34a for two transitions, in the first row of panels, the lower frequency is of greater intensity, and in the lower panel they are swapped in intensity but still have the same frequencies. The left most column (A, and D) shows the two waves vs. mirror displacement $$\tau$$ in the two cases. The yellow shading (around $$\tau=90$$) shows where the difference between them is most obvious, of course this repeats at each period. The centre panels (B & E; autocorrelations) shows the combined waves vs. displacement $$\tau$$ and on the right the spectrum obtained by fourier transform of the autocorrelations.

Figure 34a. Left column shows individual amplitudes of the waves of frequency $$\omega_0, \omega_1$$. The centre column shows how the autocorrelations differ when the amplitudes are different even though the two frequencies are unchanged. The yellow mask shows a region of most noticeable change. The right most column shows the spectrum computed from its autocorrelation. After A.Lipson 2011.

## 8.8 Spectral resolution#

In calculating the fourier transform. eqn 46b, the limits were taken to $$0\to \infty$$ and of course in an instrument this is clearly impossible, where the delay to one arm may extend only to a centimetre or so a time delay of $$\approx 0.033$$ ns. The limited range has the effect of convoluting a top-hat or rectangular shape with the delta function response of the ideal case when limits are $$\pm \infty$$. The result is a sinc function as shown in figures 15, i.e. a peak surrounded by many decreasing oscillations. In this respect the FTIR does distort the shape of the transition from its true Lorentzian shape, not that this matters in practice where only the frequency is important and the intensity only characterised as ‘weak’, to ‘strong’. More important is the resolution because the longer the maximum delay the narrower the peaks become and so finer features become distinguishable. The fwhm of the sinc function is $$0.6035/d_m$$ where $$d_m$$ is the maximum displacement of one arm of the interferometer vs. the other. If this distance is $$1$$ cm then the resolution will be $$0.6\;\mathrm{cm^{-1}}$$. Typically this would involve a transform of $$2^{13}=8192$$ points or a step of $$1.2\;\mathrm{\mu m}$$.

The calculation is

$\displaystyle \frac{1}{\sqrt{2\pi}}\int_0^{d_m} e^{-i\omega L}dL=\frac{d_m}{\sqrt{2\pi}}\frac{\sin(2\pi\bar\nu d_m)}{2\pi\bar\nu d_m}$

where $$\omega=2\pi\bar \nu$$ and $$\bar\nu$$ is in wavenumbers.

Figure 34b. The function $$\text{sinc}(x)=\sin(\pi x)/(\pi x)$$. Using $$\pi x$$ makes the zeros of the function appear at integer $$x$$ values and the fwhm is $$1.207/2d_m$$ where $$d_m$$ is the maximum path length difference.

Because of the distorting effect of the oscillations in the sinc function the fourier transform is apodised, that is, it is multiplied by a function that decreases with $$x$$, there are several forms of these, they all damp-out the oscillations but at a cost of broadening the transition, there is therefore a play-off between removing oscillations and hence removing distortion and loss of resolution. Bracewell (1986) gives examples of these and other aspects of fourier transforms.


text:
Asymptotic uniformity of the quantization error for Moran measures on $\mathbb{R}^1$. (arXiv:1802.03723v1 [math.FA])

Let $E$ be a Moran set on $\mathbb{R}^1$ associated with a closed interval $J$ and two sequences $(n_k)_{k=1}^\infty$ and $(\mathcal{C}_k=(c_{k,j})_{j=1}^{n_k})_{k\geq1}$. Let $\mu$ be the infinite product measure (Moran measure) on $E$ associated with a sequence $(\mathcal{P}_k)_{k\geq1}$ of positive probability vectors with $\mathcal{P}_k=(p_{k,j})_{j=1}^{n_k},k\geq 1$. We assume that $\inf_{k\geq1}\min_{1\leq j\leq n_k}c_{k,j}>0,\;\inf_{k\geq1}\min_{1\leq j\leq n_k}p_{k,j}>0.$ For every $n\geq 1$, let $\alpha_n$ be an $n$ optimal set in the quantization for $\mu$ of order $r\in(0,\infty)$ and $\{P_a(\alpha_n)\}_{a\in\alpha_n}$ an arbitrary Voronoi partition with respect to $\alpha_n$. For every $a\in\alpha_n$, we write $I_a(\alpha,\mu):=\int_{P_a(\alpha_n)}d(x,\alpha_n)^rd\mu(x)$ and $\underline{J}(\alpha_n,\mu):=\min_{a\in\alpha_n}I_a(\alpha,\mu),\; \overline{J}(\alpha_n,\mu):=\max_{a\in\alpha_n}I_a(\alpha,\mu).$ We show that \$\underline{J}(\alpha_n,\mu),\overline{J}( 查看全文>>


text:
## Notes to The Epistemology of Visual Thinking in Mathematics

1. A geodesic space is a metric space in which for any two points there is a geodesic segment from one to the other. Let $$b$$ and $$c$$ be points in metric space $$(X, d)$$ such that $$d(b, c) = r$$. Then a geodesic segment from $$b$$ to $$c$$ is the image of an isometric embedding $$g$$ of real interval $$[0, r]$$ into $$X$$ with $$g(0) = b$$ and $$g(r) = c$$. The embedding $$g$$ is isometric when $$d(g(x), g(y)) = y - x$$ for all $$0 \le x \le y \le r$$.

2. Figure 13a was created by Wikipedia user Ylebru and released into the public domain; the original can be found at commons.wikimedia.org/wiki/File:Triangolo_iperbolico.svg. Figure 13b was created by Wikipedia user Stomatapol and licensed as Creative Commons Atttribution-Share Alike 3.0; the original can be found at commons.wikimedia.org/wiki/File:Delta_thin_triangle_condition.svg