OpenRaiser/Intern-Atlas huggingface dataset:
Opportunistic Relaying for Space-Time Coded Cooperation with Multiple Antenna Terminals
Venue: arXiv cs.IT 2011
Year: 2011

We consider a wireless relay network with multiple antenna terminals over Rayleigh fading channels, and apply distributed space-time coding (DSTC) in amplify-and-forward (A&F) mode. The A&F scheme is used in a way that each relay transmits a scaled version of the linear combination of the received symbols. It turns out that, combined with power allocation in the relays, A&F DSTC results in an opportunistic relaying scheme, in which only the best relay is selected to retransmit the source's space-time coded signal. Furthermore, assuming the knowledge of source-relay CSI at the source node, we design an efficient power allocation which outperforms uniform power allocation across the source antennas. Next, assuming M-PSK or M-QAM modulations, we analyze the performance of the proposed cooperative diversity transmission schemes in a wireless relay networks with the multiple-antenna source and destination. We derive the probability density function (PDF) of the received SNR at the destination. Then, the PDF is used to determine the symbol error rate (SER) in Rayleigh fading channels. We derived closed-form approximations of the average SER in the high SNR scenario, from which we find the diversity order of system RminfNs;Ndg, where R, Ns, and Nd are the number of the relays, source antennas, and destination antennas, respectively. Simulation results show that the proposed system obtain more than 6 dB gain in SNR over A&F MIMO DSTC for BER 10^{-4}, when R = 2, Ns = 2, and Nd = 1.
Toward Measuring the Scaling of Genetic Programming
Venue: arXiv cs.NE 2011
Year: 2011

Several genetic programming systems are created, each solving a different problem. In these systems, the median number of generations G needed to evolve a working program is measured. The behavior of G is observed as the difficulty of the problem is increased. In these systems, the density D of working programs in the universe of all possible programs is measured. The relationship G ~ 1/sqrt(D) is observed to approximately hold for two program-like systems. For parallel systems (systems that look like several independent programs evolving in parallel), the relationship G ~ 1/(n ln n) is observed to approximately hold. Finally, systems that are anti-parallel are considered.
Term Graph Rewriting and Parallel Term Rewriting
Venue: arXiv cs.LO 2011
Year: 2011

The relationship between Term Graph Rewriting and Term Rewriting is well understood: a single term graph reduction may correspond to several term reductions, due to sharing. It is also known that if term graphs are allowed to contain cycles, then one term graph reduction may correspond to infinitely many term reductions. We stress that this fact can be interpreted in two ways. According to the "sequential interpretation", a term graph reduction corresponds to an infinite sequence of term reductions, as formalized by Kennaway et.al. using strongly converging derivations over the complete metric space of infinite terms. Instead according to the "parallel interpretation" a term graph reduction corresponds to the parallel reduction of an infinite set of redexes in a rational term. We formalize the latter notion by exploiting the complete partial order of infinite and possibly partial terms, and we stress that this interpretation allows to explain the result of reducing circular redexes in several approaches to term graph rewriting.
Repetitive Reduction Patterns in Lambda Calculus with letrec (Work in Progress)
Venue: arXiv cs.PL 2011
Year: 2011

For the lambda-calculus with letrec we develop an optimisation, which is based on the contraction of a certain class of 'future' (also: virtual) redexes. In the implementation of functional programming languages it is common practice to perform beta-reductions at compile time whenever possible in order to produce code that requires fewer reductions at run time. This is, however, in principle limited to redexes and created redexes that are 'visible' (in the sense that they can be contracted without the need for unsharing), and cannot generally be extended to redexes that are concealed by sharing constructs such as letrec. In the case of recursion, concealed redexes become visible only after unwindings during evaluation, and then have to be contracted time and again. We observe that in some cases such redexes exhibit a certain form of repetitive behaviour at run time. We describe an analysis for identifying binders that give rise to such repetitive reduction patterns, and eliminate them by a sort of predictive contraction. Thereby these binders are lifted out of recursive positions or eliminated altogether, as a result alleviating the amount of beta-reductions required for each recursive iteration. Both our analysis and simplification are suitable to be integrated into existing compilers for functional programming languages as an additional optimisation phase. With this work we hope to contribute to increasing the efficiency of executing programs written in such languages.
Environmental benefits of enhanced surveillance technology on airport departure operations
Venue: arXiv cs.SY 2011
Year: 2011

