Search

Shared information is a measure of mutual dependence among multiple jointly distributed random variables with finite alphabets. For a Markov chain on a tree with a given joint distribution, we give a new proof of an explicit characterization of shared information. The Markov chain on a tree is shown to possess a global Markov property based on graph separation; this property plays a key role in our proofs. When the underlying joint distribution is not known, we exploit the special form of this characterization to provide a multiarmed bandit algorithm for estimating shared information, and analyze its error performance., Comment: 13 pages, 4 figures, submitted to IEEE Transactions on Information Theory

For a given function of user data, a querier must recover with at least a prescribed probability, the value of the function based on a user-provided query response. Subject to this requirement, the user forms the query response so as to minimize the likelihood of the querier guessing a list of prescribed size to which the data value belongs based on the query response. We obtain a general converse upper bound for maximum list privacy. This bound is shown to be tight for the case of a binary-valued function through an explicit achievability scheme that involves an add-noise query response.

A user generates n independent and identically distributed data random variables with a probability mass function that must be guarded from a querier. The querier must recover, with a prescribed accuracy, a given function of the data from each of n independent and identically distributed query responses upon eliciting them from the user. The user chooses the data probability mass function and devises the random query responses to maximize distribution privacy as gauged by the (Kullback-Leibler) divergence between the former and the querier's best estimate of it based on the n query responses. Considering an arbitrary function, a basic achievable lower bound for distribution privacy is provided that does not depend on n and corresponds to worst-case privacy. Worst-case privacy equals the logsum cardinalities of inverse atoms under the given function, with the number of summands decreasing as the querier recovers the function with improving accuracy. Next, upper (converse) and lower (achievability) bounds for distribution privacy, dependent on n, are developed. The former improves upon worst-case privacy and the latter does so under suitable assumptions; both converge to it as n grows. The converse and achievability proofs identify explicit strategies for the user and the querier.

A user's data is represented by a finite-valued random variable. Given a function of the data, a querier is required to recover, with at least a prescribed probability, the value of the function based on a query response provided by the user. The user devises the query response, subject to the recoverability requirement, so as to maximize privacy of the data from the querier. Privacy is measured by the probability of error incurred by the querier in estimating the data from the query response. We analyze single and multiple independent query responses, with each response satisfying the recoverability requirement, that provide maximum privacy to the user. In the former setting, we also consider privacy for a predicate of the user's data. Achievability schemes with explicit randomization mechanisms for query responses are given and their privacy compared with converse upper bounds.

An empirical 2-hit hypothesis is presented to account for premature and unilateral ripening in Euonymus alatus., Comment: 8 pages, 8 figures and 1 table

Although cirrhosis is a key risk factor for the development of hepatocellular carcinoma (HCC), mounting evidence indicates that in a subset of patients presenting with non-alcoholic steatohepatitis (NASH), HCC manifests in the absence of cirrhosis. Given the sheer size of the non-alcoholic fatty liver disease (NAFLD) epidemic, and the dismal prognosis associated with late-stage primary liver cancer, there is an urgent need for HCC surveillance in the NASH patient. In the present study, adult male mice randomized to control diet or a fast food diet (FFD) were followed for up to 14 mo and serum level of a panel of HCC-relevant biomarkers was compared with liver biopsies at 3 and 14 mo. Both NAFLD Activity Score (NAS) and hepatic hydroxyproline content were elevated at 3 and 14 mo on FFD. Picrosirius red staining of liver sections revealed a filigree pattern of fibrillar collagen deposition with no cirrhosis at 14 mo on FFD. Nevertheless, 46% of animals bore one or more tumors on their livers confirmed as HCC in hematoxylin-eosin-stained liver sections. Receiver operating characteristic (ROC) curves analysis for serum levels of the HCC biomarkers osteopontin (OPN), alpha-fetoprotein (AFP) and Dickkopf-1 (DKK1) returned concordance-statistic/area under ROC curve of > 0.89. These data suggest that serum levels of OPN (threshold, 218 ng/mL; sensitivity, 82%; specificity, 86%), AFP (136 ng/mL; 91%; 97%) and DKK1 (2.4 ng/mL; 82%; 81%) are diagnostic for HCC in a clinically relevant model of NASH

We examine the coordinated and universal rate-efficient sampling of a subset of correlated discrete memoryless sources followed by lossy compression of the sampled sources. The goal is to reconstruct a predesignated subset of sources within a specified level of distortion. The combined sampling mechanism and rate distortion code are universal in that they are devised to perform robustly without exact knowledge of the underlying joint probability distribution of the sources. In Bayesian as well as nonBayesian settings, single-letter characterizations are provided for the universal sampling rate distortion function for fixed-set sampling, independent random sampling and memoryless random sampling. It is illustrated how these sampling mechanisms are successively better. Our achievability proofs bring forth new schemes for joint source distribution-learning and lossy compression.

