Search

We propose a graphical model for representing networks of stochastic processes, the minimal generative model graph. It is based on reduced factorizations of the joint distribution over time. We show that under appropriate conditions, it is unique and consistent with another type of graphical model, the directed information graph, which is based on a generalization of Granger causality. We demonstrate how directed information quantifies Granger causality in a particular sequential prediction setting. We also develop efficient methods to estimate the topological structure from data that obviate estimating the joint statistics. One algorithm assumes upper bounds on the degrees and uses the minimal dimension statistics necessary. In the event that the upper bounds are not valid, the resulting graph is nonetheless an optimal approximation in terms of Kullback-Leibler (KL) divergence. Another algorithm uses near-minimal dimension statistics when no bounds are known, but the distribution satisfies a certain criterion. Analogous to how structure learning algorithms for undirected graphical models use mutual information estimates, these algorithms use directed information estimates. We characterize the sample-complexity of two plug-in directed information estimators and obtain confidence intervals. For the setting when point estimates are unreliable, we propose an algorithm that uses confidence intervals to identify the best approximation that is robust to estimation error. Last, we demonstrate the effectiveness of the proposed algorithms through the analysis of both synthetic data and real data from the Twitter network. In the latter case, we identify which news sources influence users in the network by merely analyzing tweet times. [ABSTRACT FROM AUTHOR]

We formulate a new variant of the index coding problem, where instead of demanding a specific message, clients are pliable, and are interested in receiving any $t$ messages that they do not have. We term this problem pliable index coding or PICOD (t)$ . We prove that, with this formulation, although some instances of the problem become simple, in general, the problem of finding the optimal linear code remains NP-hard. However, we show that it is possible to construct pliable index codes that are substantially smaller than index codes in many cases. If there are n$ clients, the server has m$ messages, and each client has a side information set of cardinality s\leq m-t broadcast transmissions are sufficient to satisfy all the clients. For t=1$ , this is an exponential improvement over the n$ messages required in index coding in the worst case (for m=n , the number of broadcast transmissions required is only linearly dependent on t$ . We generalize the results to instances where the side information sets are not necessarily of equal cardinality. When m = O(n^\delta )$ , for some constant \delta >0 are sufficient in general. We also consider the scenario when the server only knows the cardinality of the side information sets of the clients and each client is interested in receiving any t$ messages that it does not have. We term this formulation oblivious pliable index coding or OB-PICOD (t)$ . If the cardinalities of side information sets of all the clients is s$ (with s\leq m-t messages are both sufficient and necessary for linear codes. Finally, we develop efficient heuristic approximation algorithms for PICOD $(t)$ and show through simulations on the random instances of PICOD $(t)$ that they perform well in practice. [ABSTRACT FROM PUBLISHER]

This paper concerns the rates of power law growth of mutual information computed for a stationary measure or for a universal code. The rates are called Hilberg exponents, and four such quantities are defined for each measure and each code: two random exponents and two expected exponents. A particularly interesting case arises for the conditional algorithmic mutual information. In this case, the random Hilberg exponents are almost surely constant on ergodic sources and are bounded by the expected Hilberg exponents. This property is the second-order analog of the Shannon–McMillan–Breiman theorem, proved without invoking the ergodic theorem. It carries over to Hilberg exponents for the underlying probability measure via Shannon–Fano coding and Barron inequality. Moreover, the expected Hilberg exponents can be linked for different universal codes. Namely, if one code dominates another, the expected Hilberg exponents are greater for the former than for the latter. This paper is concluded by an evaluation of Hilberg exponents for certain sources, such as the mixture Bernoulli process and the Santa Fe processes. [ABSTRACT FROM PUBLISHER]

Consider two remote nodes having binary sequences $X$ and Y$ , respectively. Y$ is an edited version of , where the editing involves random deletions, insertions, and substitutions, possibly in bursts. The goal is for the node with Y$ to reconstruct X$ with minimal exchange of information over a noiseless link. The communication is measured in terms of both the total number of bits exchanged and the number of interactive rounds of communication. This paper focuses on the setting where the number of edits is , where $n$ is the length of $X$ . We first consider the case where the edits are a mixture of insertions and deletions (indels), and propose an interactive synchronization algorithm with near-optimal communication rate and average computational complexity of $O(n)$ arithmetic operations. The algorithm uses interaction to efficiently split the source sequence into substrings containing exactly one deletion or insertion. Each of these substrings is then synchronized using an optimal one-way algorithm based on the single-deletion correcting channel codes of Varshamov and Tenengolts. We then build on this synchronization algorithm in three different ways. First, it is modified to work with a single round of interaction. The reduction in the number of rounds comes at the expense of higher communication, which is quantified. Next, we present an extension to the practically important case where the insertions and deletions may occur in (potentially large) bursts. Finally, we show how to synchronize the sources to within a target Hamming distance. This feature can be used to differentiate between substitution and indel edits. In addition to theoretical performance bounds, we provide several validating simulation results for the proposed algorithms. [ABSTRACT FROM PUBLISHER]

We consider the coded cooperative data exchange problem for general graphs, both undirected and directed. In this problem, given a graph $G=(V,E)$ representing clients in a broadcast network, each of which initially hold a (not necessarily disjoint) set of information packets; one wishes to design a communication scheme in which eventually all clients will hold all the packets of the network. Communication is performed in rounds, where in each round a single client broadcasts a single (possibly encoded) information packet to its neighbors in G$ . The objective is to design a broadcast scheme that satisfies all clients with the minimum number of broadcast rounds. The coded cooperative data exchange problem has seen significant research over the last few years; mostly when the graph G$ is the complete broadcast graph in which each client is adjacent to all other clients in the network, but also on general topologies, both in the fractional and integral setting. In this paper, we focus on the integral setting in general topologies G$ , both undirected and directed. For undirected graphs, we tie the coded cooperative data exchange problem on G is intractable (i.e., NP-hard). We then turn to study efficient data exchange schemes for undirected topologies yielding a number of communication rounds comparable with our intractability result. Last, we tie the coded cooperative data exchange problem for directed topologies to the directed Steiner tree problem, yielding efficient data exchange approximation schemes. Our communication schemes do not involve encoding, and in such yield bounds on the coding advantage in the setting at hand. [ABSTRACT FROM PUBLISHER]

Compressive sensing (CS) states that a sparse signal can be recovered from a small number of linear measurements, and that this recovery can be performed efficiently in polynomial time. The framework of model-based CS (model-CS) leverages additional structure in the signal and provides new recovery schemes that can reduce the number of measurements even further. This idea has led to measurement-efficient recovery schemes for a variety of signal models. However, for any given model, model-CS requires an algorithm that solves the model-projection problem: given a query signal, report the signal in the model that is closest to the query signal. Often, this optimization can be computationally very expensive. Moreover, an approximation algorithm is not sufficient for this optimization to provably succeed. As a result, the model-projection problem poses a fundamental obstacle for extending model-CS to many interesting classes of models. In this paper, we introduce a new framework that we call approximation-tolerant model-CS. This framework includes a range of algorithms for sparse recovery that require only approximate solutions for the model-projection problem. In essence, our work removes the aforementioned obstacle to model-CS, thereby extending model-CS to a much wider class of signal models. Interestingly, all our algorithms involve both the minimization and the maximization variants of the model-projection problem. We instantiate this new framework for a new signal model that we call the constrained earth mover distance (CEMD) model. This model is particularly useful for signal ensembles, where the positions of the nonzero coefficients do not change significantly as a function of spatial (or temporal) location. We develop novel approximation algorithms for both the maximization and the minimization versions of the model-projection problem via graph optimization techniques. Leveraging these algorithms and our framework results in a nearly sample-optimal sparse recovery scheme for the CEMD model. [ABSTRACT FROM AUTHOR]

It is well known that \ell 1 minimization can be used to recover sufficiently sparse unknown signals from compressed linear measurements. Exact thresholds on the sparsity, as a function of the ratio between the system dimensions, so that with high probability almost all sparse signals can be recovered from independent identically distributed (i.i.d.) Gaussian measurements, have been computed and are referred to as weak thresholds. In this paper, we introduce a reweighted \ell 1 recovery algorithm composed of two steps: 1) a standard \ell 1 minimization step to identify a set of entries where the signal is likely to reside and 2) a weighted \ell 1 minimization step where entries outside this set are penalized. For signals where the non-sparse component entries are independent and identically drawn from certain classes of distributions, (including most well-known continuous distributions), we prove a strict improvement in the weak recovery threshold. Our analysis suggests that the level of improvement in the weak threshold depends on the behavior of the distribution at the origin. Numerical simulations verify the distribution dependence of the threshold improvement very well, and suggest that in the case of i.i.d. Gaussian nonzero entries, the improvement can be quite impressive—over 20% in the example we consider. [ABSTRACT FROM AUTHOR]

