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')

One thought on “Haar basis

Comments are closed.