OpenRaiser/Intern-Atlas huggingface dataset:
Hybrid Digital and Analog Beamforming Design for Large-Scale Antenna Arrays
Venue: arXiv cs.IT 2016
Year: 2016

The potential of using of millimeter wave (mmWave) frequency for future wireless cellular communication systems has motivated the study of large-scale antenna arrays for achieving highly directional beamforming. However, the conventional fully digital beamforming methods which require one radio frequency (RF) chain per antenna element is not viable for large-scale antenna arrays due to the high cost and high power consumption of RF chain components in high frequencies. To address the challenge of this hardware limitation, this paper considers a hybrid beamforming architecture in which the overall beamformer consists of a low-dimensional digital beamformer followed by an RF beamformer implemented using analog phase shifters. Our aim is to show that such an architecture can approach the performance of a fully digital scheme with much fewer number of RF chains. Specifically, this paper establishes that if the number of RF chains is twice the total number of data streams, the hybrid beamforming structure can realize any fully digital beamformer exactly, regardless of the number of antenna elements. For cases with fewer number of RF chains, this paper further considers the hybrid beamforming design problem for both the transmission scenario of a point-to-point multipleinput multiple-output (MIMO) system and a downlink multiuser multiple-input single-output (MU-MISO) system. For each scenario, we propose a heuristic hybrid beamforming design that achieves a performance close to the performance of the fully digital beamforming baseline. Finally, the proposed algorithms are modified for the more practical setting in which only finite resolution phase shifters are available. Numerical simulations show that the proposed schemes are effective even when phase shifters with very low resolution are used.
Combinatorial algorithm for counting small induced graphs and orbits
Venue: arXiv cs.DS 2016
Year: 2016

Graphlet analysis is an approach to network analysis that is particularly popular in bioinformatics. We show how to set up a system of linear equations that relate the orbit counts and can be used in an algorithm that is significantly faster than the existing approaches based on direct enumeration of graphlets. The algorithm requires existence of a vertex with certain properties; we show that such vertex exists for graphlets of arbitrary size, except for complete graphs and $C_4$, which are treated separately. Empirical analysis of running time agrees with the theoretical results.
Bounds on Asymptotic Rate of Capacitive Crosstalk Avoidance Codes for On-chip Buses
Venue: arXiv cs.IT 2016
Year: 2016

In order to prevent the capacitive crosstalk in on-chip buses, several types of capacitive crosstalk avoidance codes have been devised. These codes are designed to prohibit transition patterns prone to the capacity crosstalk from any consecutive two words transmitted to on-chip buses. This paper provides a rigorous analysis on the asymptotic rate of (p,q)-transition free word sequences under the assumption that coding is based on a pair of a stateful encoder and a stateless decoder. The symbols p and q represent k-bit transition patterns that should not be appeared in any consecutive two words at the same adjacent k-bit positions. It is proved that the maximum rate of the sequences equals to the subgraph domatic number of (p,q)-transition free graph. Based on the theoretical results on the subgraph domatic partition problem, a pair of lower and upper bounds on the asymptotic rate is derived. We also present that the asymptotic rate 0.8325 is achievable for the (10,01)-transition free word sequences.
Efficient Coding for Multi-source Networks using Gács-Körner Common Information
Venue: arXiv cs.IT 2016
Year: 2016

Consider a multi-source network coding problem with correlated sources. While the fundamental limits are known, achieving them, in general, involves a computational burden due to the complex decoding process. Efficient solutions, on the other hand, are by large based on source and network coding separation, thus imposing strict topological constraints on the networks which can be solved. In this work, we introduce a novel notion of separation of source and network coding using Gács-Körner Common Information (CI). Unlike existing notions of separation, the sufficient condition for this separation to hold depends on the source structure rather than the network topology. Using the suggested separation scheme, we tackle three important multi-source problems. The first is the multi-source multicast. We construct efficient, zero error source codes, and via properties of the CI completely characterize the resulting rate region. The second is broadcast with side information. We establish a duality between this problem and the classical problem of degraded message set broadcast, and give two code constructions and their associated regions. Finally, we consider the Ahlswede-Korner problem in a network, and give an efficient solution which is tight under the CI constraints.
Balanced Permutation Codes
Venue: arXiv cs.IT 2016
Year: 2016

Motivated by charge balancing constraints for rank modulation schemes, we introduce the notion of balanced permutations and derive the capacity of balanced permutation codes. We also describe simple interleaving methods for permutation code constructions and show that they approach capacity
Enhanced Recursive Reed-Muller Erasure Decoding
Venue: arXiv cs.IT 2016
Year: 2016