Carrier sense multiple access (CSMA), which resolves contentions over wireless networks in a fully distributed fashion, has recently gained a lot of attentions since it has been proved that appropriate control of CSMA parameters guarantees optimality in terms of stability (i.e., scheduling) and system-wide utility (i.e., scheduling and congestion control). Most CSMA-based algorithms rely on the popular Markov chain Monte Carlo technique, which enables one to find optimal CSMA parameters through iterative loops of simulation-and-update. However, such a simulation-based approach often becomes a major cause of exponentially slow convergence, being poorly adaptive to flow/topology changes. In this paper, we develop distributed iterative algorithms which produce approximate solutions with convergence in polynomial time for both stability and utility maximization problems. In particular, for the stability problem, the proposed distributed algorithm requires, somewhat surprisingly, only one iteration among links. Our approach is motivated by the Bethe approximation (introduced by Yedidia, Freeman, and Weiss) allowing us to express approximate solutions via a certain nonlinear system with polynomial size. Our polynomial convergence guarantee comes from directly solving the nonlinear system in a distributed manner, rather than multiple simulation-and-update loops in existing algorithms. We provide numerical results to show that the algorithm produces highly accurate solutions and converges much faster than the prior ones. [ABSTRACT FROM AUTHOR]

We point out an issue with one of the results in Bellala et al. [1] that invokes a main result on adaptive stochastic minimum cost cover problem (Theorem 5.8) of Golovin and Krause. We construct an example that shows that the proof of Theorem 5.8 of Golovin and Krause is invalid, and therefore, the proof in Bellala et al. about the near-optimum performance of their algorithm is also invalid. [ABSTRACT FROM PUBLISHER]

This paper provides a proof of global convergence of gradient search for low-rank matrix approximation. Such approximations have recently been of interest for large-scale problems, as well as for dictionary learning for sparse signal representations and matrix completion. The proof is based on the interpretation of the problem as an optimization on the Grassmann manifold and Fubiny–Study distance on this space. [ABSTRACT FROM PUBLISHER]

We pose the deterministic, nonparametric, approximation problem for scalar nonnegative input/output systems via finite impulse response convolutions, based on repeated observations of input/output signal pairs. The problem is converted into a nonnegative matrix factorization with special structure for which we use Csiszár’s I-divergence as the criterion of optimality. Conditions are given, on the input/output data, that guarantee the existence and uniqueness of the minimum. We propose an algorithm of the alternating minimization type for I-divergence minimization, and study its asymptotic behavior. For the case of noisy observations, we give the large sample properties of the statistical version of the minimization problem. Numerical experiments confirm the asymptotic results and exhibit the fast convergence of the proposed algorithm. [ABSTRACT FROM PUBLISHER]

