OpenRaiser/Intern-Atlas huggingface dataset:
On Base Field of Linear Network Coding
Venue: arXiv cs.IT 2015
Year: 2015

For a (single-source) multicast network, the size of a base field is the most known and studied algebraic identity that is involved in characterizing its linear solvability over the base field. In this paper, we design a new class $\mathcal{N}$ of multicast networks and obtain an explicit formula for the linear solvability of these networks, which involves the associated coset numbers of a multiplicative subgroup in a base field. The concise formula turns out to be the first that matches the topological structure of a multicast network and algebraic identities of a field other than size. It further facilitates us to unveil \emph{infinitely many} new multicast networks linearly solvable over GF($q$) but not over GF($q'$) with $q < q'$, based on a subgroup order criterion. In particular, i) for every $k\geq 2$, an instance in $\mathcal{N}$ can be found linearly solvable over GF($2^{2k}$) but \emph{not} over GF($2^{2k+1}$), and ii) for arbitrary distinct primes $p$ and $p'$, there are infinitely many $k$ and $k'$ such that an instance in $\mathcal{N}$ can be found linearly solvable over GF($p^k$) but \emph{not} over GF($p'^{k'}$) with $p^k < p'^{k'}$. On the other hand, the construction of $\mathcal{N}$ also leads to a new class of multicast networks with $Θ(q^2)$ nodes and $Θ(q^2)$ edges, where $q \geq 5$ is the minimum field size for linear solvability of the network.
On Maximal Correlation, Mutual Information and Data Privacy
Venue: arXiv cs.IT 2015
Year: 2015

The rate-privacy function is defined in \cite{Asoodeh} as a tradeoff between privacy and utility in a distributed private data system in which both privacy and utility are measured using mutual information. Here, we use maximal correlation in lieu of mutual information in the privacy constraint. We first obtain some general properties and bounds for maximal correlation and then modify the rate-privacy function to account for the privacy-constrained estimation problem. We find a bound for the utility in this problem when the maximal correlation privacy is set to some threshold $ε>0$ and construct an explicit privacy scheme which achieves this bound.
Learning-Based Distributed Detection-Estimation in Sensor Networks with Unknown Sensor Defects
Venue: arXiv cs.IT 2015
Year: 2015

We consider the problem of distributed estimation of an unknown deterministic scalar parameter (the target signal) in a wireless sensor network (WSN), where each sensor receives a single snapshot of the field. We assume that the observation at each node randomly falls into one of two modes: a valid or an invalid observation mode. Specifically, mode one corresponds to the desired signal plus noise observation mode (\emph{valid}), and mode two corresponds to the pure noise mode (\emph{invalid}) due to node defect or damage. With no prior information on such local sensing modes, we introduce a learning-based distributed procedure, called the mixed detection-estimation (MDE) algorithm, based on iterative closed-loop interactions between mode learning (detection) and target estimation. The online learning step re-assesses the validity of the local observations at each iteration, thus refining the ongoing estimation update process. The convergence of the MDE algorithm is established analytically. Asymptotic analysis shows that, in the high signal-to-noise ratio (SNR) regime, the MDE estimation error converges to that of an ideal (centralized) estimator with perfect information about the node sensing modes. This is in contrast to the estimation performance of a naive average consensus based distributed estimator (without mode learning), whose estimation error blows up with an increasing SNR.
Energy Efficiency of Hybrid-ARQ under Statistical Queuing Constraints
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, energy efficiency of hybrid automatic repeat request (HARQ) schemes with statistical queuing constraints is studied for both constant-rate and random Markov arrivals by characterizing the minimum energy per bit and wideband slope. The energy efficiency is investigated when either an outage constraint is imposed and (the transmission rate is selected accordingly) or the transmission rate is optimized to maximize the throughput. In both cases, it is also assumed that there is a limitation on the number of retransmissions due to deadline constraints. Under these assumptions, closed-form expressions are obtained for the minimum energy per bit and wideband slope for HARQ with chase combining (CC). Through numerical results, the performances of HARQ-CC and HARQ with incremental redundancy (IR) are compared. Moreover, the impact of source variations/burstiness, deadline constraints, outage probability, queuing constraints on the energy efficiency is analyzed.
Effect-Dependent Transformations for Concurrent Programs
Venue: arXiv cs.PL 2015
Year: 2015

