Rank matrix cascade algorithm, hermite interpolation
Date
2007-12
Authors
Dongmo, Guy Blaise
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : University of Stellenbosch
Abstract
ENGLISH ABSTRACT: (Math symbols have changed) Wavelet and subdivision techniques have developed, over the last two decades, into
powerful mathematical tools, for example in signal analysis and geometric modelling.
Both wavelet and subdivision analysis are based on the concept of a matrix–refinable
function, i.e. a finitely supported matrix function which is self-replicating in the sense
that it can be expressed as a linear combination of the integer shifts of its own dilation
with factor 2:
F = TAF = å
k∈Z
F(2 ・ −k)Ak.
The coefficients Ak, k ∈ Z of d × d matrices, of this linear combination constitute the
so-called matrix- mask sequence. Wavelets are in fact constructed as a specific linear
combination of the integer shifts of the 2-dilation of a matrix- refinable function cf. [2;
9], whereas the convergence of the associated matrix- subdivision scheme
c0 = c, cr+1 = SAcr, r ∈ Z+,
SA : c = (ck : k ∈ Z) 7→ SAc =
å
ℓ∈Z
Ak−2ℓ cℓ : k ∈ Z
!
,
subject to the necessary condition that
rank := dim
\
ǫ∈{0,1}
n
y ∈ Rd : Qǫy = y
o
> 0, Qǫ := å
j∈Z
Aǫ+2j, ǫ ∈ {0, 1},
( cf. [26]) , implies the existence of a finitely supported matrix- function which is refinable
with respect to the mask coefficients defining the refinement equation and the
subdivision scheme.
Throughout this thesis, we investigate in time–domain for a given matrix mask sequence,
the related issues of the existence of a matrix–refinable function and the convergence
of the corresponding matrix– cascade algorithm, and finally we apply some
results to the particular research area of Hermite interpolatory subdivision schemes.
The dissertation is organized as follows:
In order to provide a certain flexibility or freedom over the project, we established
in Chapter 1 the equivalence relation between the matrix cascade algorithm and the
matrix subdivision scheme, subject to a well defined class of initial iterates.
Despite the general noncommutativity of matrices, we make use in the full rank case
Qǫ = I, ǫ ∈ {0, 1}, of a symbol factorization, to develop in Chapter 2 some useful
tools, yielding a convergence result which comes as close to the scalar case as possible:
we obtained a concrete sufficient condition on the mask sequence based on the matrix
version of the generating function introduced in [3, page 22] for existence and convergence.
Whilst the conjecture on nonnegative masks was confirmed in 2005 by Zhou [29],
our result on scalar case provided a progress for general mask sequences. We then
applied to obtain a new one-parameter family of refinable functions which includes
the cardinal splines as a special case, as well as corresponding convergent subdivision
schemes.
With the view to broaden the class of convergent matrix-masks, we replaced in chapter
3 the full rank condition by the rank one condition Qǫu = u, ǫ ∈ {0, 1}, u :=
(1, . . . , 1)T, then improved the paper by Dubuc and Merrien [13] by using the theory
of rank subdivision schemes by Micchelli and Sauer [25; 26], and end up this improvement
with a generalization of [13, Theorem 13, p.8] in to the context of rank subdivision
schemes.
In Chapter 4, we translated the concrete convergence criteria of the general theory from
Theorem 3.2, based on the r-norming factor introduced in [13, Definition 6, p.6], into
the context of rank, factorization and spectral radius (cf. [26]), and presented a careful
analysis of the relationship between the two concepts. We then proceed with generalizations
and improvements: we classified the matrix cascade algorithms in term of
rank = 1, 2, . . . , d, and provided a complete characterization of each class with the use
of a more general r−norming factor namely τ(r)-norming factor. On the other hand,
we presented numerical methods to determine, if possible, the convergence of each
class of matrix cascade algorithms.
In both the scalar and matrix cases above, we also obtained explicitly the geometric
constant appearing in the estimate for the geometric convergence of thematrix-cascade
algorithm iterates to the matrix- refinable function. This same geometric convergence
rate therefore also holds true for the corresponding matrix–cascade algorithm.
Finally, in Chapter 5, we apply the theory and algorithms developed in Chapter 4 to
the particular research area of Hermite interpolatory subdivision schemes: we provided
a new convergence criterium, and end up with new convergence ranges of the
parameters’ values of the famous Hermite interpolatory subdivision scheme with two
parameters, due to Merrien [23].
AFRIKAANSE OPSOMMING :(Wiskundige simbole het verander) Golfie en subdivisietegnieke het oor die afgelope twee dekades ontwikkel in kragtige wiskundige gereedskap, byvoorbeeld in seinanalise en geometriesemodellering. Beide golfie en subdivisie analise is gebaseer op die konsep van ’n matriks-verfynbare funksie; oftewel ’n eindig-ondersteunde matriksfunksie F wat selfreproduserend is in die sin dat dit uitgedruk kan word as ’n lineêre kombinasie van die heelgetalskuiwe van F se eie dilasie met faktor 2: F = Σ F(2 · −α)A(α), met A(α), α ∈ Z, wat aandui die sogenaamde matriks-masker ry. Golfies kan dan gekonstrueer word as ’n spesifieke lineêre kombinasie van die funksie ry {F(2 · −α) : α ∈ Z} (sien [2; 9]), terwyl die konvergensie van die ooreenstemmende matriks-subdivisie skema cº = c, cr+1 =(Σ β∈Z A(α − 2β) cr(β) : α ∈ Z ! , r ∈ Z+, onderhewig aan die nodige voorwaarde dat rank := dim \ ǫ∈{0,1} n y ∈ Rd : Qǫy = y o > 0, Qǫ := å α∈Z A(ǫ + 2α), ǫ ∈ {0, 1}, (sien [27]) die bestaan impliseer van ’n eindig-ondersteunde matriksfunksie F wat verfynbaar ismet betrekking tot diemaskerko¨effisi¨entewat die subdivisieskema definieer, en in terme waarvan die limietfunksie F van die subdivisieskema uitgedruk kan word as F = å α∈Z F(· − α)c(α). Ons hoofdoel hier is om , in die tydgebied, en vir ’n gegewematriks-masker ry, die verwante kwessies van die bestaan van ’nmatriks-verfynbare funksie en die konvergensie van die ooreenstemmende matriks-kaskade algoritme, en matriks-subdivisieskema, te ondersoek, en om uiteindelik sommige van ons resultate toe te pas op die spesifieke kwessie van die konvergensie van Hermite interpolerende subdivisieskemas. Summary v Eerstens, in Hoofstuk 1, ondersoek ons die verwantskap tussen matriks-kaskade algoritmes en matriks-subdivisie skemas, met verwysing na ’n goedgedefinieerde klas van begin-iterate. Vervolgens beskou ons die volle rang geval Qǫ = I, ǫ ∈ {0, 1}, om, in Hoofstuk 2, nuttige gereedskap te ontwikkel, en wat daarby ’n konvergensie resultaat met ’n sterk konneksie ten opsigte van die skalaar-geval oplewer. Met die doelstelling om ons klas van konvergente matriks-maskers te verbreed, vervang ons, in Hoofstuk 3, die volle rang voorwaarde met die rang een voorwaarde Qǫu = u, ǫ ∈ {0, 1}, u := (1, . . . , 1)T, en verkry ons dan ’n verbetering op ’n konvergensieresultaat in die artikel [14] deur Dubuc en Merrien, deur gebruik te maak van die teorie van rang subdivisieskemas van Micchelli en Sauer [26; 27], waarna ons die resultaat [14, Stelling 13, page 8] na die konteks van rang subdivisieskemas veralgemeen. InHoofstuk 4 herlei ons die konkrete konvergensie kriteria van Stelling 3.2, soos gebaseer op die r-normerende faktor gedefinieer in [14, Definisie 6, page 6] , na die konteks van rang, faktorisering en spektraalradius (sien [27]), en gee ons ’n streng analise van die verwantskap tussen die twee konsepte. Verder stel ons dan bekend ’n nuwe klassifikasie van matriks-kaskade algoritmes ten opsigte van rang, en verskaf ons ’n volledige karakterisering van elke klasmet behulp van ’nmeer algemene r-normerende faktor, nl. die τ(r)-normerende faktor. Daarby gee ons doeltreffende numeriesemetodes vir die implementering van ons teoretiese resultate. Ons verkry ook eksplisiet die geometriese konstante wat voorkom in die afskatting van die geometriese konvergensie van die matriks-kaskade algoritme iterate na die matriks-verfynbare funksie. Ten slotte, in Hoofstuk 5, pas ons die teorie en algoritmes ontwikkel in Hoofstuk 4 toe om die konvergensie van Hermite-interpolerende subdivisieskemas te analiseer. Spesifiek lei ons ’n nuwe konvergensie kriterium af, wat ons dan toepas om nuwe konvergensie gebiede vir die parameter waardes te verkry vir die beroemde Hermite interpolerende subdivisieskema met twee parameters, soos toegeskryf aan Merrien [24].
AFRIKAANSE OPSOMMING :(Wiskundige simbole het verander) Golfie en subdivisietegnieke het oor die afgelope twee dekades ontwikkel in kragtige wiskundige gereedskap, byvoorbeeld in seinanalise en geometriesemodellering. Beide golfie en subdivisie analise is gebaseer op die konsep van ’n matriks-verfynbare funksie; oftewel ’n eindig-ondersteunde matriksfunksie F wat selfreproduserend is in die sin dat dit uitgedruk kan word as ’n lineêre kombinasie van die heelgetalskuiwe van F se eie dilasie met faktor 2: F = Σ F(2 · −α)A(α), met A(α), α ∈ Z, wat aandui die sogenaamde matriks-masker ry. Golfies kan dan gekonstrueer word as ’n spesifieke lineêre kombinasie van die funksie ry {F(2 · −α) : α ∈ Z} (sien [2; 9]), terwyl die konvergensie van die ooreenstemmende matriks-subdivisie skema cº = c, cr+1 =(Σ β∈Z A(α − 2β) cr(β) : α ∈ Z ! , r ∈ Z+, onderhewig aan die nodige voorwaarde dat rank := dim \ ǫ∈{0,1} n y ∈ Rd : Qǫy = y o > 0, Qǫ := å α∈Z A(ǫ + 2α), ǫ ∈ {0, 1}, (sien [27]) die bestaan impliseer van ’n eindig-ondersteunde matriksfunksie F wat verfynbaar ismet betrekking tot diemaskerko¨effisi¨entewat die subdivisieskema definieer, en in terme waarvan die limietfunksie F van die subdivisieskema uitgedruk kan word as F = å α∈Z F(· − α)c(α). Ons hoofdoel hier is om , in die tydgebied, en vir ’n gegewematriks-masker ry, die verwante kwessies van die bestaan van ’nmatriks-verfynbare funksie en die konvergensie van die ooreenstemmende matriks-kaskade algoritme, en matriks-subdivisieskema, te ondersoek, en om uiteindelik sommige van ons resultate toe te pas op die spesifieke kwessie van die konvergensie van Hermite interpolerende subdivisieskemas. Summary v Eerstens, in Hoofstuk 1, ondersoek ons die verwantskap tussen matriks-kaskade algoritmes en matriks-subdivisie skemas, met verwysing na ’n goedgedefinieerde klas van begin-iterate. Vervolgens beskou ons die volle rang geval Qǫ = I, ǫ ∈ {0, 1}, om, in Hoofstuk 2, nuttige gereedskap te ontwikkel, en wat daarby ’n konvergensie resultaat met ’n sterk konneksie ten opsigte van die skalaar-geval oplewer. Met die doelstelling om ons klas van konvergente matriks-maskers te verbreed, vervang ons, in Hoofstuk 3, die volle rang voorwaarde met die rang een voorwaarde Qǫu = u, ǫ ∈ {0, 1}, u := (1, . . . , 1)T, en verkry ons dan ’n verbetering op ’n konvergensieresultaat in die artikel [14] deur Dubuc en Merrien, deur gebruik te maak van die teorie van rang subdivisieskemas van Micchelli en Sauer [26; 27], waarna ons die resultaat [14, Stelling 13, page 8] na die konteks van rang subdivisieskemas veralgemeen. InHoofstuk 4 herlei ons die konkrete konvergensie kriteria van Stelling 3.2, soos gebaseer op die r-normerende faktor gedefinieer in [14, Definisie 6, page 6] , na die konteks van rang, faktorisering en spektraalradius (sien [27]), en gee ons ’n streng analise van die verwantskap tussen die twee konsepte. Verder stel ons dan bekend ’n nuwe klassifikasie van matriks-kaskade algoritmes ten opsigte van rang, en verskaf ons ’n volledige karakterisering van elke klasmet behulp van ’nmeer algemene r-normerende faktor, nl. die τ(r)-normerende faktor. Daarby gee ons doeltreffende numeriesemetodes vir die implementering van ons teoretiese resultate. Ons verkry ook eksplisiet die geometriese konstante wat voorkom in die afskatting van die geometriese konvergensie van die matriks-kaskade algoritme iterate na die matriks-verfynbare funksie. Ten slotte, in Hoofstuk 5, pas ons die teorie en algoritmes ontwikkel in Hoofstuk 4 toe om die konvergensie van Hermite-interpolerende subdivisieskemas te analiseer. Spesifiek lei ons ’n nuwe konvergensie kriterium af, wat ons dan toepas om nuwe konvergensie gebiede vir die parameter waardes te verkry vir die beroemde Hermite interpolerende subdivisieskema met twee parameters, soos toegeskryf aan Merrien [24].
Description
Thesis (DSc (Mathematical Sciences))--University of Stellenbosch, 2007.
Keywords
Theses -- Mathematics, Mathematical tools, Matrix cascade algorithms, Hermite interpolation, Dissertations -- Mathematics
Citation
Dongmo, G. B. 2007,'Rank matrix cascade algorithm, hermite interpolation',Stellenbosch: University of Stellenbosch.