多元 Besov-Wiener 类的无穷维宽度和最优恢复

该文考虑 Besov-Wiener 类S_pqθ^r B(R^d)和 S_pqθ^r B(R^d)在 L_q(R^d) 空间下 (1≤q≤ p <∞ ) 的无穷维σ -宽度和最优恢复问题.通过考虑样条函数逼近和构造一种连续样条算子, 得到了关于无穷维Kolmogorov 宽度、无穷维线性宽度、无穷维 Gel'fand 宽度和最优恢复的弱渐近结果.     

On the approximation power of bivariate splines

We show how to construct stable quasi-interpolation schemes in the bivariate spline spaces S _d ^r (Δ) with d⩾ 3r + 2 which achieve optimal approximation order. In addition to treating the usual max norm, we also give results in the L _p norms, and show that the methods also approximate derivatives to optimal order. We pay special attention to the approximation constants, and show that they depend only on the smallest angle in the underlying triangulation and the nature of the boundary of the domain. This revised version was published online in August 2006 with corrections to the Cover Date.     

<Emphasis Type="Italic">L</Emphasis><Subscript>1</Subscript> spline fits via sliding window process: continuous and discrete cases

The best L ₁ approximation of the Heaviside function and the best ? ₁ approximation of multiscale univariate datasets by a cubic spline have a Gibbs phenomenon near the discontinuity. We show by numerical experiments that the Gibbs phenomenon can be reduced by using L ₁ spline fits which are the best L ₁ approximations in an appropriate spline space obtained by the union of L ₁ interpolation splines. We prove here the existence of L ₁ spline fits for function approximation which has never previously been done to the best of our knowledge. A major disadvantage of this technique is an increased computation time. Thus, we propose a sliding window algorithm on seven nodes which is as efficient as the global method both for functions and datasets with abrupt changes of magnitude, but within a linear complexity on the number of spline nodes.     

Approximating term structure of interest rates using cubic L1 splines

Classical spline fitting methods for estimating the term structure of interest rates have been criticized for generating highly fluctuating fitting curves for bond price and discount function. In addition, the performance of these methods usually relies heavily on parameter tuning involving human judgement. To overcome these drawbacks, a recently developed cubic L₁ spline model is proposed for term structure analysis. Cubic L₁ splines preserve the shape of the data, exhibit no extraneous oscillation and have small fitting errors. Cubic L₁ splines are tested using a set of real financial data and compared with the widely used B-splines.     

An extremal problem for finite topologies and distributive lattices

Let (r₁, r₂, …) be a sequence of non-negative integers summing to n. We determine under what conditions there exists a finite distributive lattice L of rank n with r_i join-irreducibles of rank i, for all i = 1, 2, …. When L exists, we give explicit expressions for the greatest number of elements L can have of any given rank, and for the greatest total number of elements L can have. The problem is also formulated in terms of finite topological spaces.     

Cardinal hermite interpolation with box splines

The study of cardinal interpolation (CIP) by the span of the lattice translates of a box spline has met with limited success. Only the case of interpolation with the box spline determined by the three directionsd ₁=(1, 0),d ₂=(0, 1), andd ₃=(1, 1) inR ² has been treated in full generality [2]. In the case ofR ^d,d ≥ 3, the directions that define the box spline must satisfy a certain determinant condition [6], [9]. If the directions occur with even multiplicities, then this condition is also sufficient. For Hermite interpolation (CHIP) both even multiplicities and the determinant condition for the directions does not prevent the linear dependence of the basis functions. This leads to singularities in the characteristic multiplier when using the standard Fourier transform method. In the case of derivatives in one direction, these singularities can be removed and a set of fundamental splines can be given. This gives the existence of a solution to CHIP inL ^p (R ^d) for data inl ^p (Z ^d), 1≤p≤2.     

Splines with maximal zero sets