We describe a denotational semantics for an abstract effect system for a higher-order, shared-variable concurrent programming language. We prove the soundness of a number of general effect-based program equivalences, including a parallelization equation that specifies sufficient conditions for replacing sequential composition with parallel composition. Effect annotations are relative to abstract locations specified by contracts rather than physical footprints allowing us in particular to show the soundness of some transformations involving fine-grained concurrent data structures, such as Michael-Scott queues, that allow concurrent access to different parts of mutable data structures. Our semantics is based on refining a trace-based semantics for first-order programs due to Brookes. By moving from concrete to abstract locations, and adding type refinements that capture the possible side-effects of both expressions and their concurrent environments, we are able to validate many equivalences that do not hold in an unrefined model. The meanings of types are expressed using a game-based logical relation over sets of traces. Two programs $e_1$ and $e_2$ are logically related if one is able to solve a two-player game: for any trace with result value $v_1$ in the semantics of $e_1$ (challenge) that the player presents, the opponent can present an (response) equivalent trace in the semantics of $e_2$ with a logically related result value $v_2$.
Uniform Learning in a Deep Neural Network via "Oddball" Stochastic Gradient Descent
Venue: arXiv cs.LG 2015
Year: 2015

When training deep neural networks, it is typically assumed that the training examples are uniformly difficult to learn. Or, to restate, it is assumed that the training error will be uniformly distributed across the training examples. Based on these assumptions, each training example is used an equal number of times. However, this assumption may not be valid in many cases. "Oddball SGD" (novelty-driven stochastic gradient descent) was recently introduced to drive training probabilistically according to the error distribution - training frequency is proportional to training error magnitude. In this article, using a deep neural network to encode a video, we show that oddball SGD can be used to enforce uniform error across the training set.
On path decompositions of 2k-regular graphs
Venue: arXiv cs.DM 2015
Year: 2015

Tibor Gallai conjectured that the edge set of every connected graph $G$ on $n$ vertices can be partitioned into $\lceil n/2\rceil$ paths. Let $\mathcal{G}_{k}$ be the class of all $2k$-regular graphs of girth at least $2k-2$ that admit a pair of disjoint perfect matchings. In this work, we show that Gallai's conjecture holds in $\mathcal{G}_{k}$, for every $k \geq 3$. Further, we prove that for every graph $G$ in $\mathcal{G}_{k}$ on $n$ vertices, there exists a partition of its edge set into $n/2$ paths of lengths in $\{2k-1,2k,2k+1\}$.
A High Throughput List Decoder Architecture for Polar Codes
Venue: arXiv cs.AR 2015
Year: 2015

While long polar codes can achieve the capacity of arbitrary binary-input discrete memoryless channels when decoded by a low complexity successive cancelation (SC) algorithm, the error performance of the SC algorithm is inferior for polar codes with finite block lengths. The cyclic redundancy check (CRC) aided successive cancelation list (SCL) decoding algorithm has better error performance than the SC algorithm. However, current CRC aided SCL (CA-SCL) decoders still suffer from long decoding latency and limited throughput. In this paper, a reduced latency list decoding (RLLD) algorithm for polar codes is proposed. Our RLLD algorithm performs the list decoding on a binary tree, whose leaves correspond to the bits of a polar code. In existing SCL decoding algorithms, all the nodes in the tree are traversed and all possibilities of the information bits are considered. Instead, our RLLD algorithm visits much fewer nodes in the tree and considers fewer possibilities of the information bits. When configured properly, our RLLD algorithm significantly reduces the decoding latency and hence improves throughput, while introducing little performance degradation. Based on our RLLD algorithm, we also propose a high throughput list decoder architecture, which is suitable for larger block lengths due to its scalable partial sum computation unit. Our decoder architecture has been implemented for different block lengths and list sizes using the TSMC 90nm CMOS technology. The implementation results demonstrate that our decoders achieve significant latency reduction and area efficiency improvement compared with other list polar decoders in the literature.
Analysing Sanity of Requirements for Avionics Systems (Preliminary Version)
Venue: arXiv cs.SE 2015
Year: 2015