Inspired by ideas from the field of stochastic approximation, we propose a randomized algorithm to compute the capacity of a finite-state channel with a Markovian input. When the mutual information rate of the channel is concave with respect to the chosen parameterization, the proposed algorithm proves to be convergent to the capacity of the channel almost surely with the derived convergence rate. We also discuss the convergence behavior of the algorithm without the concavity assumption. [ABSTRACT FROM PUBLISHER]

The use of normal bases for representing elements in a binary field is attractive in some applications because it is easy to perform squaring operations in hardware. In such cases, the costs of implementing the multiplication operation become a primary concern. We present new algorithms for reducing the space complexity of Gaussian normal basis multipliers over binary fields GF(2^m) , where $m$ is odd. Compared with previous results, our approach incurs no additional costs in time complexity, and achieves improvements in space complexity over a wide range of finite fields and digit sizes. For the binary fields specified in the NIST FIPS 186-3 elliptic curve digital signature algorithm standards document, our algorithms reduce by 16% (respectively, 27%) the number of XOR gates needed for the implementation of a digit-level parallel-input parallel-output multiplier over a 163-bit (respectively, 409 bit) binary field. [ABSTRACT FROM AUTHOR]

We propose an iterative method for approximately computing the capacity of discrete memoryless channels, possibly under additional constraints on the input distribution. Based on duality of convex programming, we derive explicit upper and lower bounds for the capacity. The presented method requires O(M^2 N \sqrt \log N/\varepsilon ) to provide an estimate of the capacity to within $\varepsilon $ , where $N$ and $M$ denote the input and output alphabet size; a single iteration has a complexity $O(M N)$ . We also show how to approximately compute the capacity of memoryless channels having a bounded continuous input alphabet and a countable output alphabet under some mild assumptions on the decay rate of the channel’s tail. It is shown that discrete-time Poisson channels fall into this problem class. As an example, we compute sharp upper and lower bounds for the capacity of a discrete-time Poisson channel with a peak-power input constraint. [ABSTRACT FROM AUTHOR]

We study the topic of dimensionality reduction for $k$ -means clustering. Dimensionality reduction encompasses the union of two approaches: 1) feature selection and 2) feature extraction. A feature selection-based algorithm for $k$ -means clustering selects a small subset of the input features and then applies $k$ -means clustering on the selected features. A feature extraction-based algorithm for $k$ -means clustering constructs a small set of new artificial features and then applies $k$ -means clustering on the constructed features. Despite the significance of $k$ -means clustering as well as the wealth of heuristic methods addressing it, provably accurate feature selection methods for $k$ -means clustering are not known. On the other hand, two provably accurate feature extraction methods for $k$ -means clustering are known in the literature; one is based on random projections and the other is based on the singular value decomposition (SVD). This paper makes further progress toward a better understanding of dimensionality reduction for $k$ -means clustering. Namely, we present the first provably accurate feature selection method for $k$ -means clustering and, in addition, we present two feature extraction methods. The first feature extraction method is based on random projections and it improves upon the existing results in terms of time complexity and number of features needed to be extracted. The second feature extraction method is based on fast approximate SVD factorizations and it also improves upon the existing results in terms of time complexity. The proposed algorithms are randomized and provide constant-factor approximation guarantees with respect to the optimal $k$ -means objective value. [ABSTRACT FROM AUTHOR]