Consider a spline s(x) of degree n with L knots of specified multiplicities R₁, …, R_L, which satisfies r sign consistent mixed boundary conditions in addition to s⁽ⁿ⁾(a) = 1. Such a spline has at most n + 1 ?r + ∑_{j = 1}^LR_j zeros in (a, b) which fulfill an interlacing condition with the knots if s(x) ? = 0 everywhere. Conversely, given a set of n ?r + ∑_{j = 1}^LR_j zeros then for any choice η₁ < ··· < η_L of the knot locations which fulfills the interlacing condition with the zeros, the unique spline s(x) possessing these knots and zeros and satisfying the boundary conditions is such that s⁽ⁿ⁾(x) vanishes nowhere and changes sign at η_j if and only if R_j is odd. Moreover there exists a choice of the knot locations, not necessarily unique, which makes $\text{¦s}{}^{\mathrm{(n)}}\text{(x)¦ ≡ 1}$. In particular, this establishes the existence of monosplines and perfect splines with knots of given multiplicities, satisfying the mixed boundary conditions and possessing a prescribed maximal zero set. An application is given to double-precision quadrature formulas with mixed boundary terms and a certain polynomial extremal problem connected with it.     

On the Wronskian combinants of binary forms

Given a sequence A=(A₁,…,A_r) of binary d-ics, we construct a set of combinants C={C_q:0≤q≤r,q≠1}, to be called the Wronskian combinants of A. We show that the span of A can be recovered from C as the solution space of an SL(2)-invariant differential equation. The Wronskian combinants define a projective imbedding of the Grassmannian G(r,S_d), and, as a corollary, any other combinant of A is expressible as a compound transvectant in C.Our main result characterises those sequences of binary forms that can arise as Wronskian combinants; namely, they are the ones such that the associated differential equation has the maximal number of linearly independent polynomial solutions. Along the way we deduce some identities which relate Wronskians to transvectants. We also calculate compound transvectant formulae for C in the case r=3.     

Quantum complexity of the approximation for the classes B(Wp ([0, 1])) and B(Hp ([0, 1]))

We study the approximation of functions from anisotropic Sobolev classes B(W^r_p([0,1]d)) and Hölder-Nikolskii classes B(H^r_p([0,1]d)) in the L_q([0,1]d) norm with q ≤ p in the quantum model of computation. We determine the quantum query complexity of this problem up to logarithmic factors. It shows that the quantum algorithms are significantly better than the classical deterministic or randomized algorithms.     

Efficient scheduling algorithms for a single batch processing machine

Scheduling problems of a batch processing machine are solved by efficient algorithms. On a batch processing machine, multiple jobs can be processed simultaneously in a batch form. We call the number of jobs in the batch the batch size, which can be any integer between 1 and k, a predetermined integer of the maximum batch size. The process time of a batch is constant and independent of the batch size. Preemption is not allowed. Given n jobs with release times r₁ and due dates d_i, i = 1…., n, we give efficient algorithms to find a feasible schedule, if any, which minimizes the final completion time under the assumption such that for r_i > r_j, d_i ⩾ d_j. Some industrial applications are discussed.     

Topological obstructions for vertex numbers of Minkowski sums

We show that for polytopes P₁,P₂,…,Pr⊂Rd, each having ni?d+1 vertices, the Minkowski sum P₁+P₂+?+Pr cannot achieve the maximum of i_∏ni vertices if r?d. This complements a recent result of Fukuda and Weibel (2006), who show that this is possible for up to d−1 summands. The result is obtained by combining methods from discrete geometry (Gale transforms) and topological combinatorics (van Kampen-type obstructions).     

On the Convergence of a Weak Greedy Algorithm for the Multivariate Haar Basis

We define a family of weak thresholding greedy algorithms for the multivariate Haar basis for L ₁[0,1] ^d (d≥1). We prove convergence and uniform boundedness of the weak greedy approximants for all f∈L ₁[0,1] ^d .     

The error term in Nevanlinna’s inequality

An upper bound is given for the error termS(r, |a _j |,f) in Nevanlinna’s inequality. For given positive increasing functions p and $ with ∫ ₁ ^∞ dr/p(r) = ∫ ₁ ^∞ dr/r ?(r) = ∞, setP(r) = ∫ ₁ ^r dt/p,Ψ(r) = ∫ ₁ ^r dt/t ?(t) We prove that $$S(r, \left\{ {a_j } \right\}, f) \leqslant \log \frac{{T(r, f)\phi (T(r, f))}}{{p(r)}} + O(1)$$ holds, with a small exceptional set of r, for any finite set of points |a _j | in the extended plane and any meromorphic function f such thatΨ(T(r, f)) =O(P(r)). This improves the known results of A. Hinkkanen and Y. F. Wang. The sharpness of the estimate is also considered.     

Some extremal properties of multivariate polynomial splines in the metric Lp(ℝd)

