{ "cells": [ { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "%matplotlib inline\n", "import matplotlib\n", "import matplotlib.pyplot as plt\n", "\n", "import numpy as np" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Exercise 1: Cranking The Machine #\n", "\n", "Typically the scaling function $\\phi$ is not known explicitly, and sometimes a closed-form analytic formula does not even exist.\n", "However, for continuous $\\phi$ we can approximate the function to arbitrarily high precision using the Cascade Algorithm, a fixed-point method for functions.
\n", "\n", "In this exercise we want to implement this algorithm by iterating over the expression\n", "\\begin{equation}\n", " F(\\gamma)(t) = \\sum_k c_k \\cdot \\gamma(2t-k)\n", "\\end{equation}\n", "in order to find the fixed point $\\gamma$ of $F$. That is, at iteration $n$, \n", "\\begin{equation}\n", " \\gamma_{n+1}(t) = \\sum_k c_k \\cdot \\gamma_n (2t-k)\n", "\\end{equation}\n", "\n", "Our starting point $\\gamma_0$ will be the mother function of all hat functions over the interval $[-1,1]$.\n" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "ename": "IndentationError", "evalue": "expected an indented block (, line 10)", "output_type": "error", "traceback": [ "\u001b[1;36m File \u001b[1;32m\"\"\u001b[1;36m, line \u001b[1;32m10\u001b[0m\n\u001b[1;33m class FixedPointWaveletApproximation:\u001b[0m\n\u001b[1;37m ^\u001b[0m\n\u001b[1;31mIndentationError\u001b[0m\u001b[1;31m:\u001b[0m expected an indented block\n" ] } ], "source": [ "class HaarScalingFunction:\n", " c = (1.0, 1.0)\n", " \n", "class Daubechies4ScalingFunction:\n", " c = (0.683012701892, 1.18301270189, 0.316987298108, -0.183012701892)\n", " \n", "class FixedPointScalingApproximation:\n", " #TODO\n", " \n", "class FixedPointWaveletApproximation:\n", " #TODO" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "ename": "NameError", "evalue": "name 'HaarScalingFunction' is not defined", "output_type": "error", "traceback": [ "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[1;31mNameError\u001b[0m Traceback (most recent call last)", "\u001b[1;32m\u001b[0m in \u001b[0;36m\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mScalingFunction\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mHaarScalingFunction\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m 2\u001b[0m \u001b[1;31m#ScalingFunction = Daubechies4ScalingFunction\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 3\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 4\u001b[0m \u001b[0ma\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mb\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;33m-\u001b[0m\u001b[1;36m1.0\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;36m4.0\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 5\u001b[0m \u001b[0mplotLevel\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;36m8\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n", "\u001b[1;31mNameError\u001b[0m: name 'HaarScalingFunction' is not defined" ] } ], "source": [ "ScalingFunction = HaarScalingFunction\n", "#ScalingFunction = Daubechies4ScalingFunction\n", "\n", "a, b = -1.0, 4.0\n", "plotLevel = 8\n", "itermax = 4\n", "\n", "fig = plt.figure(1, figsize = (11, 9))\n", "plt.suptitle('Cranking my own machine')\n", "_ = plt.grid(True)\n", "_ = plt.ylim(-1.5, 1.8)\n", "\n", "# starting point in the fixed point iteration\n", "hat = lambda t: max(0.0, 1-abs(t))\n", "\n", "# set of sampling points used for plotting\n", "x = np.linspace(a, b, int(b-a) << plotLevel)\n", "\n", "# plot the hat function\n", "ax = []\n", "ax.append(plt.plot(x, map(hat, x), label=\"hat\"))\n", "\n", "# Output scaling functions (father)\n", "fixedPointScaling = [hat,] + [None,]* itermax\n", "\n", "# Output wavelet functions (mother)\n", "fixedPointWavelet = [hat,] + [None,]* itermax\n", "\n", "for i in xrange(1, itermax + 1):\n", " fixedPointScaling[i] = FixedPointScalingApproximation(fixedPointScaling[i-1])\n", " fixedPointWavelet[i] = FixedPointWaveletApproximation(fixedPointScaling[i-1])\n", "\n", "ax.append(plt.plot(x, map(fixedPointScaling[itermax], x), label=\"scaling [%d]\" % itermax))\n", "ax.append(plt.plot(x, map(fixedPointWavelet[itermax], x), label=\"wavelet [%d]\" % itermax))\n", "\n", "_ = plt.legend()\n", "_ = plt.show()\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Exercise 2: The Haar Wavelet Basis Transform #\n", "\n", "In this exercise we want to compute the 1-$d$ wavelet transform for the Haar wavelet family and apply it to a signal vector $\\vec{s}$ of length $m=2^n$.
\n", "The transform can be implemented very efficiently as a pyramidal algorithm'' taking $\\mathcal{O}(m)$ steps.
\n", "For educational purpose we focus on the $\\mathcal{O}(m^2)$ matrix-based algorithm." ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [], "source": [ "def buildHaarWaveletTransformationMatrix(level, inverse=False):\n", " '''\n", " Haar Wavelet Transform as dense matrix\n", "\n", " @param level matrix dimensions are (2^level x 2^level)\n", " @param normalized build orthogonal matrix\n", " @param inverse build the inverse transformation matrix\n", " '''\n", " M = []\n", "\n", " # TODO\n", " \n", " return M" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[]\n", "[]\n" ] } ], "source": [ "M = buildHaarWaveletTransformationMatrix(3, False)\n", "M_inv = buildHaarWaveletTransformationMatrix(3, True)\n", "print M\n", "print M_inv" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [], "source": [ "def PyramidalAlgorithm(level, s_vec): \n", " d_vec = np.array(s_vec) # output vector\n", " \n", " # TODO\n", " \n", " return d_vec" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Input signal: [ 1. 2. 3. -1. 1. -4. -2. 4.]\n" ] }, { "ename": "ValueError", "evalue": "matrices are not aligned", "output_type": "error", "traceback": [ "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[1;31mValueError\u001b[0m Traceback (most recent call last)", "\u001b[1;32m\u001b[0m in \u001b[0;36m\u001b[1;34m()\u001b[0m\n\u001b[0;32m 3\u001b[0m \u001b[1;32mprint\u001b[0m \u001b[1;34m'Input signal: '\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0ms\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 4\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 5\u001b[1;33m \u001b[0md\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mnp\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0marray\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mnp\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mdot\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mM_inv\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0ms\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mtranspose\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m 6\u001b[0m \u001b[1;32mprint\u001b[0m \u001b[1;34m'Result from Matrix transformation: '\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0md\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 7\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n", "\u001b[1;31mValueError\u001b[0m: matrices are not aligned" ] } ], "source": [ "# Input signal vector\n", "s = np.array([1.0, 2.0, 3.0, -1.0, 1.0, -4.0, -2.0, 4.0])\n", "print 'Input signal: ',s\n", "\n", "d = np.array(np.dot(M_inv,s.transpose()))\n", "print 'Result from Matrix transformation: ',d\n", "\n", "dd = PyramidalAlgorithm(3, s)\n", "print 'Result from Pyramidal Algorithm: ',dd\n", "\n", "ss = np.array(np.dot(M, d.transpose()))\n", "print 'Resutl from reversed Matrix transforamtion: ',ss.transpose()\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 2", "language": "python", "name": "python2" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.14" } }, "nbformat": 4, "nbformat_minor": 1 }