Airport departure operations constitute an important source of airline delays and passenger frustration. Excessive surface traffic is the cause of increased controller and pilot workload; It is also the source of increased emissions; It worsens traffic safety and often does not yield improved runway throughput. Acknowledging this fact, this paper explores some of the feedback mechanisms by which airport traffic can be optimized in real time according to its current degree of congestion. In particular, it examines the environmnetal benefits that improved surveillance technologies can bring in the context of gate- or spot-release aircraft strategies. It is shown that improvements can lead yield 4% to 6% emission reductions for busy airports like New-York La Guardia or Seattle Tacoma. These benefits come on top of the benefits already obtained by adopting threshold strategies currently under evaluation.
Chernoff information of exponential families
Venue: arXiv cs.IT 2011
Year: 2011

Chernoff information upper bounds the probability of error of the optimal Bayesian decision rule for $2$-class classification problems. However, it turns out that in practice the Chernoff bound is hard to calculate or even approximate. In statistics, many usual distributions, such as Gaussians, Poissons or frequency histograms called multinomials, can be handled in the unified framework of exponential families. In this note, we prove that the Chernoff information for members of the same exponential family can be either derived analytically in closed form, or efficiently approximated using a simple geodesic bisection optimization technique based on an exact geometric characterization of the "Chernoff point" on the underlying statistical manifold.
Feature Selection via Sparse Approximation for Face Recognition
Venue: arXiv cs.CV 2011
Year: 2011

Inspired by biological vision systems, the over-complete local features with huge cardinality are increasingly used for face recognition during the last decades. Accordingly, feature selection has become more and more important and plays a critical role for face data description and recognition. In this paper, we propose a trainable feature selection algorithm based on the regularized frame for face recognition. By enforcing a sparsity penalty term on the minimum squared error (MSE) criterion, we cast the feature selection problem into a combinatorial sparse approximation problem, which can be solved by greedy methods or convex relaxation methods. Moreover, based on the same frame, we propose a sparse Ho-Kashyap (HK) procedure to obtain simultaneously the optimal sparse solution and the corresponding margin vector of the MSE criterion. The proposed methods are used for selecting the most informative Gabor features of face images for recognition and the experimental results on benchmark face databases demonstrate the effectiveness of the proposed methods.
Achievable Rate Region of Quantized Broadcast and MAC Channels
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we study the achievable rate region of Gaussian multiuser channels with the messages transmitted being from finite input alphabets and the outputs being {\em quantized at the receiver}. In particular, we focus on the achievable rate region of $i)$ Gaussian broadcast channel (GBC) and $ii)$ Gaussian multiple access channel (GMAC). First, we study the achievable rate region of two-user GBC when the messages to be transmitted to both the users take values from finite signal sets and the received signal is quantized at both the users. We refer to this channel as {\em quantized broadcast channel (QBC)}. We observe that the capacity region defined for a GBC does not carry over as such to QBC. We show that the optimal decoding scheme for GBC (i.e., high SNR user doing successive decoding and low SNR user decoding its message alone) is not optimal for QBC. We then propose an achievable rate region for QBC based on two different schemes. We present achievable rate region results for the case of uniform quantization at the receivers. Next, we investigate the achievable rate region of two-user GMAC with finite input alphabet and quantized receiver output. We refer to this channel as {\em quantized multiple access channel (QMAC)}. We derive expressions for the achievable rate region of a two-user QMAC. We show that, with finite input alphabet, the achievable rate region with the commonly used uniform receiver quantizer has a significant loss compared to the achievable rate region without receiver quantization. We propose a {\em non-uniform quantizer} which has a significantly larger rate region compared to what is achieved with a uniform quantizer in QMAC.
On the Sum Capacity of the Y-Channel
Venue: arXiv cs.IT 2011
Year: 2011

