Bias of a nonparametric entropy estimator for Markov measures

We consider the problem of nonparametric entropy (entropy rate) estimation. We study the technique of nonparametric entropy estimation based on the so-called “nearest neighbor distances” and obtain a closed-form expression of the bias for Markov measures. This bias is a discontinuous function of transition probabilities. Bibliography: 20 titles.     

On the failure of maximum entropy reconstruction for Fredholm equations and other infinite systems

We analyse several examples where the maximum entropy solution to a system of equations exists but fails to satisfy the natural (dual) formula. These examples highlight the role that finiteness of the number of constraints has in the efficacy of maximum entropy type estimation and reconstruction. We also provide two regularization processes which repair the problem.Research partially supported by NSERC grant OGP005116.     

熵损失函数下的信度模型

本文研究了信度模型问题.利用熵损失函数,获得了风险保费的信度估计和经验Bayes信度估计.所获结果是对现有风险保费信度估计和经验Bayes信度估计的一个补充.     

Minimum distance estimates

In the paper, we consider the estimation problem for an unknown density on independent observations. We use the minimum distance estimation method. It is shown that the accuracy of estimation is connected with the rate of increase of the entropy of the parametrical set. Bibliography: 9 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 339, 2006, pp. 151–162.     

Calculating Maximum Entropy Flows in Networks

This paper describes methods for calculating the most likely values of link flows in networks with incomplete data. The object is to present a thorough and rigorous treatment of maximum entropy flow estimation methods and to develop a methodological framework capable of handling different types of network problems. A multiple probability space conditional entropy approach is described for the general network problem. Results are presented and discussed for an example network intended for water supply.     

An efficient algorithm for maximum entropy extension of block-circulant covariance matrices

This paper deals with maximum entropy completion of partially specified block-circulant matrices. Since positive definite symmetric circulants happen to be covariance matrices of stationary periodic processes, in particular of stationary reciprocal processes, this problem has applications in signal processing, in particular to image modeling. In fact it is strictly related to maximum likelihood estimation of bilateral AR-type representations of acausal signals subject to certain conditional independence constraints. The maximum entropy completion problem for block-circulant matrices has recently been solved by the authors, although leaving open the problem of an efficient computation of the solution. In this paper, we provide an efficient algorithm for computing its solution which compares very favorably with existing algorithms designed for positive definite matrix extension problems. The proposed algorithm benefits from the analysis of the relationship between our problem and the band-extension problem for block-Toeplitz matrices also developed in this paper.     

Estimating the Firm Value Distribution Function by Entropy Optimization and Geometric Programming

By applying the option pricing theory ideas, this paper models the estimation of firm value distribution function as an entropy optimization problem, subject to correlation constraints. It is shown that the problem can be converted to a dual of a computationally attractive primal geometric programming (GP) problem and easily solved using publicly available software. A numerical example involving stock price data from a Japanese company demonstrates the practical value of the GP approach. Noting the use of Monte Carlo simulation in option pricing and risk analysis and its difficulties in handling distribution functions subject to correlations, the GP based method discussed here may have some computational advantages in wider areas of computational finance in addition to the application discussed here.     

How Many Needles are in a Haystack, or How to Solve #P-Complete Counting Problems Fast

We present two randomized entropy-based algorithms for approximating quite general #P-complete counting problems, like the number of Hamiltonian cycles in a graph, the permanent, the number of self-avoiding walks and the satisfiability problem. In our algorithms we first cast the underlying counting problem into an associate rare-event probability estimation, and then apply dynamic importance sampling (IS) to estimate efficiently the desired counting quantity. We construct the IS distribution by using two different approaches: one based on the cross-entropy (CE) method and the other one on the stochastic version of the well known minimum entropy (MinxEnt) method. We also establish convergence of our algorithms and confidence intervals for some special settings and present supportive numerical results, which strongly suggest that both ones (CE and MinxEnt) have polynomial running time in the size of the problem.     

Facial reduction in partially finite convex programming

We consider the problem of minimizing an extended-valued convex function on a locally convex space subject to a finite number of linear (in)equalities. When the standard constraint qualification fails a reduction technique is needed to derive necessary optimality conditions. Facial reduction is usually applied in the range of the constraints. In this paper it is applied in the domain space, thus maintaining any structure (and in particular lattice properties) of the underlying domain. Applications include constrained approximation and best entropy estimation.Research partially supported by the Natural Sciences and Engineering Research Council of Canada.     

熵损失函数下几何分布可靠度的Bayes估计

本文在几何分布的先验分布为幂分布时研究了其在熵损失函数下,可靠度的多层Bayes估计及其容许性,给出了可靠度的多层Bayes估计的计算公式.通过实例验证,在熵损失函数下计算出的几何分布可靠度的多层Bayes估计是稳健的,并进一步表明在熵损失函数下计算出的几何分布可靠度的多层Bayes估计值比其在平方损失函数下算出的结果精度更高.     

A two-dimensional glimm type scheme on cauchy problem of two-dimensional scalar conservation law

