On the Maximum Values of f-Divergence and Rényi Divergence under a Given Variational Distance

Problems of Information Transmission - We consider the problem of finding maximum values of f-divergences Df(P ∥ Q) of discrete probability distributions P and Q with values on a finite set...     

Some Undecidable Problems on Approximability of NP Optimization Problems

'1IntroductionManydecisionproblemsareNPcompleteandtheirassociatedoptimizationproblemsareNPequivalent.ButtheseoptimizationproblemshaveverydifferentaPprokimabilities.Forexample,knapsackproblemhasapolynomial-timeapproki-mationscheme,whileTSPisnotconstall-aPprotimable,unlessP=NP.WhatmakesdifferenceamongNPoptimizationproblems(NPOPs)?In[3],KolaitisandThakurinvestigatedtheapprokimabilityofNPOPsbymeansofrepresentingNPOPswithfirst-orderselltences-TheyprovedthatifP/NP,thenitisanundecidable…     

Some properties of Rényi entropy over countably infinite alphabets

We study certain properties of Rényi entropy functionals $H_\alpha \left( \mathcal{P} \right)$ on the space of probability distributions over ?₊. Primarily, continuity and convergence issues are addressed. Some properties are shown to be parallel to those known in the finite alphabet case, while others illustrate a quite different behavior of the Rényi entropy in the infinite case. In particular, it is shown that for any distribution $\mathcal{P}$ and any r ∈ [0,∞] there exists a sequence of distributions $\mathcal{P}_n$ converging to $\mathcal{P}$ with respect to the total variation distance and such that $\mathop {\lim }\limits_{n \to \infty } \mathop {\lim }\limits_{\alpha \to 1 + } H_\alpha \left( {\mathcal{P}_n } \right) = \mathop {\lim }\limits_{\alpha \to 1 + } \mathop {\lim }\limits_{n \to \infty } H_\alpha \left( {\mathcal{P}_n } \right) + r$ .     

On Extreme Values of the Rényi Entropy under Coupling of Probability Distributions

Problems of Information Transmission - We consider the problem of determining extreme values of the Rényi entropy for a discrete random variable provided that the value of the α-coupling...     

Swiveled Rényi entropies

This paper introduces “swiveled Rényi entropies” as an alternative to the Rényi entropic quantities put forward in Berta et al. (Phys Rev A 91(2):022333, 2015). What distinguishes the swiveled Rényi entropies from the prior proposal of Berta et al. is that there is an extra degree of freedom: an optimization over unitary rotations with respect to particular fixed bases (swivels). A consequence of this extra degree of freedom is that the swiveled Rényi entropies are ordered, which is an important property of the Rényi family of entropies. The swiveled Rényi entropies are, however, generally discontinuous at \(\alpha =1\) and do not converge to the von Neumann entropy-based measures in the limit as \(\alpha \rightarrow 1\), instead bounding them from above and below. Particular variants reduce to known Rényi entropies, such as the Rényi relative entropy or the sandwiched Rényi relative entropy, but also lead to ordered Rényi conditional mutual information and ordered Rényi generalizations of a relative entropy difference. Refinements of entropy inequalities such as monotonicity of quantum relative entropy and strong subadditivity follow as a consequence of the aforementioned properties of the swiveled Rényi entropies. Due to the lack of convergence at \(\alpha =1\), it is unclear whether the swiveled Rényi entropies would be useful in one-shot information theory, so that the present contribution represents partial progress toward this goal.     

On the Numerical Solution of Some Semilinear Elliptic Problems – II

In the earlier paper [6], a Galerkin method was proposed and analyzed for the numerical solution of a Dirichlet problem for a semi-linear elliptic boundary value problem of the form –U=F(·,U). This was converted to a problem on a standard domain and then converted to an equivalent integral equation. Galerkins method was used to solve the integral equation, with the eigenfunctions of the Laplacian operator on the standard domain D as the basis functions. In this paper we consider the implementing of this scheme, and we illustrate it for some standard domains D.     

Rényi Extrapolation of Shannon Entropy

