OpenRaiser/Intern-Atlas huggingface dataset:
Asymptotic stability and capacity results for a broad family of power adjustment rules: Expanded discussion
Venue: arXiv cs.IT 2009
Year: 2009

In any wireless communication environment in which a transmitter creates interference to the others, a system of non-linear equations arises. Its form (for 2 terminals) is p1=g1(p2;a1) and p2=g2(p1;a2), with p1, p2 power levels; a1, a2 quality-of-service (QoS) targets; and g1, g2 functions akin to "interference functions" in Yates (JSAC, 13(7):1341-1348, 1995). Two fundamental questions are: (1) does the system have a solution?; and if so, (2) what is it?. (Yates, 1995) shows that IF the system has a solution, AND the "interference functions" satisfy some simple properties, a "greedy" power adjustment process will always converge to a solution. We show that, if the power-adjustment functions have similar properties to those of (Yates, 1995), and satisfy a condition of the simple form gi(1,1,...,1)<1, then the system has a unique solution that can be found iteratively. As examples, feasibility conditions for macro-diversity and multiple-connection receptions are given. Informally speaking, we complement (Yates, 1995) by adding the feasibility condition it lacked. Our analysis is based on norm concepts, and the Banach's contraction-mapping principle.
Capacity regions of two new classes of 2-receiver broadcast channels
Venue: arXiv cs.IT 2009
Year: 2009

Motivated by a simple broadcast channel, we generalize the notions of a less noisy receiver and a more capable receiver to an essentially less noisy receiver and an essentially more capable receiver respectively. We establish the capacity regions of these classes by borrowing on existing techniques to obtain the characterization of the capacity region for certain new and interesting classes of broadcast channels. We also establish the relationships between the new classes and the existing classes.
An Information Theoretic Analysis of Single Transceiver Passive RFID Networks
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we study single transceiver passive RFID networks by modeling the underlying physical system as a special cascade of a certain broadcast channel (BCC) and a multiple access channel (MAC), using a "nested codebook" structure in between. The particular application differentiates this communication setup from an ordinary cascade of a BCC and a MAC, and requires certain structures such as "nested codebooks", impurity channels or additional power constraints. We investigate this problem both for discrete alphabets, where we characterize the achievable rate region, as well as for continuous alphabets with additive Gaussian noise, where we provide the capacity region. Hence, we establish the maximal achievable error free communication rates for this particular problem which constitutes the fundamental limit that is achievable by any TDMA based RFID protocol and the achievable rate region for any RFID protocol for the case of continuous alphabets under additive Gaussian noise.
SPARLS: A Low Complexity Recursive $\mathcal{L}_1$-Regularized Least Squares Algorithm
Venue: arXiv cs.IT 2009
Year: 2009

We develop a Recursive $\mathcal{L}_1$-Regularized Least Squares (SPARLS) algorithm for the estimation of a sparse tap-weight vector in the adaptive filtering setting. The SPARLS algorithm exploits noisy observations of the tap-weight vector output stream and produces its estimate using an Expectation-Maximization type algorithm. Simulation studies in the context of channel estimation, employing multi-path wireless channels, show that the SPARLS algorithm has significant improvement over the conventional widely-used Recursive Least Squares (RLS) algorithm, in terms of both mean squared error (MSE) and computational complexity.
Quantized Compressive Sensing
Venue: arXiv cs.IT 2009
Year: 2009

We study the average distortion introduced by scalar, vector, and entropy coded quantization of compressive sensing (CS) measurements. The asymptotic behavior of the underlying quantization schemes is either quantified exactly or characterized via bounds. We adapt two benchmark CS reconstruction algorithms to accommodate quantization errors, and empirically demonstrate that these methods significantly reduce the reconstruction distortion when compared to standard CS techniques.
Distributed Preemption Decisions: Probabilistic Graphical Model, Algorithm and Near-Optimality
Venue: arXiv cs.LG 2009
Year: 2009

