Reproducing kernel approximation in weighted Bergman spaces: Algorithm and applications

In this paper, we present algorithms of preorthogonal adaptive Fourier decomposition (POAFD) in weighted Bergman spaces. POAFD, as has been studied, gives rise to sparse approximations as linear combinations of the corresponding reproducing kernels. It is found that POAFD is unavailable in some weighted Hardy spaces that do not enjoy the boundary vanishing condition; as a result, the maximal selections of the parameters are not guaranteed. We overcome this difficulty with two strategies. One is to utilize the shift operator while the other is to perform weak POAFD. In the cases when the reproducing kernels are rational functions, POAFD provides rational approximations. This approximation method may be used to 1D signal processing. It is, in particular, effective to some Hardy H^p space functions for p not being equal to 2. Weighted Bergman spaces approximation may be used in system identification of discrete time‐varying systems. The promising effectiveness of the POAFD method in weighted Bergman spaces is confirmed by a set of experiments. A sequence of functions as models of the weighted Hardy spaces, being a wider class than the weighted Bergman spaces, are given, of which some are used to illustrate the algorithm and to evaluate its effectiveness over other Fourier type methods.     

Sharp asymptotics of the <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript> approximation error for interpolation on block partitions

Adaptive approximation (or interpolation) takes into account local variations in the behavior of the given function, adjusts the approximant depending on it, and hence yields the smaller error of approximation. The question of constructing optimal approximating spline for each function proved to be very hard. In fact, no polynomial time algorithm of adaptive spline approximation can be designed and no exact formula for the optimal error of approximation can be given. Therefore, the next natural question would be to study the asymptotic behavior of the error and construct asymptotically optimal sequences of partitions. In this paper we provide sharp asymptotic estimates for the error of interpolation by splines on block partitions in \mathbbR^d{\mathbb{R}^d} . We consider various projection operators to define the interpolant and provide the analysis of the exact constant in the asymptotics as well as its explicit form in certain cases.     

Parallel domain decomposition procedures of improved D-D type for parabolic problems

Two parallel domain decomposition procedures for solving initial-boundary value problems of parabolic partial differential equations are proposed. One is the extended D-D type algorithm, which extends the explicit/implicit conservative Galerkin domain decomposition procedures, given in [5], from a rectangle domain and its decomposition that consisted of a stripe of sub-rectangles into a general domain and its general decomposition with a net-like structure. An almost optimal error estimate, without the factor H^−1/2 given in Dawson-Dupont’s error estimate, is proved. Another is the parallel domain decomposition algorithm of improved D-D type, in which an additional term is introduced to produce an approximation of an optimal error accuracy in L²-norm.     

Partial Fourier approximation of the Lamé equations in axisymmetric domains

In this paper, we study the partial Fourier method for treating the Lamé equations in three‐dimensional axisymmetric domains subjected to non‐axisymmetric loads. We consider the mixed boundary value problem of the linear theory of elasticity with the displacement û , the body force f̂ ϵ (L₂)³ and homogeneous Dirichlet and Neumann boundary conditions. The partial Fourier decomposition reduces, without any error, the three‐dimensional boundary value problem to an infinite sequence of two‐dimensional boundary value problems, whose solutions û _n (n = 0, 1, 2,…) are the Fourier coefficients of û . This process of dimension reduction is described, and appropriate function spaces are given to characterize the reduced problems in two dimensions. The trace properties of these spaces on the rotational axis and some properties of the Fourier coefficients û _n are proved, which are important for further numerical treatment, e.g. by the finite‐element method. Moreover, generalized completeness relations are described for the variational equation, the stresses and the strains. The properties of the resulting system of two‐dimensional problems are characterized. Particularly, a priori estimates of the Fourier coefficients û _n and of the error of the partial Fourier approximation are given. Copyright © 1999 John Wiley & Sons, Ltd.     

Two‐dimensional adaptive Fourier decomposition

One‐dimensional adaptive Fourier decomposition, abbreviated as 1‐D AFD, or AFD, is an adaptive representation of a physically realizable signal into a linear combination of parameterized Szegö and higher‐order Szegö kernels of the context. In the present paper, we study multi‐dimensional AFDs based on multivariate complex Hardy spaces theory. We proceed with two approaches of which one uses Product‐TM Systems; and the other uses Product‐Szegö Dictionaries. With the Product‐TM Systems approach, we prove that at each selection of a pair of parameters, the maximal energy may be attained, and, accordingly, we prove the convergence. With the Product‐Szegö dictionary approach, we show that pure greedy algorithm is applicable. We next introduce a new type of greedy algorithm, called Pre‐orthogonal Greedy Algorithm (P‐OGA). We prove its convergence and convergence rate estimation, allowing a weak‐type version of P‐OGA as well. The convergence rate estimation of the proposed P‐OGA evidences its advantage over orthogonal greedy algorithm (OGA). In the last part, we analyze P‐OGA in depth and introduce the concept P‐OGA‐Induced Complete Dictionary, abbreviated as Complete Dictionary. We show that with the Complete Dictionary P‐OGA is applicable to the Hardy H² space on 2‐torus. Copyright © 2016 John Wiley & Sons, Ltd.     

Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3

