OpenRaiser/Intern-Atlas huggingface dataset:
Unified Performance Analysis of Mixed Radio Frequency/Free-Space Optical Dual-Hop Transmission Systems
Venue: arXiv cs.IT 2015
Year: 2015

The mixed radio frequency (RF)/free-space optical (FSO) relaying is a promising technology for coverage improvement, while there lacks unified expressions to describe its performance. In this paper, a unified performance analysis framework of a dual-hop relay system over asymmetric RF/FSO links is presented. More specifically, we consider the RF link follows generalized $κ$-$μ$ or $η$-$μ$ distributions, while the FSO link experiences the gamma-gamma distribution, respectively. Novel analytical expressions of the probability density function and cumulative distribution function are derived. We then capitalize on these results to provide new exact analytical expressions of the outage probability and bit error rate (BER). Furthermore, the outage probability for high signal-to-noise ratios and the BER for different modulation schemes are deduced to provide useful insights into the impact of system and channel parameters of the overall system performance. These accurate expressions are general, since they correspond to generalized fading in the RF link and account for pointing errors, atmospheric turbulence and different modulation schemes in the FSO link. The links between derived results and previous results are presented. Finally, numerical and Monte-Carlo simulation results are provided to demonstrate the validity of the proposed unified expressions.
Effective capacity of communication systems over $κ$-$μ$ shadowed fading channels
Venue: arXiv cs.IT 2015
Year: 2015

The effective capacity of communication systems over generalized $κ$-$μ$ shadowed fading channels is investigated in this letter. A novel and analytical expression for the exact effective capacity is derived in terms of extended generalized bivariate Meijer's-$G$ function. To intuitively reveal the impact of the system and channel parameters on the effective capacity, we also derive closed-form expressions for the effective capacity in the asymptotically high signal-to-noise ratio regime. Our results demonstrate that the effective capacity is a monotonically increasing function of channel fading parameters $κ$ and $μ$ as well as the shadowing parameter $m$, while it decays to zero when the delay constraint $θ\rightarrow \infty$.
Massively Parallel Methods for Deep Reinforcement Learning
Venue: arXiv cs.LG 2015
Year: 2015

We present the first massively distributed architecture for deep reinforcement learning. This architecture uses four main components: parallel actors that generate new behaviour; parallel learners that are trained from stored experience; a distributed neural network to represent the value function or behaviour policy; and a distributed store of experience. We used our architecture to implement the Deep Q-Network algorithm (DQN). Our distributed algorithm was applied to 49 games from Atari 2600 games from the Arcade Learning Environment, using identical hyperparameters. Our performance surpassed non-distributed DQN in 41 of the 49 games and also reduced the wall-time required to achieve these results by an order of magnitude on most games.
Optimal Dynamic Distributed MIS
Venue: arXiv cs.DC 2015
Year: 2015

Finding a maximal independent set (MIS) in a graph is a cornerstone task in distributed computing. The local nature of an MIS allows for fast solutions in a static distributed setting, which are logarithmic in the number of nodes or in their degrees. The result trivially applies for the dynamic distributed model, in which edges or nodes may be inserted or deleted. In this paper, we take a different approach which exploits locality to the extreme, and show how to update an MIS in a dynamic distributed setting, either \emph{synchronous} or \emph{asynchronous}, with only \emph{a single adjustment} and in a single round, in expectation. These strong guarantees hold for the \emph{complete fully dynamic} setting: Insertions and deletions, of edges as well as nodes, gracefully and abruptly. This strongly separates the static and dynamic distributed models, as super-constant lower bounds exist for computing an MIS in the former. Our results are obtained by a novel analysis of the surprisingly simple solution of carefully simulating the greedy \emph{sequential} MIS algorithm with a random ordering of the nodes. As such, our algorithm has a direct application as a $3$-approximation algorithm for correlation clustering. This adds to the important toolbox of distributed graph decompositions, which are widely used as crucial building blocks in distributed computing. Finally, our algorithm enjoys a useful \emph{history-independence} property, meaning the output is independent of the history of topology changes that constructed that graph. This means the output cannot be chosen, or even biased, by the adversary in case its goal is to prevent us from optimizing some objective function.
Trajectory generation for multi-contact momentum-control
Venue: arXiv cs.RO 2015
Year: 2015