The extent of renal scarring in chronic kidney disease (CKD) can only be ascertained by highly invasive, painful and sometimes risky tissue biopsy. Interestingly, CKD-related abnormalities in kidney size can often be visualized using ultrasound. Nevertheless, not only does the ellipsoid formula used today underestimate true renal size but also the relation governing renal size and collagen content remains unclear. We used coronal kidney sections from healthy mice and mice with renal disease to develop a new technique for estimating the renal parenchymal area. While treating the kidney as an ellipse with the major axis the polar distance, this technique involves extending the minor axis into the renal pelvis. The calculated renal parenchymal area is remarkably similar to the measured area. Biochemically determined kidney collagen content revealed a strong and positive correlation with the calculated renal parenchymal area. The extent of renal scarring, i.e. kidney collagen content, can now be computed by making just two renal axial measurements which can easily be accomplished via noninvasive imaging of this organ., Comment: 17 pages, 6 figures, 3 equations

Autosomal polycystic kidney disease (ARPKD) is associated with progressive enlargement of the kidneys fuelled by the formation and expansion of fluid-filled cysts. The disease is congenital and children that do not succumb to it during the neonatal period will, by age 10 years, more often than not, require nephrectomy+renal replacement therapy for management of both pain and renal insufficiency. Since increasing cystic index (CI; percent of kidney occupied by cysts) drives both renal expansion and organ dysfunction, management of these patients, including decisions such as elective nephrectomy and prioritization on the transplant waitlist, could clearly benefit from serial determination of CI. So also, clinical trials in ARPKD evaluating the efficacy of novel drug candidates could benefit from serial determination of CI. Although ultrasound is currently the imaging modality of choice for diagnosis of ARPKD, its utilization for assessing disease progression is highly limited. Magnetic resonance imaging or computed tomography, although more reliable for determination of CI, are expensive, time-consuming and somewhat impractical in the pediatric population. Using a well-established mammalian model of ARPKD, we undertook a big data-like analysis of minimally- or non-invasive serum and urine biomarkers of renal injury/dysfunction to derive a family of equations for estimating CI. We then applied a signal averaging protocol to distill these equations to a single empirical formula for calculation of CI. Such a formula will eventually find use in identifying and monitoring patients at high risk for progressing to end-stage renal disease and aid in the conduct of clinical trials., Comment: 3 tables and 8 figures

Consider a discrete memoryless multiple source with $m$ components of which $k \leq m$ possibly different sources are sampled at each time instant and jointly compressed in order to reconstruct all the $m$ sources under a given distortion criterion. A new notion of sampling rate distortion function is introduced, and is characterized first for the case of fixed-set sampling. Next, for independent random sampling performed without knowledge of the source outputs, it is shown that the sampling rate distortion function is the same regardless of whether or not the decoder is informed of the sequence of sampled sets. Furthermore, memoryless random sampling is considered with the sampler depending on the source outputs and with an informed decoder. It is shown that deterministic sampling, characterized by a conditional point-mass, is optimal and suffices to achieve the sampling rate distortion function. For memoryless random sampling with an uninformed decoder, an upper bound for the sampling rate distortion function is seen to possess a similar property of conditional point-mass optimality. It is shown by example that memoryless sampling with an informed decoder can outperform strictly any independent random sampler, and that memoryless sampling can do strictly better with an informed decoder than without.

A set of m terminals, observing correlated signals, communicate interactively to generate common randomness for a given subset of them. Knowing only the communication, how many direct queries of the value of the common randomness will resolve it? A general upper bound, valid for arbitrary signal alphabets, is developed for the number of such queries by using a query strategy that applies to all common randomness and associated communication. When the underlying signals are independent and identically distributed repetitions of m correlated random variables, the number of queries can be exponential in signal length. For this case, the mentioned upper bound is tight and leads to a single-letter formula for the largest query exponent, which coincides with the secret key capacity of a corresponding multiterminal source model. In fact, the upper bound constitutes a strong converse for the optimum query exponent, and implies also a new strong converse for secret key capacity. A key tool, estimating the size of a large probability set in terms of Renyi entropy, is interpreted separately, too, as a lossless block coding result for general sources. As a particularization, it yields the classic result for a discrete memoryless source., Comment: Accepted for publication in IEEE Transactions on Information Theory

We propose an approach for constructing secret and private keys based on the long-known Slepian-Wolf code, due to Wyner, for correlated sources connected by a virtual additive noise channel. Our work is motivated by results of Csisz\'ar and Narayan which highlight innate connections between secrecy generation by multiple terminals that observe correlated source signals and Slepian-Wolf near-lossless data compression. Explicit procedures for such constructions and their substantiation are provided. The performance of low density parity check channel codes in devising a new class of secret keys is examined., Comment: 12 pages; 2 figures; The material in this paper was presented in part at the IEEE International Symposium on Information Theory, Adelaide, Australia, Sept. 2005, and at the Information Theory and Applications Workshop, San Diego, CA, Feb. 2006