We show a regret minimization algorithm for setting the reserve price in a sequence of second-price auctions, under the assumption that all bids are independently drawn from the same unknown and arbitrary distribution. Our algorithm is computationally efficient, and achieves a regret of \vphantom \Big (\widetilde \mathcal O(\sqrt T) in a sequence of $T$ auctions. This holds even when the number of bidders is stochastic with a known distribution. [ABSTRACT FROM PUBLISHER]

Random projection has been widely used in data classification. It maps high-dimensional data into a low-dimensional subspace in order to reduce the computational cost in solving the related optimization problem. While previous studies are focused on analyzing the classification performance in the low-dimensional space, in this paper, we consider the recovery problem, i.e., how to accurately recover the optimal solution to the original high-dimensional optimization problem based on the solution learned after random projection. We present a simple algorithm, termed dual random projection, which uses the dual solution of the low-dimensional optimization problem to recover the optimal solution to the original problem. Our theoretical analysis shows that with a high probability, the proposed algorithm is able to accurately recover the optimal solution to the original problem, provided that the data matrix is (approximately) low-rank and/or optimal solution is (approximately) sparse. We further show that the proposed algorithm can be applied iteratively to reducing the recovery error exponentially. [ABSTRACT FROM PUBLISHER]

This paper considers a Markov-modulated duplication-deletion random graph where at each time instant, one node can either join or leave the network; the probabilities of joining or leaving evolve according to the realization of a finite state Markov chain. Two results are presented. First, motivated by social network applications, the asymptotic behavior of the degree distribution is analyzed. Second, a stochastic approximation algorithm is presented to track empirical degree distribution as it evolves over time. The tracking performance of the algorithm is analyzed in terms of mean square error and a functional central limit theorem is presented for the asymptotic tracking error. Also, a Hilbert-space-valued stochastic approximation algorithm that tracks a Markov-modulated probability mass function with support on the set of nonnegative integers is analyzed. [ABSTRACT FROM AUTHOR]

Recent advances in large-margin classification of data residing in general metric spaces (rather than Hilbert spaces) enable classification under various natural metrics, such as string edit and earthmover distance. A general framework developed for this purpose left open the questions of computational efficiency and of providing direct bounds on generalization error. We design a new algorithm for classification in general metric spaces, whose runtime and accuracy depend on the doubling dimension of the data points, and can thus achieve superior classification performance in many common scenarios. The algorithmic core of our approach is an approximate (rather than exact) solution to the classical problems of Lipschitz extension and of nearest neighbor search. The algorithm’s generalization performance is guaranteed via the fat-shattering dimension of Lipschitz classifiers, and we present experimental evidence of its superiority to some common kernel methods. As a by-product, we offer a new perspective on the nearest neighbor classifier, which yields significantly sharper risk asymptotics than the classic analysis. [ABSTRACT FROM AUTHOR]

Compressed sensing is a technique for finding sparse solutions to underdetermined linear systems. This technique relies on properties of the sensing matrix such as the restricted isometry property. Sensing matrices that satisfy this property with optimal parameters are mainly obtained via probabilistic arguments. Deciding whether a given matrix satisfies the restricted isometry property is a nontrivial computational problem. Indeed, it is shown in this paper that restricted isometry parameters cannot be approximated in polynomial time within any constant factor under the assumption that the hidden clique problem is hard. In addition, on the positive side, an improvement on the brute-force enumeration algorithm for checking the restricted isometry property is proposed. [ABSTRACT FROM PUBLISHER]

We study sparse approximation by greedy algorithms. Our contribution is twofold. First, we prove exact recovery with high probability of random \(K\) -sparse signals within \(\lceil K(1+\epsilon )\rceil \) iterations of the orthogonal matching pursuit (OMP). This result shows that in a probabilistic sense, the OMP is almost optimal for exact recovery. Second, we prove the Lebesgue-type inequalities for the weak Chebyshev greedy algorithm, a generalization of the weak orthogonal matching pursuit to the case of a Banach space. The main novelty of these results is a Banach space setting instead of a Hilbert space setting. However, even in the case of a Hilbert space, our results add some new elements to known results on the Lebesgue-type inequalities for the restricted isometry property dictionaries. Our technique is a development of the recent technique created by Zhang. [ABSTRACT FROM AUTHOR]

This paper resolves a common complexity issue in the Bethe approximation of statistical physics and the belief propagation (BP) algorithm of artificial intelligence. The Bethe approximation and the BP algorithm are heuristic methods for estimating the partition function and marginal probabilities in graphical models, respectively. The computational complexity of the Bethe approximation is decided by the number of operations required to solve a set of nonlinear equations, the so-called Bethe equation. Although the BP algorithm was inspired and developed independently, Yedidia, Freeman, and Weiss showed that the BP algorithm solves the Bethe equation if it converges (however, it often does not). This naturally motivates the following question to understand limitations and empirical successes of the Bethe and BP methods: is the Bethe equation computationally easy to solve? We present a message-passing algorithm solving the Bethe equation in a polynomial number of operations for general binary graphical models of \(n\) variables, where the maximum degree in the underlying graph is \(O(\log n)\) . Equivalently, it finds a stationary point of the Bethe free energy function. Our algorithm can be used as an alternative to BP fixing its convergence issue and is the first fully polynomial-time approximation scheme for the BP fixed-point computation in such a large class of graphical models, whereas the approximate fixed-point computation is known to be polynomial parity arguments on directed graphs (PPAD-)hard in general. We believe that our technique is of broader interest to understand the computational complexity of the cavity method in statistical physics. [ABSTRACT FROM AUTHOR]

An approximation of maximum-likelihood decoding over the binary symmetric channel was introduced by Omura in 1972. This decoder employs an iterative, randomized algorithm whose behavior closely mimics that of the simplex algorithm. In this paper, we generalize Omura's decoder to operate on an arbitrary binary-input memoryless channel. Further, we prove that the probability of the generalized Omura decoder (and hence Omura's original decoder) returning a maximum-likelihood codeword approaches 1 as the number of iterations goes to infinity, a result that has hereto remained unproven. [ABSTRACT FROM PUBLISHER]

We consider the estimation of an independent and identically distributed (i.i.d.) (possibly non-Gaussian) vector \bf x\in\BBR^n from measurements \bf y\in\BBR^m obtained by a general cascade model consisting of a known linear transform followed by a probabilistic componentwise (possibly nonlinear) measurement channel. A novel method, called adaptive generalized approximate message passing (adaptive GAMP) is presented. It enables the joint learning of the statistics of the prior and measurement channel along with estimation of the unknown vector \bf x . We prove that, for large i.i.d. Gaussian transform matrices, the asymptotic componentwise behavior of the adaptive GAMP is predicted by a simple set of scalar state evolution equations. In addition, we show that the adaptive GAMP yields asymptotically consistent parameter estimates, when a certain maximum-likelihood estimation can be performed in each step. This implies that the algorithm achieves a reconstruction quality equivalent to the oracle algorithm that knows the correct parameter values. Remarkably, this result applies to essentially arbitrary parametrizations of the unknown distributions, including nonlinear and non-Gaussian ones. The adaptive GAMP methodology thus provides a systematic, general and computationally efficient method applicable to a large range of linear–nonlinear models with provable guarantees. [ABSTRACT FROM AUTHOR]

The nascent field of compressed sensing is founded on the fact that high-dimensional signals with simple structure can be recovered accurately from just a small number of randomized samples. Several specific kinds of structures have been explored in the literature, from sparsity and group sparsity to low-rankness. However, two fundamental questions have been left unanswered. What are the general abstract meanings of structure and simplicity? Do there exist universal algorithms for recovering such simple structured objects from fewer samples than their ambient dimension? In this paper, we address these two questions. Using algorithmic information theory tools such as the Kolmogorov complexity, we provide a unified definition of structure and simplicity. Leveraging this new definition, we develop and analyze an abstract algorithm for signal recovery motivated by Occam's Razor. Minimum complexity pursuit (MCP) requires approximately 2\kappa randomized samples to recover a signal of complexity \kappa and ambient dimension n. We also discuss the performance of the MCP in the presence of measurement noise and with approximately simple signals. [ABSTRACT FROM PUBLISHER]

