Minimax goodness-of-fit testing in multivariate nonparametric regression

We consider an unknown response function f defined on Δ = [0, 1] ^d , 1 ≤ d ≤ ∞, taken at n random uniform design points and observed with Gaussian noise of known variance. Given a positive sequence r _n → 0 as n → ∞ and a known function f ₀ ∈ L ₂(Δ), we propose, under general conditions, a unified framework for goodness-of-fit testing the null hypothesis H ₀: f = f ₀ against the alternative H ₁: f ∈ $ \mathcal{F} $ \mathcal{F} , ∥f − f ₀∥ ≥ r _n , where $ \mathcal{F} $ \mathcal{F} is an ellipsoid in the Hilbert space L ₂(Δ) with respect to the tensor product Fourier basis and ∥ · ∥ is the norm in L ₂(Δ). We obtain both rate and sharp asymptotics for the error probabilities in the minimax setup. The derived tests are inherently non-adaptive. Several illustrative examples are presented. In particular, we consider functions belonging to ellipsoids arising from the well-known multidimensional Sobolev and tensor product Sobolev norms as well as from the less-known Sloan-Woźniakowski norm and a norm constructed from multivariable analytic functions on the complex strip.     

On a Distance-Regular Graph of Even Height with ke = kf

 Let Γ be a distance-regular graph of diameter d. The height of Γ is defined by h = max{j∣p ^d _d,j ≠ 0}. Let e, f be positive integers such that e < f and e + f≤d, and let d = 2e + s for some positive integer s. We show that if k _e = k _f , h≤ 2s and the height h is even, then Γ is an antipodal 2-cover. Received: October 23, 1997 Final version received: July 31, 2000     

Lipschitz functions,Schatten ideals,and unbounded derivations

It is proved that, for any Lipschitz function f(t ₁, ..., t _n ) of n variables, the corresponding map f _op: (A ₁, ...,A _n ) → f(A ₁, ..., A _n ) on the set of all commutative n-tuples of Hermitian operators on a Hilbert space is Lipschitz with respect to the norm of each Schatten ideal S ^p , p ∈ (1,∞). This result is applied to the functional calculus of normal operators and contractions. It is shown that Lipschitz functions of one variable preserve domains of closed derivations with values in S ^p . It is also proved that the map f _op is Fréchet differentiable in the norm of S ^p if f is continuously differentiable.     

On the growth of an entire dirichlet series

We establish the relation between the increase of the quantityM(σ,F) = ∣a ₀∣ + ∑ _n=1 ^∞ ∣a _n ∣ exp (σλ _n ) and the behavior of sequences (|a _n |) and (λ _n ), where (λ _n ) is a sequence of nonnegative numbers increasing to + ∞, andF(s) =a ₀ + ∑ _n=1 ^∞ a _n e ^sλn ,s=σ+it, is the Dirichlet entire series. Lviv University, Lviv. Translated from Ukrainskii Matematicheskii Zhurmal, Vol. 51, No. 8, pp. 1149–1153, August, 1999.     

Testing linear operators—An average case study

Given a specification linear operatorS, we want to test an implementation linear operatorA and determine whether it conforms to the specification operator according to an error criterion. In an earlier paper [3], we studied a worst case error in which we test whether the error is no more than a given bound ε>0 for all elements in a given setF, i.e., sup _{fεf∥Sf—Af∥≤ε}. In this work, we study the average error instead, i. e., ∫ _F ∥Sf-Af∥²μ(df)ɛ≤², where μ is a probability measure onF. We assume that an upper boundK on the norm of the difference ofS andA is given a priori. It turns out that any finite number of tests is in general inconclusive with the average error. Therefore, as in the worst case, we allow a relaxation parameter α>0 and test for weak conformance with an error bound (1+α)ε. Then a finite number of tests from an arbitrary orthogonal complete sequence is conclusive. Furthermore, the eigenvectors of the covariance operatorC _μ of the probability measure μ provide an almost optimal test sequence. This implies that the test set isuniversal; it only depends on the set of valid inputsF and the measure μ, and is independent ofS, A, and the other parameters of the problem. However, the minimal number of tests does depend on all the parameters of the testing problem, i.e., ε, α,K, and the eigenvalues ofC _μ. In contrast to the worst case setting, it also depends on the dimensiond of the range space ofS andA. This work was done while consulting at Bell Laboratories, and is partially supported by the National Science Foundation and the Air Force Office of Scientific Research.     