Recent work have shown that Reed-Muller (RM) codes achieve the erasure channel capacity. However, this performance is obtained with maximum-likelihood decoding which can be costly for practical applications. In this paper, we propose an encoding/decoding scheme for Reed-Muller codes on the packet erasure channel based on Plotkin construction. We present several improvements over the generic decoding. They allow, for a light cost, to compete with maximum-likelihood decoding performance, especially on high-rate codes, while significantly outperforming it in terms of speed.
A Novel Memetic Feature Selection Algorithm
Venue: arXiv cs.LG 2016
Year: 2016

Feature selection is a problem of finding efficient features among all features in which the final feature set can improve accuracy and reduce complexity. In feature selection algorithms search strategies are key aspects. Since feature selection is an NP-Hard problem; therefore heuristic algorithms have been studied to solve this problem. In this paper, we have proposed a method based on memetic algorithm to find an efficient feature subset for a classification problem. It incorporates a filter method in the genetic algorithm to improve classification performance and accelerates the search in identifying core feature subsets. Particularly, the method adds or deletes a feature from a candidate feature subset based on the multivariate feature information. Empirical study on commonly data sets of the university of California, Irvine shows that the proposed method outperforms existing methods.
Rank equivalent and rank degenerate skew cyclic codes
Venue: arXiv cs.IT 2016
Year: 2016

Two skew cyclic codes can be equivalent for the Hamming metric only if they have the same length, and only the zero code is degenerate. The situation is completely different for the rank metric, where lengths of codes correspond to the number of outgoing links from the source when applying the code on a network. We study rank equivalences between skew cyclic codes of different lengths and, with the aim of finding the skew cyclic code of smallest length that is rank equivalent to a given one, we define different types of length for a given skew cyclic code, relate them and compute them in most cases. We give different characterizations of rank degenerate skew cyclic codes using conventional polynomials and linearized polynomials. Some known results on the rank weight hierarchy of cyclic codes for some lengths are obtained as particular cases and extended to all lengths and to all skew cyclic codes. Finally, we prove that the smallest length of a linear code that is rank equivalent to a given skew cyclic code can be attained by a pseudo-skew cyclic code. Throughout the paper, we find new relations between linear skew cyclic codes and their Galois closures.
Distributed Detection over Adaptive Networks: Refined Asymptotics and the Role of Connectivity
Venue: arXiv cs.MA 2016
Year: 2016

We consider distributed detection problems over adaptive networks, where dispersed agents learn continually from streaming data by means of local interactions. The simultaneous requirements of adaptation and cooperation are achieved by employing diffusion algorithms with constant step-size μ. In [1], [2] some main features of adaptive distributed detection were revealed. By resorting to large deviations analysis, it was established that the Type-I and Type-II error probabilities of all agents vanish exponentially as functions of 1/μ, and that all agents share the same Type-I and Type-II error exponents. However, numerical evidences presented in [1], [2] showed that the theory of large deviations does not capture the fundamental impact of network connectivity on performance, and that additional tools and efforts are required to obtain accurate predictions for the error probabilities. This work addresses these open issues and extends the results of [1], [2] in several directions. By conducting a refined asymptotic analysis based on the mathematical framework of exact asymptotics, we arrive at a revealing and powerful understanding of the universal behavior of distributed detection over adaptive networks: as functions of 1/μ, the error (log-)probability curves corresponding to different agents stay nearly-parallel to each other (as already discovered in [1], [2]), however, these curves are ordered following a criterion reflecting the degree of connectivity of each agent. Depending on the combination weights, the more connected an agent is, the lower its error probability curve will be. Interesting and somehow unexpected behaviors emerge, in terms of the interplay between the network topology, the combination weights, and the inference performance. The lesson learned is that connectivity matters.
Coded Packet Transport for Optical Packet/Burst Switched Networks
Venue: arXiv cs.IT 2016
Year: 2016

This paper presents the Coded Packet Transport (CPT) scheme, a novel transport mechanism for Optical Packet/Burst Switched (OPS/OBS) networks. The CPT scheme exploits the combined benefits of source coding by erasure codes and path diversity to provide efficient means for recovering from packet loss due to contentions and path failures, and to provide non-cryptographic secrecy. In the CPT scheme, erasure coding is employed at the OPS/OBS ingress node to form coded packets, which are transmitted on disjoint paths from the ingress node to an egress node in the network. The CPT scheme allows for a unified view of Quality of Service (QoS) in OPS/OBS networks by linking the interactions between survivability, performance and secrecy. We provide analytical models that illustrate how QoS aspects of CPT are affected by the number of disjoint paths, packet overhead and processing delay.
Bidding policies for market-based HPC workflow scheduling
Venue: arXiv cs.DC 2016
Year: 2016