In the last decade it became a common practice to formalise software requirements to improve the clarity of users' expectations. In this work we build on the fact that functional requirements can be expressed in temporal logic and we propose new sanity checking techniques that automatically detect flaws and suggest improvements of given requirements. Specifically, we describe and experimentally evaluate approaches to consistency and redundancy checking that identify all inconsistencies and pinpoint their exact source (the smallest inconsistent set). We further report on the experience obtained from employing the consistency and redundancy checking in an industrial environment. To complete the sanity checking we also describe a semi-automatic completeness evaluation that can assess the coverage of user requirements and suggest missing properties the user might have wanted to formulate. The usefulness of our completeness evaluation is demonstrated in a case study of an aeroplane control system.
Throughput and Delay Analysis in Video Streaming over Block-Fading Channels
Venue: arXiv cs.IT 2015
Year: 2015

We study video streaming over a slow fading wireless channel. In a streaming application video packets are required to be decoded and displayed in the order they are transmitted as the transmission goes on. This results in per-packet delay constraints, and the resulting channel can be modeled as a physically degraded fading broadcast channel with as many virtual users as the number of packets. In this paper we study two important quality of user experience (QoE) metrics, namely throughput and inter-decoding delay. We introduce several transmission schemes, and compare their throughput and maximum inter-decoding delay performances. We also introduce a genie-aided scheme, which provides theoretical bounds on the achievable performance. We observe that adapting the transmission rate at the packet level, i.e., periodically dropping a subset of the packets, leads to a good tradeoff between the throughput and the maximum inter-decoding delay. We also show that an approach based on initial buffering leads to an asymptotically vanishing packet loss rate at the expense of a relatively large initial delay. For this scheme we derive a condition on the buffering time that leads to throughput maximization.
Human Head Pose Estimation by Facial Features Location
Venue: arXiv cs.CV 2015
Year: 2015

We describe a method for estimating human head pose in a color image that contains enough of information to locate the head silhouette and detect non-trivial color edges of individual facial features. The method works by spotting the human head on an arbitrary background, extracting the head outline, and locating facial features necessary to describe the head orientation in the 3D space. It is robust enough to work with both color and gray-level images featuring quasi-frontal views of a human head under variable lighting conditions.
Hybrid RF and Digital Beamformer for Cellular Networks: Algorithms, Microwave Architectures and Measurements
Venue: arXiv cs.IT 2015
Year: 2015

Modern wireless communication networks, particularly cellular networks utilize multiple antennas to improve the capacity and signal coverage. In these systems, typically an active transceiver is connected to each antenna. However, this one-to-one mapping between transceivers and antennas will dramatically increase the cost and complexity of a large phased antenna array system. In this paper, firstly we propose a \emph{partially adaptive} beamformer architecture where a reduced number of transceivers with a digital beamformer (DBF) is connected to an increased number of antennas through an RF beamforming network (RFBN). Then, based on the proposed architecture, we present a methodology to derive the minimum number of transceivers that are required for marco-cell and small-cell base stations, respectively. Subsequently, in order to achieve optimal beampatterns with given cellular standard requirements and RF operational constraints, we propose efficient algorithms to jointly design DBF and RFBN. Starting from the proposed algorithms, we specify generic microwave RFBNs for optimal marco-cell and small-cell networks. In order to verify the proposed approaches, we compare the performance of RFBN using simulations and anechoic chamber measurements. Experimental measurement results confirm the robustness and performance of the proposed hybrid DBF-RFBN concept eventually ensuring that theoretical multi-antenna capacity and coverage are achieved at a little incremental cost.
Gelisp: A Library to Represent Musical CSPs and Search Strategies
Venue: arXiv cs.AI 2015
Year: 2015

