Barycentric formulae for some optimal rational approximants involving blaschke products

We want to approximate the valueLf of some bounded linear functionalL (e.g., an integral or a function evaluation) forf∈H ² by a linear combination Σ _j=0 ^j=0 a _j f _j , wheref _j:=f(z _j) for some pointsz _j in the unit disk and the numbersa _j are to be chosen independent off _j. Using ideas of Sard, Larkin has shown that, for the errorLf?Σ _j=0 ^j=0 a _j f _j to be minimal,a _j must be chosen such that Σ _j=0 ^j=0 a _j f _j =Lf ^⊥ for the rational function \(f^ \bot (z) = \sum\nolimits_{j = 0}^n {\{ \prod\nolimits_{k = 0}^n {(1 - \bar z_k z_j )/\prod\nolimits_{k = 0}^n {(1 - \bar z_k z)} } \} l_j } (z)f_j \) , in whichl _j (z) are the Lagrange polynomials. Evaluatingf ^⊥ as given above requriesO(n ²) operations for everyz. We give here formulae, patterned after the barycentric formulae for polynomial, trigonometric and rational interpolation, which permit the evaluation off ^⊥ inO(n) operations for everyz, once some weights (that are independent ofz) have been computed. Moreover, we show that certain rational approximants introduced by F. Stenger (Math. Comp., 1986) can be interpreted as special cases of Larkin's interpolants, and are therefore optimal in the sense of Sard for the corresponding points.     

Lower estimation of approximation rate for neural networks

Let SFd and Πψ,n,d = { nj=1bjψ(ωj·x+θj) :bj,θj∈R,ωj∈Rd} be the set of periodic and Lebesgue’s square-integrable functions and the set of feedforward neural network (FNN) functions, respectively. Denote by dist (SF d, Πψ,n,d) the deviation of the set SF d from the set Πψ,n,d. A main purpose of this paper is to estimate the deviation. In particular, based on the Fourier transforms and the theory of approximation, a lower estimation for dist (SFd, Πψ,n,d) is proved. That is, dist(SF d, Πψ,n,d) (nlogC2n)1/2 . T...     

L’integrazione numerica di una classe di integrali utili nei calcoli quantomeccanici

The numerical integration of integrals of the type dx is carried out through an approximate quadrature formula of the Gauss type where the abscissasx _i and the weighting coefficientsA _i are evaluated with the requirement that the above formula be exact when thef(x) are polynomials of the highest possible degree.      

Combining the Perceptron Algorithm with Logarithmic Simulated Annealing

We present results of computational experiments with an extension of the Perceptron algorithm by a special type of simulated annealing. The simulated annealing procedure employs a logarithmic cooling schedule , where is a parameter that depends on the underlying configuration space. For sample sets S of n-dimensional vectors generated by randomly chosen polynomials , we try to approximate the positive and negative examples by linear threshold functions. The approximations are computed by both the classical Perceptron algorithm and our extension with logarithmic cooling schedules. For and , the extension outperforms the classical Perceptron algorithm by about 15% when the sample size is sufficiently large. The parameter was chosen according to estimations of the maximum escape depth from local minima of the associated energy landscape.      

Computation of Battle–Lemarie Wavelets Using an FFT-Based Algorithm

Battle and Lemarie derived independently wavelets by orthonormalizing B-splines. The scaling function _m (t) corresponding to Battle–Lemarie's wavelet _m (t) is given by , where B _m(t) is the mth-order central B-spline and the coefficients _{m, k} satisfy . In this paper, we propose an FFT-based algorithm for computing the expansion coefficients _{m, k} and the two-scale relations of the scaling functions and wavelets. The algorithm is very simple and it can be easily implemented. Moreover, the expansion coefficients can be efficiently and accurately obtained via multiple sets of FFT computations. The computational approach presented in this paper here is noniterative and is more efficient than the matrix approach recently proposed in the literature.     