Error estimates in S P for cubature formulas exact for haar polynomials in the two-dimensional case

On the spaces S _p , an upper estimate is found for the norm of the error functional δ _N (f) of cubature formulas possessing the Haar d-property in the two-dimensional case. An asymptotic relation is proved for $ \left\| {\delta _N (f)} \right\|_{S_p^* } On the spaces S _p , an upper estimate is found for the norm of the error functional δ _N (f) of cubature formulas possessing the Haar d-property in the two-dimensional case. An asymptotic relation is proved for with the number of nodes N ∼ 2 ^d , where d → ∞. For N ∼ 2 ^d with d → ∞, it is shown that the norm of δ _N for the formulas under study has the best convergence rate, which is equal to N ^−1/p . Original Russian Text ? K.A. Kirillov, M.V. Noskov, 2009, published in Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 2009, Vol. 49, No. 1, pp. 3–13.     

Bounding the number of connected components of a real algebraic set

For every polynomial mapf=(f ₁,…,f _k): ℝ ⁿ →ℝ ^k , we consider the number of connected components of its zero set,B(Z _f) and two natural “measures of the complexity off,” that is the triple(n, k, d), d being equal to max(degree off _i), and thek-tuple (Δ₁,...,Δ₄), Δ _k being the Newton polyhedron off _i respectively. Our aim is to boundB(Z _f) by recursive functions of these measures of complexity. In particular, with respect to (n, k, d) we shall improve the well-known Milnor-Thom’s bound μ _d (n)=d(2d−1) ⁿ⁻¹. Considered as a polynomial ind, μ _d (n) has leading coefficient equal to 2 ⁿ⁻¹. We obtain a bound depending onn, d, andk such that ifn is sufficiently larger thank, then it improves μ _d (n) for everyd. In particular, it is asymptotically equal to 1/2(k+1)n ^k−1 dⁿ, ifk is fixed andn tends to infinity. The two bounds are obtained by a similar technique involving a slight modification of Milnor-Thom's argument, Smith's theory, and information about the sum of Betti numbers of complex complete intersections.     

Convergence of Lagrange Interpolation Polynomials for Piecewise Smooth Functions

The present paper first establishes a decomposition result for f(x)∈ C ^r C ^r+1. By using this decomposition we thus can obtain an estimate of ∣f(x) - L _n (f,x)∣ which reflects the influence of the position of the x's and ω(f ^(r+1),δ)_j, j = 0,1,...,s, on the error of approximation. This revised version was published online in June 2006 with corrections to the Cover Date.     

Commutator equations in free groups

Letf ₁, …,f _n be free generators of a free groupF. We consider the equation [z ₁, …,z _n]_ω. where ω and ω′ indicate the disposition of brackets in the higher commutators [z ₁, …,z _n]_ω and [f ₁, …,f _n]_ω. We give a necessary and sufficient condition on ω and ω′ for the existence of solutions of this equation. It is also shown that for any solutionz ₁=r₁, …,z _z=r _n we have <r ₁, …,r _n>=〈f ₁, …f _n〉.     

Intersecting sperner families and their convex hulls

Let ℱ be a family of subsets of a finite set ofn elements. The vector (f ₀, ...,f _n ) is called the profile of ℱ wheref _i denotes the number ofi-element subsets in ℱ. Take the set of profiles of all families ℱ satisfyingF ₁⊄F ₂ andF ₁∩F ₂≠0 for allF ₁,F ₂teℱ. It is proved that the extreme points of this set inR ⁿ⁺¹ have at most two non-zero components. Dedicated to Paul Erdős on his seventieth birthday     

