linux and windows tips, mathematics, and some recipes

Thursday, December 29, 2005

Elementary Wavelet Analysis

This is the abstract for my MSci thesis on wavelet analysis. For the full article, see my main site.

Abstract: A discussion of orthonormal wavelet bases and wavelet
series, utilising the notion of multiresolution approximations. I start by discussing multiresolution approximations and show how to find an orthonormal basis of the generating space, consisting of translates of a `scaling function' φ. The notion of orthornormal wavelet bases is then introduced, and it is shown how one can go from a multiresolution approximation to a wavelet basis with a scaling function, and vice-versa. The article then turns to the description of wavelet bases of compact support and multi-dimensional wavelet bases (using the tensor product method). Finally, the regular wavelets of compact support are seen to form an unconditional basis of the space H1(Rn) of Stein and Weiss, this being an interesting subspace of L1(Rn).

This is my MSci project, which I undertook in the fourth year of my undergraduate degree at Imperial College, London. It is concerned with mathematical entities known as wavelets, and uses the wavelets to investigate a space called H1(Rn).

Though the title of the project is 'Elementary' wavelet analysis, you still do need to know some maths to understand it! In particular, you should be aquainted with undergraduate functional analysis. If you'd prefer something less technical, why don't you try The Engineers Ultimate Guide to Wavelet Analysis. This Internet article was written by a non-mathematician and designed for non-mathematicians, so anyone (well any scientist or engineer) should find it quite accessible. If you want to read more on the topic, then another not-so-technical resource is G. Kaiser, A Friendly Guide to Wavelets, Birkhauser, Boston 1994. A good introductory volume for the more mathematically minded amongst you is C. K. Chui, An Introduction to Wavelets, Academic Press Inc., New York, 1992. But the book I referred to mostly whilst writing my project was Y. Meyer, Wavelets and operators, Cambridge University Press, Cambridge, 1992. It's a pretty tough going book and I wouldn't recommend it unless you're really up to scratch on your real analysis; nonetheless it is required reading if you seriously want to understand the deeper theoretical foundations of the wavelet theory.

In case you meet the above requirement and are interested in reading further, you might first like to know a little about what wavelets are and how they can be used.

A one-dimensional wavelet basis is a basis of L2(R) (depending upon the author, the basis may or may not be required to be orthonormal) and equally an n-dimensional wavelet basis is a basis of L2(Rn), in much the same manner the complex exponentials form an orthonormal basis of L2(0,2π). So indeed wavelet analysis shares some similarities with Fourier analysis. However if you read the article, you'll find that wavelets really kick arse, compared with Fourier analysis.

GnuPG and Friends

Installation of GnuPG

GnuPG is the GNU Privacy Guard — an open source replacement for PGP. GnuPG can be used for encrypting and/or signing emails and other documents.

I'm going to describe the process of setting up GnuPG with Microsoft Windows XP. Another short guide is to be found on The canonical reference is the Gnu Privacy Handbook.

First you need to download a copy of GnuPG, verify its authenticy, then install it. The instructions for so doing are to be found on the GnuPG website.

Having installed the software, I recommend adding GnuPG to your %PATH% environment variable. To do this, right-click on "My Computer", select Properties, then Advanced, then environment Variables. Add (if it doesn't exist) or Edit (if it does), the User Variable "PATH". Add the value C:\Program Files\GNU\GnuPG. You may now access gpg from the command line.

Your personal data will be stored in %APPDATA%\gnupg. Typically, if your username is Bob, the personal data will be stored in C:\Documents and Settings\Bob\Application Data\gnupg.

If you already have some keys from another installation of GnuPG (which will be found in files called secring.gpg and pubring.gpg), you may import them with gpg --import filename.

If you don't already have your own keys, you'll have to generate them with the command gpg --gen-key. Follow the instructions. I recommend generating a key-pair which doesn't expire, though this can be changed later. Make your passphrase fairly long!


Your key is useless unless you can share it with others. One way to share your key is to use a keyserver. First find the keyID of your public key with gpg --list-keys. The keyID is an
8-digit hexadecimal number. The keyID for one of my public keys is CC144DA2. We'll use this in the following examples.

Before sending the key to a server, it's a good idea to create a revocation certificate. You'll need this if your key is every compromised. The revocation certificate is used to inform a server that the key has been revoked. The syntax for the creation of a revocation certificate is gpg -a --output filename --gen-revoke CC144DA2.

We may now add our public key to a key server. Here is the command:
gpg --send-keys --keyserver CC144DA2


Now we need to do something useful with GnuPG! I assume you're using the Thunderbird/Mozilla email client. Find and install the enigmail extension. The only setup required is to tell enigmail where to find GnuPG. Close down and restart Thunderbird (if you haven't done so already). Loacte the OpenPGP menu and select Preferences. For the GnuPG executable path, enter C:\Program Files\GNU\GnuPG\gpg.exe. It should be fairly clear how to
operate Enigmail.

Fingerprints; the Web of Trust

I mentioned that a key pair is only useful if the public key is shared. However, you need to ascertain that a key you find (from a keyserver, for example) really does belong to the person it claims to. This is where fingerprints enter the picture.

Each key has a fingerprint associated with it. If you download a key, you can contact the key's owner in person to find out the key's fingerprint. If the fingerprints match, you can be almost certain that you have found a valid key. You can find the fingerprint of a key by entering gpg --fingerprint keyID. Once you are certain of the authenticity of a key, you may sign it with your own secret key. Having signed the key, you may send the updated key to a keyserver (note, you will be sending someone else's key to the keyserver!).

Anyone who subsequently downloads the key from the server will see that you have placed your seal of approval on the key. If they have a validated copy of your key, this may give them some level of confidence that the key is authentic, without having to check the fingerprint themselves. In fact, GnuPG has a built-in system called the web of trust which automates this process to some extent.

For more information on these issues, please refer to the GNU Privacy Handbook.

First Day

Having spent almost nine years surfing the web, this is my first foray into the world of blogging. It remains to be seen what I intend to do with this site, but I hope it will be of some interest!

In the meantime, I'll point to some of the work on my main website. I have a discussion of cryptography, focusing on the RSA code; it is interactive and allows one to encode and decode text messages with the RSA algorithm. I also have a page on partial fractions, which I hope will be useful to advanced high-school students who want a more thorough understanding of this topic.