Building nonredundant adaptive wavelets by update lifting

In this paper, we propose a technique for building adaptive wavelets by means of an extension of the lifting scheme. Our scheme comprises an adaptive update lifting step and a fixed prediction lifting step. The adaptivity consists hereof that the system can choose between two different update filters, and that this choice is triggered by the local gradient of the original signal. If the gradient is large (in some seminorm sense) it chooses one filter, if it is small the other. We derive necessary and sufficient conditions for the invertibility of such an adaptive system for various scenarios. Furthermore, we present some examples to illustrate our theoretical results.     

Best approximation with wavelets in weighted Orlicz spaces

Democracy functions of wavelet admissible bases are computed for weighted Orlicz Spaces L ^??(w) in terms of the fundamental function of L ^??(w). In particular, we prove that these bases are greedy in L ^??(w) if and only if L ^??(w) =?L ^p (w), 1?<?p?<???. Also, sharp embeddings for the approximation spaces are given in terms of weighted discrete Lorentz spaces. For L ^p (w) the approximation spaces are identified with weighted Besov spaces.     

Application of Daubechies wavelets approximation to plate bending

In this paper a new wavelet-based approach is presented for solving two-dimensional boundary-value mechanical problems on the example of plate bending. The deflection equation of a bending plate is approximated by two-dimensional Daubechies wavelets using a least-squares Galerkin method. Due to the order of the differential equation in mechanics of plate structures is four, a way to perform the calculations of high order connection coefficients (that is, integrals of products of basis functions with their high order derivatives) is suggested. The implementation of two-dimensional Daubechies scaling functions approximation to plate bending is exhibited numerically in some examples. The results show that this method has good precision and reliability. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Absolute and relative choreographies in rigid body dynamics

For the classical problem of motion of a rigid body about a fixed point with zero area integral, we present a family of solutions that are periodic in the absolute space. Such solutions are known as choreographies. The family includes the well-known Delone solutions (for the Kovalevskaya case), some particular solutions for the Goryachev-Chaplygin case, and the Steklov solution. The “genealogy” of solutions of the family naturally appearing from the energy continuation and their connection with the Staude rotations are considered. It is shown that if the integral of areas is zero, the solutions are periodic with respect to a coordinate frame that rotates uniformly about the vertical (relative choreographies).      

Multilevel scattered data approximation by adaptive domain decomposition

A new multilevel approximation scheme for scattered data is proposed. The scheme relies on an adaptive domain decomposition strategy using quadtree techniques (and their higher-dimensional generalizations). It is shown in the numerical examples that the new method achieves an improvement on the approximation quality of previous well-established multilevel interpolation schemes. AMS subject classification 65D15, 65D05, 65D07, 65D17     

Fast computation in adaptive tree approximation

Summary. Adaptive methods of approximation arise in many settings including numerical methods for PDEs and image processing. They can usually be described by a tree which records the adaptive decisions. This paper is concerned with the fast computation of near optimal trees based on n adaptive decisions. The best tree based on n adaptive decisions could be found by examining all such possibilities. However, this is exponential in n and could be numerically prohibitive. The main result of this paper is to show that it is possible to find near optimal trees using computations linear in n.Mathematics Subject Classification (2000): 65Y20, 65N50, 41A63, 41A15, 68W40, 68W25This work has been supported in part by the Office of Naval Research contracts 03-10051, (N00014-00-1-0470), the Army Research Office contract DAAD 19-02-1-0028, and the National Science Foundation grants DMS 9872890, DMS 0221642.     

A Haar wavelets based approximation for nonlinear inverse problems influenced by unknown heat source

In this discussion, a new numerical algorithm focused on the Haar wavelet is used to solve linear and nonlinear inverse problems with unknown heat source. The heat source is dependent on time and space variables. These types of inverse problems are ill-posed and are challenging to solve accurately. The linearization technique converted the nonlinear problem into simple nonhomogeneous partial differential equation. In this Haar wavelet collocation method (HWCM), the time part is discretized by using finite difference approximation, and space variables are handled by Haar series approximation. The main contribution of the proposed method is transforming this ill-posed problem into well-conditioned algebraic equation with the help of Haar functions, and hence, there is no need to implement any sort of regularization technique. The results of numerical method are efficient and stable for this ill-posed problems containing different noisy levels. We have utilized the proposed method on several numerical examples and have valuable efficiency and accuracy.     

Two-direction refinable functions and two-direction wavelets with high approximation order and regularity

The concept of two-direction refinable functions and two-direction wavelets is introduced. We investigate the existence of distributional(or L~2-stable) solutions of the two-direction refinement equation: (?)(x)=(?)p_k~ (?)(mx-k) (?)p_k~-(?)(k-mx), where m≥2 is an integer.Based on the positive mask {p_k~ } and negative mask {p_k~-},the conditions that guarantee the above equation has compactly distributional solutions or L~2-stable solutions are established.Furthermore,the condition that the L~2-stable solution of the above equation can generate a two-direction MRA is given.The support interval of (?)(x) is discussed amply.The definition of orthogonal two-direction refinable function and orthogonal two-direction wavelets is presented,and the orthogonality criteria for two-direction refinable functions are established.An algorithm for construct- ing orthogonal two-direction refinable functions and their two-direction wavelets is presented.Another construction algorithm for two-direction L~2-refinable functions,which have nonnegative symbol masks and possess high approximation order and regularity,is presented.Finally,two construction examples are given.     

