Haar basis

Hilbert spaces play a prominent role in various fields of mathematics. An orthonormal basis of such a space is called a Hilbert basis. The purpose of this blog is to illustrate a very clasic and basic Hilbert basis – the Haar basis.

Let $(f_i)_{i \in I}$ be a Hilbert basis of $H:=L^2([0,1])$ equipped with the standard scalar product $(\cdot,\cdot)$ . Hence, every $f\in H$ can be written in a unique way as

$f = \sum_{i\in I} \alpha_{i} f_i,$

where $\alpha_{i}=(f,f_i)$

and $\sum_{i\in I} \alpha_{i}^2=\|f\|_2^2<\infty$

A classic Hilbert basis consists of Haar functions that are supported on $[0, 1]$ . They are defined using the Haar wavelet:

$h(x)=\left\{ \begin{array}{ll} 1 & 0< x \leq 1/2 \cr -1& 1/2 \leq x \leq 1 \cr 0& \mbox{otherwise}.\end{array}\right.$

The Haar basis consists then of rescaled (by $2^{j}$ ) versions of $h(x)$ shifted by $2^{-j}k$ ,

$h_{k}^{j}(x)= 2^{j/2} h(2^{j}x -k),\quad j \in \mathbb{N}\cup\{0\}, 0\leq k < 2^{n},$

together with the constant function $1$ . (Note: the constant function has to be added since we consider the interval $[0,1]$ and not $\mathbb{R}$ ). In R this looks like:

haar_mother <- function(x){
   (x >0 & x <= 0.5) - (x >0.5 & x <= 1)
}
haar <- function(x,j,k){
  2^(j/2) * haar_mother(2^j*x-k)
}

Animation of the Haar basis

j_max <- 3    # maximal depth
n_max <- 10   # resolution of grid
df <- data.frame(x=numeric(),
                 y=numeric(),
                 id=numeric())

x <- (1: 2^n_max)/2^n_max
id<-1
for (j in 0:j_max){
  for (k  in 0:(2^j-1))
  {
    df_new<- data.frame(x=x,
                        y=haar(x,j,k),
                        id=id)
    df <- bind_rows(df, df_new)
    id <- id+1
  }
}

ggplot(df, aes(x=x, y=y)) + 
  geom_step()+
  transition_states(
    id,
    transition_length = 2,
    state_length = 5
  ) +
  labs(title = 'Illustration of Haar basis') +
  ease_aes('sine-in-out')

Approximation via Haar basis

Now, every function $f\in L^{2}([0,1])$ can be written as

$f(x)=\sum_{j,k} (f, h_{k}^{j}) h_{k}^{j}(x) + (f,1).$

The coefficients $\alpha_{k}^{j}=(f, h_{k}^{j})$ are called the Haar Wavelet coefficients. Let us calculate them in the discrete setting. We give us a mesh $x$ and values $y$ and some function $f(x)=x \sin(x)$ :

j_max <- 12
n_max <- 13  # maximal resolution
delta <- 2^{-n_max}
x <- (1: 2^n_max)/2^n_max
y <- x* sin(1/x) 
alpha <- list()  # list of Haar coefficients
for (j in 0:j_max){
  alpha[[j+1]] <- rep(0, 2^j)
  for (k  in 0:(2^j-1))
  {
    alpha[[j+1]][k+1] <-sum(haar(x,j,k)*y)*delta  # approximation of scalar product
  }
  
}

y_approx <- rep(0, length(y))  # approximated values of y

#### Calculating the approximations for different values of j

df <- data.frame(x=numeric(),
                 y=numeric(),
                 id=numeric())


y_approx <-  mean(y) # this is the contribution of the constant function
for (j in 0:j_max){
  for (k  in 0:(2^j-1))
  {
    y_approx <- y_approx + alpha[[j+1]][k+1]*haar(x,j,k)
  }
  df_new <- data.frame(x=x,
                       y=y_approx,
                       id=j)
  df <- bind_rows(df, df_new)
}

Animation of convergence


ggplot(df, aes(x=x, y=y)) + 
  geom_step()+
  transition_states(
    id,
    transition_length = 2,
    state_length = 1
  ) +
  labs(title = "Haar basis approximation of x sin(1/x). Depth:  {closest_state}") +
  ease_aes('sine-in-out')

Haar basis

Animation of the Haar basis

Approximation via Haar basis

Animation of convergence

Related

Published by Naitsabes

One thought on “Haar basis”