Computing channel capacity is in general intractable because it is given by the limit of a sequence of optimization problems whose dimensionality grows to infinity. As a result, constant-sized characterizations of feedback or non-feedback capacity are known for only a few classes of channels with memory. This paper introducesposet-causal channels—a new formalism of a communication channel in which channel inputs and outputs are indexed by the elements of a partially ordered set (poset). We develop a novel methodology that allows us to establish a single-letter upper bound on the feedback capacity of a subclass of poset-causal channels whose memory structure exhibits a Markov property and symmetry. The methodology is based on symmetry reduction in optimization. Additionally, we establish connections to the literature on graphical models by providing a sufficient condition for our capacity upper bound to be tight, expressed in terms of the running intersection property. We instantiate our method on two channel models: the Noisy Output is the STate (NOST) channel—for which the bound is tight—and a new two-dimensional extension of it.

Statistical estimation in many contemporary settings involves the acquisition, analysis, and aggregation of data sets from multiple sources, which can have significant differences in character and in value. Due to these variations, the effectiveness of employing a given resource, e.g., a sensing device or computing power, for gathering or processing data from a particular source depends on the nature of that source. As a result, the appropriate division and assignment of a collection of resources to a set of data sources can substantially impact the overall performance of an inferential strategy. In this expository article, we adopt a general view of the notion of a resource and its effect on the quality of a data source, and we describe a framework for the allocation of a given set of resources to a collection of sources in order to optimize a specified metric of statistical efficiency. We discuss several stylized examples involving inferential tasks such as parameter estimation and hypothesis testing based on heterogeneous data sources, in which optimal allocations can be computed either in closed form or via efficient numerical procedures based on convex optimization. This work is an inferential analog of the literature in information theory on allocating power across communications channels of variable quality in order to optimize for total throughput.

We consider the problem of cardinality penalized optimization of a convex function over the probability simplex with additional convex constraints. It's well-known that the classical L1 regularizer fails to promote sparsity on the probability simplex since L1 norm on the probability simplex is trivially constant. We propose a direct relaxation of the minimum cardinality problem and show that it can be efficiently solved using convex programming. As a first application we consider recovering a sparse probability measure given moment constraints, in which our formulation becomes linear programming, hence can be solved very efficiently. A sufficient condition for exact recovery of the minimum cardinality solution is derived for arbitrary affine constraints. We then develop a penalized version for the noisy setting which can be solved using second order cone programs. The proposed method outperforms known heuristics based on L1 norm. As a second application we consider convex clustering using a sparse Gaussian mixture and compare our results with the well known soft k-means algorithm.

We consider the #P-complete problem of counting the number of independent sets in a given graph. Our interest is in understanding the effectiveness of the popular belief propagation (BP) heuristic. BP is a simple iterative algorithm that is known to have at least one fixed point, where each fixed point corresponds to a stationary point of the Bethe free energy (introduced by Yedidia, Freeman, and Weiss [IEEE Trans. Inform. Theory, 51 (2004), pp. 2282–2312] in recognition of Bethe’s earlier work in 1935). The evaluation of the Bethe free energy at such a stationary point (or BP fixed point) leads to the Bethe approximation for the number of independent sets of the given graph. BP is not known to converge in general, nor is an efficient, convergent procedure for finding stationary points of the Bethe free energy known. Furthermore, the effectiveness of the Bethe approximation is not well understood. As the first result of this paper we propose a BP-like algorithm that always converges to a stationary point of the Bethe free energy for any graph for the independent set problem. This procedure finds an [Formula: see text]-approximate stationary point in [Formula: see text] iterations for a graph of [Formula: see text] nodes with max-degree [Formula: see text]. We study the quality of the resulting Bethe approximation using the recently developed “loop series” framework of Chertkov and Chernyak [J. Stat. Mech. Theory Exp., 6 (2006), P06009]. As this characterization is applicable only for exact stationary points of the Bethe free energy, we provide a slightly modified characterization that holds for [Formula: see text]-approximate stationary points. We establish that for any graph on [Formula: see text] nodes with max-degree [Formula: see text] and girth larger than [Formula: see text], the multiplicative error between the number of independent sets and the Bethe approximation decays as [Formula: see text] for some [Formula: see text]. This provides a deterministic counting algorithm that leads to strictly different results compared to a recent result of Weitz [in Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, ACM Press, New York, 2006, pp. 140–149]. Finally, as a consequence of our analysis we prove that the Bethe approximation is exceedingly good for a random 3-regular graph conditioned on the shortest cycle cover conjecture of Alon and Tarsi [SIAM J. Algebr. Discrete Methods, 6 (1985), pp. 345–350] being true.