The best approximation algorithm for Max Cut in graphs of maximum degree 3 uses semidefinite programming, has approximation ratio 0.9326, and its running time is Θ(n^3.5logn); but the best combinatorial algorithms have approximation ratio 4/5 only, achieved in O(n²) time [J.A. Bondy, S.C. Locke, J. Graph Theory 10 (1986) 477–504; E. Halperin, et al., J. Algorithms 53 (2004) 169–185]. Here we present an improved combinatorial approximation, which is a 5/6-approximation algorithm that runs in O(n²) time, perhaps improvable even to O(n). Our main tool is a new type of vertex decomposition for graphs of maximum degree 3.     

Design Approximation Problems for Linear-Phase Nonrecursive Digital Filters

The topic of this paper is the study of four real, linear, possibly constrained minimum norm approximation problems, which arise in connection with the design of linear-phase nonrecursive digital filters and are distinguished by the type of used trigonometric approximation functions. In the case of unconstrained minimax designs these problems are normally solved by the Parks–McClellan algorithm, which is an application of the second algorithm of Remez to these problems and which is one of the most popular tools in filter design. In this paper the four types of approximation problems are investigated for all L^p and l^p norms, respectively. It is especially proved that the assumptions for the Remez algorithm are satisfied in all four cases, which has been claimed, but is not obvious for three of them. Furthermore, results on the existence and uniqueness of solutions and on the convergence and the rate of convergence of the approximation errors are derived.     

Complexity of Local Solution of Multivariate Integral Equations

In this paper the complexity of the local solution of Fredholm integral equations is studied. For certain Sobolev classes of multivariate periodic functions with dominating mixed derivative we prove matching lower and upper hounds. The lower bound is shown using relations to s-numbers. The upper hound is proved in a constructive way providing an implementable algorithm of optimal order based on Fourier coefficients and a hyperbolic cross approximation.     

An Optimal L∞–error Estimate for an Approximation of a Parabolic Variational Inequality

In this article, an optimal error estimate for parabolic variational inequalities is studied. Existence and uniqueness of the solution is provided by the introduction of a constructive algorithm. An optimally L^∞-asymptotic behavior in uniform norm is proved using the semi-implicit time scheme combined with the finite element spatial approximation. The approach is based on the concept of subsolutions.     

Discrete-time queue with unreliable server and multiple adaptive delayed vacations

In this paper we consider a discrete-time Geo^X/G/1 queue with unreliable server and multiple adaptive delayed vacations policy in which the vacation time, service time, repair time and the delayed time all follow arbitrary discrete distribution. By using a concise decomposition method, the transient and steady-state distributions of the queue length are studied, and the stochastic decomposition property of steady-state queue length has been proved. Several common vacation policies are special cases of the vacation policy presented in this study. The relationship between the generating functions of steady-state queue length at departure epoch and arbitrary epoch is obtained. Finally, we give some numerical examples to illustrate the effect of the parameters on several performance characteristics.     

On Multivariate Adaptive Approximation

Recently, A. Cohen, R. A. DeVore, P. Petrushev, and H. Xu investigated nonlinear approximation in the space BV (R ² ). They modified the classical adaptive algorithm to solve related extremal problems. In this paper, we further study the modified adaptive approximation and obtain results on some extremal problems related to the spaces V _σ,p ^r (R ^d ) of functions of ``Bounded Variation" and Besov spaces B ^α (R ^d ). November 23, 1998. Date revised: June 25, 1999. Date accepted: September 13, 1999.     

Sparse-grid finite-volume multigrid for 3D-problems

We introduce a multigrid algorithm for the solution of a second order elliptic equation in three dimensions. For the approximation of the solution we use a partially ordered hierarchy of finite-volume discretisations. We show that there is a relation with semicoarsening and approximation by more-dimensional Haar wavelets. By taking a proper subset of all possible meshes in the hierarchy, a sparse grid finite-volume discretisation can be constructed.The multigrid algorithm consists of a simple damped point-Jacobi relaxation as the smoothing procedure, while the coarse grid correction is made by interpolation from several coarser grid levels.The combination of sparse grids and multigrid with semi-coarsening leads to a relatively small number of degrees of freedom,N, to obtain an accurate approximation, together with anO(N) method for the solution. The algorithm is symmetric with respect to the three coordinate directions and it is fit for combination with adaptive techniques.To analyse the convergence of the multigrid algorithm we develop the necessary Fourier analysis tools. All techniques, designed for 3D-problems, can also be applied for the 2D case, and — for simplicity — we apply the tools to study the convergence behaviour for the anisotropic Poisson equation for this 2D case.     

