imported>Headbomb: Add: journal, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this tool. Report bugs. | #UCB_Gadget

2024-12-18T14:51:55Z

Add: journal, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this tool. Report bugs. | #UCB_Gadget

New page

In [[mathematics]], in the area of [[wavelet]] analysis, a '''refinable function''' is a function which fulfils some kind of [[self-similarity]]. A function <math>\varphi</math> is called refinable with respect to the mask <math>h</math> if
:<math>\varphi(x)=2\cdot\sum_{k=0}^{N-1} h_k\cdot\varphi(2\cdot x-k)</math>
This condition is called '''refinement equation''', '''dilation equation''' or '''two-scale equation'''.

Using the [[convolution]] (denoted by a star, *) of a function with a discrete mask and the dilation operator <math>D</math> one can write more concisely:
:<math>\varphi=2\cdot D_{1/2} (h * \varphi)</math>
It means that one obtains the function, again, if you convolve the function with a discrete mask and then scale it back.
There is a similarity to [[iterated function systems]] and [[de Rham curve]]s.

The operator <math>\varphi\mapsto 2\cdot D_{1/2} (h * \varphi)</math> is linear.
A refinable function is an [[eigenfunction]] of that operator.
Its absolute value is not uniquely defined.
That is, if <math>\varphi</math> is a refinable function,
then for every <math>c</math> the function <math>c\cdot\varphi</math> is refinable, too.

