OpenRaiser/Intern-Atlas huggingface dataset:
Full-Diversity Precoding Design of Bit-Interleaved Coded Multiple Beamforming with Orthogonal Frequency Division Multiplexing
Venue: arXiv cs.IT 2013
Year: 2013

Multi-Input Multi-Output (MIMO) techniques have been incorporated with Orthogonal Frequency Division Multiplexing (OFDM) for broadband wireless communication systems. Bit-Interleaved Coded Multiple Beamforming (BICMB) can achieve both spatial diversity and spatial multiplexing for flat fading MIMO channels. For frequency selective fading MIMO channels, BICMB with OFDM (BICMB-OFDM) can be employed to provide both spatial diversity and multipath diversity, making it an important technique. In our previous work, the subcarrier grouping technique was applied to combat the negative effect of subcarrier correlation. It was also proved that full diversity of BICMB-OFDM with Subcarrier Grouping (BICMB-OFDM-SG) can be achieved within the condition R_cSL<=1, where R_c, S, and L are the code rate, the number of parallel streams at each subcarrier, and the number of channel taps, respectively. The full diversity condition implies that if S increases, R_c may have to decrease to maintain full diversity. As a result, increasing the number of parallel streams may not improve the total transmission rate. In this paper, the precoding technique is employed to overcome the full diversity restriction issue of R_cSL<=1 for BICMB-OFDM-SG. First, the diversity analysis of precoded BICMB-OFDM-SG is carried out. Then, the full-diversity precoding design is developed with the minimum achievable decoding complexity.
Chernoff-Hoeffding Inequality and Applications
Venue: arXiv cs.DS 2013
Year: 2013

When dealing with modern big data sets, a very common theme is reducing the set through a random process. These generally work by making "many simple estimates" of the full data set, and then judging them as a whole. Perhaps magically, these "many simple estimates" can provide a very accurate and small representation of the large data set. The key tool in showing how many of these simple estimates are needed for a fixed accuracy trade-off is the Chernoff-Hoeffding inequality[Che52,Hoe63]. This document provides a simple form of this bound, and two examples of its use.
Scoring and Searching over Bayesian Networks with Causal and Associative Priors
Venue: arXiv cs.AI 2013
Year: 2013

A significant theoretical advantage of search-and-score methods for learning Bayesian Networks is that they can accept informative prior beliefs for each possible network, thus complementing the data. In this paper, a method is presented for assigning priors based on beliefs on the presence or absence of certain paths in the true network. Such beliefs correspond to knowledge about the possible causal and associative relations between pairs of variables. This type of knowledge naturally arises from prior experimental and observational data, among others. In addition, a novel search-operator is proposed to take advantage of such prior knowledge. Experiments show that, using path beliefs improves the learning of the skeleton, as well as the edge directions in the network.
Citation analysis may severely underestimate the impact of clinical research as compared to basic research
Venue: arXiv cs.DL 2013
Year: 2013

Background: Citation analysis has become an important tool for research performance assessment in the medical sciences. However, different areas of medical research may have considerably different citation practices, even within the same medical field. Because of this, it is unclear to what extent citation-based bibliometric indicators allow for valid comparisons between research units active in different areas of medical research. Methodology: A visualization methodology is introduced that reveals differences in citation practices between medical research areas. The methodology extracts terms from the titles and abstracts of a large collection of publications and uses these terms to visualize the structure of a medical field and to indicate how research areas within this field differ from each other in their average citation impact. Results: Visualizations are provided for 32 medical fields, defined based on journal subject categories in the Web of Science database. The analysis focuses on three fields. In each of these fields, there turn out to be large differences in citation practices between research areas. Low-impact research areas tend to focus on clinical intervention research, while high-impact research areas are often more oriented on basic and diagnostic research. Conclusions: Popular bibliometric indicators, such as the h-index and the impact factor, do not correct for differences in citation practices between medical fields. These indicators therefore cannot be used to make accurate between-field comparisons. More sophisticated bibliometric indicators do correct for field differences but still fail to take into account within-field heterogeneity in citation practices. As a consequence, the citation impact of clinical intervention research may be substantially underestimated in comparison with basic and diagnostic research.
Best Practices for Scientific Computing
Venue: arXiv cs.MS 2013
Year: 2013

