Algorithms of wavelet compression of linear spline spaces
А. А. Макаров · Vestnik St Petersburg University Mathematics · 2012
Splines and wavelets have been finding increasing use in the theory of information. Wavelet decompositions are used in designing efficient algorithms for processing (compression) of large information flows. If one succeeds in establishing the embeddability of spaces of splines on a sequence of sparsing/refining grids, in representing the chain of embedded spaces as a direct sum of wavelet spaces, and in realizing the base functions with the minimum length of their support, then this suggests a wavelet decomposition of the information flow, leading, in turn, to substantial savings in the computational cost. This being so, it proves possible to resolve the initial information flow into components to single out the principal and refining information flows, depending on the needs. For uniform grids on the real line, wavelet decompositions are well known. In this case, there applies the powerful technique of harmonic analysis, as well as the lifting scheme or the wavelet scheme. However, many applications require considering bounded intervals and nonuniform grids. For example, for efficient compression of nonuniform flows of information (featuring singularities or rapidly fluctuating characteristics), it is expedient to employ an adaptive nonuniform grid, which takes account of the singularities of the flow being processed. This renders possible to improve approximation of functions without complicating the computations. The previously obtained results pertained to splines on infinite grids. Making both the grid and the corresponding numerical flow infinite renders theoretical studies simpler; however, in practice, one has to deal with finite flows. This paper continues the studies initiated for finite-dimensional spaces. The purpose of this work is to built a wavelet decomposition (compression) on a nonuniform grid and develop the corresponding decomposition and reconstruction algorithms for infinite flows (with a grid on an open interval) and finite flows (with a grid on a segment) for linear spaces of splines of Lagrange type.