In this paper we present Gelisp, a new library to represent musical Constraint Satisfaction Problems and search strategies intuitively. Gelisp has two interfaces, a command-line one for Common Lisp and a graphical one for OpenMusic. Using Gelisp, we solved a problem of automatic music generation proposed by composer Michael Jarrell and we found solutions for the All-interval series.
AtomNet: A Deep Convolutional Neural Network for Bioactivity Prediction in Structure-based Drug Discovery
Venue: arXiv cs.LG 2015
Year: 2015

Deep convolutional neural networks comprise a subclass of deep neural networks (DNN) with a constrained architecture that leverages the spatial and temporal structure of the domain they model. Convolutional networks achieve the best predictive performance in areas such as speech and image recognition by hierarchically composing simple local features into complex models. Although DNNs have been used in drug discovery for QSAR and ligand-based bioactivity predictions, none of these models have benefited from this powerful convolutional architecture. This paper introduces AtomNet, the first structure-based, deep convolutional neural network designed to predict the bioactivity of small molecules for drug discovery applications. We demonstrate how to apply the convolutional concepts of feature locality and hierarchical composition to the modeling of bioactivity and chemical interactions. In further contrast to existing DNN techniques, we show that AtomNet's application of local convolutional filters to structural target information successfully predicts new active molecules for targets with no previously known modulators. Finally, we show that AtomNet outperforms previous docking approaches on a diverse set of benchmarks by a large margin, achieving an AUC greater than 0.9 on 57.8% of the targets in the DUDE benchmark.
Fast and Accurate Poisson Denoising with Optimized Nonlinear Diffusion
Venue: arXiv cs.CV 2015
Year: 2015

The degradation of the acquired signal by Poisson noise is a common problem for various imaging applications, such as medical imaging, night vision and microscopy. Up to now, many state-of-the-art Poisson denoising techniques mainly concentrate on achieving utmost performance, with little consideration for the computation efficiency. Therefore, in this study we aim to propose an efficient Poisson denoising model with both high computational efficiency and recovery quality. To this end, we exploit the newly-developed trainable nonlinear reaction diffusion model which has proven an extremely fast image restoration approach with performance surpassing recent state-of-the-arts. We retrain the model parameters, including the linear filters and influence functions by taking into account the Poisson noise statistics, and end up with an optimized nonlinear diffusion model specialized for Poisson denoising. The trained model provides strongly competitive results against state-of-the-art approaches, meanwhile bearing the properties of simple structure and high efficiency. Furthermore, our proposed model comes along with an additional advantage, that the diffusion process is well-suited for parallel computation on GPUs. For images of size $512 \times 512$, our GPU implementation takes less than 0.1 seconds to produce state-of-the-art Poisson denoising performance.
On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth
Venue: arXiv cs.CC 2015
Year: 2015

In this paper we study complexity of an extension of ordered binary decision diagrams (OBDDs) called $c$-OBDDs on CNFs of bounded (primal graph) treewidth. In particular, we show that for each $k$ there is a class of CNFs of treewidth $k \geq 3$ for which the equivalent $c$-OBDDs are of size $Ω(n^{k/(8c-4)})$. Moreover, this lower bound holds if $c$-OBDD is non-deterministic and semantic. Our second result uses the above lower bound to separate the above model from sentential decision diagrams (SDDs). In order to obtain the lower bound, we use a structural graph parameter called matching width. Our third result shows that matching width and pathwidth are linearly related.
Synthesis of separable controlled invariant sets for modular local control design
Venue: arXiv cs.SY 2015
Year: 2015

