Fisher information of orthogonal polynomials I

Following the lead of J. Dehesa and his collaborators, we compute the Fisher information of the Meixner-Pollaczek, Meixner, Krawtchouk and Charlier polynomials.     

Spreading lengths of Hermite polynomials

The Renyi, Shannon and Fisher spreading lengths of the classical or hypergeometric orthogonal polynomials, which are quantifiers of their distribution all over the orthogonality interval, are defined and investigated. These information-theoretic measures of the associated Rakhmanov probability density, which are direct measures of the polynomial spreading in the sense of having the same units as the variable, share interesting properties: invariance under translations and reflections, linear scaling and vanishing in the limit that the variable tends towards a given definite value. The expressions of the Renyi and Fisher lengths for the Hermite polynomials are computed in terms of the polynomial degree. The combinatorial multivariable Bell polynomials, which are shown to characterize the finite power of an arbitrary polynomial, play a relevant role for the computation of these information-theoretic lengths. Indeed these polynomials allow us to design an error-free computing approach for the entropic moments (weighted L^q-norms) of Hermite polynomials and subsequently for the Renyi and Tsallis entropies, as well as for the Renyi spreading lengths. Sharp bounds for the Shannon length of these polynomials are also given by means of an information-theoretic-based optimization procedure. Moreover, the existence of a linear correlation between the Shannon length (as well as the second-order Renyi length) and the standard deviation is computationally proved. Finally, the application to the most popular quantum-mechanical prototype system, the harmonic oscillator, is discussed and some relevant asymptotical open issues related to the entropic moments, mentioned previously, are posed.     

Perfect couples of graphs

We generalize the concept of perfect graphs in terms of additivity of a functional called graph entropy. The latter is an information theoretic functional on a graphG with a probability distributionP on its vertex set. For any fixedP it is sub-additive with respect to graph union. The entropy of the complete graph equals the sum of those ofG and its complement G iffG is perfect. We generalize this recent result to characterize all the cases when the sub-additivity of graph entropy holds with equality.The research of the authors is partially supported by the Hungarian National Foundation for Scientific Research (OTKA), grant No. 1806 resp. No. 1812.     

Symbolic Computation for Moments and Filter Coefficients of Scaling Functions

Algebraic relations between discrete and continuous moments of scaling functions are investigated based on the construction of Bell polynomials. We introduce families of scaling functions which are parametrized by moments. Filter coefficients of scaling functions and wavelets are computed with computer algebra methods (in particular Gröbner bases) using relations between moments. Moreover, we propose a novel concept for data compression based on parametrized wavelets.Received December 15, 2003     

A q-linear analogue of the plane wave expansion

We obtain a q-linear analogue of Gegenbauer?s expansion of the plane wave. It is expanded in terms of the little q-Gegenbauer polynomials and the third Jackson q-Bessel function. The result is obtained by using a method based on bilinear biorthogonal expansions.     

Gabor frames, unimodularity, and window decay

We study time-continuous Gabor frame generating window functions g satisfying decay properties in time and/or frequency with particular emphasis on rational time-frequency lattices. Specifically, we show under what conditions these decay properties of g are inherited by its minimal dual γ⁰ and by generalized duals γ. We consider compactly supported, exponentially decaying, and faster than exponentially decaying (i.e., decay like |g(t)|≤Ce^{−α|t| 1/α} for some 1/2≤α<1) window functions. Particularly, we find that g and γ⁰ have better than exponential decay in both domains if and only if the associated Zibulski-Zeevi matrix is unimodular, i.e., its determinant is a constant. In the case of integer oversampling, unimodularity of the Zibulski-Zeevi matrix is equivalent to tightness of the underlying Gabor frame. For arbitrary oversampling, we furthermore consider tight Gabor frames canonically associated to window functions g satisfying certain decay properties. Here, we show under what conditions and to what extent the canonically associated tight frame inherits decay properties of g. Our proofs rely on the Zak transform, on the Zibulski-Zeevi representation of the Gabor frame operator, on a result by Jaffard, on a functional calculus for Gabor frame operators, on results from the theory of entire functions, and on the theory of polynomial matrices.     

On spherical expansions of zonal functions on Euclidean spheres

This paper describes a new approach to the problem of computing spherical expansions of zonal functions on Euclidean spheres. We derive an explicit formula for the coefficients of the expansion expressing them in terms of the Taylor coefficients of the profile function rather than (as done usually) in terms of its integrals against Gegenbauer polynomials. Our proof of this result is based on a polynomial identity equivalent to the canonical decomposition of homogeneous polynomials and uses only basic properties of this decomposition together with simple facts concerning zonal harmonic polynomials. As corollaries, we obtain direct and apparently new derivations of the so-called plane wave expansion and of the expansion of the Poisson kernel for the unit ball. Received: 26 January 2007     

Noncommutative biorthogonal polynomials

We define and study biorthogonal sequences of polynomials over noncommutative rings, generalizing previous treatments of biorthogonal polynomials over commutative rings and of orthogonal polynomials over noncommutative rings. We extend known recurrence relations for specific cases of biorthogonal polynomials and prove a general version of Favard?s theorem.     

A one-round,two-prover,zero-knowledge protocol for NP