On Itô s formula for multidimensional Brownian motion

Consider a d-dimensional Brownian motion X = (X ¹,…,X ^d ) and a function F which belongs locally to the Sobolev space W ^1,2. We prove an extension of It? s formula where the usual second order terms are replaced by the quadratic covariations [f _k (X), X ^k ] involving the weak first partial derivatives f _k of F. In particular we show that for any locally square-integrable function f the quadratic covariations [f(X), X ^k ] exist as limits in probability for any starting point, except for some polar set. The proof is based on new approximation results for forward and backward stochastic integrals. Received: 16 March 1998 / Revised version: 4 April 1999     

Inversion and characterization of the hemispherical transform

Explicit inversion formulas are obtained for the hemispherical transform(FΜ)(x) = Μ{y ∃S ⁿ :x. y ≥ 0},x ∃S ⁿ, whereS ⁿ is thendimensional unit sphere in ℝⁿ⁺¹,n ≥ 2, and Μ is a finite Borel measure onS ⁿ. If Μ is absolutely continuous with respect to Lebesgue measuredy onS ⁿ, i.e.,dΜ(y) =f(y)dy, we write(F f)(x) = ∫ _{x.y> 0} f(y)dy and consider the following cases: (a)f ∃C ^∞(Sⁿ); (b)f ∃ L^p(S ⁿ), 1 ≤ p < ∞; and (c)f ∃C(Sⁿ). In the case (a), our inversion formulas involve a certain polynomial of the Laplace-Beltrami operator. In the remaining cases, the relevant wavelet transforms are employed. The range ofF is characterized and the action in the scale of Sobolev spacesL _p ^γ (Sⁿ) is studied. For zonalf ∃ L¹(S ²), the hemispherical transformF f was inverted explicitly by P. Funk (1916); we reproduce his argument in higher dimensions. Partially sponsored by the Edmund Landau Center for Research in Mathematical Analysis, supported by the Minerva Foundation (Germany).     

Sobolev functions whose inner trace at the boundary is zero

Let Ω⊂R ⁿ be an arbitrary open set. In this paper it is shown that if a Sobolev functionf∈W ^1,p (Ω) possesses a zero trace (in the sense of Lebesgue points) on ϖΩ, thenf is weakly zero on ϖΩ in the sense thatf∈W ₀ ^1,p (Ω).     

Bounds on the number of cycles of length three in a planar graph

LetG be ap-vertex planar graph having a representation in the plane with nontriangular facesF ₁,F ₂, …,F _r. Letf ₁,f ₂, …,f _r denote the lengths of the cycles bounding the facesF ₁,F ₂, …,F _r respectively. LetC ₃(G) be the number of cycles of length three inG. We give bounds onC ₃(G) in terms ofp,f ₁,f ₂, …,f _r. WhenG is 3-connected these bounds are bounds for the number of triangles in a polyhedron. We also show that all possible values ofC ₃(G) between the maximum and minimum value are actually achieved. This research was supported in part by the U.S.A.F. Office of Scientific Research, Systems Command, under Grant AFOSR-76-3017 and the National Science Foundation under Grant ENG79-09724.     

Construction of positive definite cubature formulae and approximation of functions via Voronoi tessellations

Let Ω ⊂ ℝ ^d be a compact convex set of positive measure. In a recent paper, we established a definiteness theory for cubature formulae of order two on Ω. Here we study extremal properties of those positive definite formulae that can be generated by a centroidal Voronoi tessellation of Ω. In this connection we come across a class of operators of the form L_n[f](x): = ?_i=1ⁿ f_i(x)(f(y_i) + á?f(y_i), x-y_i?)L_n[f](\boldsymbol{x}):= \sum_{i=1}^n \phi_i(\boldsymbol{x})(f(\boldsymbol{y}_i) + \langle\nabla f(\boldsymbol{y}_i), \boldsymbol{x}-\boldsymbol{y}_i\rangle), where y₁,..., y_n\boldsymbol{y}_1,\dots, \boldsymbol{y}_n are distinct points in Ω and {ϕ ₁, ..., ϕ _n } is a partition of unity on Ω. We present best possible pointwise error estimates and describe operators L _n with a smallest constant in an L ^p error estimate for 1 ≤ p < ∞ . For a generalization, we introduce a new type of Voronoi tessellation in terms of a twice continuously differentiable and strictly convex function f. It allows us to describe a best operator L _n for approximating f by L _n [f] with respect to the L ^p norm.     