Lower Bounds for Agnostic Learning via Approximate Rank

We prove that the concept class of disjunctions cannot be pointwise approximated by linear combinations of any small set of arbitrary real-valued functions. That is, suppose that there exist functions f₁, ?, f_r\phi_{1}, \ldots , \phi_{r} : {− 1, 1}ⁿ → \mathbbR{\mathbb{R}} with the property that every disjunction f on n variables has $\|f - \sum\nolimits_{i=1}^{r} \alpha_{i}\phi _{i}\|_{\infty}\leq 1/3$\|f - \sum\nolimits_{i=1}^{r} \alpha_{i}\phi _{i}\|_{\infty}\leq 1/3 for some reals a₁, ?, a_r\alpha_{1}, \ldots , \alpha_{r}. We prove that then $r \geq exp \{\Omega(\sqrt{n})\}$r \geq exp \{\Omega(\sqrt{n})\}, which is tight. We prove an incomparable lower bound for the concept class of decision lists. For the concept class of majority functions, we obtain a lower bound of W(2ⁿ/n)\Omega(2^{n}/n) , which almost meets the trivial upper bound of 2ⁿ for any concept class. These lower bounds substantially strengthen and generalize the polynomial approximation lower bounds of Paturi (1992) and show that the regression-based agnostic learning algorithm of Kalai et al. (2005) is optimal.     

An approximation algorithm for minimum-cost vertex-connectivity problems

We present an approximation algorithm for solving graph problems in which a low-cost set of edges must be selected that has certain vertex-connectivity properties. In the survivable network design problem, a valuer _ij for each pair of verticesi andj is given, and a minimum-cost set of edges such that there arer _ij vertex-disjoint paths between verticesi andj must be found. In the case for whichr _ij ∈{0, 1, 2} for alli, j, we can find a solution of cost no more than three times the optimal cost in polynomial time. In the case in whichr _ij =k for alli, j, we can find a solution of cost no more than 2H(k) times optimal, where . No approximation algorithms were previously known for these problems. Our algorithms rely on a primal-dual approach which has recently led to approximation algorithms for many edge-connectivity problems. This research was supported by NSF Grant CCR-91-03937 and a DIMACS postdoctoral fellowship, and was conducted in part while the author was visiting MIT. This research was supported by an NSF Graduate Fellowship and an NSF Postdoctoral Fellowship, and was conducted in part while the author was a graduate student at MIT and in part while a postdoc at Cornell.     

A 2.5n lower bound on the monotone network complexity of T 3 n

Summary The k-th threshold function, T _k ⁿ , is defined as: where x _i{0,1} and the summation is arithmetic. We prove that any monotone network computing T _3/n(x ₁,...,x _n) contains at least 2.5n-5.5 gates.This research was supported by the Science and Engineering Research Council of Great Britain, UK     

Expansion of Self-Similar Functions in the Faber–Schauder System

Let Ω = A^N be a space of right-sided infinite sequences drawn from a finite alphabet A = {0,1}, N = {1,2,…}. Let ρ(x, y)Σ_k=1^∞|x _k ? y _k |2^?k be a metric on Ω = AN, and μ the Bernoulli measure on Ω with probabilities p₀, p₁ > 0, p₀ + p₁ = 1. Denote by B(x,ω) an open ball of radius r centered at ω. The main result of this paper \(\mu (B(\omega ,r))r + \sum\nolimits_{n = 0}^\infty {\sum\nolimits_{j = 0}^{{2^n} - 1} {{\mu _{n,j}}} } (\omega )\tau ({2^n}r - j)\), where τ(x) = 2min {x,1 ? x}, 0 ≤ x ≤ 1, (τ(x) = 0, if x < 0 or x > 1 ), \({\mu _{n,j}}(\omega ) = (1 - {p_{{\omega _{n + 1}}}})\prod _{k = 1}^n{p_{{\omega _k}}} \oplus {j_k}\), \(j = {j_1}{2^{n - 1}} + {j_2}{2^{n - 2}} + ... + {j_n}\). The family of functions 1, x, τ(2 ⁿ r ? j), j = 0,1,…, 2 ⁿ ? 1, n = 0,1,…, is the Faber–Schauder system for the space C([0,1]) of continuous functions on [0, 1]. We also obtain the Faber–Schauder expansion for Lebesgue’s singular function, Cezaro curves, and Koch–Peano curves. Article is published in the author’s wording.     