We present a deterministic algorithm for finding the significant Fourier frequencies of a given signal f\in\BBC^N and their approximate Fourier coefficients in running time and sample complexity polynomial in \log N, L1(\widehat f)/\Vert\widehat f\Vert2, and 1/\tau, where the significant frequencies are those occupying at least a \tau-fraction of the energy of the signal, and L1(\widehat f) denotes the L1-norm of the Fourier transform of f. Furthermore, the algorithm is robust to additive random noise. This strictly extends the class of compressible/Fourier sparse signals efficiently handled by previous deterministic algorithms for signals in \BBC^N. As a central tool, we prove there is a deterministic algorithm that takes as input N, \varepsilon and an arithmetic progression P in \BBZN, runs in time polynomial in \ln N and 1/\varepsilon, and returns a set AP that \varepsilon-approximates P in \BBZN in the sense that \vert\mathop\BBEx\in APe^{2\pi i\omega x/N}-\mathop\BBEx\in Pe^{2\pi i\omega x/N}\vert <\varepsilon for all \omega=0,\ldots, N-1. In other words, we show there is an explicit construction of sets AP of size polynomial in \ln N and 1/\varepsilon that \varepsilon-approximate given arithmetic progressions P in \BBZN. This extends results on small-bias sets, which are sets approximating the entire domain, to sets approximating a given arithmetic progression; this result may be of independent interest. [ABSTRACT FROM PUBLISHER]

The table of contents for the November 2013 issue of "IEEE Transactions on Information Theory" is presented.

In this paper, a low-complexity delay-aware cross-layer scheduling algorithm for two-hop relay communication systems is proposed. The complex interactions of the queues at the source node and the M relay nodes (RSs) are modeled as an infinite horizon average reward Markov decision process (MDP), whose state space involves the joint queue state information (QSI) of the queues at the source node and the M RSs as well as the joint channel state information (CSI) of all S-R and R-D links. To address the curse of dimensionality, an equivalent MDP formulation is first proposed, where the system state depends only on global QSI. Furthermore, using approximate MDP and stochastic learning, an auction-based distributed online learning algorithm is derived, where each node iteratively estimates a per-node value function based on real-time observations of the local CSI and local QSI as well as signaling between relays. The combined distributed learning converges almost surely to a global optimal solution for large arrivals. Finally, it is showed by simulations that the proposed scheme achieves significant gain compared with various baselines such as the conventional CSIT-only control and the throughput optimal control (in stability sense). [ABSTRACT FROM AUTHOR]

In this paper, a distributed stochastic approximation algorithm is studied. Applications of such algorithms include decentralized estimation, optimization, control or computing. The algorithm consists in two steps: a local step, where each node in a network updates a local estimate using a stochastic approximation algorithm with decreasing step size, and a gossip step, where a node computes a local weighted average between its estimates and those of its neighbors. Convergence of the estimates toward a consensus is established under weak assumptions. The approach relies on two main ingredients: the existence of a Lyapunov function for the mean field in the agreement subspace, and a contraction property of the random matrices of weights in the subspace orthogonal to the agreement subspace. A second-order analysis of the algorithm is also performed under the form of a central limit Theorem. The Polyak-averaged version of the algorithm is also considered. [ABSTRACT FROM AUTHOR]

Compressive sensing (CS) has recently emerged as a powerful framework for acquiring sparse signals. The bulk of the CS literature has focused on the case where the acquired signal has a sparse or compressible representation in an orthonormal basis. In practice, however, there are many signals that cannot be sparsely represented or approximated using an orthonormal basis, but that do have sparse representations in a redundant dictionary. Standard results in CS can sometimes be extended to handle this case provided that the dictionary is sufficiently incoherent or well conditioned, but these approaches fail to address the case of a truly redundant or overcomplete dictionary. In this paper, we describe a variant of the iterative recovery algorithm CoSaMP for this more challenging setting. We utilize the \mbi D-RIP, a condition on the sensing matrix analogous to the well-known restricted isometry property. In contrast to prior work, the method and analysis are “signal-focused”; that is, they are oriented around recovering the signal rather than its dictionary coefficients. Under the assumption that we have a near-optimal scheme for projecting vectors in signal space onto the model family of candidate sparse signals, we provide provable recovery guarantees. Developing a practical algorithm that can provably compute the required near-optimal projections remains a significant open problem, but we include simulation results using various heuristics that empirically exhibit superior performance to traditional recovery algorithms. [ABSTRACT FROM AUTHOR]

Recursive algorithms for the estimation of mixtures of densities have attracted a lot of attention in the last 10 years. Here an algorithm for recursive estimation is studied. It complements existing approaches in the literature, as it is based on conditions that are usually very weak. For example, the parameter space over which the mixture is taken does not need to be necessarily bounded. The essence of the procedure is to combine density estimation via empirical characteristic function together with an iterative Hilbert space approximation algorithm. The conditions for consistency of the estimator are verified for three important statistical problems. A simulation study is also included. [ABSTRACT FROM AUTHOR]

A method for efficiently constructing polar codes is presented and analyzed. Although polar codes are explicitly defined, straightforward construction is intractable since the resulting polar bit-channels have an output alphabet that grows exponentially with the code length. Thus, the core problem that needs to be solved is that of faithfully approximating a bit-channel with an intractably large alphabet by another channel having a manageable alphabet size. We devise two approximation methods which “sandwich” the original bit-channel between a degraded and an upgraded version thereof. Both approximations can be efficiently computed and turn out to be extremely close in practice. We also provide theoretical analysis of our construction algorithms, proving that for any fixed \varepsilon > 0 and all sufficiently large code lengths n, polar codes whose rate is within \varepsilon of channel capacity can be constructed in time and space that are both linear in n. [ABSTRACT FROM AUTHOR]