This paper considers the scheduling of jobs on distributed, heterogeneous High Performance Computing (HPC) clusters. Market-based approaches are known to be efficient for allocating limited resources to those that are most prepared to pay. This context is applicable to an HPC or cloud computing scenario where the platform is overloaded. In this paper, jobs are composed of dependent tasks. Each job has a non-increasing time-value curve associated with it. Jobs are submitted to and scheduled by a market-clearing centralised auctioneer. This paper compares the performance of several policies for generating task bids. The aim investigated here is to maximise the value for the platform provider while minimising the number of jobs that do not complete (or starve). It is found that the Projected Value Remaining bidding policy gives the highest level of value under a typical overload situation, and gives the lowest number of starved tasks across the space of utilisation examined. It does this by attempting to capture the urgency of tasks in the queue. At high levels of overload, some alternative algorithms produce slightly higher value, but at the cost of a hugely higher number of starved workflows.
Binary Codes with Locality for Multiple Erasures Having Short Block Length
Venue: arXiv cs.IT 2016
Year: 2016

The focus of this paper is on linear, binary codes with locality having locality parameter $r$, that are capable of recovering from $t\geq 2$ erasures and that moreover, have short block length. Both sequential and parallel (through orthogonal parity checks) recovery is considered here. In the case of parallel repair, minimum-block-length constructions for general $t$ are discussed. In the case of sequential repair, the results include (a) extending and characterizing minimum-block-length constructions for $t=2$, (b) providing improved bounds on block length for $t=3$ as well as a general construction for $t=3$ having short block length, (c) providing short-block-length constructions for general $r,t$ and (d) providing high-rate constructions for $r=2$ and $t$ in the range $4 \leq t \leq7$. Most of the constructions provided are of binary codes.
LIA-RAG: a system based on graphs and divergence of probabilities applied to Speech-To-Text Summarization
Venue: arXiv cs.CL 2016
Year: 2016

This paper aims to introduces a new algorithm for automatic speech-to-text summarization based on statistical divergences of probabilities and graphs. The input is a text from speech conversations with noise, and the output a compact text summary. Our results, on the pilot task CCCS Multiling 2015 French corpus are very encouraging
Energy Efficiency of Many-Soft-Core Processors
Venue: arXiv cs.DC 2016
Year: 2016

The growing capacity of integration allows to instantiate hundreds of soft-core processors in a single FPGA to create a reconfigurable multiprocessing system. Lately, FPGAs have been proven to give a higher energy efficiency than alternative platforms like CPUs and GPGPUs for certain workloads and are increasingly used in data-centers. In this paper we investigate whether many-soft-core processors can achieve similar levels of energy efficiency while providing a general purpose environment, more easily programmed, and allowing to run other applications without reconfiguring the device. With a simple application example we are able to create a reconfigurable multiprocessing system achieving an energy efficiency 58 times higher than a recent ultra-low-power processor and 124 times higher than a recent high performance GPGPU.
Knowledge Discovery In GIS Data
Venue: arXiv cs.DB 2016
Year: 2016

Intelligent geographic information system (IGIS) is one of the promising topics in GIS field. It aims at making GIS tools more sensitive for large volumes of data stored inside GIS systems by integrating GIS with other computer sciences such as Expert system (ES) Data Warehouse (DW), Decision Support System (DSS), or Knowledge Discovery Database (KDD). One of the main branches of IGIS is the Geographic Knowledge Discovery (GKD) which tries to discover the implicit knowledge in the spatial databases. The main difference between traditional KDD techniques and GKD techniques is hidden in the nature of spatial data sets. In other words in the traditional data set the values of each object are supposed to be independent from other objects in the same data set, whereas the spatial dataset tends to be highly correlated according to the first law of geography. The spatial outlier detection is one of the most popular spatial data mining techniques which is used to detect spatial objects whose non-spatial attributes values are extremely different from those of their neighboring objects. Analyzing the behavior of these objects may produce an interesting knowledge, which has an effective role in the decision-making process. In this thesis, a new definition for the spatial neighborhood relationship by is proposed considering the weights of the most effective parameters of neighboring objects in a given spatial dataset. The spatial parameters taken into our consideration are; distance, cost, and number of direct connections between neighboring objects. A new model to detect spatial outliers is also presented based on the new definition of the spatial neighborhood relationship. This model is adapted to be applied to polygonal objects. The proposed model is applied to an existing project for supporting literacy in Fayoum governorate in Arab Republic of Egypt (ARE).
Font Identification in Historical Documents Using Active Learning
Venue: arXiv cs.CV 2016
Year: 2016