Many correct-by-construction control synthesis methods suffer from the curse of dimensionality. Motivated by this challenge, we seek to reduce a correct-by-construction control synthesis problem to subproblems of more modest dimension. As a step towards this goal, in this paper we consider the problem of synthesizing decoupled robustly controlled invariant sets for dynamically coupled linear subsystems with state and input constraints. Our approach, which gives sufficient conditions for decoupled invariance, is based on optimization over linear matrix inequalities which are obtained using slack variable identities. We illustrate the applicability of our method on several examples, including one where we solve local control synthesis problems in a compositional manner.
Characterization of behavioral patterns exploiting description of geographical areas
Venue: arXiv cs.SI 2015
Year: 2015

The enormous amount of recently available mobile phone data is providing unprecedented direct measurements of human behavior. Early recognition and prediction of behavioral patterns are of great importance in many societal applications like urban planning, transportation optimization, and health-care. Understanding the relationships between human behaviors and location's context is an emerging interest for understanding human-environmental dynamics. Growing availability of Web 2.0, i.e. the increasing amount of websites with mainly user created content and social platforms opens up an opportunity to study such location's contexts. This paper investigates relationships existing between human behavior and location context, by analyzing log mobile phone data records. First an advanced approach to categorize areas in a city based on the presence and distribution of categories of human activity (e.g., eating, working, and shopping) found across the areas, is proposed. The proposed classification is then evaluated through its comparison with the patterns of temporal variation of mobile phone activity and applying machine learning techniques to predict a timeline type of communication activity in a given location based on the knowledge of the obtained category vs. land-use type of the locations areas. The proposed classification turns out to be more consistent with the temporal variation of human communication activity, being a better predictor for those compared to the official land use classification.
Gaussian information matrix for Wiener model identification
Venue: arXiv cs.SY 2015
Year: 2015

We present a closed form expression for the information matrix associated with the Wiener model identification problem under the assumption that the input signal is a stationary Gaussian process. This expression holds under quite generic assumptions. We allow the linear sub-system to have a rational transfer function of arbitrary order, and the static nonlinearity to be a polynomial of arbitrary degree. We also present a simple expression for the determinant of the information matrix. The expressions presented herein has been used for optimal experiment design for Wiener model identification.
Reliability Analysis of Processes with Moving Cracked Material
Venue: arXiv cs.CE 2015
Year: 2015

The reliability of processes with moving elastic and isotropic material containing initial cracks is considered in terms of fracture. The material is modelled as a moving plate which is simply supported from two of its sides and subjected to homogeneous tension acting in the travelling direction. For tension, two models are studied: i) tension is constant with respect to time, and ii) tension varies temporally according to an Ornstein-Uhlenbeck process. Cracks of random length are assumed to occur in the material according to a stochastic counting process. For a general counting process, a representation of the nonfracture probability of the system is obtained that exploits conditional Monte Carlo simulation. Explicit formulae are derived for special cases. To study the reliability of the system with temporally varying tension, a known explicit result for the first passage time of an Ornstein-Uhlenbeck process to a constant boundary is utilized. Numerical examples are provided for printing presses and paper material.
GPS Receiver with Enhanced User Positioning Time
Venue: arXiv cs.SY 2015
Year: 2015

This paper introduces a Global Positioning System (GPS) Receiver that locates user's position instantly. Recently, many mobile devices require location information to add user position into their contents, and some applications require quick positioning when the device is initially switched on. In order to reduce the time to fix user's position, we propose the Instant-On GPS receiver system which is implemented on an ARM based FPGA board, and operates under a very low power mode. We've developed a repeated sleep mode by periods to control the GPS receiver's main power in order to achieve reduced power consumption. By using a high resolution Real Time Clock (RTC), we can estimate frame sync timing without receiving the current frame sync preamble data from a satellite when GPS turns back on. However, the navigation solution needs to be calculated once in advance. The performance results of the proposed GPS receiver in both real world and simulation environment are presented.