A network where three users communicate with each other via a relay is considered. Users do not receive other users' signals via a direct link, and thus the relay is essential for their communication. Each user is assumed to have an individual message to be delivered to each other user. Thus, each user wants to send two messages and to decode two messages. In general, the transmit signals of different nodes can be dependent since they can depend on previously received symbols. We call this case the general case. The sum-capacity is studied, and upper bounds and lower bounds are given. If all nodes have the same power, the sum-capacity is characterized to within a gap of 5/2 bits or a factor of 3 for all values of channel coefficients. This gap is also shown to approach 3/2 bits as the transmit power increases. Moreover, for the symmetric case with equal channel coefficients, the gap is shown to be less than 1 bit. The restricted case is also considered where the transmit signal does not depend on previously received symbols. In this case, the sum-capacity is characterized to within a gap of 2 bits or a factor of 3 for all values of channel coefficients, and approaches 1 bit as the transmit power increases.
Universal approximation using differentiators and application to feedback control
Venue: arXiv cs.SY 2011
Year: 2011

In this paper, we consider the problems of approximating uncertainties and feedback control for a class of nonlinear systems without full-known states, and two approximation methods are proposed: universal approximation using integral-chain differentiator or extended observer. Comparing to the approximations by fuzzy system and radial-based-function (RBF) neural networks, the presented two methods can not only approximate universally the uncertainties, but also estimate the unknown states. Moreover, the integral-chain differentiator can restrain noises thoroughly. The theoretical results are confirmed by computer simulations for feedback control.
A Tight Lower Bound on Distributed Random Walk Computation
Venue: arXiv cs.DC 2011
Year: 2011

We consider the problem of performing a random walk in a distributed network. Given bandwidth constraints, the goal of the problem is to minimize the number of rounds required to obtain a random walk sample. Das Sarma et al. [PODC'10] show that a random walk of length $\ell$ on a network of diameter $D$ can be performed in $\tilde O(\sqrt{\ell D}+D)$ time. A major question left open is whether there exists a faster algorithm, especially whether the multiplication of $\sqrt{\ell}$ and $\sqrt{D}$ is necessary. In this paper, we show a tight unconditional lower bound on the time complexity of distributed random walk computation. Specifically, we show that for any $n$, $D$, and $D\leq \ell \leq (n/(D^3\log n))^{1/4}$, performing a random walk of length $Θ(\ell)$ on an $n$-node network of diameter $D$ requires $Ω(\sqrt{\ell D}+D)$ time. This bound is {\em unconditional}, i.e., it holds for any (possibly randomized) algorithm. To the best of our knowledge, this is the first lower bound that the diameter plays a role of multiplicative factor. Our bound shows that the algorithm of Das Sarma et al. is time optimal. Our proof technique introduces a new connection between {\em bounded-round} communication complexity and distributed algorithm lower bounds with $D$ as a trade-off parameter, strengthening the previous study by Das Sarma et al. [STOC'11]. In particular, we make use of the bounded-round communication complexity of the pointer chasing problem. Our technique can be of independent interest and may be useful in showing non-trivial lower bounds on the complexity of other fundamental distributed computing problems.
A Large Deviations Result for Aggregation of Independent Noisy Observations
Venue: arXiv cs.IT 2011
Year: 2011