Scientists spend an increasing amount of time building and using software. However, most scientists are never taught how to do this efficiently. As a result, many are unaware of tools and practices that would allow them to write more reliable and maintainable code with less effort. We describe a set of best practices for scientific software development that have solid foundations in research and experience, and that improve scientists' productivity and the reliability of their software.
Tracking Large-Scale Video Remix in Real-World Events
Venue: arXiv cs.SI 2013
Year: 2013

Social information networks, such as YouTube, contains traces of both explicit online interaction (such as "like", leaving a comment, or subscribing to video feed), and latent interactions (such as quoting, or remixing parts of a video). We propose visual memes, or frequently re-posted short video segments, for tracking such latent video interactions at scale. Visual memes are extracted by scalable detection algorithms that we develop, with high accuracy. We further augment visual memes with text, via a statistical model of latent topics. We model content interactions on YouTube with visual memes, defining several measures of influence and building predictive models for meme popularity. Experiments are carried out on with over 2 million video shots from more than 40,000 videos on two prominent news events in 2009: the election in Iran and the swine flu epidemic. In these two events, a high percentage of videos contain remixed content, and it is apparent that traditional news media and citizen journalists have different roles in disseminating remixed content. We perform two quantitative evaluations for annotating visual memes and predicting their popularity. The joint statistical model of visual memes and words outperform a concurrence model, and the average error is ~2% for predicting meme volume and ~17% for their lifespan.
Type Directed Partial Evaluation for Level-1 Shift and Reset
Venue: arXiv cs.PL 2013
Year: 2013

We present an implementation in the Coq proof assistant of type directed partial evaluation (TDPE) algorithms for call-by-name and call-by-value versions of shift and reset delimited control operators, and in presence of strong sum types. We prove that the algorithm transforms well-typed programs to ones in normal form. These normal forms can not always be arrived at using the so far known equational theories. The typing system does not allow answer-type modification for function types and allows delimiters to be set on at most one atomic type. The semantic domain for evaluation is expressed in Constructive Type Theory as a dependently typed monadic structure combining Kripke models and continuation passing style translations.
A Map-Reduce Parallel Approach to Automatic Synthesis of Control Software
Venue: arXiv cs.DC 2013
Year: 2013

Many Control Systems are indeed Software Based Control Systems, i.e. control systems whose controller consists of control software running on a microcontroller device. This motivates investigation on Formal Model Based Design approaches for automatic synthesis of control software. Available algorithms and tools (e.g., QKS) may require weeks or even months of computation to synthesize control software for large-size systems. This motivates search for parallel algorithms for control software synthesis. In this paper, we present a Map-Reduce style parallel algorithm for control software synthesis when the controlled system (plant) is modeled as discrete time linear hybrid system. Furthermore we present an MPI-based implementation PQKS of our algorithm. To the best of our knowledge, this is the first parallel approach for control software synthesis. We experimentally show effectiveness of PQKS on two classical control synthesis problems: the inverted pendulum and the multi-input buck DC/DC converter. Experiments show that PQKS efficiency is above 65%. As an example, PQKS requires about 16 hours to complete the synthesis of control software for the pendulum on a cluster with 60 processors, instead of the 25 days needed by the sequential algorithm in QKS.
Counting and generating lambda terms
Venue: arXiv cs.LO 2013
Year: 2013