We study the (constrained) least-squares regression as well as multiple response least-squares regression and ask the question of whether a subset of the data, a coreset, suffices to compute a good approximate solution to the regression. We give deterministic, low-order polynomial-time algorithms to construct such coresets with approximation guarantees, together with lower bounds indicating that there is not much room for improvement upon our results. [ABSTRACT FROM AUTHOR]

Index coding has received considerable attention recently motivated in part by applications such as fast video-on-demand and efficient communication in wireless networks and in part by its connection to network coding. Optimal encoding schemes and efficient heuristics were studied in various settings, while also leading to new results for network coding such as improved gaps between linear and non-linear capacity as well as hardness of approximation. The problem of broadcasting with side information, a generalization of the index coding problem, begins with a sender and sets of users and messages. Each user possesses a subset of the messages and desires an additional message from the set. The sender wishes to broadcast a message so that on receipt of the broadcast each user can compute her desired message. The fundamental parameter of interest is the broadcast rate, \beta , the average communication cost for sufficiently long broadcasts. Though there have been many new nontrivial bounds on \beta by Bar-Yossef (2006), Lubetzky and Stav (2007), Alon (2008), and Blasiak (2011) there was no known polynomial-time algorithm for approximating \beta within a nontrivial factor, and the exact value of \beta remained unknown for all nontrivial instances. Using the information theoretic linear program introduced in Blasiak (2011), we give a polynomial-time algorithm for recognizing instances with \beta = 2 and pinpoint \beta precisely for various classes of graphs (e.g., various Cayley graphs of cyclic groups). Further, extending ideas from Ramsey theory, we give a polynomial-time algorithm with a nontrivial approximation ratio for computing \beta . Finally, we provide insight into the quality of previous bounds by giving constructions showing separations between \beta and the respective bounds. In particular, we construct graphs where \beta is uniformly bounded while its upper bound derived from the naïve encoding scheme is polynomially worse. [ABSTRACT FROM AUTHOR]

We present the tree-structure expectation propagation (Tree-EP) algorithm to decode low-density parity-check (LDPC) codes over discrete memoryless channels (DMCs). Expectation propagation generalizes belief propagation (BP) in two ways. First, it can be used with any exponential family distribution over the cliques in the graph. Second, it can impose additional constraints on the marginal distributions. We use this second property to impose pairwise marginal constraints over pairs of variables connected to a check node of the LDPC code's Tanner graph. Thanks to these additional constraints, the Tree-EP marginal estimates for each variable in the graph are more accurate than those provided by BP. We also reformulate the Tree-EP algorithm for the binary erasure channel (BEC) as a peeling-type algorithm (TEP) and we show that the algorithm has the same computational complexity as BP and it decodes a higher fraction of errors. We describe the TEP decoding process by a set of differential equations that represents the expected residual graph evolution as a function of the code parameters. The solution of these equations is used to predict the TEP decoder performance in both the asymptotic regime and the finite-length regimes over the BEC. While the asymptotic threshold of the TEP decoder is the same as the BP decoder for regular and optimized codes, we propose a scaling law for finite-length LDPC codes, which accurately approximates the TEP improved performance and facilitates its optimization. [ABSTRACT FROM PUBLISHER]

Compressed sensing posits that, within limits, one can undersample a sparse signal and yet reconstruct it accurately. Knowing the precise limits to such undersampling is important both for theory and practice. We present a formula that characterizes the allowed undersampling of generalized sparse objects. The formula applies to approximate message passing (AMP) algorithms for compressed sensing, which are here generalized to employ denoising operators besides the traditional scalar soft thresholding denoiser. This paper gives several examples including scalar denoisers not derived from convex penalization—the firm shrinkage nonlinearity and the minimax nonlinearity—and also nonscalar denoisers—block thresholding, monotone regression, and total variation minimization. Let the variables \varepsilon = k/N and \delta = n/N denote the generalized sparsity and undersampling fractions for sampling the k-generalized-sparse N-vector x0 according to y=Ax0. Here, A is an n\times N measurement matrix whose entries are iid standard Gaussian. The formula states that the phase transition curve \delta = \delta (\varepsilon ) separating successful from unsuccessful reconstruction of x0 by AMP is given by \delta = M(\varepsilon \vert Denoiser) where M(\varepsilon \vert Denoiser) denotes the per-coordinate minimax mean squared error (MSE) of the specified, optimally tuned denoiser in the directly observed problem y = x + z. In short, the phase transition of a noiseless undersampling problem is identical to the minimax MSE in a denoising problem. We prove that this formula follows from state evolution and present numerical results validating it in a wide range of settings. The above formula generates numerous new insights, both in the scalar and in the nonscalar cases. [ABSTRACT FROM PUBLISHER]

The closest vector problem (CVP) and shortest (nonzero) vector problem (SVP) are the core algorithmic problems on Euclidean lattices. They are central to the applications of lattices in many problems of communications and cryptography. Kannan's embedding technique is a powerful technique for solving the approximate CVP; yet, its remarkable practical performance is not well understood. In this paper, the embedding technique is analyzed from a bounded distance decoding (BDD) viewpoint. We present two complementary analyses of the embedding technique: we establish a reduction from BDD to Hermite SVP (via unique SVP), which can be used along with any Hermite SVP solver (including, among others, the Lenstra, Lenstra and Lovász (LLL) algorithm), and show that, in the special case of LLL, it performs at least as well as Babai's nearest plane algorithm (LLL-aided successive interference cancellation). The former analysis helps us to explain the folklore practical observation that unique SVP is easier than standard approximate SVP. It is proven that when the LLL algorithm is employed, the embedding technique can solve the CVP provided that the noise norm is smaller than a decoding radius \lambda1/(2\gamma), where \lambda1 is the minimum distance of the lattice, and \gamma\approx O(2^n/4). This substantially improves the previously best known correct decoding bound \gamma\approxO(2^n). Focusing on the applications of BDD to decoding of multiple-input multiple-output systems, we also prove that BDD of the regularized lattice is optimal in terms of the diversity–multiplexing gain tradeoff, and propose practical variants of embedding decoding which require no knowledge of the minimum distance of the lattice and/or further improve the error performance. [ABSTRACT FROM PUBLISHER]

