Reducing an infinite dimensional expansion to a finite dimensional algorithm

Question

The following is a big-picture question about the interplay between infinite dimensional function expansions and finite dimensional algorithms. I feel like I have a good understanding of these ideas (I use them nearly every day), but I'm interested to hear if anyone has a nice, simple way to connect the dots. Consider the following:

Suppose (for concreteness) we have an orthonormal basis $\{e_k\}$ of $L^2(\Bbb{R})$, so that for each $f\in L^2$ we may write (in the $L^2$ sense)

$$ f=\sum_{k\in\Bbb{Z}}\langle f,e_k\rangle e_k\tag{1} $$ My favorite such example is an orthonormal wavelet basis (more generally a wavelet frame), though this isn't important.

The expansion (1) defines an operator $T:L^2(\Bbb{R})\rightarrow l^2(\Bbb{Z})$, which we call the analysis operator, and the coefficients $\langle f,e_k\rangle$ provide the components of $f$ `in the direction' of $e_k$ - for example, they might provide frequency, smoothness, correlation, etc.

Now, in the so-called real world of numerical analysis, we never have the complete function $f\in L^2(\Bbb{R})$, but rather we have a finite dimensional approximation of $f$, say obtained via sampling. Let's call it $f_h\in\Bbb{C}^N$. The goal is now to approximate $\langle f,e_k\rangle$ using only $f_h$, that is provide an approximation to the analysis operator. In other words, we want a finite dimensional operator $T_h:\Bbb{C}^N\rightarrow\Bbb{C}^N$ which in some way approximates $T:L^2(\Bbb{R})\rightarrow l^2(\Bbb{R})$.

Is there a systematic or general way to handle this process? I have lots of specific examples, e.g. reducing the Fourier transform to the DFT and wavelet expansions to the DWT, but I'm curious if there is deeper/broader theory here. Thanks!

Answer 1

The general formulation is harmonic analysis on finite group. For example, if $f\in L^2(\mathbb{R})$, an $n$-point sampling produces $S_n$, i.e., the cyclic group of order $n$. The DFT basis are irreducible representations of $S_n$.

finite group

applications

Answer 2

Before I start Id like to suggest some methods I found here and here, the wiki articles are not too detailed, but I'm sure one can find papers relating to these procedures. These techniques sort of remind me of auto-correlation, smoothing and time series related theory.

This is an interesting question, this I think in some way relates functional analysis, spectral theory and quantum mechanics and the part where it gets really interesting is when you start to look at the structures of the first two in the interpretation of the third.

In short we take the probability distribution interpretation of the Fourier spectrum of a function $f \in L^p(\mathbb R)$. If we get a finite dimensional approximation to the function by sampling, then we can sort of treat the problem of approximation of the Fourier spectrum as a distribution fitting exercise.

Let the signal be $x(t) \in \mathbb R$, now we can treat it as a probabilistic signal by the following $x(t) \tilde \quad N(\mu(t), \sigma^2(t))$. From here on we try to estimate the distributions of $\mu(t)$ and $\sigma^2(t)$ using a procedure like. (If $x \in \mathbb C$ then this shall be done in two dimensions, Real and Imaginary).

A) Divide the $N$ observations $\{x_0,...,x_{N-1}\}$ into $K$ bins.

B) For each bin $k$ which ranges from $(x_{(k-1){N/K}}, ..., x_{(k{N/K}) - 1})$ estimate the parameters $\mu_k$ and $\sigma^2_k$, if you are using Bayesian distribution fitting then model them on a prior like $\mu_k \tilde \quad N(\theta , \gamma^2)$.

C) Using the formula for DFT one can see that the frequency spectrum can be represented as the distribution. $$X_k \tilde \quad N(\sum_{n = 1}^{K}{\mu_n e^{-2i\pi nk/K}}, \sum_{n = 1}^{K}{\sigma^2_n e^{-2i\pi nk/K}})$$ or $${\bf X} \tilde \quad N(DFT[{\mu}], DFT[{\sigma^2}])$$

Please note that the last $\mu$ and $\sigma$ inside the $DFT$ are $K$ dimensional vectors.

P.S. The standard methods quoted at the start should work fine I guess, I was only thinking out loud and trying to find my own way around the problem. Something tells me this method might work if one has a large number of data points and one can divide them into many bins of small size.

EDIT: Taking the mean of the distributions as the estimator of the spectral density, one can obtain the map $T_h : \mathbb C^K \rightarrow \mathbb C^K$ This does not strictly obey your conditions on $T_h$ being a function from $\mathbb C^N \rightarrow \mathbb C^N$ but it sort of estimates it on the "reduced space" $\mathbb C^K$.

Answer 3

If the quantity you want to express is, for instance a solution of a partial differential equation, then Galerkin approximation is an approximation process in which one balances approximation accuracy with computational time. If the level of approximation is specified beforehand but one refines the approximation (e.g. adding more wavelets to your expansion) in view of some already computed quantities one speaks of adaptive methods.

Googling "adaptive finite element methods" or "adaptive wavelet methods" will lead you to a lot of work in these fields. Also there are several books (Babushka, Rannacher, Cohen, Dahmen, Hackbusch,…).