Cooperative decision making is a vision of future network management and control. Distributed connection preemption is an important example where nodes can make intelligent decisions on allocating resources and controlling traffic flows for multi-class service networks. A challenge is that nodal decisions are spatially dependent as traffic flows trespass multiple nodes in a network. Hence the performance-complexity trade-off becomes important, i.e., how accurate decisions are versus how much information is exchanged among nodes. Connection preemption is known to be NP-complete. Centralized preemption is optimal but computationally intractable. Decentralized preemption is computationally efficient but may result in a poor performance. This work investigates distributed preemption where nodes decide whether and which flows to preempt using only local information exchange with neighbors. We develop, based on the probabilistic graphical models, a near-optimal distributed algorithm. The algorithm is used by each node to make collectively near-optimal preemption decisions. We study trade-offs between near-optimal performance and complexity that corresponds to the amount of information-exchange of the distributed algorithm. The algorithm is validated by both analysis and simulation.
Approximate inference on planar graphs using Loop Calculus and Belief Propagation
Venue: arXiv cs.AI 2009
Year: 2009

We introduce novel results for approximate inference on planar graphical models using the loop calculus framework. The loop calculus (Chertkov and Chernyak, 2006) allows to express the exact partition function of a graphical model as a finite sum of terms that can be evaluated once the belief propagation (BP) solution is known. In general, full summation over all correction terms is intractable. We develop an algorithm for the approach presented in (Certkov et al., 2008) which represents an efficient truncation scheme on planar graphs and a new representation of the series in terms of Pfaffians of matrices. We analyze the performance of the algorithm for the partition function approximation for models with binary variables and pairwise interactions on grids and other planar graphs. We study in detail both the loop series and the equivalent Pfaffian series and show that the first term of the Pfaffian series for the general, intractable planar model, can provide very accurate approximations. The algorithm outperforms previous truncation schemes of the loop series and is competitive with other state-of-the-art methods for approximate inference.
A New Universal Random-Coding Bound for Average Probability Error Exponent for Multiple-Access Channels
Venue: arXiv cs.IT 2009
Year: 2009

In this work, a new upper bound for average error probability of a two-user discrete memoryless (DM) multiple-access channel (MAC) is derived. This bound can be universally obtained for all discrete memoryless MACs with given input and output alphabets. This is the first bound of this type that explicitly uses the method of expurgation. It is shown that the exponent of this bound is greater than or equal to those of previously known bounds.
The Symmetries of the $π$-metric
Venue: arXiv cs.IT 2009
Year: 2009

Let V be an n-dimensional vector space over a finite field F_q. We consider on V the $π$-metric recently introduced by K. Feng, L. Xu and F. J. Hickernell. In this short note we give a complete description of the group of symmetries of V under the $π$-metric.
A nonclassical symbolic theory of working memory, mental computations, and mental set
Venue: arXiv cs.AI 2009
Year: 2009

The paper tackles four basic questions associated with human brain as a learning system. How can the brain learn to (1) mentally simulate different external memory aids, (2) perform, in principle, any mental computations using imaginary memory aids, (3) recall the real sensory and motor events and synthesize a combinatorial number of imaginary events, (4) dynamically change its mental set to match a combinatorial number of contexts? We propose a uniform answer to (1)-(4) based on the general postulate that the human neocortex processes symbolic information in a "nonclassical" way. Instead of manipulating symbols in a read/write memory, as the classical symbolic systems do, it manipulates the states of dynamical memory representing different temporary attributes of immovable symbolic structures stored in a long-term memory. The approach is formalized as the concept of E-machine. Intuitively, an E-machine is a system that deals mainly with characteristic functions representing subsets of memory pointers rather than the pointers themselves. This nonclassical symbolic paradigm is Turing universal, and, unlike the classical one, is efficiently implementable in homogeneous neural networks with temporal modulation topologically resembling that of the neocortex.
A Generalized Carpenter's Rule Theorem for Self-Touching Linkages
Venue: arXiv cs.CG 2009
Year: 2009