Lambda calculus is the basis of functional programming and higher order proof assistants. However, little is known about combinatorial properties of lambda terms, in particular, about their asymptotic distribution and random generation. This paper tries to answer questions like: How many terms of a given size are there? What is a "typical" structure of a simply typable term? Despite their ostensible simplicity, these questions still remain unanswered, whereas solutions to such problems are essential for testing compilers and optimizing programs whose expected efficiency depends on the size of terms. Our approach toward the afore-mentioned problems may be later extended to any language with bound variables, i.e., with scopes and declarations. This paper presents two complementary approaches: one, theoretical, uses complex analysis and generating functions, the other, experimental, is based on a generator of lambda-terms. Thanks to de Bruijn indices, we provide three families of formulas for the number of closed lambda terms of a given size and we give four relations between these numbers which have interesting combinatorial interpretations. As a by-product of the counting formulas, we design an algorithm for generating lambda terms. Performed tests provide us with experimental data, like the average depth of bound variables and the average number of head lambdas. We also create random generators for various sorts of terms. Thereafter, we conduct experiments that answer questions like: What is the ratio of simply typable terms among all terms? (Very small!) How are simply typable lambda terms distributed among all lambda terms? (A typable term almost always starts with an abstraction.) In this paper, abstractions and applications have size 1 and variables have size 0.
An asymptotically optimal push-pull method for multicasting over a random network
Venue: arXiv cs.IT 2013
Year: 2013

We consider allcast and multicast flow problems where either all of the nodes or only a subset of the nodes may be in session. Traffic from each node in the session has to be sent to every other node in the session. If the session does not consist of all the nodes, the remaining nodes act as relays. The nodes are connected by undirected links whose capacities are independent and identically distributed random variables. We study the asymptotics of the capacity region (with network coding) in the limit of a large number of nodes, and show that the normalized sum rate converges to a constant almost surely. We then provide a decentralized push-pull algorithm that asymptotically achieves this normalized sum rate without network coding.
Energy Efficient Decentralized Detection Based on Bit-optimal Multi-hop Transmission in One-dimensional Wireless Sensor Networks
Venue: arXiv cs.DC 2013
Year: 2013

Existing information theoretic work in decentralized detection is largely focused on parallel configuration of Wireless Sensor Networks (WSNs), where an individual hard or soft decision is computed at each sensor node and then transmitted directly to the fusion node. Such an approach is not efficient for large networks, where communication structure is likely to comprise of multiple hops. On the other hand, decentralized detection problem investigated for multi-hop networks is mainly concerned with reducing number and/or size of messages by using compression and fusion of information at intermediate nodes. In this paper an energy efficient multi-hop configuration of WSNs is proposed to solve the detection problem in large networks with two objectives: maximizing network lifetime and minimizing probability of error in the fusion node. This optimization problem is considered under the constraint of total consumed energy. The two objectives mentioned are achieved simultaneously in the multi-hop configuration by exploring tradeoffs between different path lengths and number of bits allocated to each node for quantization. Simulation results show significant improvement in the proposed multi-hop configuration compared with the parallel configuration in terms of energy efficiency and detection accuracy for different size networks, especially in larger networks.
Inferring clonal evolution of tumors from single nucleotide somatic mutations
Venue: arXiv cs.LG 2013
Year: 2013

High-throughput sequencing allows the detection and quantification of frequencies of somatic single nucleotide variants (SNV) in heterogeneous tumor cell populations. In some cases, the evolutionary history and population frequency of the subclonal lineages of tumor cells present in the sample can be reconstructed from these SNV frequency measurements. However, automated methods to do this reconstruction are not available and the conditions under which reconstruction is possible have not been described. We describe the conditions under which the evolutionary history can be uniquely reconstructed from SNV frequencies from single or multiple samples from the tumor population and we introduce a new statistical model, PhyloSub, that infers the phylogeny and genotype of the major subclonal lineages represented in the population of cancer cells. It uses a Bayesian nonparametric prior over trees that groups SNVs into major subclonal lineages and automatically estimates the number of lineages and their ancestry. We sample from the joint posterior distribution over trees to identify evolutionary histories and cell population frequencies that have the highest probability of generating the observed SNV frequency data. When multiple phylogenies are consistent with a given set of SNV frequencies, PhyloSub represents the uncertainty in the tumor phylogeny using a partial order plot. Experiments on a simulated dataset and two real datasets comprising tumor samples from acute myeloid leukemia and chronic lymphocytic leukemia patients demonstrate that PhyloSub can infer both linear (or chain) and branching lineages and its inferences are in good agreement with ground truth, where it is available.
Synthesis from LTL Specifications with Mean-Payoff Objectives
Venue: arXiv cs.LO 2013
Year: 2013