Relations between Shannon entropy and Rényi entropies of integer order are discussed. For any N-point discrete probability distribution for which the Rényi entropies of order two and three are known, we provide a lower and an upper bound for the Shannon entropy. The average of both bounds provide an explicit extrapolation for this quantity. These results imply relations between the von Neumann entropy of a mixed quantum state, its linear entropy and traces.     

Perfect Strategies for the Ulam-Rényi Game with Multi-interval Questions

We study a new variant of the classical 20 question game with lies (a.k.a. Ulam-Rényi game). The Ulam-Rényi game models the problem of identifying an initially unknown m-bit number by asking subset questions, where up to e of the answers might be mendacious. In the variant considered in this paper, we set an additional constraint on the type of questions, namely, that the subsets they ask for should be the union of at most k intervals for some k>0 fixed beforehand. We show that for any e and m, there exists k only depending on e such that strategies using k-interval question are as powerful (in terms of the minimum number of queries needed) as the best strategies using arbitrary membership questions.     

Efficient Parallel Algorithms for Some Graph Theory Problems

In this paper,a sequential algorithm computing the aww vertex pair distance matrix D and the path matrix Pis given.On a PRAM EREW model with p,1≤p≤n^2,processors,a parallel version of the sequential algorithm is shown.This method can also be used to get a parallel algorithm to compute transitive closure array A^* of an undirected graph.The time complexity of the parallel algorithm is O(n^3/p).If D,P and A^* are known,it is shown that the problems to find all connected components,to compute the diameter of an undirected graph,to determine the center of a directed graph and to search for a directed cycle with the minimum(maximum)length in a directed graph can all be solved in O(n^2/p logp)time.     

On the Equivalence of Some Models of Computation

In[1],a definition of computation was given.In[3],we have clarified the necessity of thedefinition.Here we prove the equivalence between the definition and some models ofcomputation.Hence the sufficiency of the definition is clear abundantly.     

On Reversible Cascades in Scale-Free and Erdős-Rényi Random Graphs

Consider the following cascading process on a simple undirected graph G(V,E) with diameter Δ. In round zero, a set S?V of vertices, called the seeds, are active. In round i+1, i∈?, a non-isolated vertex is activated if at least a ρ∈(0,1] fraction of its neighbors are active in round i; it is deactivated otherwise. For k∈?, let min-seed^(k)(G,ρ) be the minimum number of seeds needed to activate all vertices in or before round k. This paper derives upper bounds on min-seed^(k)(G,ρ). In particular, if G is connected and there exist constants C>0 and γ>2 such that the fraction of degree-k vertices in G is at most C/k ^γ for all k∈?⁺, then min-seed^(Δ)(G,ρ)=O(?ρ ^γ?1|V|?). Furthermore, for n∈?⁺, p=Ω((ln(e/ρ))/(ρn)) and with probability 1?exp(?n ^Ω(1)) over the Erd?s-Rényi random graphs G(n,p), min-seed⁽¹⁾(G(n,p),ρ)=O(ρn).     

基于特征点Rényi互信息的医学图像配准

针对医学图像配准有鲁棒性强、准确性高和速度快的要求,文中提出一种基于特征点Rényi互信息的医学图像配准算法.起初从模板图像与待配准图像中依次提取出多尺度特征点,其次使用其空间坐标计算特征点Rényi互信息目标函数,实现图像配准.该算法有效地避免了多模噪声图像间的灰度差异影响,减少了待处理的数据量,同时使用Rényi互信息来消除目标函数所受的局部极值的影响,进一步提高了配准精度.实验证明该算法适于单模和多模医学图像配准,速度较快、精度高、鲁棒性强,是一种有效的自动配准方法,并且具有较好的临床应用价值.     

基于Rényi散度最大化的多特征闭环检测

相比单特征,多图像特征的组合提供更多的场景判别信息,可以提高检测精度,但需要设计合适的组合准则.文中提出多特征组合的加权方法,把特征组合的闭环检测精度表示为正确匹配和错误匹配的图像对在特征空间中距离分布的Rényi散度,最优特征组合为最大化Rényi散度.分析验证Rényi散度的参数与对应最优特征组合的闭环检测性能之间的关系.实验表明,文中方法可以提高闭环检测精度.当Rényi散度的参数取0.75~1 时,最优特征组合性能最佳.     

