Search

The paper studies distributed static parameter (vector) estimation in sensor networks with nonlinear observation models and noisy intersensor communication. It introduces separably estimable observation models that generalize the observability condition in linear centralized estimation to nonlinear distributed estimation. It studies two distributed estimation algorithms in separably estimable models, the \cal NU (with its linear counterpart \cal LU) and the \cal NLU. Their update rule combines a consensus step (where each sensor updates the state by weight averaging it with its neighbors' states) and an innovation step (where each sensor processes its local current observation). This makes the three algorithms of the consensus + innovations type, very different from traditional consensus. This paper proves consistency (all sensors reach consensus almost surely and converge to the true parameter value), efficiency, and asymptotic unbiasedness. For \cal LU and \cal NU, it proves asymptotic normality and provides convergence rate guarantees. The three algorithms are characterized by appropriately chosen decaying weight sequences. Algorithms \cal LU and \cal NU are analyzed in the framework of stochastic approximation theory; algorithm \cal NLU exhibits mixed time-scale behavior and biased perturbations, and its analysis requires a different approach that is developed in this paper. [ABSTRACT FROM PUBLISHER]

The weight distribution and list-decoding size of Reed–Muller codes are studied in this work. Given a weight parameter, we are interested in bounding the number of Reed–Muller codewords with weight up to the given parameter; and given a received word and a distance parameter, we are interested in bounding the size of the list of Reed–Muller codewords that are within that distance from the received word. Obtaining tight bounds for the weight distribution of Reed–Muller codes has been a long standing open problem in coding theory, dating back to 1976. In this work, we make a new connection between computer science techniques used to study low-degree polynomials and these coding theory questions. This allows us to resolve the weight distribution and list-decoding size of Reed–Muller codes for all distances. Previous results could only handle bounded distances: Azumi, Kasami, and Tokura gave bounds on the weight distribution which hold up to 2.5 times the minimal distance of the code; and Gopalan, Klivans, and Zuckerman gave bounds on the list-decoding size which hold up to the Johnson bound. [ABSTRACT FROM PUBLISHER]

We present a new lossy compressor for finite-alphabet sources. For coding a sequence x^n, the encoder starts by assigning a certain cost to each possible reconstruction sequence. It then finds the one that minimizes this cost and describes it losslessly to the decoder via a universal lossless compressor. The cost of each sequence is a linear combination of its distance from the sequence x^n and a linear function of its k^th order empirical distribution. The structure of the cost function allows the encoder to employ the Viterbi algorithm to find the sequence with minimum cost. We identify a choice of the coefficients used in the cost function which ensures that the algorithm universally achieves the optimum rate-distortion performance for any stationary ergodic source, in the limit of large n, provided that k increases as o(\log n). Iterative techniques for approximating the coefficients, which alleviate the computational burden of finding the optimal coefficients, are proposed and studied. [ABSTRACT FROM AUTHOR]

The general theory of greedy approximation is well developed. Much less is known about how specific features of a dictionary can be used to our advantage. In this paper, we discuss incoherent dictionaries. We build a new greedy algorithm which is called the orthogonal super greedy algorithm (OSGA). We show that the rates of convergence of OSGA and the orthogonal matching pursuit (OMP) with respect to incoherent dictionaries are the same. Based on the analysis of the number of orthogonal projections and the number of iterations, we observed that OSGA(s) is s times simpler (more efficient) than OMP. Greedy approximation is also a fundamental tool for sparse signal recovery. The performance of orthogonal multimatching pursuit, a counterpart of OSGA in the compressed sensing setting, is also analyzed under restricted isometry property conditions. [ABSTRACT FROM AUTHOR]

Principal curves are nonlinear generalizations of the notion of first principal component. Roughly, a principal curve is a parameterized curve in \BBR^d which passes through the “middle” of a data cloud drawn from some unknown probability distribution. Depending on the definition, a principal curve relies on some unknown parameters (number of segments, length, turn, etc.) which have to be properly chosen to recover the shape of the data without interpolating. In this paper, we consider the principal curve problem from an empirical risk minimization perspective and address the parameter selection issue using the point of view of model selection via penalization. We offer oracle inequalities and implement the proposed approach to recover the hidden structures in both simulated and real-life data. [ABSTRACT FROM AUTHOR]

We examine LDPC codes decoded using linear programming (LP). Four contributions to the LP framework are presented. First, a new method of tightening the LP relaxation, and thus improving the LP decoder, is proposed. Second, we present an algorithm which calculates a lower bound on the minimum distance of a specific code. This algorithm exhibits complexity which scales quadratically with the block length. Third, we propose a method to obtain a tight lower bound on the fractional distance, also with quadratic complexity, and thus less than previously-existing methods. Finally, we show how the fundamental LP polytope for generalized LDPC codes and nonbinary LDPC codes can be obtained. [ABSTRACT FROM AUTHOR]

Consider the noisy underdetermined system of linear equations: y=Ax_0 + z, with A an n \times N measurement matrix, n < N, and z \sim \ssr N(0,\sigma^2 I) a Gaussian white noise. Both y and A are known, both x_0 and z are unknown, and we seek an approximation to x_0. When x_0 has few nonzeros, useful approximations are often obtained by \ell_1-penalized \ell_2 minimization, in which the reconstruction \mathhatx^1,\lambda solves \min\\Vert y - Ax\Vert_2^2/2 + \lambda \Vert x\Vert_1\. [ABSTRACT FROM AUTHOR]

Peer-to-peer (P2P) systems provide a scalable way to stream content to multiple receivers over the Internet. The maximum rate achievable by all receivers is the capacity of a P2P streaming session. We provide a taxonomy of sixteen problem formulations, depending on whether there is a single P2P session or there are multiple concurrent sessions, whether the given topology is a full mesh graph or an arbitrary graph, whether the number of peers a node can have is bounded or not, and whether there are nonreceiver relay nodes or not. In each formulation, computing P2P streaming capacity requires the computation of an optimal set of multicast trees, with an exponential complexity, except in three simplest formulations that have been recently solved with polynomial time algorithms. These solutions, however, do not extend to the other more general formulations. In this paper, we develop a family of constructive, polynomial-time algorithms that can compute P2P streaming capacity and the associated multicast trees, arbitrarily accurately for seven formulations, to a factor of 4-approximation for two formulations, and to a factor of log of the number of receivers for two formulations. The optimization problem is reformulated in each case so as to convert the combinatorial problem into a linear program with an exponential number of variables. The linear program is then solved using a primal-dual approach. The algorithms combine an outer loop of primal-dual update with an inner loop of smallest price tree construction, driven by the update of dual variables in the outer loop. We show that when the construction of smallest price tree can be carried out arbitrarily accurately in polynomial time, so can the computation of P2P streaming capacity. We also develop several efficient algorithms for smallest price tree construction. Using the developed algorithms, we investigate the impact of several factors on P2P streaming capacity using topologies derived from statistics of uplink capacities of Internet hosts. [ABSTRACT FROM PUBLISHER]

We study the centroid with respect to the class of information-theoretic Burbea-Rao divergences that generalize the celebrated Jensen-Shannon divergence by measuring the non-negative Jensen difference induced by a strictly convex and differentiable function. Although those Burbea-Rao divergences are symmetric by construction, they are not metric since they fail to satisfy the triangle inequality. We first explain how a particular symmetrization of Bregman divergences called Jensen-Bregman distances yields exactly those Burbea-Rao divergences. We then proceed by defining skew Burbea-Rao divergences, and show that skew Burbea-Rao divergences amount in limit cases to compute Bregman divergences. We then prove that Burbea-Rao centroids can be arbitrarily finely approximated by a generic iterative concave-convex optimization algorithm with guaranteed convergence property. In the second part of the paper, we consider the Bhattacharyya distance that is commonly used to measure overlapping degree of probability distributions. We show that Bhattacharyya distances on members of the same statistical exponential family amount to calculate a Burbea-Rao divergence in disguise. Thus we get an efficient algorithm for computing the Bhattacharyya centroid of a set of parametric distributions belonging to the same exponential families, improving over former specialized methods found in the literature that were limited to univariate or “diagonal” multivariate Gaussians. To illustrate the performance of our Bhattacharyya/Burbea-Rao centroid algorithm, we present experimental performance results for k-means and hierarchical clustering methods of Gaussian mixture models. [ABSTRACT FROM PUBLISHER]

We derive generalization error (loss) bounds for orthogonal matching pursuit algorithms, starting with kernel matching pursuit and sparse kernel principal components analysis. We propose (to the best of our knowledge) the first loss bound for kernel matching pursuit using a novel application of sample compression and Vapnik-Chervonenkis bounds. For sparse kernel principal components analysis, we find that it can be bounded using a standard sample compression analysis, as the subspace it constructs is a compression scheme. We demonstrate empirically that this bound is tighter than previous state-of-the-art bounds for principal components analysis, which use global and local Rademacher complexities. From this analysis we propose a novel sparse variant of kernel canonical correlation analysis and bound its generalization performance using the results developed in this paper. We conclude with a general technique for designing matching pursuit algorithms for other learning domains. [ABSTRACT FROM PUBLISHER]

In this paper, we study the problem of sampling and reconstructing signals which are assumed to lie on or close to one of several subspaces of a Hilbert space. Importantly, we here consider a very general setting in which we allow infinitely many subspaces in infinite dimensional Hilbert spaces. This general approach allows us to unify many results derived recently in areas such as compressed sensing, affine rank minimization, analog compressed sensing and structured matrix decompositions. [ABSTRACT FROM AUTHOR]

“Approximate message passing” (AMP) algorithms have proved to be effective in reconstructing sparse signals from a small number of incoherent linear measurements. Extensive numerical experiments further showed that their dynamics is accurately tracked by a simple one-dimensional iteration termed state evolution. In this paper, we provide rigorous foundation to state evolution. We prove that indeed it holds asymptotically in the large system limit for sensing matrices with independent and identically distributed Gaussian entries. While our focus is on message passing algorithms for compressed sensing, the analysis extends beyond this setting, to a general class of algorithms on dense graphs. In this context, state evolution plays the role that density evolution has for sparse graphs. The proof technique is fundamentally different from the standard approach to density evolution, in that it copes with a large number of short cycles in the underlying factor graph. It relies instead on a conditioning technique recently developed by Erwin Bolthausen in the context of spin glass theory. [ABSTRACT FROM AUTHOR]

Turbo codes and the iterative algorithm for decoding them sparked a new era in the theory and practice of error control codes. Turbo equalization followed as a natural extension to this development, as an iterative technique for detection and decoding of data that has been both protected with forward error correction and transmitted over a channel with intersymbol interference (ISI). In this paper, we review the turbo equalization approach to coded data transmission over ISI channels, with an emphasis on the basic ideas, some of the practical details, and many of the research directions that have arisen from this offshoot, introduced by Douillard, of the original turbo decoding algorithm. The subsequent relaxation of the maximum a posteriori (MAP) equalization algorithm to include linear and other simpler receivers sparked a decade and a half of research into iterative algorithms, spanning research problems ranging from trellis coded modulation to underwater acoustic communications. [ABSTRACT FROM AUTHOR]

Non-Gaussian processes may require not only the information provided by first two moments, but also that given by the higher-order statistics, in particular, by the third- and fourth-order moments or cumulants. This paper addresses a fourth-order cumulant estimation problem for real discrete-time random non-i.i.d. signal, that can be approximated as an MA stochastic process. An unbiased estimator is proposed, studied and compared to two other frequently used estimators of the fourth-order cumulant (natural estimator and fourth k-statistics). Statistical comparative studies are undertaken from both bias and MSE points of view, for different distribution laws and MA filters. Algorithms, aiming to reduce computational complexity of the proposed estimator, as well as that of the fourth k-statistics bias, are also provided. [ABSTRACT FROM PUBLISHER]

A system with an n-dimensional state vector and a controller and an actor is considered. The controller has complete information about the system state, and reveals a certain “minimum” amount of information to the actor. The actor takes certain actions based on the information the controller reveals, and the actions fetch certain utilities for each entity. Both the controller and actor seek to maximize their individual utilities by respectively selecting the information to reveal and the actions to adopt. This decision problem forms the basis of several technical and social systems, and can be formulated as a signaling game. It is shown that the Perfect Bayesian Equilibrium of this game has several counterintuitive properties and can be obtained as a saddle point of a different two person zero sum game. The computation time for saddle points using standard linear programs however turns out to be superexponential in n, which leads to computational intractability even for moderate n. Algorithms for computing saddle point policies using a computation time that is exponential in n are presented. Finally, simple linear time computable policies that approximate the saddle-point policies within guaranteeable approximation ratios are obtained. [ABSTRACT FROM PUBLISHER]