Sensing and aggregation of noisy observations should not be considered as separate issues. The quality of collective estimation involves a difficult tradeoff between sensing quality which increases by increasing the number of sensors, and aggregation quality which typically decreases if the number of sensors is too large. We examine a strategy for optimal aggregation for an ensemble of independent sensors with constrained system capacity. We show that in the large capacity limit larger scale aggregation always outperforms smaller scale aggregation at higher noise levels, while below a critical value of noise, there exist moderate scale aggregation levels at which optimal estimation is realized.
An Algorithmic Analysis of the Honey-Bee Game
Venue: arXiv cs.GT 2011
Year: 2011

The Honey-Bee game is a two-player board game that is played on a connected hexagonal colored grid or (in a generalized setting) on a connected graph with colored nodes. In a single move, a player calls a color and thereby conquers all the nodes of that color that are adjacent to his own current territory. Both players want to conquer the majority of the nodes. We show that winning the game is PSPACE-hard in general, NP-hard on series-parallel graphs, but easy on outerplanar graphs. In the solitaire version, the goal of the single player is to conquer the entire graph with the minimum number of moves. The solitaire version is NP-hard on trees and split graphs, but can be solved in polynomial time on co-comparability graphs.
The Multiplexing Gain of a Two-cell MIMO Channel with Unequal CSI
Venue: arXiv cs.IT 2011
Year: 2011

In this work, the joint precoding across two distant transmitters (TXs), sharing the knowledge of the data symbols to be transmitted, to two receivers (RXs), each equipped with one antenna, is discussed. We consider a distributed channel state information (CSI) configuration where each TX has its own local estimate of the channel and no communication is possible between the TXs. Based on the distributed CSI configuration, we introduce a concept of distributed MIMO precoding. We focus on the high signal-to-noise ratio (SNR) regime such that the two TXs aim at designing a precoding matrix to cancel the interference. Building on the study of the multiple antenna broadcast channel, we obtain the following key results: We derive the multiplexing gain (MG) as a function of the scaling in the SNR of the number of bits quantizing at each TX the channel to a given RX. Particularly, we show that the conventional Zero Forcing precoder is not MG maximizing, and we provide a precoding scheme optimal in terms of MG. Beyond the established MG optimality, simulations show that the proposed precoding schemes achieve better performances at intermediate SNR than known linear precoders.
Maximizing Cloud Providers Revenues via Energy Aware Allocation Policies
Venue: arXiv cs.DC 2011
Year: 2011

Cloud providers, like Amazon, offer their data centers' computational and storage capacities for lease to paying customers. High electricity consumption, associated with running a data center, not only reflects on its carbon footprint, but also increases the costs of running the data center itself. This paper addresses the problem of maximizing the revenues of Cloud providers by trimming down their electricity costs. As a solution allocation policies which are based on the dynamic powering servers on and off are introduced and evaluated. The policies aim at satisfying the conflicting goals of maximizing the users' experience while minimizing the amount of consumed electricity. The results of numerical experiments and simulations are described, showing that the proposed scheme performs well under different traffic conditions.
Hash-and-Forward Relaying for Two-Way Relay Channel
Venue: arXiv cs.IT 2011
Year: 2011

This paper considers a communication network comprised of two nodes, which have no mutual direct communication links, communicating two-way with the aid of a common relay node (RN), also known as separated two-way relay (TWR) channel. We first recall a cut-set outer bound for the set of rates in the context of this network topology assuming full-duplex transmission capabilities. Then, we derive a new achievable rate region based on hash-and-forward (HF) relaying where the RN does not attempt to decode but instead hashes its received signal, and show that under certain channel conditions it coincides with Shannon's inner-bound for the two-way channel [1]. Moreover, for binary adder TWR channel with additive noise at the nodes and the RN we provide a detailed capacity achieving coding scheme based on structure codes.
Capacity Region of $K$-User Discrete Memoryless Interference Channels with a Mixed Strong-Very Strong Interference
Venue: arXiv cs.IT 2011
Year: 2011