Simplified models of the dynamics such as the linear inverted pendulum model (LIPM) have proven to perform well for biped walking on flat ground. However, for more complex tasks the assumptions of these models can become limiting. For example, the LIPM does not allow for the control of contact forces independently, is limited to co-planar contacts and assumes that the angular momentum is zero. In this paper, we propose to use the full momentum equations of a humanoid robot in a trajectory optimization framework to plan its center of mass, linear and angular momentum trajectories. The model also allows for planning desired contact forces for each end-effector in arbitrary contact locations. We extend our previous results on LQR design for momentum control by computing the (linearized) optimal momentum feedback law in a receding horizon fashion. The resulting desired momentum and the associated feedback law are then used in a hierarchical whole body control approach. Simulation experiments show that the approach is computationally fast and is able to generate plans for locomotion on complex terrains while demonstrating good tracking performance for the full humanoid control.
Parallel MMF: a Multiresolution Approach to Matrix Computation
Venue: arXiv cs.NA 2015
Year: 2015

Multiresolution Matrix Factorization (MMF) was recently introduced as a method for finding multiscale structure and defining wavelets on graphs/matrices. In this paper we derive pMMF, a parallel algorithm for computing the MMF factorization. Empirically, the running time of pMMF scales linearly in the dimension for sparse matrices. We argue that this makes pMMF a valuable new computational primitive in its own right, and present experiments on using pMMF for two distinct purposes: compressing matrices and preconditioning large sparse linear systems.
Vehicle Authentication via Monolithically Certified Public Key and Attributes
Venue: arXiv cs.CR 2015
Year: 2015

Vehicular networks are used to coordinate actions among vehicles in traffic by the use of wireless transceivers (pairs of transmitters and receivers). Unfortunately, the wireless communication among vehicles is vulnerable to security threats that may lead to very serious safety hazards. In this work, we propose a viable solution for coping with Man-in-the-Middle attacks. Conventionally, Public Key Infrastructure (PKI) is utilized for a secure communication with the pre-certified public key. However, a secure vehicle-to-vehicle communication requires additional means of verification in order to avoid impersonation attacks. To the best of our knowledge, this is the first work that proposes to certify both the public key and out-of-band sense-able static attributes to enable mutual authentication of the communicating vehicles. Vehicle owners are bound to preprocess (periodically) a certificate for both a public key and a list of fixed unchangeable attributes of the vehicle. Furthermore, the proposed approach is shown to be adaptable with regards to the existing authentication protocols. We illustrate the security verification of the proposed protocol using a detailed proof in Spi calculus.
The Internet of Flying-Things: Opportunities and Challenges with Airborne Fog Computing and Mobile Cloud in the Clouds
Venue: arXiv cs.CY 2015
Year: 2015

This paper focuses on services and applications provided to mobile users using airborne computing infrastructure. We present concepts such as drones-as-a-service and fly-in,fly-out infrastructure, and note data management and system design issues that arise in these scenarios. Issues of Big Data arising from such applications, optimising the configuration of airborne and ground infrastructure to provide the best QoS and QoE, situation-awareness, scalability, reliability, scheduling for efficiency, interaction with users and drones using physical annotations are outlined.
Static Analysis for Logic-Based Dynamic Programs
Venue: arXiv cs.LO 2015
Year: 2015