The model of zero-knowledge multi-prover interactive proofs was introduced by Ben-Or, Goldwasser, Kilian and Wigderson in [4]. A major open problem associated with this model is whether NP problems can be proven by one-round, two-prover, zero-knowledge protocols with exponentially small error probability (e.g. via parallel executions). A positive answer was claimed by Fortnow, Rompel and Sipser in [12], but its proof was later shown to be flawed by Fortnow who demonstrated that the probability of cheating inn independent parallel rounds can be much higher than the probability of cheating inn independent sequential rounds (with exponential ratio between them). In this paper we solve this problem: We show a new one-round two-prover interactive proof for Graph Hamiltonicity, we prove that it is complete, sound and perfect zeroknowledge, and thus every problem in NP has a one-round two-prover interactive proof which is perfectly zero knowledge under no cryptographic assumptions. The main difficulty is in proving the soundness of our parallel protocol namely, proving that the probability of cheating in this one-round protocol is upper bounded by some exponentially low threshold. We prove that this probability is at most 1/2 ^n/9 (wheren is the number of parallel rounds), by translating the soundness problem into some extremal combinatorial problem, and then solving this new problem.     

Majorization and multiplier sequences

We present applications of matrix methods to the analytic theory of polynomials. We first show how matrix analysis can be used to give new proofs of a number of classical results on roots of polynomials. Then we use matrix methods to establish a new log-majorization result on roots of polynomials. The theory of multiplier sequences gives the common link between the applications.     

On entropy-preserving stochastic averages

When an n×n doubly stochastic matrix A acts on Rⁿ on the left as a linear transformation and P is an n-long probability vector, we refer to the new probability vector AP as the stochastic average of the pair (A,P). Let Γ_n denote the set of pairs (A,P) whose stochastic average preserves the entropy of P:H(AP)=H(P). Γ_n is a subset of B_n×Σ_n where B_n is the Birkhoff polytope and Σ_n is the probability simplex.We characterize Γ_n and determine its geometry, topology,and combinatorial structure. For example, we find that (A,P)∈Γ_n if and only if A^tAP=P. We show that for any n, Γ_n is a connected set, and is in fact piecewise-linearly contractible in B_n×Σ_n. We write Γ_n as a finite union of product subspaces, in two distinct ways. We derive the geometry of the fibers (A,·) and (·,P) of Γ_n. Γ₃ is worked out in detail. Our analysis exploits the convexity of xlogx and the structure of an efficiently computable bipartite graph that we associate to each ds-matrix. This graph also lets us represent such a matrix in a permutation-equivalent, block diagonal form where each block is doubly stochastic and fully indecomposable.     

The spectral radii of a graph and its line graph

The spectral radius of a (directed) graph is the largest eigenvalue of adjacency matrix of the (directed) graph. We give the relation on the characteristic polynomials of a directed graph and its line graph, and obtain sharp bounds on the spectral radius of directed graphs. We also give the relation on the spectral radii of a graph and its line graph. As a consequence, the spectral radius of a connected graph does not exceed that of its line graph except that the graph is a path.     

A new type of Hermite matrix polynomial series

Conventional Hermite polynomials emerge in a great diversity of applications in mathematical physics, engineering, and related fields. However, in physical systems with higher degrees of freedom it will be of practical interest to extend the scalar Hermite functions to their matrix analogue. This work introduces various new generating functions for Hermite matrix polynomials and examines existence and convergence of their associated series expansion by using Mehler’s formula for the general matrix case. Moreover, we derive interesting new relations for even- and odd-power summation in the generating-function expansion containing Hermite matrix polynomials. Some new results for the scalar case are also presented.     

Eulerian polynomials and B-splines

An interrelationship between Eulerian polynomials, Eulerian fractions and Euler–Frobe nius polynomials, Euler–Frobenius fractions, and B-splines is presented. The properties of Eulerian polynomials and Eulerian fractions and their applications in B-spline interpolation and evaluation of Riemann zeta function values at odd integers are given. The relation between Eulerian numbers and B-spline values at knot points are also discussed.     

Reconstruction of bandlimited signal from its non-uniform integral samples

In this article, we discuss the problem of reconstructing a bandlimited signal f from the samples of the integral of the signal. We first apply the trigonometric polynomials to approximate the integral of the signal and then reconstruct instantaneous samples from the signal integral.     

Gibbs' phenomenon for sampling series and what to do about it

Gibbs' phenomenon occurs for most orthogonal wavelet expansions. It is also shown to occur with many wavelet interpolating series, and a characterization is given. By introducing modifications in such a series, it can be avoided. However, some series that exhibit Gibbs' phenomenon for orthogonal series do not for the associated sampling series.     

Codes And Xor Graph Products

What is the maximum possible number, f₃(n), of vectors of length n over {0,1,2} such that the Hamming distance between every two is even? What is the maximum possible number, g³(n), of vectors in {0,1,2}ⁿ such that the Hamming distance between every two is odd? We investigate these questions, and more general ones, by studying Xor powers of graphs, focusing on their independence number and clique number, and by introducing two new parameters of a graph G. Both parameters denote limits of series of either clique numbers or independence numbers of the Xor powers of G (normalized appropriately), and while both limits exist, one of the series grows exponentially as the power tends to infinity, while the other grows linearly. As a special case, it follows that f₃(n) = Θ(2ⁿ) whereas g₃(n)=Θ(n). * Research supported in part by a USA-Israeli BSF grant, by the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. † Research partially supported by a Charles Clore Foundation Fellowship.     

Sequences of orthogonal Laurent polynomials,bi-orthogonality and quadrature formulas on the unit circle

In this paper, the construction of orthogonal bases in the space of Laurent polynomials on the unit circle is considered. As an application, a connection with the so-called bi-orthogonal systems of trigonometric polynomials is established and quadrature formulas on the unit circle based on Laurent polynomials are studied.