For Gaussian graphical models with cycles, loopy belief propagation often performs reasonably well, but its convergence is not guaranteed and the computation of variances is generally incorrect. In this paper, we identify a set of special vertices called a feedback vertex set whose removal results in a cycle-free graph. We propose a feedback message passing algorithm in which non-feedback nodes send out one set of messages while the feedback nodes use a different message update scheme. Exact inference results can be obtained in O(k2n), where k is the number of feedback nodes and n is the total number of nodes. For graphs with large feedback vertex sets, we describe a tractable approximate feedback message passing algorithm. Experimental results show that this procedure converges more often, faster, and provides better results than loopy belief propagation.

We consider Gaussian multiresolution (MR) models in which coarser, hidden variables serve to capture statistical dependencies among the finest scale variables. Tree-structured MR models have limited modeling capabilities, as variables at one scale are forced to be uncorrelated with each other conditioned on other scales. We propose a new class of Gaussian MR models that capture the residual correlations within each scale using sparse covariance structure. Our goal is to learn a tree-structured graphical model connecting variables across different scales, while at the same time learning sparse structure for the conditional covariance within each scale conditioned on other scales. This model leads to an efficient, new inference algorithm that is similar to multipole methods in computational physics.

We study the representation, approximation, and compression of functions inMdimensions that consist of constant or smooth regions separated by smooth(M-1)-dimensional discontinuities. Examples include images containing edges, video sequences of moving objects, and seismic data containing geological horizons. For both function classes, we derive the optimal asymptotic approximation and compression rates based on Kolmogorov metric entropy. For piecewise constant functions, we develop a multiresolution predictive coder that achieves the optimal rate-distortion performance; for piecewise smooth functions, our coder has near-optimal rate-distortion performance. Our coder for piecewise constant functions employssurflets, a new multiscale geometric tiling consisting ofM-dimensional piecewise constant atoms containing polynomial discontinuities. Our coder for piecewise smooth functions usessurfprints, which wed surflets to wavelets for piecewise smooth approximation. Both of these schemes achieve the optimal asymptotic approximation performance. Key features of our algorithms are that they carefully control the potential growth in surflet parameters at higher smoothness and do not require explicit estimation of the discontinuity. We also extend our results to the corresponding discrete function spaces for sampled data. We provide asymptotic performance results for both discrete function spaces and relate this asymptotic performance to the sampling rate and smoothness orders of the underlying functions and discontinuities. For approximation of discrete data, we propose a new scale-adaptive dictionary that contains few elements at coarse and fine scales, but many elements at medium scales. Simulation results on synthetic signals provide a comparison between surflet-based coders and previously studied approximation schemes based on wedgelets and wavelets.

We consider the problem of learning multiscale graphical models. Given a collection of variables along with covariance specifications for these variables, we introduce hidden variables and learn a sparse graphical model approximation on the entire set of variables (original and hidden). Our method for learning such models is based on maximizing entropy over an exponential family of graphical models, subject to divergence constraints on small subsets of variables. We demonstrate the advantages of our approach compared to methods that do not use hidden variables (which do not capture long-range behavior) and methods that use tree-structure approximations (which result in blocky artifacts).

We consider the estimation problem in Gaussian graphical models with arbitrary structure. We analyze the Embedded Trees algorithm, which solves a sequence of problems on tractable subgraphs thereby leading to the solution of the estimation problem on an intractable graph. Our analysis is based on the recently developed walk-sum interpretation of Gaussian estimation. We show that non-stationary iterations of the Embedded Trees algorithm using any sequence of subgraphs converge in walk-summable models. Based on walk-sum calculations, we develop adaptive methods that optimize the choice of subgraphs used at each iteration with a view to achieving maximum reduction in error. These adaptive procedures provide a significant speedup in convergence over stationary iterative methods, and also appear to converge in a larger class of models.

Discontinuities in data often provide vital information, and representing these discontinuities sparsely is an important goal for approximation and compression algorithms. Little work has been done on efficient representations for higher dimensional functions containing arbitrarily smooth discontinuities. We consider the N-dimensional Horizon class-N-dimensional functions containing a C/sup K/ smooth (N-1)-dimensional singularity separating two constant regions. We derive the optimal rate-distortion function for this class and introduce the multiscale surflet representation for sparse piecewise approximation of these functions. We propose a compression algorithm using surflets that achieves the optimal asymptotic rate-distortion performance for Horizon functions. This algorithm can be implemented using knowledge of only the N-dimensional function, without explicitly estimating the (N-1)-dimensional discontinuity.