A dynamic program, as introduced by Patnaik and Immerman (1994), maintains the result of a fixed query for an input database which is subject to tuple insertions and deletions. It can use an auxiliary database whose relations are updated via first-order formulas upon modifications of the input database. This paper studies static analysis problems for dynamic programs and investigates, more specifically, the decidability of the following three questions. Is the answer relation of a given dynamic program always empty? Does a program actually maintain a query? Is the content of auxiliary relations independent of the modification sequence that lead to an input database? In general, all these problems can easily be seen to be undecidable for full first-order programs. Therefore the paper aims at pinpointing the exact decidability borderline for programs with restricted arity (of the input and/or auxiliary database) and restricted quantification.
Notes on axiomatising Hurkens's Paradox
Venue: arXiv cs.LO 2015
Year: 2015

An axiomatisation of Hurkens's paradox in dependent type theory is given without assuming any impredicative feature of said type theory.
GFDM - A Framework for Virtual PHY Services in 5G Networks
Venue: arXiv cs.IT 2015
Year: 2015

The next generation of wireless networks will face different challenges from new scenarios. The main contribution of this paper is to show that Generalized Frequency Division Multiplexing (GFDM), as a baseline of flexible circular filtered multicarrier systems, can be used as a framework to virtualize the PHY service for the upper layers of 5G networks. This framework opens the possibility to apply software-defined network principles to produce software-defined waveforms capable of addressing the requirements of future mobile networks. Hence, a block oriented concept will be used to provide the modulation service, emulating different flavors of waveforms designed to go beyond the well-established Orthogonal Frequency Division Multiplexing (OFDM) principles, in scenarios where they perform best. The virtual physical layer (PHY) service opens the opportunity to have a fast and dynamic evolution of the infrastructure, as applications change over time. The presented unified modulation concept contributes with future research directions to address burst and continuous transmissions, referencing basic approaches for synchronization and advanced receiver design that can be exploited in future for the whole frame structure design and channel estimation strategies.
Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover
Venue: arXiv cs.CC 2015
Year: 2015

Set cover, over a universe of size $n$, may be modelled as a data-streaming problem, where the $m$ sets that comprise the instance are to be read one by one. A semi-streaming algorithm is allowed only $O(n\, \mathrm{poly}\{\log n, \log m\})$ space to process this stream. For each $p \ge 1$, we give a very simple deterministic algorithm that makes $p$ passes over the input stream and returns an appropriately certified $(p+1)n^{1/(p+1)}$-approximation to the optimum set cover. More importantly, we proceed to show that this approximation factor is essentially tight, by showing that a factor better than $0.99\,n^{1/(p+1)}/(p+1)^2$ is unachievable for a $p$-pass semi-streaming algorithm, even allowing randomisation. In particular, this implies that achieving a $Θ(\log n)$-approximation requires $Ω(\log n/\log\log n)$ passes, which is tight up to the $\log\log n$ factor. These results extend to a relaxation of the set cover problem where we are allowed to leave an $\varepsilon$ fraction of the universe uncovered: the tight bounds on the best approximation factor achievable in $p$ passes turn out to be $Θ_p(\min\{n^{1/(p+1)}, \varepsilon^{-1/p}\})$. Our lower bounds are based on a construction of a family of high-rank incidence geometries, which may be thought of as vast generalisations of affine planes. This construction, based on algebraic techniques, appears flexible enough to find other applications and is therefore interesting in its own right.
Recursive Sparse Point Process Regression with Application to Spectrotemporal Receptive Field Plasticity Analysis
Venue: arXiv cs.NE 2015
Year: 2015

We consider the problem of estimating the sparse time-varying parameter vectors of a point process model in an online fashion, where the observations and inputs respectively consist of binary and continuous time series. We construct a novel objective function by incorporating a forgetting factor mechanism into the point process log-likelihood to enforce adaptivity and employ $\ell_1$-regularization to capture the sparsity. We provide a rigorous analysis of the maximizers of the objective function, which extends the guarantees of compressed sensing to our setting. We construct two recursive filters for online estimation of the parameter vectors based on proximal optimization techniques, as well as a novel filter for recursive computation of statistical confidence regions. Simulation studies reveal that our algorithms outperform several existing point process filters in terms of trackability, goodness-of-fit and mean square error. We finally apply our filtering algorithms to experimentally recorded spiking data from the ferret primary auditory cortex during attentive behavior in a click rate discrimination task. Our analysis provides new insights into the time-course of the spectrotemporal receptive field plasticity of the auditory neurons.
The Complexity of Switching and FACTS Maximum-Potential-Flow Problems
Venue: arXiv cs.CC 2015
Year: 2015