We consider perfect secret key generation for a ``pairwise independent network'' model in which every pair of terminals share a random binary string, with the strings shared by distinct terminal pairs being mutually independent. The terminals are then allowed to communicate interactively over a public noiseless channel of unlimited capacity. All the terminals as well as an eavesdropper observe this communication. The objective is to generate a perfect secret key shared by a given set of terminals at the largest rate possible, and concealed from the eavesdropper. First, we show how the notion of perfect omniscience plays a central role in characterizing perfect secret key capacity. Second, a multigraph representation of the underlying secrecy model leads us to an efficient algorithm for perfect secret key generation based on maximal Steiner tree packing. This algorithm attains capacity when all the terminals seek to share a key, and, in general, attains at least half the capacity. Third, when a single ``helper'' terminal assists the remaining ``user'' terminals in generating a perfect secret key, we give necessary and sufficient conditions for the optimality of the algorithm; also, a ``weak'' helper is shown to be sufficient for optimality., Comment: accepted to the IEEE Transactions on Information Theory

We consider secret key generation for a "pairwise independent network" model in which every pair of terminals observes correlated sources that are independent of sources observed by all other pairs of terminals. The terminals are then allowed to communicate publicly with all such communication being observed by all the terminals. The objective is to generate a secret key shared by a given subset of terminals at the largest rate possible, with the cooperation of any remaining terminals. Secrecy is required from an eavesdropper that has access to the public interterminal communication. A (single-letter) formula for secret key capacity brings out a natural connection between the problem of secret key generation and a combinatorial problem of maximal packing of Steiner trees in an associated multigraph. An explicit algorithm is proposed for secret key generation based on a maximal packing of Steiner trees in a multigraph; the corresponding maximum rate of Steiner tree packing is thus a lower bound for the secret key capacity. When only two of the terminals or when all the terminals seek to share a secret key, the mentioned algorithm achieves secret key capacity in which case the bound is tight., Comment: IEEE Transactions on Information Theory, in revision prior to review for final approval

A subset of a set of terminals that observe correlated signals seek to compute a given function of the signals using public communication. It is required that the value of the function be kept secret from an eavesdropper with access to the communication. We show that the function is securely computable if and only if its entropy is less than the "aided secret key" capacity of an associated secrecy generation model, for which a single-letter characterization is provided.

We consider a Gelfand-Pinsker discrete memoryless channel (DMC) model and provide a strong converse for its capacity. The strong converse is then used to obtain an upper bound on the reliability function. Instrumental in our proofs is a new technical lemma which provides an upper bound for the rate of codes with codewords that are conditionally typical over large message dependent subsets of a typical set of state sequences. This technical result is a nonstraightforward analog of a known result for a DMC without states that provides an upper bound on the rate of a good code with codewords of a fixed type (to be found in, for instance, the Csiszar-Korner book)., Comment: 4 pages, Presented at the ISIT 2009

This work is motivated by recent results of Csiszar and Narayan (IEEE Trans. on Inform. Theory, Dec. 2004), which highlight innate connections between secrecy generation by multiple terminals and multiterminal Slepian-Wolf near-lossless data compression (sans secrecy restrictions). We propose a new approach for constructing secret and private keys based on the long-known Slepian-Wolf code for sources connected by a virtual additive noise channel, due to Wyner (IEEE Trans. on Inform. Theory, Jan. 1974). Explicit procedures for such constructions, and their substantiation, are provided., Comment: Appeared in the proceedings of the 2005 IEEE International Symposium on Information Theory, Adelaide, Australia, September 4 -- 9, 2005

We consider a model with three terminals and examine the problem of characterizing the largest rates at which two pairs of terminals can simultaneously generate private keys, each of which is effectively concealed from the remaining terminal., Comment: Appeared in the proceedings of the 2004 IEEE International Symposium on Information Theory, Chicago, Illinois, June 27 -- July 2, 2004

We consider a model for secrecy generation, with three terminals, by means of public interterminal communication, and examine the problem of characterizing all the rates at which all three terminals can generate a ``secret key,'' and -- simultaneously -- two designated terminals can generate a ``private key'' which is effectively concealed from the remaining terminal; both keys are also concealed from an eavesdropper that observes the public communication. Inner and outer bounds for the ``secret key--private key capacity region'' are derived. Under a certain special condition, these bounds coincide to yield the (exact) secret key--private key capacity region., Comment: Appeared in the proceedings of the 2005 IEEE International Symposium on Information Theory, Adelaide, Australia, September 4 -- 9, 2005