Search

Diaconis and Griffiths (2014) study the multivariate Krawtchouk polynomials orthogonal on the multinomial distribution. In this paper we derive the reproducing kernel orthogonal polynomials Q n ( x , y ; N , p ) on the multinomial distribution which are sums of products of orthonormal polynomials in x and y of fixed total degree n = 0 , 1 , … , N . The Poisson kernel ∑ n = 0 N ρ n Q n ( x , y ; N , p ) arises naturally from a probabilistic argument. An application to a multinomial goodness of fit test is developed, where the chi-squared test statistic is decomposed into orthogonal components which test the order of fit. A new duplication formula for the reproducing kernel polynomials in terms of the 1-dimensional Krawtchouk polynomials is derived. The duplication formula allows a Lancaster characterization of all reversible Markov chains with a multinomial stationary distribution whose eigenvectors are multivariate Krawtchouk polynomials and where eigenvalues are repeated within the same total degree. The χ 2 cutoff time, and total variation cutoff time is investigated in such chains. Emphasis throughout the paper is on a probabilistic understanding of the polynomials and their applications, particularly to Markov chains.

In this paper we make a comparison between certain probabilistic and deterministic point sets and show that some deterministic constructions (especially spherical t -designs) are better or as good as probabilistic ones like the jittered sampling model. We find asymptotic equalities for the discrete Riesz s -energy of sequences of well separated t -designs on the unit sphere S d ⊂ R d + 1 , d ≥ 2 . The case d = 2 was studied in Hesse (2009) and Hesse and Leopardi (2008). In Bondarenko et al., (2015) it was established that for d ≥ 2 , there exists a constant c d , such that for every N > c d t d there exists a well-separated spherical t -design on S d with N points. This paper gives results, based on recent developments that there exists a sequence of well separated spherical t -designs such that t and N are related by N ≍ t d .

In this paper we study the so called optimal polynomial meshes for domains in K ⊂ R d , d ≥ 2 . These meshes are discrete point sets Y n of cardinality c n d which have the property that ‖ p ‖ K ≤ A ‖ p ‖ Y n for every polynomial p of degree at most n with a constant A > 1 independent of n . It was conjectured earlier that optimal polynomial meshes exist in every convex domain. This statement was previously shown to hold for polytopes and C 2 like domains. In this paper we give a complete affirmative answer to the above conjecture when d = 2 .

This paper studies the approximation of the Hilbert transform f ? = H f of continuous functions f with continuous conjugate f ? based on a finite number of samples. It is known that every sequence { H N f } N ? N which approximates f ? from samples of f diverges (weakly) with respect to the uniform norm. This paper conjectures that all of these approximation sequences even contain no convergent subsequence. A property which is termed strong divergence.The conjecture is supported by two results. First it is proven that the sequence of the sampled conjugate Fejer means diverges strongly. Second, it is shown that for every sample based approximation method { H N } N ? N there are functions f such that ? H N f ? ∞ exceeds any given bound for any given number of consecutive indices N .As an application, the later result is used to investigate a problem associated with a question of Ul'yanov on Fourier series which is related to the possibility to construct adaptive approximation methods to determine the Hilbert transform from sampled data. This paper shows that no such approximation method with a finite search horizon exists.

This paper provides the theoretical foundation for the component-by-component (CBC) construction of randomly shifted lattice rules that are tailored to integrals over R s arising from practical applications. For an integral of the form ∫ R s f ( y ) ∏ j = 1 s ϕ ( y j ) d y with a univariate probability density ϕ , our general strategy is to first map the integral into the unit cube [ 0 , 1 ] s using the inverse of the cumulative distribution function of ϕ , and then apply quasi-Monte Carlo (QMC) methods. However, the transformed integrand in the unit cube rarely falls within the standard QMC setting of Sobolev spaces of functions with mixed first derivatives. Therefore, a non-standard function space setting for integrands over R s , previously considered by Kuo, Sloan, Wasilkowski and Waterhouse (2010), is required for the analysis. Motivated by the needs of three applications, the present paper extends the theory of the aforementioned paper in several non-trivial directions, including a new error analysis for the CBC construction of lattice rules with general non-product weights, the introduction of an unanchored variant for the setting, the use of coordinate-dependent weight functions in the norm, and the strategy for fast CBC construction with POD (“product and order dependent”) weights.

In the present paper, we study conditions under which the metric projection of a polyhedral Banach space X onto a closed subspace is Hausdorff lower or upper semicontinuous. For example, we prove that if X satisfies (*) (a geometric property stronger than polyhedrality) and Y@?X is any proximinal subspace, then the metric projection P"Y is Hausdorff continuous and Y is strongly proximinal (i.e., if {y"n}@?Y, x@?X and @?y"n-x@?->dist(x,Y), then dist(y"n,P"Y(x))->0). One of the main results of a different nature is the following: if X satisfies (*) and Y@?X is a closed subspace of finite codimension, then the following conditions are equivalent: (a) Y is strongly proximinal; (b) Y is proximinal; (c) each element of Y^@? attains its norm. Moreover, in this case the quotient X/Y is polyhedral. The final part of the paper contains examples illustrating the importance of some hypotheses in our main results.