Identifying the type of font (e.g., Roman, Blackletter) used in historical documents can help optical character recognition (OCR) systems produce more accurate text transcriptions. Towards this end, we present an active-learning strategy that can significantly reduce the number of labeled samples needed to train a font classifier. Our approach extracts image-based features that exploit geometric differences between fonts at the word level, and combines them into a bag-of-word representation for each page in a document. We evaluate six sampling strategies based on uncertainty, dissimilarity and diversity criteria, and test them on a database containing over 3,000 historical documents with Blackletter, Roman and Mixed fonts. Our results show that a combination of uncertainty and diversity achieves the highest predictive accuracy (89% of test cases correctly classified) while requiring only a small fraction of the data (17%) to be labeled. We discuss the implications of this result for mass digitization projects of historical documents.
Persuasive Teachable Agent for Intergenerational Learning
Venue: arXiv cs.HC 2016
Year: 2016

Teachable agents are computer agents based on the pedagogical concept of learning-by-teaching. During the tutoring process, where students take on the role of the tutor to teach a computer agent tutee, learners have been observed to gain deeper understanding of the subject matter. Teachable agents are commonly used in the areas of science and mathematics learning where learners are able to learn complex concepts and deep reasoning by teaching the teachable agent through graphic representation such as concept maps. Literature review on teachable agents as well as observations during field studies conducted by the researcher, have shown that many current teachable agents lack the interaction abilities required to keep learners engage in learning tasks. The result of this is learners deviating from the teaching process, and thus the learners are unable to benefit fully from learning with the teachable agent. The applications of teachable agents are restricted to the learning of academic subjects such as mathematics and science. In this book, we have proposed the Persuasive Teachable Agent (PTA), a teachable agent based on the theoretical framework of persuasion, computational and goal-oriented agent modelling. We argue that the PTA, an autonomous agent, capable of encouraging attitude and behavioural change can offer a more meaningful and engaging learning experiences for learners from different age groups. Based on the findings from our research we argue that persuasive feedback actions generated by the PTA provide significant influence over learner's decision to participate in intergenerational learning. The PTA plays a crucial role in the development of future persuasive technologies in artificially intelligent agents.
Optimal Power Distribution Control for a Network of Fuel Cell Stacks
Venue: arXiv cs.SY 2016
Year: 2016

In power networks where multiple fuel cell stacks are employed to deliver the required power, optimal sharing of the power demand between different stacks is an important problem. This is because the total current collectively produced by all the stacks is directly proportional to the fuel utilization, through stoichiometry. As a result, one would like to produce the required power while minimizing the total current produced. In this paper, an optimization formulation is proposed for this power distribution control problem. An algorithm that identifies the globally optimal solution for this problem is developed. Through an analysis of the KKT conditions, the solution to the optimization problem is decomposed into on-line and on-line computations. The on-line computations reduce to simple equation solving. For an application with a specific v-i function derived from data, we show that analytical solutions exist for on-line computations. We also discuss the wider applicability of the proposed approach for similar problems in other domains.
Myopic Policy Bounds for Information Acquisition POMDPs
Venue: arXiv cs.SY 2016
Year: 2016

This paper addresses the problem of optimal control of robotic sensing systems aimed at autonomous information gathering in scenarios such as environmental monitoring, search and rescue, and surveillance and reconnaissance. The information gathering problem is formulated as a partially observable Markov decision process (POMDP) with a reward function that captures uncertainty reduction. Unlike the classical POMDP formulation, the resulting reward structure is nonlinear in the belief state and the traditional approaches do not apply directly. Instead of developing a new approximation algorithm, we show that if attention is restricted to a class of problems with certain structural properties, one can derive (often tight) upper and lower bounds on the optimal policy via an efficient myopic computation. These policy bounds can be applied in conjunction with an online branch-and-bound algorithm to accelerate the computation of the optimal policy. We obtain informative lower and upper policy bounds with low computational effort in a target tracking domain. The performance of branch-and-bounding is demonstrated and compared with exact value iteration.
OneClock to Rule Them All: Using Time in Networked Applications
Venue: arXiv cs.NI 2016
Year: 2016

This paper introduces OneClock, a generic approach for using time in networked applications. OneClock provides two basic time-triggered primitives: the ability to schedule an operation at a remote host or device, and the ability to receive feedback about the time at which an event occurred or an operation was executed at a remote host or device. We introduce a novel prediction-based scheduling approach that uses timing information collected at runtime to accurately schedule future operations. Our work includes an extension to the Network Configuration protocol (NETCONF), which enables OneClock in real-life systems. This extension has been published as an Internet Engineering Task Force (IETF) RFC, and a prototype of our NETCONF time extension is publicly available as open source. Experimental evaluation shows that our prediction-based approach allows accurate scheduling in diverse and heterogeneous environments, with various hardware capabilities and workloads. OneClock is a generic approach that can be applied to any managed device: sensors, actuators, Internet of Things (IoT) devices, routers, or toasters.