Bivariate wavelet construction based on solutions of algebraic polynomial identities
Date
2012-03
Authors
Van der Bijl, Rinske
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: Multi-resolution analysis (MRA) has become a very popular eld of mathematical study
in the past two decades, being not only an area rich in applications but one that remains
lled with open problems. Building on the foundation of re nability of functions, MRA
seeks to lter through levels of ever-increasing detail components in data sets { a concept
enticing to an age where development of digital equipment (to name but one example)
needs to capture more and more information and then store this information in di erent
levels of detail. Except for designing digital objects such as animation movies, one of the
most recent popular research areas in which MRA is applied, is inpainting, where \lost"
data (in example, a photograph) is repaired by using boundary values of the data set
and \smudging" these values into the empty entries. Two main branches of application
in MRA are subdivision and wavelet analysis. The former uses re nable functions to
develop algorithms with which digital curves are created from a nite set of initial points
as input, the resulting curves (or drawings) of which possess certain levels of smoothness
(or, mathematically speaking, continuous derivatives). Wavelets on the other hand, yield
lters with which certain levels of detail components (or noise) can be edited out of a
data set. One of the greatest advantages when using wavelets, is that the detail data is
never lost, and the user can re-insert it to the original data set by merely applying the
wavelet algorithm in reverse. This opens up a wonderful application for wavelets, namely
that an existent data set can be edited by inserting detail components into it that were
never there, by also using such a wavelet algorithm. In the recent book by Chui and De Villiers (see [2]), algorithms for both subdivision and wavelet applications were developed
without using Fourier analysis as foundation, as have been done by researchers in earlier
years and which have left such algorithms unaccessible to end users such as computer
programmers. The fundamental result of Chapter 9 on wavelets of [2] was that feasibility
of wavelet decomposition is equivalent to the solvability of a certain set of identities
consisting of Laurent polynomials, referred to as Bezout identities, and it was shown how
such a system of identities can be solved in a systematic way. The work in [2] was done in
the univariate case only, and it will be the purpose of this thesis to develop similar results
in the bivariate case, where such a generalization is entirely non-trivial. After introducing
MRA in Chapter 1, as well as discussing the re nability of functions and introducing box
splines as prototype examples of functions that are re nable in the bivariate setting, our
fundamental result will also be that wavelet decomposition is equivalent to solving a set
of Bezout identities; this will be shown rigorously in Chapter 2. In Chapter 3, we give
a set of Laurent polynomials of shortest possible length satisfying the system of Bezout
identities in Chapter 2, for the particular case of the Courant hat function, which will
have been introduced as a linear box spline in Chapter 1. In Chapter 4, we investigate
an application of our result in Chapter 3 to bivariate interpolatory subdivision. With the
view to establish a general class of wavelets corresponding to the Courant hat function,
we proceed in the subsequent Chapters 5 { 8 to develop a general theory for solving the
Bezout identities of Chapter 2 separately, before suggesting strategies for reconciling these
solution classes in order to be a simultaneous solution of the system.
AFRIKAAANSE OPSOMMING: Multi-resolusie analise (MRA) het in die afgelope twee dekades toenemende gewildheid geniet as 'n veld in wiskundige wetenskappe. Nie net is dit 'n area wat ryklik toepaslik is nie, maar dit bevat ook steeds vele oop vraagstukke. MRA bou op die grondleggings van verfynbare funksies en poog om deur vlakke van data-komponente te sorteer, of te lter, 'n konsep wat aanloklik is in 'n era waar die ontwikkeling van digitale toestelle (om maar 'n enkele voorbeeld te noem) sodanig moet wees dat meer en meer inligting vasgel^e en gestoor moet word. Behalwe vir die ontwerp van digitale voorwerpe, soos animasie- lms, word MRA ook toegepas in 'n mees vername navorsingsgebied genaamd inverwing, waar \verlore" data (soos byvoorbeeld in 'n foto) herwin word deur data te neem uit aangrensende gebiede en dit dan oor die le e data-dele te \smeer." Twee hooftakke in toepassing van MRA is subdivisie en gol e-analise. Die eerste gebruik verfynbare funksies om algoritmes te ontwikkel waarmee digitale krommes ontwerp kan word vanuit 'n eindige aantal aanvanklike gegewe punte. Die verkrygde krommes (of sketse) kan voldoen aan verlangde vlakke van gladheid (of verlangde grade van kontinue afgeleides, wiskundig gesproke). Gol es word op hul beurt gebruik om lters te bou waarmee gewensde dataof geraas-komponente verwyder kan word uit datastelle. Een van die grootste voordeel van die gebruik van gol es bo ander soortgelyke instrumente om data lters mee te bou, is dat die geraas-komponente wat uitgetrek word nooit verlore gaan nie, sodat die proses omkeerbaar is deurdat die gebruiker die sodanige geraas-komponente in die groter datastel kan terugbou deur die gol e-algoritme in trurat toe te pas. Hierdie eienskap van gol fies open 'n wonderlike toepassingsmoontlikheid daarvoor, naamlik dat 'n bestaande datastel verander kan word deur data-komponente daartoe te voeg wat nooit daarin was nie, deur so 'n gol e-algoritme te gebruik. In die onlangse boek deur Chui and De Villiers (sien [2]) is algoritmes ontwikkel vir die toepassing van subdivisie sowel as gol es, sonder om staat te maak op die grondlegging van Fourier-analise, soos wat die gebruik was in vroe ere navorsing en waardeur algoritmes wat ontwikkel is minder e ektief was vir eindgebruikers. Die fundamentele resultaat oor gol es in Hoofstuk 9 in [2], verduidelik hoe suksesvolle gol e-ontbinding ekwivalent is aan die oplosbaarheid van 'n sekere versameling van identiteite bestaande uit Laurent-polinome, bekend as Bezout-identiteite, en dit is bewys hoedat sodanige stelsels van identiteite opgelos kan word in 'n sistematiese proses. Die werk in [2] is gedoen in die eenveranderlike geval, en dit is die doelwit van hierdie tesis om soortgelyke resultate te ontwikkel in die tweeveranderlike geval, waar sodanige veralgemening absoluut nie-triviaal is. Nadat 'n inleiding tot MRA in Hoofstuk 1 aangebied word, terwyl die verfynbaarheid van funksies, met boks-latfunksies as prototipes van verfynbare funksies in die tweeveranderlike geval, bespreek word, word ons fundamentele resultaat gegee en bewys in Hoofstuk 2, naamlik dat gol e-ontbinding in die tweeveranderlike geval ook ekwivalent is aan die oplos van 'n sekere stelsel van Bezout-identiteite. In Hoofstuk 3 word 'n versameling van Laurent-polinome van korste moontlike lengte gegee as illustrasie van 'n oplossing van 'n sodanige stelsel van Bezout-identiteite in Hoofstuk 2, vir die besondere geval van die Courant hoedfunksie, wat in Hoofstuk 1 gede nieer word. In Hoofstuk 4 ondersoek ons 'n toepassing van die resultaat in Hoofstuk 3 tot tweeveranderlike interpolerende subdivisie. Met die oog op die ontwikkeling van 'n algemene klas van gol es verwant aan die Courant hoedfunksie, brei ons vervolglik in Hoofstukke 5 { 8 'n algemene teorie uit om die oplossing van die stelsel van Bezout-identiteite te ondersoek, elke identiteit apart, waarna ons moontlike strategie e voorstel vir die versoening van hierdie klasse van gelyktydige oplossings van die Bezout stelsel.
AFRIKAAANSE OPSOMMING: Multi-resolusie analise (MRA) het in die afgelope twee dekades toenemende gewildheid geniet as 'n veld in wiskundige wetenskappe. Nie net is dit 'n area wat ryklik toepaslik is nie, maar dit bevat ook steeds vele oop vraagstukke. MRA bou op die grondleggings van verfynbare funksies en poog om deur vlakke van data-komponente te sorteer, of te lter, 'n konsep wat aanloklik is in 'n era waar die ontwikkeling van digitale toestelle (om maar 'n enkele voorbeeld te noem) sodanig moet wees dat meer en meer inligting vasgel^e en gestoor moet word. Behalwe vir die ontwerp van digitale voorwerpe, soos animasie- lms, word MRA ook toegepas in 'n mees vername navorsingsgebied genaamd inverwing, waar \verlore" data (soos byvoorbeeld in 'n foto) herwin word deur data te neem uit aangrensende gebiede en dit dan oor die le e data-dele te \smeer." Twee hooftakke in toepassing van MRA is subdivisie en gol e-analise. Die eerste gebruik verfynbare funksies om algoritmes te ontwikkel waarmee digitale krommes ontwerp kan word vanuit 'n eindige aantal aanvanklike gegewe punte. Die verkrygde krommes (of sketse) kan voldoen aan verlangde vlakke van gladheid (of verlangde grade van kontinue afgeleides, wiskundig gesproke). Gol es word op hul beurt gebruik om lters te bou waarmee gewensde dataof geraas-komponente verwyder kan word uit datastelle. Een van die grootste voordeel van die gebruik van gol es bo ander soortgelyke instrumente om data lters mee te bou, is dat die geraas-komponente wat uitgetrek word nooit verlore gaan nie, sodat die proses omkeerbaar is deurdat die gebruiker die sodanige geraas-komponente in die groter datastel kan terugbou deur die gol e-algoritme in trurat toe te pas. Hierdie eienskap van gol fies open 'n wonderlike toepassingsmoontlikheid daarvoor, naamlik dat 'n bestaande datastel verander kan word deur data-komponente daartoe te voeg wat nooit daarin was nie, deur so 'n gol e-algoritme te gebruik. In die onlangse boek deur Chui and De Villiers (sien [2]) is algoritmes ontwikkel vir die toepassing van subdivisie sowel as gol es, sonder om staat te maak op die grondlegging van Fourier-analise, soos wat die gebruik was in vroe ere navorsing en waardeur algoritmes wat ontwikkel is minder e ektief was vir eindgebruikers. Die fundamentele resultaat oor gol es in Hoofstuk 9 in [2], verduidelik hoe suksesvolle gol e-ontbinding ekwivalent is aan die oplosbaarheid van 'n sekere versameling van identiteite bestaande uit Laurent-polinome, bekend as Bezout-identiteite, en dit is bewys hoedat sodanige stelsels van identiteite opgelos kan word in 'n sistematiese proses. Die werk in [2] is gedoen in die eenveranderlike geval, en dit is die doelwit van hierdie tesis om soortgelyke resultate te ontwikkel in die tweeveranderlike geval, waar sodanige veralgemening absoluut nie-triviaal is. Nadat 'n inleiding tot MRA in Hoofstuk 1 aangebied word, terwyl die verfynbaarheid van funksies, met boks-latfunksies as prototipes van verfynbare funksies in die tweeveranderlike geval, bespreek word, word ons fundamentele resultaat gegee en bewys in Hoofstuk 2, naamlik dat gol e-ontbinding in die tweeveranderlike geval ook ekwivalent is aan die oplos van 'n sekere stelsel van Bezout-identiteite. In Hoofstuk 3 word 'n versameling van Laurent-polinome van korste moontlike lengte gegee as illustrasie van 'n oplossing van 'n sodanige stelsel van Bezout-identiteite in Hoofstuk 2, vir die besondere geval van die Courant hoedfunksie, wat in Hoofstuk 1 gede nieer word. In Hoofstuk 4 ondersoek ons 'n toepassing van die resultaat in Hoofstuk 3 tot tweeveranderlike interpolerende subdivisie. Met die oog op die ontwikkeling van 'n algemene klas van gol es verwant aan die Courant hoedfunksie, brei ons vervolglik in Hoofstukke 5 { 8 'n algemene teorie uit om die oplossing van die stelsel van Bezout-identiteite te ondersoek, elke identiteit apart, waarna ons moontlike strategie e voorstel vir die versoening van hierdie klasse van gelyktydige oplossings van die Bezout stelsel.
Description
Thesis (PhD)--Stellenbosch University, 2012.
Keywords
Algebraic polynomial identities, Multi-resolution analysis (MRA), Lost data, Designing digital objects, Wavelets, Dissertations -- Mathematics, Theses -- Mathematics, Bezout identities