This papers considers the problem of maximizing the load that can be served by a power network. We use the commonly accepted Linear DC power network model and consider wo configuration options: switching lines and using FACTS devices. We present the first comprehensive complexity study of this optimization problem. Our results show hat the problem is NP-complete and that there is no fully polynomial-time approximation scheme. For switching, these results extend to planar networks with a aximum-node degree of 3. Additionally, we demonstrate that the optimization problems are still NP-hard if we restrict the network structure to cacti with a maximum degree of 3.
Multiscale Adaptive Representation of Signals: I. The Basic Framework
Venue: arXiv cs.CV 2015
Year: 2015

We introduce a framework for designing multi-scale, adaptive, shift-invariant frames and bi-frames for representing signals. The new framework, called AdaFrame, improves over dictionary learning-based techniques in terms of computational efficiency at inference time. It improves classical multi-scale basis such as wavelet frames in terms of coding efficiency. It provides an attractive alternative to dictionary learning-based techniques for low level signal processing tasks, such as compression and denoising, as well as high level tasks, such as feature extraction for object recognition. Connections with deep convolutional networks are also discussed. In particular, the proposed framework reveals a drawback in the commonly used approach for visualizing the activations of the intermediate layers in convolutional networks, and suggests a natural alternative.
Do recommender systems benefit users?
Venue: arXiv cs.CY 2015
Year: 2015

Recommender systems are present in many web applications to guide our choices. They increase sales and benefit sellers, but whether they benefit customers by providing relevant products is questionable. Here we introduce a model to examine the benefit of recommender systems for users, and found that recommendations from the system can be equivalent to random draws if one relies too strongly on the system. Nevertheless, with sufficient information about user preferences, recommendations become accurate and an abrupt transition to this accurate regime is observed for some algorithms. On the other hand, we found that a high accuracy evaluated by common accuracy metrics does not necessarily correspond to a high real accuracy nor a benefit for users, which serves as an alarm for operators and researchers of recommender systems. We tested our model with a real dataset and observed similar behaviors. Finally, a recommendation approach with improved accuracy is suggested. These results imply that recommender systems can benefit users, but relying too strongly on the system may render the system ineffective.
A New and More General Capacity Theorem for the Gaussian Channel with Two-sided Input-Noise Dependent State Information
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, a new and general version of Gaussian channel in presence of two-sided state information correlated to the channel input and noise is considered. Determining a general achievable rate for the channel and obtaining the capacity in a non-limiting case, we try to analyze and solve the Gaussian version of the Cover-Chiang theorem -as an open problem- mathematically and information-theoretically. Our capacity theorem, while including all previous theorems as its special cases, explains situations that can not be analyzed by them; for example, the effect of the correlation between the side information and the channel input on the capacity of the channel that can not be analyzed with Costa's "writing on dirty paper" theorem. Meanwhile, we try to introduce our new idea, i.e., describing the concept of "cognition" of a communicating object (transmitter, receiver, relay and so on) on some variable (channel noise, interference and so on) with the information-theoretic concept of "side information" correlated to that variable and known by the object. According to our theorem, the channel capacity is an increasing function of the mutual information of the side information and the channel noise. Therefore our channel and its capacity theorem exemplify the "cognition" of the transmitter and receiver on the channel noise based on the new description. Our capacity theorem has interesting interpretations originated from this new idea.
A class of cyclic Codes Over the Ring $\Z_4[u]/<u^2>$ and its Gray image
Venue: arXiv cs.IT 2015
Year: 2015