The classical LTL synthesis problem is purely qualitative: the given LTL specification is realized or not by a reactive system. LTL is not expressive enough to formalize the correctness of reactive systems with respect to some quantitative aspects. This paper extends the qualitative LTL synthesis setting to a quantitative setting. The alphabet of actions is extended with a weight function ranging over the rational numbers. The value of an infinite word is the mean-payoff of the weights of its letters. The synthesis problem then amounts to automatically construct (if possible) a reactive system whose executions all satisfy a given LTL formula and have mean-payoff values greater than or equal to some given threshold. The latter problem is called LTLMP synthesis and the LTLMP realizability problem asks to check whether such a system exists. We first show that LTLMP realizability is not more difficult than LTL realizability: it is 2ExpTime-Complete. This is done by reduction to two-player mean-payoff parity games. While infinite memory strategies are required to realize LTLMP specifications in general, we show that epsilon-optimality can be obtained with finite memory strategies, for any epsilon > 0. To obtain an efficient algorithm in practice, we define a Safraless procedure to decide whether there exists a finite-memory strategy that realizes a given specification for some given threshold. This procedure is based on a reduction to two-player energy safety games which are in turn reduced to safety games. Finally, we show that those safety games can be solved efficiently by exploiting the structure of their state spaces and by using antichains as a symbolic data-structure. All our results extend to multi-dimensional weights. We have implemented an antichain-based procedure and we report on some promising experimental results.
Autonomous Reinforcement of Behavioral Sequences in Neural Dynamics
Venue: arXiv cs.NE 2013
Year: 2013

We introduce a dynamic neural algorithm called Dynamic Neural (DN) SARSA(λ) for learning a behavioral sequence from delayed reward. DN-SARSA(λ) combines Dynamic Field Theory models of behavioral sequence representation, classical reinforcement learning, and a computational neuroscience model of working memory, called Item and Order working memory, which serves as an eligibility trace. DN-SARSA(λ) is implemented on both a simulated and real robot that must learn a specific rewarding sequence of elementary behaviors from exploration. Results show DN-SARSA(λ) performs on the level of the discrete SARSA(λ), validating the feasibility of general reinforcement learning without compromising neural dynamics.
On Precoding for Constant K-User MIMO Gaussian Interference Channel with Finite Constellation Inputs
Venue: arXiv cs.IT 2013
Year: 2013

This paper considers linear precoding for constant channel-coefficient $K$-User MIMO Gaussian Interference Channel (MIMO GIC) where each transmitter-$i$ (Tx-$i$), requires to send $d_i$ independent complex symbols per channel use that take values from fixed finite constellations with uniform distribution, to receiver-$i$ (Rx-$i$) for $i=1,2,\cdots,K$. We define the maximum rate achieved by Tx-$i$ using any linear precoder, when the interference channel-coefficients are zero, as the signal to noise ratio (SNR) tends to infinity to be the Constellation Constrained Saturation Capacity (CCSC) for Tx-$i$. We derive a high SNR approximation for the rate achieved by Tx-$i$ when interference is treated as noise and this rate is given by the mutual information between Tx-$i$ and Rx-$i$, denoted as $I[X_i;Y_i]$. A set of necessary and sufficient conditions on the precoders under which $I[X_i;Y_i]$ tends to CCSC for Tx-$i$ is derived. Interestingly, the precoders designed for interference alignment (IA) satisfy these necessary and sufficient conditions. Further, we propose gradient-ascent based algorithms to optimize the sum-rate achieved by precoding with finite constellation inputs and treating interference as noise. Simulation study using the proposed algorithms for a 3-user MIMO GIC with two antennas at each node with $d_i=1$ for all $i$, and with BPSK and QPSK inputs, show more than 0.1 bits/sec/Hz gain in the ergodic sum-rate over that yielded by precoders obtained from some known IA algorithms, at moderate SNRs.
LLR Compression for BICM Systems Using Large Constellations
Venue: arXiv cs.IT 2013
Year: 2013