A geometric approach to the cascade approximation operator for wavelets

This paper is devoted to an approximation problem for operators in Hilbert space, that appears when one tries to study geometrically thecascade algorithm in wavelet theory. Let be a Hilbert space, and let be a representation ofL ( ) on . LetR be a positive operator inL ( ) such thatR(1) =1, where1 denotes the constant function 1. We study operatorsM on (bounded, but noncontractive) such that

Absolute approximation of Tukey depth: Theory and experiments

A Monte Carlo approximation algorithm for the Tukey depth problem in high dimensions is introduced. The algorithm is a generalization of an algorithm presented by Rousseeuw and Struyf (1998) [20]. The performance of this algorithm is studied both analytically and experimentally.     

Matrix valued adaptive cross approximation

A new variant of the Adaptive Cross Approximation (ACA) for approximation of dense block matrices is presented. This algorithm can be applied to matrices arising from the Boundary Element Methods (BEM) for elliptic or Maxwell systems of partial differential equations. The usual interpolation property of the ACA is generalised for the matrix valued case. Some numerical examples demonstrate the efficiency of the new method. The main example will be the electromagnetic scattering problem, that is, the exterior boundary value problem for the Maxwell system. Here, we will show that the matrix valued ACA method works well for high order BEM, and the corresponding high rate of convergence is preserved. Another example shows the efficiency of the new method in comparison with the standard technique, whilst approximating the smoothed version of the matrix valued fundamental solution of the time harmonic Maxwell system. Copyright © 2016 John Wiley & Sons, Ltd.     

Absolute and relative Weyl theorems for generalized eigenvalue problems

Weyl-type eigenvalue perturbation theories are derived for Hermitian definite pencils A-λB, in which B is positive definite. The results provide a one-to-one correspondence between the original and perturbed eigenvalues, and give a uniform perturbation bound. We give both absolute and relative perturbation results, defined in the standard Euclidean metric instead of the chordal metric that is often used.     

Solving a large dense linear system by adaptive cross approximation

An efficient algorithm for the direct solution of a linear system associated with the discretization of boundary integral equations (in two dimensions) is described without having to compute the complete matrix of the linear system. This algorithm is based on the unitary-weight representation, for which a new construction based on adaptive cross approximation is proposed. This low rank approximation uses only a small part of the entries to construct the adaptive cross representation, and therefore the linear system can be solved efficiently.     

Optimal approximation of stochastic differential equations by adaptive step-size control

We study the pathwise (strong) approximation of scalar stochastic differential equations with respect to the global error in the -norm. For equations with additive noise we establish a sharp lower error bound in the class of arbitrary methods that use a fixed number of observations of the driving Brownian motion. As a consequence, higher order methods do not exist if the global error is analyzed. We introduce an adaptive step-size control for the Euler scheme which performs asymptotically optimally. In particular, the new method is more efficient than an equidistant discretization. This superiority is confirmed in simulation experiments for equations with additive noise, as well as for general scalar equations.

     

An error analysis for absolute and relative approximation

We consider the vectorial algorithm for finding best polynomial approximationsp P _n to a given functionf C[a, b], with respect to the norm · _s , defined byp – f _s =w ₁ (p – f)+w ₂ (p – f) A bound for the modulus of continuity of the best vectorial approximation operator is given, and using the floating point calculus of J. H. Wilkinson, a bound for the rounding error in the algorithm is derived. For givenf, these estimates provide an indication of the conditioning of the problem, an estimate of the obtainable accuracy, and a practical method for terminating the iteration.This paper was supported in part by the Canadian NCR A-8108, FCAC 74-09 and G.E.T.M.A.Part of this research was done during the first-named author's visit to theB! Chair of Applied Mathematics, University of Athens, Spring term, 1975.     

The relative approximation degree in valued function fields

We continue the work of Kaplansky on immediate valued field extensions and determine special properties of elements in such extensions. In particular, we are interested in the question when an immediate valued function field of transcendence degree 1 is henselian rational (i.e., generated, modulo henselization, by one element). If so, then ramification can be eliminated in this valued function field. The results presented in this paper are crucial for the first author’s proof of henselian rationality over tame fields, which in turn is used in his work on local uniformization.     

Exponential convergence of adaptive quarklet approximation

This paper is concerned with approximation properties of polynomially enriched wavelet systems, so-called quarklet frames. We show that certain model singularities that arise in elliptic boundary value problems on polygonal domains can be approximated from the span of such quarklet systems at inverse-exponential rates. In order to realize these, we combine spatial refinement in the vicinity of the singularities with suitable growth of the polynomial degrees in regions where the solution is smooth, similar to adaptive hp-finite element approximation.     

A note on adaptive approximation in Sobolev spaces

In this article, we consider the adaptive approximation in Sobolev spaces. After establishing some norm equivalences and inequalities in Besov spaces, we are able to prove that the best N terms approximation with wavelet‐like basis in Sobolev spaces exhibits the proper approximation order in terms of N^?1. This indicates that the computational load in adaptive approximation is proportional to the approximation accuracy. © 2006 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2007     

The information-based complexity of approximation problem by adaptive Monte Carlo methods

In this paper, we study the complexity of information of approximation problem on the multivariate Sobolev space with bounded mixed derivative MWpr,α(Td), 1 < p < ∞, in the norm of Lq(Td), 1 < q < ∞, by adaptive Monte Carlo methods. Applying the discretization technique and some properties of pseudo-s-scale, we determine the exact asymptotic orders of this problem.