Machine learning: Homework: integral metrics

Metrics on continuous functions #

Background #

In our first analysis course, we studied one way of measuring distance between continuous functions: the uniform metric. Let us write \(\mathcal{C}[a,b]\) for the set of real-valued continuous functions defined on the interval \([a,b]\). If \(f\) and \(g\) are members of \(\mathcal{C}[a,b]\) then the uniform metric is: \[\rho(f,g) = \max_{x\in[a,b]} |f(x) - g(x)|.\] I will not detail the proof why this is in fact a metric here, but just note that the definition itself makes sense: since \(f\) and \(g\) are continuous, so is their difference; and since the absolute value function is continuous, so is the composition \(|f(x) - g(x)|\). Finally, by a theorem from analysis, any continous function on a compace set has a maximum value. Visually, this metric measures the greatest vertical distance between the graphs of the two functions on the interval \([a,b]\). The goal of these exercises is to explore another family of metrics on \(\mathcal{C}[a,b]\).

Integral-based metrics #

The uniform metric is some sense measures the worst-case scenario: two functions can be fairly close over most of \([a,b]\) but differ substantially only near one point. Their uniform distance will be large. Sometimes it is desirable to account for the difference of the two functions over all of the interval. One approach is to measure the area between the two graphs: \[\rho_1(f,g) = \int_a^b |f(x) - g(x)| \; dx.\]

Exercise: Make sure this definition makes sense: can you always compute \(\rho_1(f,g)\) and does it really represent the area between the two graphs of the functions? Why?
Homework exercise: Show that \((\mathcal{C}[a,b], \rho_1)\) forms a metric space. Hint: Two results from your first analysis class may be especially useful: the triangle inequality for real numbers, and the fact that if a continuous function is positive near \(x\), it will also be positive on a small interval around \(x\).

It turns out that this is not the only way to proceed. A variant of the integral idea is to take powers. Consider the function: \[\rho_2(f,g) = \sqrt{\int_a^b |f(x) - g(x)|^2 \; dx.}\]

Exercise: Make sure this definition also makes sense. More precisely, if \(f\) and \(g\) are both continuous functions, can you always compute \(\rho_2(f,g)\), at least in principle?
Homework exercise: Show that \((\mathcal{C}[a,b], \rho_2)\) forms a metric space. Hint: To prove the triangle inequality use the integral version of the Cauchy-Schwarz inequality: \[ \Big(\int_a^b f \cdot g \Big)^2 \leq \int_a^b f^2 \cdot \int_a^b g^2. \] You may use this inequality without proof, but if you have time, read an understand its why it is true; it is short and fun, but takes a little time to digest.

More integral-based metrics #

There are even more ways to proceed! Another variant of the integral idea is to take other powers. Let \(p\geq 1\) and consider the function: \[\rho_p(f,g) = \sqrt[p]{\int_a^b |f(x) - g(x)|^p \; dx.}\]

Challenge exercise: Show that \((\mathcal{C}[a,b], \rho_p)\) forms a metric space if \(p\geq 1\). You will need to figure out what the correct version of the Cauchy-Schwarz inequality is necessary. Consider the following additional questions:

  • Does this definition yield a metric space if \(p<1\)? If so, prove it, and if not, find an example where it fails.
  • What differences between two functions are emphasized by different choices of \(p\)? When would we use one versus another?
  • What happens as \(p \rightarrow \infty\)? Do you recognize this metric?

Challenge exercise: A linear transformation \(A :\mathbb{R}^n \rightarrow \mathbb{R}^n \) is an isometry for the metric \(\rho_p\) if and only if \[ \rho_p (Ax, Ay) = \rho_p(x,y)\] for all vectors \(x\) and \(y\) in \(\mathbb{R}^n\). For instance, things like rotations preserve the \(\rho_2\)-distance and so are isometries for \(\rho_2\). Show the following:

According to Scott Aaronson the latter result is one of the reasons that the classical and quantum models for the world are the only two reasonable possibilities (!).