Berrizbeitia and Olivieri showed in a recent paper that, for any integer r, the notion of @w-prime to base a leads to a primality test for numbers n=1 mod r, that under the Extended Riemann Hypothesis (ERH) runs in polynomial time. They showed that the complexity of their test is at most the complexity of the Miller primality test (MPT), which is O((logn)^4^+^o^(^1^)). They conjectured that their test is more effective than the MPT if r is large. In this paper, we show that their conjecture is not true by showing that the Berrizbeitia-Olivieri primality test (BOPT) has no advantage over the MPT, either for proving primality of a prime under the ERH, or for detecting compositeness of a composite. In particular, we point out that the complexity of the BOPT depends not only on n but also on r and that in the worst cases (usually when n is prime) for both tests, the BOPT is in general at least twice slower than the MPT, and in some cases (usually when n is composite) the BOPT may be much slower. Moreover, the BOPT needs O(rlogn) bit memories. We also give facts and numerical examples to show that, for some composites n and for some r, the rth roots of unity @w do not exist, and thus outputs of the BOPT are ERH conditional, whereas the MPT always quickly and definitely (without ERH) detects compositeness for all odd composites.

In a paper Cheung, Cucker and Peña (in press) [5] that can be seen as the first part of this one, we extended the well-known condition numbers for polyhedral conic systems C(A) Renegar (1994, 1995) [7–9] and C(A) Cheung and Cucker (2001) [3] to versions C¯(A) and C¯(A) that are finite for all input matrices A∈Rn×m. In this paper we compare C¯(A) and C¯(A) with other condition measures for the same problem that are also always finite.

The cyclic projections algorithm is an important method for determining a point in the intersection of a finite number of closed convex sets in a Hilbert space. That is, for determining a solution to the ''convex feasibility'' problem. This is the third paper in a series on a study of the rate of convergence for the cyclic projections algorithm. In the first of these papers, we showed that the rate could be described in terms of the ''angles'' between the convex sets involved. In the second, we showed that these angles often had a more tractable formulation in terms of the ''norm'' of the product of the (nonlinear) metric projections onto related convex sets. In this paper, we show that the rate of convergence of the cyclic projections algorithm is also intimately related to the ''linear regularity property'' of Bauschke and Borwein, the ''normal property'' of Jameson (as well as Bakan, Deutsch, and Li's generalization of Jameson's normal property), the ''strong conical hull intersection property'' of Deutsch, Li, and Ward, and the rate of convergence of iterated parallel projections. Such properties have already been shown to be important in various other contexts as well.