It has recently been observed that the permanent of a nonnegative square matrix, i.e., of a square matrix containing only nonnegative real entries, can very well be approximated by solving a certain Bethe free energy function minimization problem with the help of the sum–product algorithm. We call the resulting approximation of the permanent the Bethe permanent. In this paper, we give reasons why this approach to approximating the permanent works well. Namely, we show that the Bethe free energy function is convex and that the sum–product algorithm finds its minimum efficiently. We then discuss the fact that the permanent is lower bounded by the Bethe permanent, and we comment on potential upper bounds on the permanent based on the Bethe permanent. We also present a combinatorial characterization of the Bethe permanent in terms of permanents of so-called lifted versions of the matrix under consideration. Moreover, we comment on possibilities to modify the Bethe permanent so that it approximates the permanent even better, and we conclude the paper with some observations and conjectures about permanent-based pseudocodewords and permanent-based kernels. [ABSTRACT FROM AUTHOR]

Principal component analysis plays a central role in statistics, engineering, and science. Because of the prevalence of corrupted data in real-world applications, much research has focused on developing robust algorithms. Perhaps surprisingly, these algorithms are unequipped—indeed, unable—to deal with outliers in the high-dimensional setting where the number of observations is of the same magnitude as the number of variables of each observation, and the dataset contains some (arbitrarily) corrupted observations. We propose a high-dimensional robust principal component analysis algorithm that is efficient, robust to contaminated points, and easily kernelizable. In particular, our algorithm achieves maximal robustness—it has a breakdown point of 50% (the best possible), while all existing algorithms have a breakdown point of zero. Moreover, our algorithm recovers the optimal solution exactly in the case where the number of corrupted points grows sublinearly in the dimension. [ABSTRACT FROM AUTHOR]

We present a joint message passing approach that combines belief propagation and the mean field approximation. Our analysis is based on the region-based free energy approximation method proposed by Yedidia et al. We show that the message passing fixed-point equations obtained with this combination correspond to stationary points of a constrained region-based free energy approximation. Moreover, we present a convergent implementation of these message passing fixed-point equations provided that the underlying factor graph fulfills certain technical conditions. In addition, we show how to include hard constraints in the part of the factor graph corresponding to belief propagation. Finally, we demonstrate an application of our method to iterative channel estimation and decoding in an orthogonal frequency division multiplexing system. [ABSTRACT FROM AUTHOR]

For an ordered set, consider the model of distributions P for which an element that precedes another element is considered the more significant one in the sense that the implication a\leq b\Rightarrow P(a)\geq P(b) holds. It will be shown that if the ordered set is a finite co-tree, then the universal predictor for the model or, equivalently, the corresponding universal code, can be determined exactly via an algorithm of low complexity. Natural relations to problems on the computation of capacity and on the determination of information projections are established. More surprisingly, a direct connection to a problem of isotone regression also appears possible. [ABSTRACT FROM AUTHOR]

Suppose that we observe noisy linear measurements of an unknown signal that can be modeled as the sum of two component signals, each of which arises from a nonlinear submanifold of a high-dimensional ambient space. We introduce successive projections onto incoherent manifolds (SPIN), a first-order projected gradient method to recover the signal components. Despite the nonconvex nature of the recovery problem and the possibility of underdetermined measurements, SPIN provably recovers the signal components, provided that the signal manifolds are incoherent and that the measurement operator satisfies a certain restricted isometry property. SPIN significantly extends the scope of current recovery models and algorithms for low-dimensional linear inverse problems and matches (or exceeds) the current state of the art in terms of performance. [ABSTRACT FROM AUTHOR]

Determining the minimum distance of a linear code is one of the most important problems in algorithmic coding theory. The exact version of the problem was shown to be NP-complete by Vardy. The gap version of the problem was shown to be NP-hard for any constant factor under a randomized reduction in an earlier work. It was shown in the same paper that the minimum distance problem is not approximable in randomized polynomial time to the factor 2^\log^1-\epsilonn unless NP\subseteq RTIME(2^polylog(n)). In this paper, we derandomize the reduction and thus prove that there is no deterministic polynomial time algorithm to approximate the minimum distance to any constant factor unless P=NP. We also prove that the minimum distance is not approximable in deterministic polynomial time to the factor 2^\log^1-\epsilonn unless NP\subseteq DTIME(2^polylog(n)). As the main technical contribution, for any constant 2/3 < \rho < 1, we present a deterministic algorithm that given a positive integer s, runs in time poly(s) and constructs a code \cal C of length poly(s) with an explicit Hamming ball of radius \rho d(\cal C), such that the projection at the first s coordinates sends the codewords in the ball surjectively onto a linear subspace of dimension s, where d(\cal C) denotes the minimum distance of \cal C. The codes are obtained by concatenating Reed–Solomon codes with Hadamard codes. [ABSTRACT FROM PUBLISHER]