Interpolation of Shifted-Lacunary Polynomials

Given a “black box” function to evaluate an unknown rational polynomial f ? \mathbbQ[x]f \in {\mathbb{Q}}[x] at points modulo a prime p, we exhibit algorithms to compute the representation of the polynomial in the sparsest shifted power basis. That is, we determine the sparsity $t \in {\mathbb{Z}}_{>0}$t \in {\mathbb{Z}}_{>0}, the shift a ? \mathbbQ\alpha \in {\mathbb{Q}}, the exponents 0 ￡ e₁ < e₂ < ? < e_t{0 \leq e_{1} < e_{2} < \cdots < e_{t}}, and the coefficients c₁, ?, c_t ? \mathbbQ \{0}c_{1}, \ldots , c_{t} \in {\mathbb{Q}} \setminus \{0\} such that

Almost Periodic Solution for Shunting Inhibitory Cellular Neural Networks with Time-varying Delays and Variable Coefficients

In this paper, a class of two-dimensional shunting inhibitory cellular neural networks with time-varying delays and variable coefficients as following system

Quadrature rules for Prandtl's integral equation

In this paper we construct an interpolatory quadrature formula of the type $$\mathop {\rlap{--} \smallint }\limits_{ - 1}^1 \frac{{f'(x)}}{{y - x}}dx \approx \sum\limits_{i = 1}^n {w_{ni} (y)f(x_{ni} )} ,$$ wheref(x)=(1?x)^α(1+x)^β f _o(x), α, β>0, and {x _ni} are then zeros of then-th degree Chebyshev polynomial of the first kind,T _n (x). We also give a convergence result and examine the behavior of the quantity \( \sum\limits_{i = 1}^n {|w_{ni} (y)|} \) asn→∞.     

Construction and enumeration of Boolean functions with maximum algebraic immunity

Algebraic immunity is a new cryptographic criterion proposed against algebraic attacks. In order to resist algebraic attacks, Boolean functions used in many stream ciphers should possess high algebraic immunity. This paper presents two main results to find balanced Boolean functions with maximum algebraic immunity. Through swapping the values of two bits, and then generalizing the result to swap some pairs of bits of the symmetric Boolean function constructed by Dalai, a new class of Boolean functions with maximum algebraic immunity are constructed. Enumeration of such functions is also given. For a given function p(x) with deg(p(x)) < , we give a method to construct functions in the form p(x)+q(x) which achieve the maximum algebraic immunity, where every term with nonzero coefficient in the ANF of q(x) has degree no less than . Supported by the National Natural Science Foundation of China (Grant No. 60673068), and the Natural Science Foundation of Shandong Province (Grant Nos. Y2007G16, Y2008G01)     

Computational Divided Differencing and Divided-Difference Arithmetics

Tools for computational differentiation transform a program that computes a numerical function F(x) into a related program that computes F(x) (the derivative of F). This paper describes how techniques similar to those used in computational-differentiation tools can be used to implement other program transformations—in particular, a variety of transformations for computational divided differencing. The specific technical contributions of the paper are as follows:– It presents a program transformation that, given a numerical function F(x) defined by a program, creates a program that computes F[x ₀, x ₁], the first divided difference of F(x), where – It shows how computational first divided differencing generalizes computational differentiation.– It presents a second program transformation that permits the creation of higher-order divided differences of a numerical function defined by a program.– It shows how to extend these techniques to handle functions of several variables.The paper also discusses how computational divided-differencing techniques could lead to faster and/or more robust programs in scientific and graphics applications.Finally, the paper describes how computational divided differencing relates to the numerical-finite-differencing techniques that motivated Robert Paige's work on finite differencing of set-valued expressions in SETL programs.     

Large deviations for distributions of sums of random variables: Markov chain method

Let {ξ _k } _k=0^∞ be a sequence of i.i.d. real-valued random variables, and let g(x) be a continuous positive function. Under rather general conditions, we prove results on sharp asymptotics of the probabilities $ P\left\{ {\frac{1} {n}\sum\limits_{k = 0}^{n - 1} {g\left( {\xi _k } \right) < d} } \right\} $ P\left\{ {\frac{1} {n}\sum\limits_{k = 0}^{n - 1} {g\left( {\xi _k } \right) < d} } \right\} , n → ∞, and also of their conditional versions. The results are obtained using a new method developed in the paper, namely, the Laplace method for sojourn times of discrete-time Markov chains. We consider two examples: standard Gaussian random variables with g(x) = |x| ^p , p > 0, and exponential random variables with g(x) = x for x ≥ 0.     

Asymptotic Fourier Coefficients for a C∞ Bell (Smoothed-“Top-Hat”) & the Fourier Extension Problem

In constructing local Fourier bases and in solving differential equations with nonperiodic solutions through Fourier spectral algorithms, it is necessary to solve the Fourier Extension Problem. This is the task of extending a nonperiodic function, defined on an interval , to a function which is periodic on the larger interval . We derive the asymptotic Fourier coefficients for an infinitely differentiable function which is one on an interval , identically zero for , and varies smoothly in between. Such smoothed “top-hat” functions are “bells” in wavelet theory. Our bell is (for x ≥ 0) where where . By applying steepest descents to approximate the coefficient integrals in the limit of large degree j, we show that when the width L is fixed, the Fourier cosine coefficients a _j of on are proportional to where Λ(j) is an oscillatory factor of degree given in the text. We also show that to minimize error in a Fourier series truncated after the Nth term, the width should be chosen to increase with N as . We derive similar asymptotics for the function f(x)=x as extended by a more sophisticated scheme with overlapping bells; this gives an even faster rate of Fourier convergence     

A Representation of the Interval Hull of a Tolerance Polyhedron Describing Inclusions of Function Values and Slopes

Given a nonempty set of functions

Estimating temperature fluctuations in the early universe

A lagrangian for a k-essence field is constructed for a constant scalar potential, and its form is determined when the scale factor is very small as compared to the present epoch but very large as compared to the inflationary epoch. This means that one is already in an expanding and flat universe. The form is similar to that of an oscillator with time-dependent frequency. Expansion is naturally built into the theory with the existence of growing classical solutions of the scale factor. The formalism allows one to estimate the temperature fluctuations of the background radiation at these early stages (as compared to the present epoch) of the Universe. If the temperature is T _a at time t _a and T _b at time t _b (t _b > t _a ), then, for small times, the probability evolution for the logarithm of the inverse temperature can be estimated as

Valutazione dell'errore per una formula di quadratura alla Tchebycheff di tipo chiuso

In this paper we study the remainder term of a quadrature formula of the form $$\int\limits_{ - 1}^1 {f(x)dx = A_n \left[ {f( - 1) + f(1)} \right] + C_n \sum\limits_{i = 1}^n {f(x_{n,i} ) + R_n \left[ f \right],} } $$ , withx _x,i ∈^-1,1, andR _n [f]=0 whenf(x) is a polynomial of degree ≤n+3 ifn is even, or ≤n+2 ifn is odd. Such a formula exists only forn=1(1)11. It is shown that, iff(x)∈ ^C(h+1) [-1,1], (h=n+3 orn+2), thenR _n [f]=f ^h+1 (τ)·± _n . The values α _n are given.