Many papers study polynomial tractability for multivariate problems. Let n(@?,d) be the minimal number of information evaluations needed to reduce the initial error by a factor of @? for a multivariate problem defined on a space of d-variate functions. Here, the initial error is the minimal error that can be achieved without sampling the function. Polynomial tractability means that n(@?,d) is bounded by a polynomial in @?^-^1 and d and this holds for all (@?^-^1,d)@?[1,~)xN. In this paper we study generalized tractability by verifying when n(@?,d) can be bounded by a power of T(@?^-^1,d) for all (@?^-^1,d)@[email protected], where @W can be a proper subset of [1,~)xN. Here T is a tractability function, which is non-decreasing in both variables and grows slower than exponentially to infinity. In this article we consider the set @W=[1,~)x{1,2,...,d^*}@?[1,@?"0^-^1)xN for some d^*>=1 and @?"[email protected]?(0,1). We study linear tensor product problems for which we can compute arbitrary linear functionals as information evaluations. We present necessary and sufficient conditions on T such that generalized tractability holds for linear tensor product problems. We show a number of examples for which polynomial tractability does not hold but generalized tractability does.

Suppose that X- = (X 0 , X 1 ) and Y-=(Y 0 ,Y 1 ) are Banach couples and suppose that T 0 : X 0 → Y 0 and T 1 : X 1 → Y 1 are bounded and linear. Also assume that Γ ∈ (Δ(X-))' and that T 0 and T 1 agree as maps from Δ(X-) ∩ ker Γ to Σ(Y-). If the maps do not agree as maps from all of Δ(X-) we cannot interpolate T 0 and T 1 to a map T : J 0,p (X- → J 0,p (Y-), where J 0,p denotes the classical J-method. This situation can for example be found in an article on interpolation of Hardy-type inequalities by Krugljak, Maligranda and Persson. We will in this paper define functors J 0,p;Γ such that T 0 and T 1 interpolate to a map T: J 0,p:Γ (X-) → J 0,p (Y-). The main purpose of this paper is to make the definition of the J 0,p;Γ (X-) spaces and build a theory for them. We will also do this for more general real parameters. If Γ is bounded on X 0 it holds that J 0,p:Γ (X-)=J 0,p (X 0 ∩ ker Γ, X 1 ). These spaces have been studied by Kalton, Ivanov and Lofstrom. Their results will follow as corollaries to the more general results of this article and our new theory can be thought of as a theory for generalized subcouples of codimension one. In the last section, we apply our theory to a situation considered by Krugljak, Maligranda and Persson in connection with Hardy-type inequalities. We prove new results and provide a new way of understanding that kind of problems.

Let Q: R → R be even, nonnegative and continuous, Q' be continuous, Q' > 0 in (0, ∞), and let Q'' be continuous in (0, ∞). Furthermore, Q satisfies further conditions. We consider a certain generalized Freud-type weight WrQ2(x) = |x|2r exp(-2Q(x)). In previous paper (J. Approx. Theory 121 (2003) 13) we studied the properties of orthonormal polynomials {Pn(WrQ2; x)}n=0x with the generalized Freud-type weight WrQ2(x) on R. In this paper we treat three themes. Firstly, we give an estimate of Pn(WrQ2; x) in the Lp-space, 0 < p ≤ ∞. Secondly, we obtain the Markov inequalities, and third we study the higher-order Hermite Fejer interpolation polynomials based at the zeros {xkn}k=1n of Pn(WrQ2; x). In Section 5 we show that our results are applicable to the study of approximation for continuous functions by the higher-order Hermite-Fejer interpolation polynomials.

Consider the Hardy-type integral operator T : Lp(a,b) → Lp(a,b), -∞ ≤ a < b ≤ ∞, which is defined by (Tf)(x) = v(x) ∫ax u(t)f(t)dt.In the papers by Edmunds et al. (J. London Math. Soc. (2) 37 (1988) 471) and Evans et al. (Studia Math. 130 (2) (1998) 171) upper and lower estimates and asymptotic results were obtained for the approximation numbers an(T) of T. In case p = 2 for "nice" u and v these results were improved in Edmunds et al. (J. Anal. Math. 85 (2001) 225). In this paper, we extend these results for 1 < p < ∞ by using a new technique. We will show that under suitable conditions on u and v, lim supn → ∞ n1/2 |λp-1/p ∫ab |u(t)v(t)|dt - nan(T)| ≤ c(||u'||p'/(p'+1) + ||v'||p/(p+1))(||u||p' + ||v||p) + 3αp||uv||1, where ||w||p = (∫ab |w(t)|p dt)1/p and λp is the first eigenvalue of the p-Laplacian eigenvalue problem on (0, 1).

We exhibit a new method for showing lower bounds for time-space tradeoffs of polynomial evaluation procedures given by straight-line programs. From the tradeoff results obtained by this method we deduce lower space bounds for polynomial evaluation procedures running in optimal nonscalar time. Time, denoted by L, is measured in terms of nonscalar arithmetic operations and space, denoted by S, is measured by the maximal number of pebbles (registers) used during the given evaluation procedure. The time-space tradeoff function considered in this paper is LS2. We show that for "almost all" univariate polynomials of degree at most d our time-space tradeoff functions satisfy the inequality LS2≥d8. From this we conclude that for "almost all" degree d univariate polynomials, any nonscalar time optimal evaluation procedure requires space at least S≥cd, where c>0 is a suitable universal constant. The main part of this paper is devoted to the exhibition of specific families of univariate polynomials which are "hard to compute" in the sense of time-space tradeoff (this means that our tradeoff function increases linearly in the degree). © 2000 Academic Press. Fil:Matera, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.

We consider the problem of approximating fixed points of contractive functions whose contraction factor is close to 1. In a previous paper (1993, K. Sikorski et al. , J. Complexity 9 , 181–200), we proved that for the absolute error criterion, the upper bound on the number of function evaluations to compute e -approximations is O( n 3 (ln(1/ e )+ln(1/(1− q ))+ln n )) in the worst case, where 0 q n is the dimension of the problem. This upper bound is achieved by the circumscribed ellipsoid (CE) algorithm combined with a dimensional deflation process. In this paper we present an inscribed ellipsoid (IE) algorithm that enjoys O( n (ln(1/ e )+ln(1/(1− q )))) bound. For q close to 1, the IE algorithm thus runs in many fewer iterations than the simple iteration method, that requires ⌈ln(1/ e )/ln(1/ q )⌉ function evaluations. Our analysis also implies that: (1) The dimensional deflation procedure in the CE algorithm is not necessary and that the resulting “plain” CE algorithm enjoys O( n 2 (log(1/ e )+log(1/(1− q )))) upper bound on the number of function evaluations. (2) The IE algorithm solves the problem in the residual sense, i.e., computes x such that ‖ f ( x )− x ‖⩽ δ , with O( n ln(1/ δ )) function evaluations for every q ⩽1.

It is known that if f ∈ W k p , then ω m ( f , t ) p ⩽ tω m −1 ( f ′, t ) p ⩽…. Its inverse with any constants independent of f is not true in general. Hu and Yu proved that the inverse holds true for splines S with equally spaced knots, thus ω m ( S , t ) p ∼ tω m −1 ( S ′, t ) p ∼ t 2 ω m −2 ( S ″, t ) p …. In this paper, we extend their results to splines with any given knot sequence, and further to principal shift-invariant spaces and wavelets under certain conditions. Applications are given at the end of the paper.

We show that if the Generalized Riemann Hypothesis is true, the problem of deciding whether a system of polynomial equations in several complex variables has a solution is in the second level of the polynomial hierarchy. In fact, this problem is in AM, the ``Arthur-Merlin'''' class (recall that $\np \subseteq \am \subseteq \rp^{\tiny \np} \subseteq \Pi_2$). The best previous bound was PSPACE. An earlier version of this paper was distributed as NeuroCOLT Technical Report~96-44. The present paper includes in particular a new lower bound for unsatisfiable systems, and remarks on the Arthur-Merlin class.

For two nonzero polynomialsformula]the successive signed Euclidean division yields algorithms, that is, semialgebraic computation trees, for tasks such as computing the sequence of successive quotients, deciding the signs of the sequence of remainders in a pointa?R, deciding the number of remainders, or deciding the degree pattern of the sequence of remainders. In this paper we show lower bounds of ordermlog2(m) for these tasks, within the computational framework of semi-algebraic computation trees. The inevitably long paths in semi-algebraic computation trees can be specified as those followed by certain prime cones in the real spectrum of a polynomial ring. We give in the paper a positive answer to the question posed in T. Lickteig (J. Pure Appl. Algebra110(2), 131?184 (1996)) whether the degree of the zero-set of the support of a prime cone provides a lower bound on the complexity of isolating the prime cone. The applications are based on the degree inequalities given by Strassen and Schuster and extend their work to the real situation in various directions.

In a recent paper by Hu it is proved that for any convex function f there is a C 1 convex quadratic spline s with n knots that approximates f at the rate of ω 3 ( f , n −1 ). The knots of the spline are basically equally spaced. In this paper we give a simple construction of such a spline with equally spaced knots.

Previous work on the ϵ-complexity of elliptic boundary-value problems Lu = f assumed that the class F of problem elements f was the unit ball of a Sobolev space. In a recent paper, we considered the case of a model two-point boundary-value problem, with F being a class of analytic functions. In this paper, we ask what happens if F is a class of piecewise analytic functions. We find that the complexity depends strongly on how much a priori information we have about the breakpoints. If the location of the breakpoints is known, then the "-complexity is proportional to ln（ϵ-1）, and there is a finite element p-method (in the sense of Babuska) whose cost is optimal to within a constant factor. If we know neither the location nor the number of breakpoints, then the problem is unsolvable for ϵ less than sqroot(2). If we know only that there are b equal or greater than 2 breakpoints, but we don't know their location, then the ϵ-complexity is proportional to bϵ-1, and a finite element h-method is nearly optimal. . In short, knowing the location of the breakpoints is as good as knowing that the problem elements are analytic, whereas only knowing the number of breakpoints is no better than knowing that the problem elements have a bounded derivative in the L2 sense.

A radial basis function approximation has the form [formula] where φ: [0,∞)→ R is some given function, (yj)n1 are real coefficients, and the centres (xj)n1 are points in Rd. For a wide class of functions φ, it is known that the interpolation matrix A = (φ(||xj − xk||2))nj,k=1 is invertible. Further, several recent papers have provided upper bounds on ||A−1||2, where the points (xj)n1 satisfy the condition ||xj − xk||2 ≥ δ, j ≠ k, for some positive constant δ. In this paper, we provide the least upper bound on ||A−1||2 when the points (xj)n1 form any subset of the integer lattice Ld, and when φ is a conditionally negative definite function of order 1, a large set of functions which includes the multiquadric. Specifically, for any set of points (xj)n1 ⊂ Ld, we provide the inequality [formula] where e = [1, . . . , 1]T ∈ Rd and where φ̂ is the generalized Fourier transform of φ. We provide a constructive proof that no smaller bound is valid and comment on the relevance of the method of analysis to the problem of estimating all the eigenvalues of such an interpolation matrix

The paper considers Hermite interpolation for vector-valued functions. Corresponding to the interpolating functions f we define functionals I which contain function values of f ( r ) and integrals of f ( r ) where 0 ≤ r ≤ m for some integer m . The main purpose of the paper is to characterize those functions which satisfy the interpolation problem and have a minimal value of I . These characterizations contain several results of the literature including splines in tension and geometric splines.

The probabilistic setting for approximately solved problems has been studied in a number of papers; see, e.g., (Lee and Wasilkowski, 1986; Traub et al., 1988) and papers cited therein. Roughly speaking, it can be described in the following way. Suppose that we want to approximate the solutions SY-, for f E F, where S: F + G is an operator, F is a linear space, and G is a normed linear space. The elements S(j) are approximated by Ucf) E G, where Ucf) = 4(Ncf)) with information Ncf) consisting of n values of linear functionals Liv), and with an algorithm 4: N(F) + G being an arbitrary mapping. Assuming that the space F is endowed with a given probability measure /,L, the quality of U = 4 0 N is measured by the p-probability that the error [IS(j) U(‘j)ll is small. That is, for a given parameter 6 E (0, l), we seek an “optimal” algorithm U that, with probability at least 1 6, approximates Scf) to within E for as small E as possible. Equivalently: for a given 6 E (0, l), we want to find a pair (U, E) such that E is the smallest number for which p(CfE F: [IS(~) U(j)II 5 E}) 2 1 6. Since the bound E is independent off, it is an a priori bound. Since we seek the smallest E, in the probabilistic setting we actually search for U = $J 0 N that admits the sharpest a priori error bounds. In this paper, we propose a more general approach by permitting a posteriori bounds. That is, in addition to algorithms $, we let bounds Bcf

In this paper we consider weighted polynomial approximation on unbounded multidimensional domains in the spirit of the weighted version of the Weierstrass trigonometric theorem according to which every continuous function on the real line with equal finite limits at ± ∞ is a uniform limit on R of weighted algebraic polynomials of degree 2 n with varying weights ( 1 + t 2 ) − n . We will verify a similar statement in the multivariate setting for a general class of convex weights. We also consider the similar problem of multivariate polynomial approximation with varying weights for some typical non convex weights. In case of non convex weights of the form w α ( x ) ≔ ( 1 + | x 1 | α + . . . + | x d | α ) 1 α , 0 α 1 in order for weighted polynomial approximation to hold for a given continuous function it is necessary that the function vanishes on a certain exceptional set consisting of all coordinate hyperplanes and ∞ . Moreover, in case of rational α this condition is also sufficient for weighted polynomial approximation to hold.

The study of the restricted isometry property (RIP) of corrupted random matrices is particularly important in the field of compressed sensing (CS) with corruptions. If a matrix still satisfies the RIP after that a certain portion of rows are erased, then we say that this matrix has the strong restricted isometry property (SRIP). In the field of compressed sensing, random matrices which satisfy certain moment conditions are of particular interest. Among these matrices, those with entries generated from i.i.d. Gaussian or symmetric Bernoulli random variables are often typically considered. Recent studies have shown that matrices with entries generated from i.i.d. Gaussian random variables satisfy the SRIP under arbitrary erasure of rows with high probability. In this paper, we study the erasure robustness property of Bernoulli random matrices. Our main result shows that with overwhelming probability, the SRIP holds for Bernoulli random matrices. Moreover, our analysis leads to a robust version of the famous Johnson–Lindenstrauss lemma for Bernoulli random matrices.

Let $L$ be the generator of an analytic semigroup whose kernels satisfy Gaussian upper bounds and H\"older's continuity. Also assume that $L$ has a bounded holomorphic functional calculus on $L^2(\mathbb{R}^n)$. In this paper, we construct a frame decomposition for the functions belonging to the Hardy space $H_{L}^{1}(\mathbb{R}^n)$ associated to $L$, and for functions in the Lebesgue spaces $L^p$, $1, Comment: 37 pages, to appear in Journal of Approximation Theory

The objective of this paper is to present a unified study of multivariate super vertex splines with emphasis on the construction procedure and an application to least-squares approximation with interpolatory constraints. Both simplicial and parallelepiped partitions are studied in some detail, and in the bivariate setting, even a partition consisting of both triangles and parallelograms is considered. When the polynomial degree is allowed to be sufficiently large as compared to the order of smoothness, it is clear that vertex splines can be constructed by working on each simplex or parallelepiped separately as long as certain suitable normal derivative constraints are imposed on the boundary faces. Our constructive procedure will take a different route. Instead of normal derivatives, we impose extra interpolatory conditions at the “vertices”. This gives rise to the notion of “super splines” introduced in this paper. It should also be emphasized that the view point of considering a basis of piecewise polynomials with smallest possible supports so that the full approximation order is preserved makes vertex splines different from the standard approach in finite elements. After all, if the polynomial degree is required to be lower, it is necessary to work on at least three adjacent simplices or parallelepipeds simultaneously in constructing a basis of vertex splines.

We show in this paper that the VC-dimension of the family of d-dimensional axis-parallel boxes and cubes on the d-dimensional torus are both asymptotically d log 2 ⁡ d . This is especially surprising as in most other examples the VC-dimension usually grows linearly with d in similar settings.

Recently, the convergence–divergence properties of the Berrut rational interpolant (Berrut, 1988) were studied in the case of equidistant nodes (Mastroianni and Szabados, 2017). A very general class called “well-spaced nodes” was introduced in Bos et al. (2013), a class which includes essentially any distribution of nodes that satisfies a particular regularity condition, such as equidistant nodes, Chebyshev nodes as well as extended Chebyshev nodes. In this paper we show that results obtained in Mastroianni and Szabados, (2017) for the equidistant nodes hold more generally for the class of well-spaced nodes, with the restriction that the end points of the definition interval are nodes.

We analyze a new random algorithm for numerical integration of d -variate functions over [ 0 , 1 ] d from a weighted Sobolev space with dominating mixed smoothness α ≥ 0 and product weights 1 ≥ γ 1 ≥ γ 2 ≥ ⋯ > 0 , where the functions are continuous and periodic when α > 1 ∕ 2 . The algorithm is based on rank-1 lattice rules with a random number of points n . For the case α > 1 ∕ 2 , we prove that the algorithm achieves almost the optimal order of convergence of O ( n − α − 1 ∕ 2 ) , where the implied constant is independent of the dimension d if the weights satisfy ∑ j = 1 ∞ γ j 1 ∕ α ∞ . The same rate of convergence holds for the more general case α > 0 by adding a random shift to the lattice rule with random n . This shows, in particular, that the exponent of strong tractability in the randomized setting equals 1 ∕ ( α + 1 ∕ 2 ) , if the weights decay fast enough. We obtain a lower bound to indicate that our results are essentially optimal. This paper is a significant advancement over previous related works with respect to the potential for implementation and the independence of error bounds on the problem dimension. Other known algorithms which achieve the optimal error bounds, such as those based on Frolov’s method, are very difficult to implement especially in high dimensions. Here we adapt a lesser-known randomization technique introduced by Bakhvalov in 1961. This algorithm is based on rank-1 lattice rules which are very easy to implement given the integer generating vectors. A simple probabilistic approach can be used to obtain suitable generating vectors.

In this paper, we study the problem of whether the best approximation to any x in a real Hilbert space X from the closed convex set K ≔ C ∩ D can be characterized by the best approximation to a perturbation x − l of x from the set C for some l in a certain cone in X . The set C is a closed convex subset of X and D ≔ { x ∈ X : g j ( x ) ≤ 0 , ∀ j = 1 , 2 , … , m } , where the functions g j : X ⟶ R ( j = 1 , 2 , … , m ) are continuously Frechet differentiable that are not necessarily convex. We show under suitable conditions that this “perturbation property” is characterized by the strong conical hull intersection property of C and D at the point x 0 ∈ K . We prove this by first establishing a dual cone characterization of a nearly convex set. Our result shows that the convex geometry of K is critical for the characterization rather than the representation of D by convex inequalities, which is commonly assumed for the problems of best approximation from a convex set. In the special case where the set D is convex, we show that the Lagrange multiplier characterization of best approximation holds under the standard Slater’s constraint qualification together with a non-degeneracy condition. The lack of representation of D by convex inequalities is supplemented by the non-degeneracy condition, but the characterization, even in this special case, allows applications to problems with quasi-convex functions g j , j = 1 , 2 , … , m , as they guarantee the convexity of D . Simple numerical examples illustrate the nature of our assumptions.

In this paper we study ( s , t ) -weak tractability of the weighted star discrepancy with general coefficients of centered regular grids with different mesh-sizes. We give matching necessary and sufficient conditions on ( s , t ) -weak tractability with s > 0 and t ∈ ( 0 , 1 ] in terms of the weight sequences. We also prove that the weighted star discrepancy has ( s , t ) -weak tractability for all s > 0 and t > 1 .

Let $\Pi_n^d$ denote the space of spherical polynomials of degree at most $n$ on the unit sphere $\mathbb{S}^d\subset \mathbb{R}^{d+1}$ that is equipped with the surface Lebesgue measure $d\sigma$ normalized by $\int_{\mathbb{S}^d} \, d\sigma(x)=1$. This paper establishes a close connection between the asymptotic Nikolskii constant, $$ \mathcal{L}^\ast(d):=\lim_{n\to \infty} \frac 1 {\dim \Pi_n^d} \sup_{f\in \Pi_n^d} \frac { \|f\|_{L^\infty(\mathbb{S}^d)}}{\|f\|_{L^1(\mathbb{S}^d)}},$$ and the following extremal problem: $$ \mathcal{I}_\alpha:=\inf_{a_k} \Bigl\| j_{\alpha+1} (t)- \sum_{k=1}^\infty a_k j_{\alpha} \bigl( q_{\alpha+1,k}t/q_{\alpha+1,1}\bigr)\Bigr\|_{L^\infty(\mathbb{R}_+)} $$ with the infimum being taken over all sequences $\{a_k\}_{k=1}^\infty\subset \mathbb{R}$ such that the infinite series converges absolutely a.e. on $\mathbb{R}_+$. Here $j_\alpha $ denotes the Bessel function of the first kind normalized so that $j_\alpha(0)=1$, and $\{q_{\alpha+1,k}\}_{k=1}^\infty$ denotes the strict increasing sequence of all positive zeros of $j_{\alpha+1}$. We prove that for $\alpha\ge -0.272$, $$\mathcal{I}_\alpha= \frac{\int_{0}^{q_{\alpha+1,1}}j_{\alpha+1}(t)t^{2\alpha+1}\,dt}{\int_{0}^{q_{\alpha+1,1}}t^{2\alpha+1}\,dt}= {}_{1}F_{2}\Bigl(\alpha+1;\alpha+2,\alpha+2;-\frac{q_{\alpha+1,1}^{2}}{4}\Bigr). $$ As a result, we deduce that the constant $\mathcal{L}^\ast(d)$ goes to zero exponentially fast as $d\to\infty$: \[ 0.5^d\le \mathcal{L}^{*}(d)\le (0.857\cdots)^{d\,(1+\varepsilon_d)} \ \ \ \ \ \text{with $\varepsilon_d =O(d^{-2/3})$.} \]

Let n ≥ 2 . In this paper, we obtain approximation properties of various families of normalized univalent mappings f on the Euclidean unit ball B n in C n by automorphisms of C n whose restrictions to B n have the same geometric property of f . First, we obtain approximation properties of spirallike, convex and g -starlike mappings f on B n by automorphisms of C n whose restrictions to B n have the same geometric property of f , respectively. Next, for a nonresonant operator A with m ( A ) > 0 , we obtain an approximation property of mappings which have A -parametric representation by automorphisms of C n whose restrictions to B n have A -parametric representation. Certain questions will be also mentioned. Finally, we obtain an approximation property by automorphisms of C n for a subset of S I n 0 ( B n ) consisting of mappings f which satisfy the condition ‖ D f ( z ) − I n ‖ 1 , z ∈ B n . Related results will be also obtained.

In this paper we investigate a special sequence related to the Halton sequence, namely the Halton sequence indexed by ⌊ n β ⌋ with β ∈ R , and prove a metric almost low-discrepancy result.

Let F ( x ) : = ( f i j ( x ) ) i = 1 , … , p ; j = 1 , … , q , be a ( p × q )-real polynomial matrix and let f ( x ) be the smallest singular value function of F ( x ) . In this paper, we first give the following nonsmooth version of Łojasiewicz gradient inequality for the function f with an explicit exponent: For any x ∈ R n , there exist c > 0 and ϵ > 0 such that we have for all ‖ x − x ‖ ϵ , inf { ‖ w ‖ : w ∈ ∂ f ( x ) } ≥ c | f ( x ) − f ( x ) | 1 − τ , where ∂ f ( x ) is the limiting subdifferential of f at x , d : = max i = 1 , … , p ; j = 1 , … , q deg f i j , ℛ ( n , d ) : = d ( 3 d − 3 ) n − 1 if d ≥ 2 and ℛ ( n , d ) : = 1 if d = 1 , and τ : = 1 ℛ ( n + p , 2 d + 2 ) . Then we establish some versions of Łojasiewicz inequality for the distance function with explicit exponents, locally and globally, for the smallest singular value function f ( x ) of the matrix F ( x ) .

In this paper, we compute the probability that an $N \times N$ matrix from the generalised Gaussian Unitary Ensemble (gGUE) is positive definite, extending a previous result of Dean and Majumdar \cite{DM}. For this purpose, we work out the large degree asymptotics of semi-classical Laguerre polynomials and their recurrence coefficients, using the steepest descent analysis of the corresponding Riemann--Hilbert problem., 21 pages, 1 figure. Revised version, minor changes and references added

The PCP theorem has recently been shown to hold as well in the real number model of Blum, Shub, and Smale (Baartse and Meer, 2015). The proof given there structurally closely follows the proof of the original PCP theorem by Dinur (2007). In this paper we show that the theorem also can be derived using algebraic techniques similar to those employed by Arora etal. (Arora etal., 1998; Arora and Safra, 1998) in the first proof of the PCP theorem. This needs considerable additional efforts. Due to severe problems when using low degree algebraic polynomials over the reals as codewords for one of the verifiers to be constructed, we work with certain trigonometric polynomials. This entails the necessity to design new segmentation procedures in order to obtain well structured real verifiers appropriate for applying the classical technique of verifier composition.We believe that designing as well an algebraic proof for the real PCP theorem on one side leads to interesting questions in real number complexity theory and on the other sheds light on which ingredients are necessary in order to prove an important result as the PCP theorem in different computational models.

In this paper, we extend the sharp upper bound of Christiansen et al. (2017) and the sharp lower bound of Schiefermayr (2008) to the case of weighted Chebyshev polynomials on subsets of [ − 1 , 1 ] for the weight w ( x ) = 1 − x 2 . We then analyse the norm of Chebyshev polynomials on a circular arc, prove monotonicity of the corresponding Widom factors, find exact values of their supremum and infimum, and obtain a new proof for their limit.

In this paper, we discuss the compressed data separation problem. In order to reconstruct the distinct subcomponents, which are sparse in morphologically different dictionaries D 1 ∈ R n × d 1 and D 2 ∈ R n × d 2 , we present a general class of convex optimization decoder. It can deal with signal separation under the corruption of different kinds of noises, including Gaussian noise ( p = 2 ), Laplacian noise ( p = 1 ), and uniformly bounded noise ( p = ∞ ). Although the restricted isometry property adapted to frames is a commonly used tool, the measurement number is suboptimal when p > 2 . Furthermore, the l p robust nullspace property adapted to Ψ , which is constructed by D 1 and D 2 , may fail to work on data separation problem. Here we introduce the modified l p robust nullspace property adapted to Ψ (abbreviated as the modified ( l p , Ψ )-RNSP). First of all, we show the robust recovery of signals based on the modified ( l p , Ψ )-RNSP and the mutual coherence between D 1 and D 2 . Besides, we find that Gaussian measurements meet the modified ( l p , Ψ )-RNSP for any 1 ≤ p ≤ ∞ , provided with the optimal number of measurements O ( s log ( d ∕ s ) ) , where s is the sparsity level and d = d 1 + d 2 . Furthermore, we introduce another properly constrained l 1 -analysis optimization model, called the Split Dantzig Selector. It can recover signals which are approximately sparse in terms of different frame representations, when the measurement matrix satisfies the modified ( l p , Ψ )-RNSP. As a special case, when considering Gaussian white noise, the recovery error by the Split Dantzig Selector is O s log d m . It outperforms the l 2 -constrained model, whose recovery error is O ( log m ) , if the sparsity level is small.

Meixner type polynomials ( q n ) n ≥ 0 are defined from the Meixner polynomials by using Casoratian determinants whose entries belong to two given finite sets of polynomials ( S h ) h = 1 m 1 and ( T g ) g = 1 m 2 . They are eigenfunctions of higher order difference operators but only for a careful choice of the polynomials ( S h ) h = 1 m 1 and ( T g ) g = 1 m 2 , the sequence ( q n ) n ≥ 0 is orthogonal with respect to a measure. In this paper, we prove that the Meixner type polynomials ( q n ) n ≥ 0 always satisfy higher order recurrence relations (hence, they are bispectral). We also introduce and characterize the algebra of difference operators associated to these recurrence relations. Our characterization is constructive and surprisingly simple. As a consequence, we determine the unique choice of the polynomials ( S h ) h = 1 m 1 and ( T g ) g = 1 m 2 such that the sequence ( q n ) n ≥ 0 is orthogonal with respect to a measure.

In this paper, we find strong uniqueness constants for a certain class of operators with a unit norm from a space of dimension 2 n onto its subspace of codimension n , which is formed by using hyperplanes in l ∞ 2 n ( n ≥ 2 ) .

In this paper we will study the harmonic analysis of a class of Cantor–Moran measures μ with three-element digit sets on R . Our results give some sufficient conditions for the maximal orthonormal set of exponential functions to be or not to be a basis for the space L 2 ( μ ) .

In this paper, we study the sequence of orthogonal polynomials { S n } n = 0 ∞ with respect to the Sobolev-type inner product 〈 f , g 〉 = ∫ − 1 1 f ( x ) g ( x ) d μ ( x ) + ∑ j = 1 N η j f ( d j ) ( c j ) g ( d j ) ( c j ) where μ is a finite positive Borel measure whose support supp μ ⊂ [ − 1 , 1 ] contains an infinite set of points, η j > 0 , N , d j ∈ Z + and { c 1 , … , c N } ⊂ R ∖ [ − 1 , 1 ] . Under some restriction of order in the discrete part of 〈 ⋅ , ⋅ 〉 , we prove that for sufficiently large n the zeros of S n are real, simple, n − N of them lie on ( − 1 , 1 ) and each of the mass points c j “attracts” one of the remaining N zeros. The sequences of associated polynomials { S n [ k ] } n = 0 ∞ are defined for each k ∈ Z + . If μ is in the Nevai class M ( 0 , 1 ) , we prove an analogue of Markov’s Theorem on rational approximation to Markov type functions and prove that convergence takes place with geometric speed.

In polynomial regression modeling, the use of a second order orthogonal Latin hypercube design guarantees that the estimates of the first order effects are uncorrelated to each other as well as to the estimates of the second order effects. In this paper, we prove that such designs with n runs and k>2 columns do not exist if n4mod8. Furthermore, we prove that second order Latin hypercube designs with k4 columns that guarantee the orthogonality of two-factor interactions which do not share a common factor, do not exist for even n that is not a multiple of 16. Finally, we investigate the class of symmetric orthogonal Latin hypercube designs (SOLHD), which are a special subset of second order orthogonal Latin hypercube designs. We describe construction techniques for SOLHDs with n runs and (a) k4 columns, when n0mod8 or n1mod8, (b) k8 columns when n0mod16 or n1mod16 and (c) k=4 columns when n0mod16 or n1mod16, that guarantee the orthogonality of two-factor interactions which do not share a common factor. Finally, we construct and enumerate all non-isomorphic SOLHDs with n17 runs and k2 columns, as well as with 19n20 runs and k=2 columns.

In this paper, we study average sampling numbers of the multivariate periodic function space L ź 2 with a Gaussian measure µ in the L q metric for 1 ź q ź ∞ , and obtain their asymptotical orders, where the Cameron-Martin space of the measure µ is an anisotropic periodic Sobolev space. Moreover, we show that in the average case setting, the Lagrange interpolating operators are asymptotically optimal linear algorithms in the L q metric for all 1 ź q ź ∞ . This is different from the situation in the worst case setting, where the Lagrange interpolating operators are not asymptotically optimal linear algorithms in the L q metric for q = 1 or ∞ .

We give an algorithm for the symbolic solution of polynomial systems in Z X , Y . Following previous work with Lebreton, we use a combination of lifting and modular composition techniques, relying in particular on Kedlaya and Umans' recent quasi-linear time modular composition algorithm.The main contribution in this paper is an adaptation of a deflation algorithm of Lecerf, that allows us to treat singular solutions for essentially the same cost as the regular ones. Altogether, for an input system with degree d and coefficients of bit-size h , we obtain Monte Carlo algorithms that achieve probability of success at least 1 - 1 / 2 P , with running time d 2 + e O ? ( d 2 + d h + d P + P 2 ) bit operations, for any e 0 , where the O ? notation indicates that we omit polylogarithmic factors.

In this paper we prove that if a multivariate function of a certain smoothness class is represented by a sum of k arbitrarily behaved ridge functions, then it can be represented by a sum of k ridge functions of the same smoothness class and a polynomial of degree at most k − 1 . This solves the problem posed by A. Pinkus in his monograph “Ridge Functions” up to a multivariate polynomial.

Let B R ? ( h ? 2 ; f ) , ( R 0 ) denote the Bochner-Riesz means of order ? - 1 for the Dunkl transform of f ? L 1 ( R d ; h ? 2 d x ) associated with the weight function h ? 2 ( x ) : = ? j = 1 d | x j | 2 ? j on R d , where ? : = ( ? 1 , ? , ? d ) ? 0 , ∞ ) d . This paper shows that if ? ? 0 , then the Bochner-Riesz mean B R ? ( h ? 2 ; f ) ( x ) of each function f ? L 1 ( R d ; h ? 2 d x ) converges almost everywhere to f ( x ) on R d at the critical index ? = λ ? : = d - 1 2 + ? j = 1 d ? j as R ? ∞ . As is well-known in classical analysis, this result is no longer true in the unweighted case where ? = 0 , h ? ( x ) ? 1 , and B R ? ( h ? 2 ; f ) is the Bochner-Riesz mean of the Fourier transform.

We study the local discrepancy of a symmetrized version of the well-known van der Corput sequence and of modified two-dimensional Hammersley point sets in arbitrary base b . We give upper bounds on the norm of the local discrepancy in Besov spaces of dominating mixed smoothness S p , q r B ( 0 , 1 ) s ) , which will also give us bounds on the L p -discrepancy. Our sequence and point sets will achieve the known optimal order for the L p - and S p , q r B -discrepancy. The results in this paper generalize several previous results on L p - and S p , q r B -discrepancy estimates and provide a sharp upper bound on the S p , q r B -discrepancy of one-dimensional sequences for r 0 . We will use the b -adic Haar function system in the proofs.