The capacity region of the 3-user Gaussian Interference Channel (GIC) with mixed strong-very strong interference was established in \cite{ChS}. The mixed strong-very strong interference conditions considered in \cite{ChS} correspond to the case where, at each receiver, one of the interfering signals is strong and the other is very strong. In this paper, we derive the capacity region of $K$-user $(K\geq 3)$ Discrete Memoryless Interference Channels (DMICs) with a mixed strong-very strong interference. This corresponds to the case where, at each receiver one of the interfering signals is strong and the other $(K-2)$ interfering signals are very strong. This includes, as a special case, the 3-user DMIC with mixed strong-very strong interference. The proof is specialized to the 3-user GIC case and hence an alternative simpler derivation for the capacity region of the 3-user GIC with mixed strong-very strong interference is provided.
A signal recovery algorithm for sparse matrix based compressed sensing
Venue: arXiv cs.IT 2011
Year: 2011

We have developed an approximate signal recovery algorithm with low computational cost for compressed sensing on the basis of randomly constructed sparse measurement matrices. The law of large numbers and the central limit theorem suggest that the developed algorithm saturates the Donoho-Tanner weak threshold for the perfect recovery when the matrix becomes as dense as the signal size $N$ and the number of measurements $M$ tends to infinity keep $α=M/N \sim O(1)$, which is supported by extensive numerical experiments. Even when the numbers of non-zero entries per column/row in the measurement matrices are limited to $O(1)$, numerical experiments indicate that the algorithm can still typically recover the original signal perfectly with an $O(N)$ computational cost per update as well if the density $ρ$ of non-zero entries of the signal is lower than a certain critical value $ρ_{\rm th}(α)$ as $N,M \to \infty$.
Capacity to within 3 bits for a class of Gaussian Interference Channels with a Cognitive Relay
Venue: arXiv cs.IT 2011
Year: 2011

The InterFerence Channel with a Cognitive Relay (IFC-CR) consists of a classical two-user interference channel in which the two independent messages are also non-causally known at a cognitive relay node. In this work a special class of IFC-CRs in which the sources do not create interference at the non-intended destinations is analyzed. This special model results in a channel with two non-interfering point-to-point channels whose transmission is aided by an in-band cognitive relay, which is thus referred to as the Parallel Channel with a Cognitive Relay (PC-CR). We determine the capacity of the PC-CR channel to within 3 bits/s/Hz for all channel parameters. In particular, we present several new outer bounds which we achieve to within a constant gap by proper selection of Gaussian input distributions in a simple rate-splitting and superposition coding-based inner bound. The inner and outer bounds are numerically evaluated to show that the actual gap can be far less than 3 bits/s/Hz.
K-user Interference Channels: General Outer Bound and Sum-capacity for Certain Gaussian Channels
Venue: arXiv cs.IT 2011
Year: 2011

This paper derives an outer bound on the capacity region of a general memoryless interference channel with an arbitrary number of users. The derivation follows from a generalization of the techniques developed by Kramer and by Etkin et al for the Gaussian two-user channel. The derived bound is the first known outer bound valid for any memoryless channel. In Gaussian noise, classes of channels for which the proposed bound gives the sum-rate capacity are identified, including degraded channels and a class of Z-channels.
Causal Rate Distortion Function on Abstract Alphabets and Optimal Reconstruction Kernel
Venue: arXiv cs.IT 2011
Year: 2011

A Causal rate distortion function with a general fidelity criterion is formulated on abstract alphabets and the optimal reconstruction kernel is derived, which consists of a product of causal kernels. In the process, general abstract spaces are introduced to show existence of the minimizing kernel using weak*-convergence. Certain properties of the causal rate distortion function are presented.
Efficient Error-Correcting Geocoding
Venue: arXiv cs.IR 2011
Year: 2011

We study the problem of resolving a perhaps misspelled address of a location into geographic coordinates of latitude and longitude. Our data structure solves this problem within a few milliseconds even for misspelled and fragmentary queries. Compared to major geographic search engines such as Google or Bing we achieve results of significantly better quality.