Univalent mappings associated with the Roper-Suffridge extension operator

The Roper-Suffridge extension operator provides a way of extending a (locally) univalent functionfεH(U) to a (locally) biholomorphic mappingF∈H(B_n). In this paper, we give a simplified proof of the Roper-Suffridge theorem: iff is convex, then so isF. We also show that iff∈S ^*, theF is starlike and that iff is a Bloch function inU, thenF is a Bloch mapping onB _n. Finally, we investigate some open problems. Partially supported by the Natural Sciences and Engineering Research Council of Canada under grant A9221.     

On the ingham divisor problem

The main result of this paper is the following theorem. Suppose thatτ(n) = ∑ _d|n l and the arithmetical functionF satisfies the following conditions:

On the index of approximating sets of periodic points

Summary LetK be a compact space andf:K→K a continuous map without fixed points, i.e. Fixf=⊘. For prime numbersp, the sets Fixf ^p are freeℤ/p-spaces with theℤ/p-action induced byf. Our aim is to estimate the topological indicesi(F _p,f) of invariant subsetsF _p⊂Fixf ^p approximating a givenS⊂K. We construct an example (K,f,S) withS⊂Fixf ^q (q being some prime number) such that, for each neighborhoodU ofS, i (Fix (f|u) ^p, f) increases linearly withp. This article was processed by the author using the L^AT_EX style filecljour1 from Springer-Verlag.     

Frames and their associated $\emph{H}_{{\kern-2pt}\emph{F}}^{\emph{p}}$-subspaces

Given a frame F = {f _j } for a separable Hilbert space H, we introduce the linear subspace H^p_FH^{p}_{F} of H consisting of elements whose frame coefficient sequences belong to the ℓ ^p -space, where 1 ≤ p < 2. Our focus is on the general theory of these spaces, and we investigate different aspects of these spaces in relation to reconstructions, p-frames, realizations and dilations. In particular we show that for closed linear subspaces of H, only finite dimensional ones can be realized as H^p_FH^{p}_{F}-spaces for some frame F. We also prove that with a mild decay condition on the frame F the frame expansion of any element in H_F^pH_{F}^{p} converges in both the Hilbert space norm and the ||·|| _{F, p} -norm which is induced by the ℓ ^p -norm.     

On homomorphisms from the Hamming cube to Z

WriteF for the set of homomorphisms from {0, 1} ^d toZ which send0 to 0 (think of members ofF as labellings of {0, 1} ^d in which adjacent strings get labels differing by exactly 1), andF ₁ for those which take on exactlyi values. We give asymptotic formulae for |F| and |F|. In particular, we show that the probability that a uniformly chosen memberf ofF takes more than five values tends to 0 asd→∞. This settles a conjecture of J. Kahn. Previously, Kahn had shown that there is a constantb such thatf a.s. takes at mostb values. This in turn verified a conjecture of I. Benjaminiet al., that for eacht>0,f a.s. takes at mosttd values. Determining |F| is equivalent both to counting the number of rank functions on the Boolean lattice 2^[d] (functionsf: 2^[d]→N satisfyingf( ) andf(A)≤f(A∪x)≤f(A)+1 for allA∈2^[d] andx∈[d]) and to counting the number of proper 3-colourings of the discrete cube (i.e., the number of homomorphisms from {0, 1} ^d toK ₃, the complete graph on 3 vertices). Our proof uses the main lemma from Kahn’s proof of constant range, together with some combinatorial approximation techniques introduced by A. Sapozhenko. Research supported by a Graduate School Fellowship from Rutgers University.