14960041
On Characterization of Entropy Function via Information Inequalities
Given n discrete random variables /spl Omega/={X/sub 1/, /spl middot//spl middot//spl middot/, X/sub n/}, associated with any subset /spl alpha/ of (1, 2, /spl middot//spl middot//spl middot/, n), there is a joint entropy H(X/sub /spl alpha//) where X/sub /spl alpha//={X/sub i/:i/spl epsiv//spl alpha/}. This can be viewed as a function defined on 2/sup {1, 2, /spl middot//spl middot//spl middot/, n}/ taking values in (0, +/spl infin/). We call this function the entropy function of /spl Omega/. The nonnegativity of the joint entropies implies that this function is nonnegative; the nonnegativity of the conditional joint entropies implies that this function is nondecreasing; and the nonnegativity of the conditional mutual information implies that this function has the following property: for any two subsets /spl alpha/ and /spl beta/ of {1, 2, /spl middot//spl middot//spl middot/, n} H/sub /spl Omega//(/spl alpha/)+H/sub /spl Omega//(/spl beta/)/spl ges/H/sub /spl Omega//(/spl alpha//spl cup//spl beta/)+H/sub /spl Omega//(/spl alpha//spl cap//spl beta/). These properties are the so-called basic information inequalities of Shannon's information measures. Do these properties fully characterize the entropy function? To make this question more precise, we view an entropy function as a 2/sup n/-1-dimensional vector where the coordinates are indexed by the nonempty subsets of the ground set {1, 2, /spl middot//spl middot//spl middot/, n}. Let /spl Gamma//sub n/ be the cone in R/sup 2n-1/ consisting of all vectors which have these three properties when they are viewed as functions defined on 2/sup {1, 2, /spl middot//spl middot//spl middot/, n}/. Let /spl Gamma//sub n/* be the set of all 2/sup n/-1-dimensional vectors which correspond to the entropy functions of some sets of n discrete random variables. The question can be restated as: is it true that for any n, /spl Gamma/~/sub n/*=/spl Gamma//sub n/? Here /spl Gamma/~/sub n/* stands for the closure of the set /spl Gamma//sub n/*. The answer is "yes" when n=2 and 3 as proved in our previous work. Based on intuition, one may tend to believe that the answer should be "yes" for any n. The main discovery of this paper is a new information-theoretic inequality involving four discrete random variables which gives a negative answer to this fundamental problem in information theory: /spl Gamma/~*/sub n/ is strictly smaller than /spl Gamma//sub n/ whenever n>3. While this new inequality gives a nontrivial outer bound to the cone /spl Gamma/~/sub 4/*, an inner bound for /spl Gamma/~*/sub 4/ is also given. The inequality is also extended to any number of random variables.
19004655
Identification via compressed data
A new coding problem is introduced for a correlated source (X/sup n/,Y/sup n/)/sub n=1//sup /spl infin//. The observer of X/sup n/ can transmit data depending on X/sup n/ at a prescribed rate R. Based on these data the observer of Y/sup n/ tries to identify whether for some distortion measure /spl rho/ (like the Hamming distance) n/sup -1/ /spl rho/(X/sup n/,Y/sup n/)/spl les/d, a prescribed fidelity criterion. We investigate as functions of R and d the exponents of two error probabilities, the probabilities for misacceptance, and the probabilities for misrejection. In the case where X/sup n/ and Y/sup n/ are independent, we completely characterize the achievable region for the rate R and the exponents of two error probabilities; in the case where X/sup n/ and Y/sup n/ are correlated, we get some interesting partial results for the achievable region. During the process, we develop a new method for proving converses, which is called "the inherently typical subset lemma". This new method goes considerably beyond the "entropy characterization" the "image size characterization," and its extensions. It is conceivable that this new method has a strong impact on multiuser information theory.
32850524
Linear inequalities for covering codes: Part I: Pair covering inequalities
The lower bounds on K(n,R), minimum number of codewords of any binary code of length n, and covering radius R are improved. A new technique combining the Hamming association scheme and the results of a classic problem of covering pairs by k-tuples is introduced. The new lower bounds are obtained by studying various linear inequalities satisfied by covering codes, and such an inequality is derived. The lower bounds for K(n,R) are studied for some special values of n and R, which serve as examples showing how the methods developed are applied to concrete cases. >
32960689
On Maximal Shadows of Members in Left-compressed Sets
Whereas Stanley, Proctor and others studied Sperner properties of the poset L(k,m) we consider shadows of left-compressed sets and derive asymptotic bounds on their sizes.
15006226
Bounds on the sizes of constant weight covering codes
Motivated by applications in universal data compression algorithms we study the problem of bounds on the sizes of constant weight covering codes. We are concerned with the minimal sizes of codes of lengthn and constant weightu such that every word of lengthn and weightv is within Hamming distanced from a codeword. In addition to a brief summary of part of the relevant literature, we also give new results on upper and lower bounds to these sizes. We pay particular attention to the asymptotic covering density of these codes. We include tables of the bounds on the sizes of these codes both for small values ofn and for the asymptotic behavior. A comparison with techniques for attaining bounds for packing codes is also given. Some new combinatorial questions are also arising from the techniques.
43476378
Partial converse for a relay channel
A special case of the general discrete memoryless relay channel is studied. This channel consists of an input x, a relay output z, a channel output y, and a noiseless channel of capacity C/sub r/ allowing the relay sender to send additional information to the decoder. The channel is described by a collection of distributions (p(y, z mod x)). The decoder uses the channel output y and a function f(z) of the relay output at a rate no greater than C/sub r/ to recover the message. Some results on the capacity of the channel are obtained. >
1150626
A Flexible New Technique for Camera Calibration
We propose a flexible technique to easily calibrate a camera. It only requires the camera to observe a planar pattern shown at a few (at least two) different orientations. Either the camera or the planar pattern can be freely moved. The motion need not be known. Radial lens distortion is modeled. The proposed procedure consists of a closed-form solution, followed by a nonlinear refinement based on the maximum likelihood criterion. Both computer simulation and real data have been used to test the proposed technique and very good results have been obtained. Compared with classical techniques which use expensive equipment such as two or three orthogonal planes, the proposed technique is easy to use and flexible. It advances 3D computer vision one more step from laboratory environments to real world use.
12105004
New Measurements and Corner-Guidance for Curve Matching with Probabilistic Relaxation
Reliable curve matching is a difficult yet important problem in many vision-based applications including image-based modeling. We describe in this paper two aspects of our research in this area: a new algorithm for curve matching (including lines) within a probabilistic relaxation framework, and an approach of incorporating previously matched points/corners to guide curve matching. We propose similarity-invariant unary and binary measurements suitable for curves, and introduce an additional measurement to model the uncertainty of the binary measurements. The uncertainty measure is proven to be very important in computing the matching support from neighboring matches. We also show how to use a set of previously matched points/corners to guide the curve matching. The role of the corner guidance is explicitly modeled by a set of unary measurements and a similarity function under the same relaxation framework. Preprocessing techniques contributing to the success of our curve matching techniques are also developed and discussed. Experiments with complex real scenes show that the rate of correct matching is higher than 98%.
81034
Co-clustering by block value decomposition
Dyadic data matrices, such as co-occurrence matrix, rating matrix, and proximity matrix, arise frequently in various important applications. A fundamental problem in dyadic data analysis is to find the hidden block structure of the data matrix. In this paper, we present a new co-clustering framework, block value decomposition(BVD), for dyadic data, which factorizes the dyadic data matrix into three components, the row-coefficient matrix R, the block value matrix B, and the column-coefficient matrix C. Under this framework, we focus on a special yet very popular case -- non-negative dyadic data, and propose a specific novel co-clustering algorithm that iteratively computes the three decomposition matrices based on the multiplicative updating rules. Extensive experimental evaluations also demonstrate the effectiveness and potential of this framework as well as the specific algorithms for co-clustering, and in particular, for discovering the hidden block structure in the dyadic data.
14910614
An inequality between the diameter and the inverse dual degree of a tree
Let T be a nontrivial tree with diameter D(T) and radius R(T). Let I(T) be the inverse dual degree of T which is defined to be ΣueV(T) 1/d(u), where d(u) = (Συ∈ N(u)d(υ))/d(u) for u ∈ V(T). For any longest path P of T, denote by a(P) the number of vertices outside P with degree at least 2, b(P) the number of vertices on P with degree at least 3 and distance at least 2 to each of the end-vertices of P, and c(P) the number of vertices adjacent to one of the end-vertices of P and with degree at least 3. In this note we prove that I(T) ≥ D(T)/2+ a(P)/3 + b(P)/10 + c(P)/12 + 5/6. As a corollary we then get {R(T) + 1/3 if D(T) is odd, I(T) ≥ {R(T) + 5/6 if D(T) is even, with equality if and only if T is a path of at least four vertices. The latter inequality strengthens a conjecture made by the program Graffiti.
10032867
Incubating services in legacy systems for architectural migration
Legacy systems are valuable assets for organisations. They continuously evolve with new emerged technologies in rapidly changing business environment. Web services, together with service-oriented architectures, facilitate legacy system webification and evolution in service-oriented computing environment. Traditional approaches to integrate legacy systems with Web service technology are wrapping a legacy system as a black-box without adequate system understanding. In this paper, we proposed a reengineering approach which applies an improved agglomerative hierarchical clustering algorithm to restructure legacy code and to facilitate legacy code extraction for Web service construction. It supports service identification and service packaging and archives legacy system migration into service-oriented architectures by providing functional legacy code as Web services.