A subgroup permutation code is a set of permutations on n symbols with the property that its elements are closed under the operation of composition. In this paper, we give inapproximability results for the minimum and maximum weight problems of subgroup permutation codes under several well-known metrics. Based on previous works, we prove that under Hamming, Lee, Cayley, Kendall's tau, Ulam's, and \ell p distance metrics, 1) there is no polynomial-time 2^\log ^1-\epsilon n-approximation algorithm for the minimum weight problem for any constant \epsilon >0 unless NP\subseteq DTIME(2^ polylog(n)) (quasi-polynomial time), and 2) there is no polynomial-time r-approximation algorithm for the minimum weight problem for any constant r >1 unless P= NP. Under \ell \infty -metric, we prove that it is NP-hard to approximate the minimum weight problem within factor 2-\epsilon for any constant \epsilon >0. We also prove that for any constant \epsilon >0, it is NP-hard to approximate the maximum weight within ^p \!\!\! \sqrt 3\over 2-\epsilon under \ell p distance metric, and within 3\over 2-\epsilon under Hamming, Lee, Cayley, Kendall's tau, and Ulam's distance metrics. [ABSTRACT FROM PUBLISHER]

We study the effect on diversity of using the sphere encoder-based vector perturbation (VP) technique of Peel and the lattice reduction-aided techniques (Babai approximations) of Windpassinger on a subset of the transmitted symbols. For a system with n diversity channels, we prove that the diversity order gap between the maximum diversity of n achieved by the full-size VP and the minimum diversity of 1 provided by linear precoding can be bridged by applying VP to a group of transmitted symbols. In particular, we prove that the diversity order is n-l, where l is the number of symbols that are not vector-perturbed. We show that this result holds true for lattice-reduction with both the rounding-off and nearest plane Babai approximations. The result shows that in terms of diversity, the group of vector-perturbed users counts as a single user. In fact, in a multiple-input and multiple-output Gaussian broadcast channel with l linearly precoded users, we can add up to n-l VP users and the diversity order for all users will decrease only by one, irrespective of how many VP users are added. [ABSTRACT FROM PUBLISHER]

We consider the problem of finding high-dimensional approximate nearest neighbors. We introduce an old style probabilistic formulation instead of the more general locality sensitive hashing (LSH) formulation, and show that at least for sparse problems it recognizes much more efficient algorithms than the sparseness destroying LSH random projections. Efficient algorithms for homogeneous (all coordinates have the same probability distribution) problems are well known, the most famous reference being the work by Broder in 1998. The main theme of this paper is to find its “best” generalization to heterogeneous (different coordinate probabilities) problems. We find a practical algorithm which is asymptotically best in a wide natural class of algorithms. Readers interested in the more complicated very best (at least up to date) can look up our previous work in 2010. The analysis of our algorithms reveals that its complexity is governed by an information like function, which we call “small leaves bucketing forest information.” Any doubts whether it is “information” are dispelled by the aforementioned work. [ABSTRACT FROM PUBLISHER]

We formulate and solve the problem of optimal channel coding and flow-rate control for serving deadline-constrained traffic with average delivery ratio requirements (typical of multimedia streaming and interactive real-time applications) over time-varying channels. To that end, we first characterize the largest set of arrival processes (rather than rates) whose deadline and delivery ratio requirements can be satisfied. Then, we propose a dynamic (channel) coding algorithm that provably satisfies the requirements of any arrival process in this region. This optimal dynamic algorithm evolves through simple iterations to utilize a combination of pricing and finite-horizon dynamic programming operations. Next, we proposed two low-complexity approximations of the algorithm that has provable performance. We also extend the setup to allow for a flow controller that adjusts the incoming flow rates to satisfy their delivery ratio constraints when the arrival process is unknown but controllable. We propose a joint dynamic coding and a rate control algorithm to solve this problem, and prove its stability under the stochastic system operation. We also apply these general results to an important wireless down-link broadcast scenario with and without random network coding capabilities. Our theoretical work is supported by extensive numerical studies, which also reveal that our dynamic coding strategy outperforms any static coding strategy by opportunistically exploiting the statistical variations in the arrival and channel processes. [ABSTRACT FROM PUBLISHER]

We consider codes over permutations under the infinity norm. Given such a code, we show that a simple relabeling operation, which produces an isomorphic code, may drastically change the minimal distance of the code. Thus, we may choose a code structure for efficient encoding procedures, and then optimize the code's minimal distance via relabeling. To establish that the relabeling problem is hard and is of interest, we formally define it and show that all codes may be relabeled to get a minimal distance at most 2. On the other hand, the decision problem of whether a code may be relabeled to distance 2 or more is shown to be NP-complete, and calculating the best achievable minimal distance after relabeling is proved to be hard to approximate up to a factor of 2. We then consider general bounds on the relabeling problem. We specifically construct the optimal relabeling for transitive cyclic groups. We conclude with the main result—a general probabilistic bound, which we then use to show both the \mathopAGL(p) group and the dihedral group on p elements may be relabeled to a minimal distance of p-O(\sqrtp\ln p). [ABSTRACT FROM PUBLISHER]

We consider the problem of generating a connected identifying code for an arbitrary graph. After a brief motivation, we show that the decision problem regarding the existence of such a code is NP-complete, and we propose a novel polynomial-time approximation \tt ConnectID that transforms any identifying code into a connected version of at most twice the size, thus leading to an asymptotically optimal approximation bound. When the input identifying code to \tt ConnectID is robust to graph distortions, we show that the size of the resulting connected code is related to the best error-correcting code of a given minimum distance, permitting the use of known coding bounds. In addition, we show that the size of the input and output codes converge for increasing robustness, meaning that highly robust identifying codes are almost connected. Finally, we evaluate the performance of \tt ConnectID on various random graphs. Simulations for Erdős–Rényi random graphs show that the connected codes generated are actually at most 25% larger than their unconnected counterparts, while simulations with robust input identifying codes confirm that robustness often provides connectivity for free. [ABSTRACT FROM PUBLISHER]