The Carpenter's Rule Theorem states that any chain linkage in the plane can be folded continuously between any two configurations while preserving the bar lengths and without the bars crossing. However, this theorem applies only to strictly simple configurations, where bars intersect only at their common endpoints. We generalize the theorem to self-touching configurations, where bars can touch but not properly cross. At the heart of our proof is a new definition of self-touching configurations of planar linkages, based on an annotated configuration space and limits of nontouching configurations. We show that this definition is equivalent to the previously proposed definition of self-touching configurations, which is based on a combinatorial description of overlapping features. Using our new definition, we prove the generalized Carpenter's Rule Theorem using a topological argument. We believe that our topological methodology provides a powerful tool for manipulating many kinds of self-touching objects, such as 3D hinged assemblies of polygons and rigid origami. In particular, we show how to apply our methodology to extend to self-touching configurations universal reconfigurability results for open chains with slender polygonal adornments, and single-vertex rigid origami with convex cones.
Condition for Energy Efficient Watermarking with Random Vector Model without WSS Assumption
Venue: arXiv cs.MM 2009
Year: 2009

Energy efficient watermarking preserves the watermark energy after linear attack as much as possible. We consider in this letter non-stationary signal models and derive conditions for energy efficient watermarking under random vector model without WSS assumption. We find that the covariance matrix of the energy efficient watermark should be proportional to host covariance matrix to best resist the optimal linear removal attacks. In WSS process our result reduces to the well known power spectrum condition. Intuitive geometric interpretation of the results are also discussed which in turn also provide more simpler proof of the main results.
Exploiting the Path Propagation Time Differences in Multipath Transmission with FEC
Venue: arXiv cs.NI 2009
Year: 2009

We consider a transmission of a delay-sensitive data stream from a single source to a single destination. The reliability of this transmission may suffer from bursty packet losses - the predominant type of failures in today's Internet. An effective and well studied solution to this problem is to protect the data by a Forward Error Correction (FEC) code and send the FEC packets over multiple paths. In this paper we show that the performance of such a multipath FEC scheme can often be further improved. Our key observation is that the propagation times on the available paths often significantly differ, typically by 10-100ms. We propose to exploit these differences by appropriate packet scheduling that we call `Spread'. We evaluate our solution with a precise, analytical formulation and trace-driven simulations. Our studies show that Spread substantially outperforms the state-of-the-art solutions. It typically achieves two- to five-fold improvement (reduction) in the effective loss rate. Or conversely, keeping the same level of effective loss rate, Spread significantly decreases the observed delays and helps fighting the delay jitter.
An information inequality for the BSSC channel
Venue: arXiv cs.IT 2009
Year: 2009

We establish an information theoretic inequality concerning the binary skew-symmetric broadcast channel that was conjectured by one of the authors. This inequality helps to quantify the gap between the sum rate obtained by the inner bound and outer bound for the binary skew-symmetric broadcast channel.
Fast Algorithms for Max Independent Set in Graphs of Small Average Degree
Venue: arXiv cs.DM 2009
Year: 2009

