next up previous
Next: Computation of the functions Up: sampling Previous: sampling

What is sampling? (aka What are these $\psi$ functions I keep hearing about?)

Sampling is the practice of reconstructing a function from its values at a finite number of points. The simplest case is to consider is a function $f:[0,\pi]\rightarrow\mathbb{R}$. Clearly, not every function can be reconstructed, as seen in the example below:

One will note that at the marked points, both the red and the blue functions are $0$, but only one is the constant function $0$, hence sampling would fail at these points.

Hence, some restrictions must be put on $f$. For a sufficiently nice function $f$ on $[0,\pi]$, with $f(0)=f(\pi)=0$, $f$ may be expanded into a sine series:

\begin{displaymath}f(t)=\sum_{k=1}^{\infty}c_k sin(kt)\end{displaymath}

.
One says $f$ is band-limited with bandwidth $n$ if $c_k=0, \forall k>n$. In this case, one can see that in fact,

\begin{displaymath}f(t)=\sum_{j=1}^{n} f(\frac{j\pi}{n+1})\frac{sin((n+1)t)}{sin( t-\frac{j\pi}{n+1} )}\end{displaymath}


Hence, we see that bandlimited functions of bandwidth $n$, can be reconstructed by sampling from $n$ points.

We wish to study the analogous concept on the Sierpinski Gasket. First, one must note that $-\Delta sin(kx)=k^2sin(kx)$, and hence $sin(kx)$ is an eigenfunction of the laplacian of eigenvalue $k^2$. Moreover, $sin(k0)=sin(k\pi)=0$, and so we say that $sin(kx)$ has Dirichlet boundary conditions. Hence, for a function $f$ defined on the Sierpinski Gasket, we say $f$ is bandlimited if $f(x)=\sum_{\lambda_k\le a(n)} c_k \phi_k(x)$, where $-\Delta \phi_k = \lambda_k \phi_k$ and $\phi_k\vert _{V_0} = 0$.
It makes the most sense to sample on $V_n$, the $n$th level of the Sierpinski Gasket. One wishes to find functions $\psi_y(x):G\rightarrow\mathbb{R}$ such that, for a band limited function $f$, $f(x)=\sum_{y\in V_n-V_0}f(y)\psi_y(x)$.
Hence, we wish to have $\psi_y(x)=\sum_{\lambda_k\le a(n)}c_k(y)\phi_k(y)$, and $\psi_y(x)=\Delta_{x,y}$ for $x\in V_n-V_0$. Consider the matrix $A=(\phi_k\vert _{V_m-V_0}(x)$, letting $x$ and $k$ vary. This matrix is square and invertible due to a result by Shima and Fukashima. Noting that $A^{-1}A=I$, we see that we ought to define $\psi_y(x)=\sum_{k=1}^{\vert V_m-V_0\vert} (A^{-1})_{k,y} \phi_k(x)$. Since this was essentially a change of basis, clearly we will be able to reconstruct bandlimited functions with these $\psi$ functions.


next up previous
Next: Computation of the functions Up: sampling Previous: sampling
Brain Street 2001-11-11