In this paper,we construct a new two-dimensional convergent scheme to solve Cauchy problem of following two-dimensional scalar conservation law{?_tu +?_xf(u) + ?_yg(u) = 0,u(x,y,0) = u_0(x,y).In which initial data can be unbounded.Although the existence and uniqueness of the weak entropy solution are obtained,little is known about how to investigate two-dimensional or higher dimensional conservation law by the schemes based on wave interaction of 2D Riemann solutions and their estimation.So we construct such scheme in our paper and get some new results.     

Estimation of the entropy of a multivariate normal distribution

Motivated by problems in molecular biosciences wherein the evaluation of entropy of a molecular system is important for understanding its thermodynamic properties, we consider the efficient estimation of entropy of a multivariate normal distribution having unknown mean vector and covariance matrix. Based on a random sample, we discuss the problem of estimating the entropy under the quadratic loss function. The best affine equivariant estimator is obtained and, interestingly, it also turns out to be an unbiased estimator and a generalized Bayes estimator. It is established that the best affine equivariant estimator is admissible in the class of estimators that depend on the determinant of the sample covariance matrix alone. The risk improvements of the best affine equivariant estimator over the maximum likelihood estimator (an estimator commonly used in molecular sciences) are obtained numerically and are found to be substantial in higher dimensions, which is commonly the case for atomic coordinates in macromolecules such as proteins. We further establish that even the best affine equivariant estimator is inadmissible and obtain Stein-type and Brewster–Zidek-type estimators dominating it. The Brewster–Zidek-type estimator is shown to be generalized Bayes.     

Topological entropy for local processes

The aim of this article is to formalize definition of chaos (in terms of topological entropy) for dynamics of processes described by nonautonomous differential equations. We state a formal definition of topological entropy in this setting and provide tools for estimation of its value (its upper or lower bounds) in terms of Poincaré sections.     

Lectures on the theory of estimation of many parameters

This article is based on the series of lectures given by Prof. Charles Stein of Stanford University at LOMI AN SSSR in the fall of 1976. The first three lectures are concerned with the estimation of the mean vector of a multivariate normal distribution with quadratic loss function. James-Stein estimators are considered and their relation to Bayesian estimators is discussed. The problem of estimating the covariance matrix of the normal distribution and the estimation of the entropy of a multinomial distribution are considered in the following two lectures. The final lecture discusses several problems related to the estimation of multivariate parameters and poses some unsolved problems.Published in Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 74, pp. 4–65, 1977.In conclusion of this series of lectures, I would like to acknowledge the assistance of M. Ermakov, A. Borodin, and A. Makshanov in translating my lectures into Russian.     

不等式组与变分不等式的极大熵函数方法

利用极大熵函数方法将不等式组及变分不等式的求解问题转化为近似可微优化问题，给出了不等式组及变分不等式问题近似解的可微优化方法，得到了不等式组和变分不等式问题的解集合的示性函数．     

变分不等式的极大熵函数方法

利用极大熵函数方法将不等式组及变分不等式的求解问题转化为近似可微优化问题,给出了不等式组及变分不等式问题近似解的可微优化方法,得到了不等式组和变分不等式问题的解集合的示性函数.     

Classes of improved estimators for parameters of a Pareto distribution

The problem of estimating parameters of a Pareto distribution is investigated under a general scale invariant loss function when the scale parameter is restricted to the interval (0, 1]. We consider the estimation of shape parameter when the scale parameter is unknown. Techniques for improving equivariant estimators developed by Stein, Brewster–Zidek and Kubokawa are applied to derive improved estimators. In particular improved classes of estimators are obtained for the entropy loss and a symmetric loss. Risk functions of various estimators are compared numerically using simulations. It is also shown that the technique of Kubokawa produces improved estimators for estimating the scale parameter when the shape parameter is known.     

关于滑动相对熵的若干极限性质

引入滑动似然比和滑动相对熵等概念,讨论了滑动相对熵的若干渐近性质.主要结果是,获得了随机变量任意状态的相对频率与滑动相对熵之间的关系,并且给出了滑动相对熵基于相对频率的上界的估计.作为推论,得到了随机序列滑动平均的强大数定理.     

Estimations of topological entropy for non-autonomous discrete systems

This paper is concerned with estimations of topological entropy for non-autonomous discrete systems. An estimation of lower bound of topological entropy for coupled-expanding systems associated with transition matrices in compact Hausdorff spaces is given. Estimations of upper and lower bounds of topological entropy for systems in compact metric spaces are obtained by their topological equi-semiconjugacy to subshifts of finite type under certain conditions. One example is provided for illustration.     

An unbounded Sum-of-Squares hierarchy integrality gap for a polynomially solvable problem

In this expository article, we study optimization problems specified via linear and relative entropy inequalities. Such relative entropy programs (REPs) are convex optimization problems as the relative entropy function is jointly convex with respect to both its arguments. Prominent families of convex programs such as geometric programs (GPs), second-order cone programs, and entropy maximization problems are special cases of REPs, although REPs are more general than these classes of problems. We provide solutions based on REPs to a range of problems such as permanent maximization, robust optimization formulations of GPs, and hitting-time estimation in dynamical systems. We survey previous approaches to some of these problems and the limitations of those methods, and we highlight the more powerful generalizations afforded by REPs. We conclude with a discussion of quantum analogs of the relative entropy function, including a review of the similarities and distinctions with respect to the classical case. We also describe a stylized application of quantum relative entropy optimization that exploits the joint convexity of the quantum relative entropy function.