These functions play a fundamental role in [[wavelet]] theory as [[Wavelet#Scaling_function|scaling functions]].

==Properties==
===Values at integral points===

A refinable function is defined only implicitly.
It may also be that there are several functions which are refinable with respect to the same mask.
If <math>\varphi</math> shall have finite support
and the function values at integer arguments are wanted,
then the two scale equation becomes a system of [[simultaneous linear equations]].

Let <math>a</math> be the minimum index and <math>b</math> be the maximum index
of non-zero elements of <math>h</math>, then one obtains
<math display="block">
\begin{pmatrix}
\varphi(a)\\
\varphi(a+1)\\
\vdots\\
\varphi(b)
\end{pmatrix}
=
\begin{pmatrix}
h_{a } & & & & & \\
h_{a+2} & h_{a+1} & h_{a } & & & \\
h_{a+4} & h_{a+3} & h_{a+2} & h_{a+1} & h_{a } & \\
\ddots & \ddots & \ddots & \ddots & \ddots & \ddots \\
& h_{b } & h_{b-1} & h_{b-2} & h_{b-3} & h_{b-4} \\
& & & h_{b } & h_{b-1} & h_{b-2} \\
& & & & & h_{b }
\end{pmatrix}
\begin{pmatrix}
\varphi(a)\\
\varphi(a+1)\\
\vdots\\
\varphi(b)
\end{pmatrix}.
</math>

Using the [[discretization]] operator, call it <math>Q</math> here, and the [[transfer matrix]] of <math>h</math>, named <math>T_h</math>, this can be written concisely as
<math display="block">Q\varphi = T_h Q\varphi. </math>

This is again a [[Fixed point (mathematics)|fixed-point equation]]. But this one can now be considered as an [[eigenvector]]-[[eigenvalue]] problem. That is, a finitely supported refinable function exists only (but not necessarily), if <math>T_h</math> has the eigenvalue 1.

===Values at dyadic points===

From the values at integral points you can derive the values at dyadic points,
i.e. points of the form <math>k\cdot 2^{-j}</math>, with <math>k\in\Z</math> and <math>j\in\N</math>.
:<math>\varphi = D_{1/2} (2\cdot (h * \varphi))</math>
:<math>D_2 \varphi = 2\cdot (h * \varphi)</math>
:<math>Q(D_2 \varphi) = Q(2\cdot (h * \varphi)) = 2\cdot (h * Q\varphi)</math>
The star denotes the [[convolution]] of a discrete filter with a function.
With this step you can compute the values at points of the form <math>\frac{k}{2}</math>.
By replacing iteratedly <math>\varphi</math> by <math>D_2 \varphi</math> you get the values at all finer scales.

<math display="block">Q(D_{2^{j+1}}\varphi) = 2\cdot (h * Q(D_{2^j}\varphi))</math>

===Convolution===

If <math>\varphi</math> is refinable with respect to <math>h</math>, and <math>\psi</math> is refinable with respect to <math>g</math>, then <math>\varphi*\psi</math> is refinable with respect to <math>h*g</math>.

===Differentiation===

If <math>\varphi</math> is refinable with respect to <math>h</math>,
and the derivative <math>\varphi'</math> exists, then <math>\varphi'</math> is refinable with respect to <math>2\cdot h</math>.
This can be interpreted as a special case of the convolution property, where one of the convolution operands is a derivative of the [[Dirac delta function|Dirac impulse]].

===Integration===

If <math>\varphi</math> is refinable with respect to <math>h</math>, and there is an antiderivative <math>\Phi</math> with <math display="inline">\Phi(t) = \int_0^{t}\varphi(\tau)\,\mathrm{d}\tau</math>, then the antiderivative <math>t \mapsto \Phi(t) + c</math> is refinable with respect to mask <math display="inline">\frac{1}{2}\cdot h</math> where the constant <math>c</math> must fulfill <math display="inline">c\cdot \left(1 - \sum_j h_j\right) = \sum_j h_j \cdot \Phi(-j)</math>.

If <math>\varphi</math> has [[compact support|bounded support]],
then we can interpret integration as convolution with the [[Heaviside function]] and apply the convolution law.

===Scalar products===

Computing the scalar products of two refinable functions and their translates can be broken down to the two above properties.
Let <math>T</math> be the translation operator. It holds
<math display="block">\langle \varphi, T_k \psi\rangle = \langle \varphi * \psi^*, T_k\delta\rangle = (\varphi*\psi^*)(k)</math>
where <math>\psi^*</math> is the [[adjoint filter|adjoint]] of <math>\psi</math> with respect to [[convolution]], i.e., <math>\psi^*</math> is the flipped and [[complex conjugate]]d version of <math>\psi</math>, i.e., <math>\psi^*(t) = \overline{\psi(-t)}</math>.

Because of the above property, <math>\varphi*\psi^*</math> is refinable with respect to <math>h*g^*</math>,
and its values at integral arguments can be computed as eigenvectors of the transfer matrix.
This idea can be easily generalized to integrals of products of more than two refinable functions.<ref>{{Cite journal
| last1 = Dahmen | first1 = Wolfgang
| last2 = Micchelli | first2 = Charles A.
| title = Using the refinement equation for evaluating integrals of wavelets | journal = SIAM Journal on Numerical Analysis
| volume = 30 | pages = 507–537 | year = 1993 | issue = 2
| doi=10.1137/0730024 }}</ref>

===Smoothness===

A refinable function usually has a fractal shape.
The design of continuous or smooth refinable functions is not obvious.
Before dealing with forcing smoothness it is necessary to measure smoothness of refinable functions.
Using the Villemoes machine<ref>{{Cite web
|last = Villemoes
|first = Lars
|title = Sobolev regularity of wavelets and stability of iterated filter banks
|url = http://www.math.kth.se/~larsv/paper3.ps.Z
|format = PostScript
|access-date =
|url-status = dead
|archive-url = https://web.archive.org/web/20020511071537/http://www.math.kth.se/~larsv/paper3.ps.Z
|archive-date = 2002-05-11
}}
</ref>
one can compute the smoothness of refinable functions in terms of [[Sobolev space|Sobolev exponents]].

In a first step the refinement mask <math>h</math> is divided into a filter <math>b</math>, which is a power of the smoothness factor <math>(1,1)</math> (this is a binomial mask) and a rest <math>q</math>.
Roughly spoken, the binomial mask <math>b</math> makes smoothness and
<math>q</math> represents a fractal component, which reduces smoothness again.
Now the Sobolev exponent is roughly
the order of <math>b</math> minus [[logarithm]] of the [[spectral radius]] of <math>T_{q*q^*}</math>.

==Generalization==

The concept of refinable functions can be generalized to functions of more than one variable,
that is functions from <math>\R^d \to \R</math>.
The most simple generalization is about [[tensor product]]s.
If <math>\varphi</math> and <math>\psi</math> are refinable with respect to <math>h</math> and <math>g</math>, respectively, then <math>\varphi\otimes\psi</math>
is refinable with respect to <math>h\otimes g</math>.

The scheme can be generalized even more to different scaling factors with respect to different dimensions or even to mixing data between dimensions.<ref>
{{Citation
| last1 = Berger | first1 = Marc A.
| last2 = Wang | first2 = Yang
| chapter = Multidimensional two-scale dilation equations (chapter IV)
| publisher = Academic Press, Inc.
| year = 1992
| volume = 2
| series = Wavelet Analysis and its Applications
| title = Wavelets: A Tutorial in Theory and Applications
| editor-last = Chui | editor-first = Charles K.
| pages = 295–323 }}
</ref>
Instead of scaling by scalar factor like 2 the signal the coordinates are transformed by a matrix <math>M</math> of integers.
In order to let the scheme work, the absolute values of all eigenvalues of <math>M</math> must be larger than one.
(Maybe it also suffices that <math>\left|\det M\right|>1</math>.)

Formally the two-scale equation does not change very much:
<math display="block">\varphi(x)=\left|\det M\right|\cdot\sum_{k\in\Z^d} h_k\cdot\varphi(M\cdot x-k)</math>
<math display="block">\varphi=\left|\det M\right|\cdot D_{M^{-1}} (h * \varphi)</math>

==Examples==

* If the definition is extended to [[Distribution_(mathematics)|distributions]], then the [[Dirac delta function|Dirac impulse]] is refinable with respect to the unit vector <math>\delta</math>, that is known as [[Kronecker delta]]. The <math>n</math>-th derivative of the Dirac distribution is refinable with respect to <math>2^n\cdot\delta</math>.
* The [[Heaviside function]] is refinable with respect to <math>\frac{1}{2}\cdot\delta</math>.
* The [[truncated power function]]s with exponent <math>n</math> are refinable with respect to <math>\frac{1}{2^{n+1}}\cdot\delta</math>.
* The [[triangular function]] is a refinable function.<ref>
{{Cite web
|last = Nathanael
|first = Berglund
|title = Reconstructing Refinable Functions
|url = http://www.math.gatech.edu/~berglund/Refinable/index.html
|access-date = 2010-12-24
|url-status = dead
|archive-url = https://web.archive.org/web/20090404080724/http://www.math.gatech.edu/~berglund/Refinable/index.html
|archive-date = 2009-04-04
}}
</ref> [[B-spline]] functions with successive integral nodes are refinable, because of the convolution theorem and the refinability of the [[indicator function|characteristic function]] for the interval <math>[0,1)</math> (a [[boxcar function]]).
* All [[polynomial function]]s are refinable. For every refinement mask there is a polynomial that is uniquely defined up to a constant factor. For every polynomial of degree <math>n</math> there are many refinement masks that all differ by a mask of type <math>v * (1,-1)^{n+1}</math> for any mask <math>v</math> and the convolutional power <math>(1,-1)^{n+1}</math>.<ref>
{{cite arXiv
| last = Thielemann | first = Henning
| title = How to refine polynomial functions
| date = 2012-01-29
| class = math.FA
| eprint = 1012.2453
}}</ref>
* A [[rational function]] <math>\varphi</math> is refinable if and only if it can be represented using [[partial fraction]]s as <math>\varphi(x) = \sum_{i\in\mathbb{Z}} \frac{s_i}{(x-i)^k}</math>, where <math>k</math> is a [[positive number|positive]] [[natural number]] and <math>s</math> is a real sequence with finitely many non-zero elements (a [[Laurent polynomial]]) such that <math>s | (s \uparrow 2)</math> (read: <math>\exists h(z)\in\mathbb{R}[z,z^{-1}]\ h(z)\cdot s(z) = s(z^2)</math>). The Laurent polynomial <math>2^{k-1}\cdot h</math> is the associated refinement mask.<ref>
{{Citation
| last1 = Gustafson | first1 = Paul
| last2 = Savir | first2 = Nathan
| last3 = Spears | first3 = Ely
| title = A Characterization of Refinable Rational Functions
| journal = American Journal of Undergraduate Research
| volume = 5
| issue = 3
| pages = 11–20
| date = 2006-11-14
| doi = 10.33697/ajur.2006.021
| url = http://www.uni.edu/ajur/v5n3/Gufstafson%20et%20al%20new%20pp%2011-20.pdf}}
</ref>

== References ==
{{reflist}}

==See also==
* [[Subdivision surface|Subdivision scheme]]

[[Category:Wavelets]]

Refinable function - Revision history

imported>Headbomb: Add: journal, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this tool. Report bugs. | #UCB_Gadget