Projection–difference method for controlled Fourier filtering

A projection–difference method is developed for approximating controlled Fourier filtering for quasilinear parabolic functional-differential equations. The method relies on a projection–difference scheme (PDS) for the approximation of the differential problem and derives a O(τ^1/2 + h) bound on the rate of convergence of PDS in the weighted energy norm without prior assumptions of additional smoothness of the generalized solutions. The PDS leads to a natural approximation of the objective functional in the optimal Fourier filtering problem. A bound of the same order is obtained for the rate of convergence in the functional of the problems approximating the Fourier filter control problem.     

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     

Adaptive Fourier decomposition‐based Dirac type time‐frequency distribution

The Dirac‐type time‐frequency distribution (TFD), regarded as ideal TFD, has long been desired. It, until the present time, cannot be implemented, due to the fact that there has been no appropriate representation of signals leading to such TFD. Instead, people have been developing other types of TFD, including the Wigner and the windowed Fourier transform types. This paper promotes a practical passage leading to a Dirac‐type TFD. Based on the proposed function decomposition method, viz., adaptive Fourier decomposition, we establish a rigorous and practical Dirac‐type TFD theory. We do follow the route of analytic signal representation of signals founded and developed by Garbo, Ville, Cohen, Boashash, Picinbono, and others. The difference, however, is that our treatment is theoretically throughout and rigorous. To well illustrate the new theory and the related TFD, we include several examples and experiments of which some are in comparison with the most commonly used TFDs. Copyright © 2016 John Wiley & Sons, Ltd.     

An a Posteriori Error Estimate for a Semi-Lagrangian Scheme for Hamilton–Jacobi Equations

We present an a posteriori estimate for a first order semi-Lagrangian method for Hamilton–Jacobi equations. The result requires piecewise C ^1,1 regularity of the viscosity solution and is stated for the Bellman equation related to the infinite horizon problem, although it can be applied to more general Hamilton–Jacobi equations with convex Hamiltonians. This estimate suggests different numerical indicators that can be used to construct an adaptive algorithm for the approximation of the viscosity solution.     

Interpolatory Wavelet Packets

In this note, we present a construction of interpolatory wavelet packets. Interpolatory wavelet packets provide a finer decomposition of the 2^jth dilate cardinal interpolation space and hence give a better localization for an adaptive interpolation. This can lead to a more efficient compression scheme which, in turn, provides an interpolation algorithm with a smaller set of data for use in applications.     

Fractal Interpolation on a Torus

A very general method of fractal interpolation on T ¹ is proposed in the first place. The approach includes the classical cases using trigonometric functions, periodic splines, etc. but, at the same time, adds a diversity of fractal elements which may be more appropriate to model the complexity of some variables. Upper bounds of the committed error are provided. The arguments avoid the use of derivatives in order to handle a wider framework. The Lebesgue constant of the associated partition plays a key role. The procedure is proved convergent for the interpolation of specific functions with respect to some nodal bases. In a second part, the approximation is then extended to bidimensional tori via tensor product of interpolation spaces. Some sufficient conditions for the convergence of the process in the Fourier case are deduced.      

An iterative computation of approximations on Korobov-like spaces

This paper treats the multidimensional application of a previous iterative Monte Carlo algorithm that enables the computation of approximations in L². The case of regular functions is studied using a Fourier basis on periodised functions, Legendre and Tchebychef polynomial bases. The dimensional effect is reduced by computing these approximations on Korobov-like spaces. Numerical results show the efficiency of the algorithm for both approximation and numerical integration.     

Decomposition of Completely Positive Maps

The paper is concerned with completely positive maps on the algebra of unbounded operatore L+(D) and on its completion L(D, D⁺). A decomposition theorem for continuous positive functionals is proved in [Tim. Loef.), and [Scholz 91] contains a generalization to maps into operator algebra on finite dimensional Hilbert spaces H₀. The aim of the present paper is to construct an analogous decomposition without the assumption that H₀ is finite dimensional. Moreover, the Kraus - theorem [Kraus] is proved for normal completely positive mappings on L(D, D⁺). The paper is organized as follows. Section 1 contains the necessary definitions and notations. In Section 2 we prove the decomposition theorem. Section 3 deal with the structure of the normal completely positive mappings.