Max Independent Set (MIS) is a paradigmatic problem in theoretical computer science and numerous studies tackle its resolution by exact algorithms with non-trivial worst-case complexity. The best such complexity is, to our knowledge, the $O^*(1.1889^n)$ algorithm claimed by J.M. Robson (T.R. 1251-01, LaBRI, Univ. Bordeaux I, 2001) in his unpublished technical report. We also quote the $O^*(1.2210^n)$ algorithm by Fomin and al. (in Proc. SODA'06, pages 18-25, 2006), that is the best published result about MIS. In this paper we settle MIS in (connected) graphs with "small" average degree, more precisely with average degree at most 3, 4, 5 and 6. Dealing with graphs of average degree at most 3, the best bound known is the recent $O^*(1.0977^n)$ bound by N. Bourgeois and al. in Proc. IWPEC'08, pages 55-65, 2008). Here we improve this result down to $O^*(1.0854^n)$ by proposing finer and more powerful reduction rules. We then propose a generic method showing how improvement of the worst-case complexity for MIS in graphs of average degree $d$ entails improvement of it in any graph of average degree greater than $d$ and, based upon it, we tackle MIS in graphs of average degree 4, 5 and 6. For MIS in graphs with average degree 4, we provide an upper complexity bound of $O^*(1.1571^n)$ that outperforms the best known bound of $O^*(1.1713^n)$ by R. Beigel (Proc. SODA'99, pages 856-857, 1999). For MIS in graphs of average degree at most 5 and 6, we provide bounds of $O^*(1.1969^n)$ and $O^*(1.2149^n)$, respectively, that improve upon the corresponding bounds of $O^*(1.2023^n)$ and $O^*(1.2172^n)$ in graphs of maximum degree 5 and 6 by (Fomin et al., 2006).
Triple-Error-Correcting BCH-Like Codes
Venue: arXiv cs.IT 2009
Year: 2009

The binary primitive triple-error-correcting BCH code is a cyclic code of minimum distance 7 with generator polynomial having zeros $α$, $α^3$ and $α^5$ where $α$ is a primitive root of unity. The zero set of the code is said to be {1,3,5}. In the 1970's Kasami showed that one can construct similar triple-error-correcting codes using zero sets consisting of different triples than the BCH codes. Furthermore, in 2000 Chang et. al. found new triples leading to triple-error-correcting codes. In this paper a new such triple is presented. In addition a new method is presented that may be of interest in finding further such triples.
Low-Complexity Near-ML Decoding of Large Non-Orthogonal STBCs Using PDA
Venue: arXiv cs.IT 2009
Year: 2009

Non-orthogonal space-time block codes (STBC) from cyclic division algebras (CDA) having large dimensions are attractive because they can simultaneously achieve both high spectral efficiencies (same spectral efficiency as in V-BLAST for a given number of transmit antennas) {\em as well as} full transmit diversity. Decoding of non-orthogonal STBCs with hundreds of dimensions has been a challenge. In this paper, we present a probabilistic data association (PDA) based algorithm for decoding non-orthogonal STBCs with large dimensions. Our simulation results show that the proposed PDA-based algorithm achieves near SISO AWGN uncoded BER as well as near-capacity coded BER (within about 5 dB of the theoretical capacity) for large non-orthogonal STBCs from CDA. We study the effect of spatial correlation on the BER, and show that the performance loss due to spatial correlation can be alleviated by providing more receive spatial dimensions. We report good BER performance when a training-based iterative decoding/channel estimation is used (instead of assuming perfect channel knowledge) in channels with large coherence times. A comparison of the performances of the PDA algorithm and the likelihood ascent search (LAS) algorithm (reported in our recent work) is also presented.
Efficient erasure decoding of Reed-Solomon codes
Venue: arXiv cs.IT 2009
Year: 2009

We present a practical algorithm to decode erasures of Reed-Solomon codes over the q elements binary field in O(q \log_2^2 q) time where the constant implied by the O-notation is very small. Asymptotically fast algorithms based on fast polynomial arithmetic were already known, but even if their complexity is similar, they are mostly impractical. By comparison our algorithm uses only a few Walsh transforms and has been easily implemented.
Performance bounds on compressed sensing with Poisson noise
Venue: arXiv cs.IT 2009
Year: 2009

This paper describes performance bounds for compressed sensing in the presence of Poisson noise when the underlying signal, a vector of Poisson intensities, is sparse or compressible (admits a sparse approximation). The signal-independent and bounded noise models used in the literature to analyze the performance of compressed sensing do not accurately model the effects of Poisson noise. However, Poisson noise is an appropriate noise model for a variety of applications, including low-light imaging, where sensing hardware is large or expensive, and limiting the number of measurements collected is important. In this paper, we describe how a feasible positivity-preserving sensing matrix can be constructed, and then analyze the performance of a compressed sensing reconstruction approach for Poisson data that minimizes an objective function consisting of a negative Poisson log likelihood term and a penalty term which could be used as a measure of signal sparsity.
A Lower Bound on the Capacity of Wireless Erasure Networks with Random Node Locations
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, a lower bound on the capacity of wireless ad hoc erasure networks is derived in closed form in the canonical case where $n$ nodes are uniformly and independently distributed in the unit area square. The bound holds almost surely and is asymptotically tight. We assume all nodes have fixed transmit power and hence two nodes should be within a specified distance $r_n$ of each other to overcome noise. In this context, interference determines outages, so we model each transmitter-receiver pair as an erasure channel with a broadcast constraint, i.e. each node can transmit only one signal across all its outgoing links. A lower bound of $Θ(n r_n)$ for the capacity of this class of networks is derived. If the broadcast constraint is relaxed and each node can send distinct signals on distinct outgoing links, we show that the gain is a function of $r_n$ and the link erasure probabilities, and is at most a constant if the link erasure probabilities grow sufficiently large with $n$. Finally, the case where the erasure probabilities are themselves random variables, for example due to randomness in geometry or channels, is analyzed. We prove somewhat surprisingly that in this setting, variability in erasure probabilities increases network capacity.
Two-Way Relay Channels: Error Exponents and Resource Allocation
Venue: arXiv cs.IT 2009
Year: 2009

In a two-way relay network, two terminals exchange information over a shared wireless half-duplex channel with the help of a relay. Due to its fundamental and practical importance, there has been an increasing interest in this channel. However, surprisingly, there has been little work that characterizes the fundamental tradeoff between the communication reliability and transmission rate across all signal-to-noise ratios. In this paper, we consider amplify-and-forward (AF) two-way relaying due to its simplicity. We first derive the random coding error exponent for the link in each direction. From the exponent expression, the capacity and cutoff rate for each link are also deduced. We then put forth the notion of the bottleneck error exponent, which is the worst exponent decay between the two links, to give us insight into the fundamental tradeoff between the rate pair and information-exchange reliability of the two terminals. As applications of the error exponent analysis, we present two optimal resource allocations to maximize the bottleneck error exponent: i) the optimal rate allocation under a sum-rate constraint and its closed-form quasi-optimal solution that requires only knowledge of the capacity and cutoff rate of each link; and ii) the optimal power allocation under a total power constraint, which is formulated as a quasi-convex optimization problem. Numerical results verify our analysis and the effectiveness of the optimal rate and power allocations in maximizing the bottleneck error exponent.
Beyond Language Equivalence on Visibly Pushdown Automata
Venue: arXiv cs.CC 2009
Year: 2009

