Location-based services (LBS) are an integral part of the mobile ecosystem today, relying on the Global Positioning System (GPS) and other technologies. However, while these technologies have been highly successful at positioning outdoors, they either fail to obtain a fix or do not provide the necessary accuracy indoors. In this paper, we will describe a low-cost high-accuracy indoor positioning system that can run on mobile devices. The system has high-accuracy because it combines several sources of information, thus improving accuracy over using any one of them alone. The cost is low because the sources of information used by the system such as WiFi measurements, inertial sensor data and building maps are readily available for use on a mobile device.

In this paper, we study the redundancy of Huffman codes. In particular, we consider sources for which the probability of one of the source symbols is known. We prove a conjecture of Ye and Yeung regarding the upper bound on the redundancy of such Huffman codes, which yields in a tight upper bound. We also derive a tight lower bound for the redundancy under the same assumption. We further apply the method introduced in this paper to other related problems. It is shown that several other previously known bounds with different constraints follow immediately from our results.

We present some simple information inequalities on binary sums of Bernoulli random variables that appear to be new. Consequences for information across binary input memoryless symmetric channels are also presented.

Computing the partition function and the marginals of a global probability distribution are two important issues in any probabilistic inference problem. In a previous work, we presented sub-tree based upper and lower bounds on the partition function of a given probabilistic inference problem. Using the entropies of the sub-trees we proved an inequality that compares the lower bounds obtained from different sub-trees. In this paper we investigate the properties of one specific lower bound, namely the lower bound computed by the minimum entropy sub-tree. We also investigate the relationship between the minimum entropy sub-tree and the sub-tree that gives the best lower bound.

In this paper we propose a notion of EXIT functions for LT-codes and Raptor codes, and discuss some of their useful properties that can be used to design good codes. We will further use these results to derive interesting conclusions on ranks of random matrices. New expressions for the asymptotic ranks of certain classes of random binary matrices are derived and the results are compared to previously known bounds and results.

A probabilistic inference problem is concerned with computing the partition function and the marginals of a global probability distribution. We investigate upper and lower bounds on the partition function of a given inference problem. Our bounds depend on the partition function of any sub-junction tree of a given junction graph representing the inference problem. In a theorem we compare such bounds using the entropies of the sub-junction trees. Finally we propose a greedy algorithm that computes low-complexity bounds on the partition function. Simulation results on two-dimensional grids are reported

In this paper we study the redundancy of Huffman codes. In particular, we consider sources for which the probability of one of the source symbols is known. We prove a conjecture of Ye and Yeung regarding the upper bound on the redundancy of such Huffman codes, which yields in a tight upper bound. We also derive a tight lower bound for the redundancy under the same assumption. We further apply the method introduced in this paper to other related problems. It is shown that several other previously known bounds with different constraints follow immediately from our results.

In this paper we describe some practical aspects of the design process of good Raptor codes for finite block lengths over arbitrary binary input symmetric channels. In particular we introduce a simple model for the finite-length convergence behavior of the iterative decoding algorithm based on density evolution, and propose a practical design procedure. We report simulation results for some example codes.

In this letter, we apply the Kikuchi approximation method to the problem of joint decoding of a low-density parity-check code and a partial-response channel. The Kikuchi method is, in general, more powerful than the conventional loopy belief propagation (BP) algorithm, and can produce better approximations to an underlying inference problem. We will first review the Kikuchi approximation method and the generalized BP algorithm, which is an iterative message-passing algorithm based on this method. We will then report simulation results which show that the Kikuchi method outperforms the best conventional iterative method

Recent work has related the belief propagation algorithm for probabilistic inference problem to some approximations to the free energy function in statistical physics. In this paper we investigate some properties of one such approximation, called the Bethe-Kikuchi approximation. We also derive low-complexity upper and lower bounds on the partition function, i.e. the global normalization constant, for a given inference problem

We consider a simple network, where a source and destination node are connected with a line of erasure channels. It is well known that in order to achieve the min-cut capacity, the intermediate nodes are required to process the information. We propose coding schemes for this setting, and discuss each scheme in terms of complexity, delay, achievable rate, memory requirement, and adaptability to unknown channel parameters. We also briefly discuss how these schemes can be extended to more general networks

In this letter, we examine a general method of approximation, known as the Kikuchi approximation method, for finding the marginals of a product distribution, as well as the corresponding partition function. The Kikuchi approximation method defines a certain constrained optimization problem, called the Kikuchi problem, and treats its stationary points as approximations to the desired marginals. We show how to associate a graph to any Kikuchi problem and describe a class of local message-passing algorithms along the edges of any such graph, which attempt to find the solutions to the problem. Implementation of these algorithms on graphs with fewer edges requires fewer operations in each iteration. We therefore characterize minimal graphs for a Kikuchi problem, which are those with the minimum number of edges. We show with empirical results that these simpler algorithms often offer significant savings in computational complexity, without suffering a loss in the convergence rate. We give conditions for the convexity of a given Kikuchi problem and the exactness of the approximations in terms of the loops of the minimal graph. More precisely, we show that if the minimal graph is cycle free, then the Kikuchi approximation method is exact, and the converse is also true generically. Together with the fact that in the cycle-free case, the iterative algorithms are equivalent to the well-known belief propagation algorithm, our results imply that, generically, the Kikuchi approximation method can be exact if and only if traditional junction tree methods could also solve the problem exactly.

In this paper, we develop a measure-theoretic version of the junction tree algorithm to compute desired marginals of a product function. We reformulate the problem in a measure-theoretic framework, where the desired marginals are viewed as corresponding conditional expectations of a product of random variables. We generalize the notions of independence and junction trees to collections of /spl sigma/-fields on a space with a signed measure. We provide an algorithm to find such a junction tree when one exists. We also give a general procedure to augment the /spl sigma/-fields to create independencies, which we call "lifting." This procedure is the counterpart of the moralization and triangulation procedure in the conventional generalized distributive law (GDL) framework, in order to guarantee the existence of a junction tree. Our procedure includes the conventional GDL procedure as a special case. However, it can take advantage of structures at the atomic level of the sample space to produce junction tree-based algorithms for computing the desired marginals that are less complex than those GDL can discover, as we argue through examples. Our formalism gives a new way by which one can hope to find low-complexity algorithms for marginalization problems.

Two decoding schedules and the corresponding serialized architectures for low-density parity-check (LDPC) decoders are presented. They are applied to codes with parity-check matrices generated either randomly or using geometric properties of elements in Galois fields. Both decoding schedules have low computational requirements. The original concurrent decoding schedule has a large storage requirement that is dependent on the total number of edges in the underlying bipartite graph, while a new, staggered decoding schedule which uses an approximation of the belief propagation, has a reduced memory requirement that is dependent only on the number of bits in the block. The performance of these decoding schedules is evaluated through simulations on a magnetic recording channel.