Some Hard Examples for the Resolution Method

Given n propositional variables,let Kn(i,j),0≤i≤j≤n,be the set(or disjunction)of all conjunctions of i literals of which exactly j literals are negative.Dunham and Wang conjectured that it may require exponential time to decide that every disjunction Kn(i,j)is not valid by the resolution metho.This paper gives a proof of the conjecture and then exhibits a new counterexample to the feasibility of the resolution or consensus method.     

基于Rényi熵图的医学图像自动弹性配准

提出一种基于Rényi熵最小生成图和multi-quadric径向基函数的医学图像自动弹性配准方法。应用图像金字塔的思想,对图像分层分块,将Rényi熵最小生成图作为相似性测度对子块进行配准,在对应的子块中选取对应的标记点,用multi-quadric径向基函数插值这些标记点,从而实现医学图像弹性配准。实验结果表明,该方法配准速度较快,精度较高,是一种有效的自动弹性配准方法。     

Exponential Lower Bounds on the Complexity of?a?Class of?Dynamic Programs for Combinatorial Optimization Problems

We prove exponential lower bounds on the running time of Dynamic Programs (DP) of a certain class for some Combinatorial Optimization Problems. The class of DPs for which we derive the lower bounds is general enough to include well-known DPs for Combinatorial Optimization Problems, such as the ones developed for the Shortest Path Problem, the Knapsack Problem, or the Traveling Salesman Problem. The problems analyzed include the Traveling Salesman Problem (TSP), the Bipartite Matching Problem (BMP), the Min and the Max Cut Problems (MCP), the Min Partition Problem (MPP), and the Min Cost Test Collection Problem (MCTCP). We draw a connection between Dynamic Programs and algorithms for polynomial evaluation. We then derive and use complexity results of polynomial evaluation to prove similar results for Dynamic Programs for the TSP or the BMP. We define a reduction between problems that allows us to generalize these bounds to problems for which either the TSP or the BMP transforms to. Moreover, we show that some standard transformations between problems are of this kind. In this fashion, we extend the lower bounds to other Combinatorial Optimization Problems.     

面向目标跟踪的基于Rényi信息增量多的传感器管理

针对地面防空武器系统传感器的管理问题,面向机动目标跟踪,提出了一种基于Rényi信息增量的多传感器管理方案.首先利用交互式多模型容积卡尔曼滤波解决高斯非线性环境下系统状态估计问题,计算各目标和各传感器配对时的Rényi信息增量;然后建立了基于Rényi信息增量的多传感器管理模型,以系统总效能最大为原则选择传感器进行目标跟踪.关联仿真结果表明,该方法与基于Shannon信息增量的多传感器管理方法相比能够提高跟踪精度,实现传感器资源的有效利用.     

一种基于Rényi信息增量的机动目标协同跟踪方法

针对传感器网络中的动态跟踪问题,提出一种基于Rényi信息增量的机动目标协同跟踪方法.首先利用粒子滤波计算每个传感器Rényi信息增量;然后以Rényi信息增量最大为原则选择传感器进行目标跟踪,并在跟踪时通过多模型的交互作用实现对机动目标状态的准确估计.仿真结果表明,在非线性非高斯环境下,所提出的方法与传统方法相比能够有效提高跟踪精度,动态分配传感器资源,实现协同跟踪.     

On the smooth convergence of subdivision and degree elevation for Bézier curves

Bézier subdivision and degree elevation algorithms generate piecewise linear approximations of Bézier curves that converge to the original Bézier curve. Discrete derivatives of arbitrary order can be associated with these piecewise linear functions via divided differences. Here we establish the convergence of these discrete derivatives to the corresponding continuous derivatives of the initial Bézier curve. Thus, we show that the control polygons generated by subdivision and degree elevation provide not only an approximation to a Bézier curve, but also approximations of its derivatives of arbitrary order.     

On the Condition for FSM Being a Scrambler

A necessary condition for a self-synchronizing delayless invertible finite state machine(FSM)being ascrambler was conjectured in[1].A counterexample to the conjecture is given in this paper.