We study (bi)simulation-like preorder/equivalence checking on the class of visibly pushdown automata and its natural subclasses visibly BPA (Basic Process Algebra) and visibly one-counter automata. We describe generic methods for proving complexity upper and lower bounds for a number of studied preorders and equivalences like simulation, completed simulation, ready simulation, 2-nested simulation preorders/equivalences and bisimulation equivalence. Our main results are that all the mentioned equivalences and preorders are EXPTIME-complete on visibly pushdown automata, PSPACE-complete on visibly one-counter automata and P-complete on visibly BPA. Our PSPACE lower bound for visibly one-counter automata improves also the previously known DP-hardness results for ordinary one-counter automata and one-counter nets. Finally, we study regularity checking problems for visibly pushdown automata and show that they can be decided in polynomial time.
Encapsulation theory: the transformation equations of absolute information hiding
Venue: arXiv cs.SE 2009
Year: 2009

This paper describes how the maximum potential number of edges of an encapsulated graph varies as the graph is transformed, that is, as nodes are created and modified. The equations governing these changes of maximum potential number of edges caused by the transformations are derived and briefly analysed.
Performance of Polar Codes for Channel and Source Coding
Venue: arXiv cs.IT 2009
Year: 2009

Polar codes, introduced recently by Arıkan, are the first family of codes known to achieve capacity of symmetric channels using a low complexity successive cancellation decoder. Although these codes, combined with successive cancellation, are optimal in this respect, their finite-length performance is not record breaking. We discuss several techniques through which their finite-length performance can be improved. We also study the performance of these codes in the context of source coding, both lossless and lossy, in the single-user context as well as for distributed applications.