Cyclic codes over R have been introduced recently. In this paper, we study the cyclic codes over R and their $\Z_2$ image. Making use of algebraic structure, we find the some good $\Z_2$ codes of length 28.
Structurally Tractable Uncertain Data
Venue: arXiv cs.DB 2015
Year: 2015

Many data management applications must deal with data which is uncertain, incomplete, or noisy. However, on existing uncertain data representations, we cannot tractably perform the important query evaluation tasks of determining query possibility, certainty, or probability: these problems are hard on arbitrary uncertain input instances. We thus ask whether we could restrict the structure of uncertain data so as to guarantee the tractability of exact query evaluation. We present our tractability results for tree and tree-like uncertain data, and a vision for probabilistic rule reasoning. We also study uncertainty about order, proposing a suitable representation, and study uncertain data conditioned by additional observations.
Target localization in wireless sensor networks based on received signal strength
Venue: arXiv cs.NI 2015
Year: 2015

We consider the problem of localizing a target taking the help of a set of anchor beacon nodes.A small number of beacon nodes are deployed at known locations in the area.The target can detect a beacon provided it happens to lie within the beacons's transmission range.Thus, the target contains a measurement vector containing the readings of the beacons: '1' corresponding to a beacon if it is able to detect the target and '0' if the beacon is not able to detect the target.The goal is two fold: to determine the location of the target based on the binary measurement vector at the target and to study the behavior of the localization uncertainty as a function of the beacon transmission range and the number of beacons deployed.Beacon transmission range means signal strength of the beacon to transmit and receive the signals which is called as Received Signal Strength.To localize the target, we propose a grid mapping based approach, where the readings corresponding to locations on a grid overlaid on a region of interest are used to localize a target.To study the behavior of the localization uncertainty as a function of the sensing radius and number of beacons,extensive simulations and numerical experiments are carried out.The results provide insights into an importance of optimally setting the sensing radius and the improvement obtainable with increasing number of beacons.
Classification of Complex Wishart Matrices with a Diffusion-Reaction System guided by Stochastic Distances
Venue: arXiv cs.CV 2015
Year: 2015

We propose a new method for PolSAR (Polarimetric Synthetic Aperture Radar) imagery classification based on stochastic distances in the space of random matrices obeying complex Wishart distributions. Given a collection of prototypes $\{Z_m\}_{m=1}^M$ and a stochastic distance $d(.,.)$, we classify any random matrix $X$ using two criteria in an iterative setup. Firstly, we associate $X$ to the class which minimizes the weighted stochastic distance $w_md(X,Z_m)$, where the positive weights $w_m$ are computed to maximize the class discrimination power. Secondly, we improve the result by embedding the classification problem into a diffusion-reaction partial differential system where the diffusion term smooths the patches within the image, and the reaction term tends to move the pixel values towards the closest class prototype. In particular, the method inherits the benefits of speckle reduction by diffusion-like methods. Results on synthetic and real PolSAR data show the performance of the method.
Toward a new language of legal drafting
Venue: arXiv cs.CY 2015
Year: 2015

Lawyers should write in document markup language just like web developers, digital publishers, scientists, and almost everyone else
Secure management of logs in internet of things
Venue: arXiv cs.CR 2015
Year: 2015

Ever since the advent of computing, managing data has been of extreme importance. With innumerable devices getting added to network infrastructure, there has been a proportionate increase in the data which needs to be stored. With the advent of Internet of Things (IOT) it is anticipated that billions of devices will be a part of the internet in another decade. Since those devices will be communicating with each other on a regular basis with little or no human intervention, plethora of real time data will be generated in quick time which will result in large number of log files. Apart from complexity pertaining to storage, it will be mandatory to maintain confidentiality and integrity of these logs in IOT enabled devices. This paper will provide a brief overview about how logs can be efficiently and securely stored in IOT devices.