Digital video broadcasting (DVB-C2) and other modern communication standards increase diversity by means of a symbol-level interleaver that spans over several codewords. De-interleaving at the receiver requires a large memory, which has a significant impact on the implementation cost. In this paper, we propose a technique that reduces the de-interleaver memory size. By quantizing log-likelihood ratios with bit-specific quantizers and compressing the quantized output, we can significantly reduce the memory size with a negligible increase in computational complexity. Both the quantizer and compressor are designed via a GMI-based maximization procedure. For a typical DVB-C2 scenario, numerical results show that the proposed solution enables a memory saving up to 30%.
Compressed Sensing Signal Recovery via Forward-Backward Pursuit
Venue: arXiv cs.IT 2013
Year: 2013

Recovery of sparse signals from compressed measurements constitutes an l0 norm minimization problem, which is unpractical to solve. A number of sparse recovery approaches have appeared in the literature, including l1 minimization techniques, greedy pursuit algorithms, Bayesian methods and nonconvex optimization techniques among others. This manuscript introduces a novel two stage greedy approach, called the Forward-Backward Pursuit (FBP). FBP is an iterative approach where each iteration consists of consecutive forward and backward stages. The forward step first expands the support estimate by the forward step size, while the following backward step shrinks it by the backward step size. The forward step size is larger than the backward step size, hence the initially empty support estimate is expanded at the end of each iteration. Forward and backward steps are iterated until the residual power of the observation vector falls below a threshold. This structure of FBP does not necessitate the sparsity level to be known a priori in contrast to the Subspace Pursuit or Compressive Sampling Matching Pursuit algorithms. FBP recovery performance is demonstrated via simulations including recovery of random sparse signals with different nonzero coefficient distributions in noisy and noise-free scenarios in addition to the recovery of a sparse image.
Insertion and Sorting in a Sequence of Numbers Minimizing the Maximum Sum of a Contiguous Subsequence
Venue: arXiv cs.DS 2013
Year: 2013

Let $A$ be a sequence of $n \geq 0$ real numbers. A subsequence of $A$ is a sequence of contiguous elements of $A$. A \emph{maximum scoring subsequence} of $A$ is a subsequence with largest sum of its elements, which can be found in O(n) time by Kadane's dynamic programming algorithm. We consider in this paper two problems involving maximal scoring subsequences of a sequence. Both of these problems arise in the context of buffer memory minimization in computer networks. The first one, which is called {\sc Insertion in a Sequence with Scores (ISS)}, consists in inserting a given real number $x$ in $A$ in such a way to minimize the sum of a maximum scoring subsequence of the resulting sequence, which can be easily done in $O(n^2)$ time by successively applying Kadane's algorithm to compute the maximum scoring subsequence of the resulting sequence corresponding to each possible insertion position for $x$. We show in this paper that the ISS problem can be solved in linear time and space with a more specialized algorithm. The second problem we consider in this paper is the {\sc Sorting a Sequence by Scores (SSS)} one, stated as follows: find a permutation $A'$ of $A$ that minimizes the sum of a maximum scoring subsequence. We show that the SSS problem is strongly NP-Hard and give a 2-approximation algorithm for it.