We constructed a kind of continuous multivariate spline operators as the approximation tools of the multivariate functions on the (?^d instead of the usual multivariate cardinal interpolation operators of splines, and obtained the approximation error by this kind of spline operators. Meantime, by the results, we also obtained that the spaces of multivariate polynomial splines are weakly asyrnptotically optimal for the Kolrnogorov widths and the linear widths of some anisotropic Sobolev classes of smooth functions on (?^d in the metric L_p((?^d).     

Planar Graded Lattices and the <Emphasis Type="Bold">c</Emphasis><Subscript>1</Subscript>-Median Property

Let L be a lattice of finite length, ξ = (x ₁,…, x _k )∈L ^k , and y ∈ L. The remoteness r(y, ξ) of y from ξ is d(y, x ₁)+?+d(y, x _k ), where d stands for the minimum path length distance in the covering graph of L. Assume, in addition, that L is a graded planar lattice. We prove that whenever r(y, ξ) ≤ r(z, ξ) for all z ∈ L, then y ≤ x ₁∨?∨x _k . In other words, L satisfies the so-called c ₁ -median property.     

Harmonic manifolds with some specific volume densities

We show that a noncompact, complete, simply connected harmonic manifold (M ^d, g) with volume densityθ _m(r)=sinh^d-1 r is isometric to the real hyperbolic space and a noncompact, complete, simply connected Kähler harmonic manifold (M ^2d, g) with volume densityθ _m(r)=sinh^2d-1 r coshr is isometric to the complex hyperbolic space. A similar result is also proved for quaternionic Kähler manifolds. Using our methods we get an alternative proof, without appealing to the powerful Cheeger-Gromoll splitting theorem, of the fact that every Ricci flat harmonic manifold is flat. Finally a rigidity result for real hyperbolic space is presented.     

The convergence of three spline methods for scattered data interpolation and fitting

The convergences of three L₁ spline methods for scattered data interpolation and fitting using bivariate spline spaces are studied in this paper. That is, L₁ interpolatory splines, splines of least absolute deviation, and L₁ smoothing splines are shown to converge to the given data function under some conditions and hence, the surfaces from these three methods will resemble the given data values.     

Asymptotics of Multivariate Sequences: I. Smooth Points of the Singular Variety

Given a multivariate generating function F(z1, …, zd)=∑ ar1, …, rdzr11…zrdd, we determine asymptotics for the coefficients. Our approach is to use Cauchy's integral formula near singular points of F, resulting in a tractable oscillating integral. This paper treats the case where the singular point of F is a smooth point of a surface of poles. Companion papers treat singular points of F where the local geometry is more complicated, and for which other methods of analysis are not known.     

Non-linear Approximations Using Sets of Finite Cardinality or Finite Pseudo-dimension

We investigate optimal non-linear approximations of multivariate periodic functions with mixed smoothness. In particular, we study optimal approximation using sets of finite cardinality (as measured by the classical entropy number), as well as sets of finite pseudo-dimension (as measured by the non-linear widths introduced by Ratsaby and Maiorov). Approximation error is measured in the L_q(T^d)-sense, where T^d is the d-dimensional torus. The functions to be approximated are in the unit ball SB^r_p, θ of the mixed smoothness Besov space or in the unit ball SW^r_p of the mixed smoothness Sobolev space. For 1<p, q<∞, 0<θ⩽∞ and r>0 satisfying some restrictions, we establish asymptotic orders of these quantities, as well as construct asymptotically optimal approximation algorithms. We particularly prove that for either r>1/p and θ⩾p or r>(1/p−1/q)₊ and θ⩾min{q, 2}, the asymptotic orders of these quantities for the Besov class SB^r_p, θ are both n^−r(log n)^{(d−1)(r+1/2−1/θ)}.     

On tilings of the binary vector space

Let n be a positive integer, L a subset of {0, 1,…,n}. We discuss the existence of partitions (or tilings) of the n-dimensional binary vector space F_n into L-spheres. By a L-sphere around an x in F_n we mean {y ? F_n, d(x, y) ? L}, d(x, y) being the Hamming distance betwe en x and y. These tilings are generalizations of perfect error correcting codes. We show that very few such tilings exist (Theorem 2) and characterize them all for any L ? {0, 1,…,[$\text{1}\text{2}$n]}.