OpenRaiser/Intern-Atlas huggingface dataset:
Sampling for approximating $R$-limited functions
Venue: arXiv cs.IT 2017
Year: 2017

$R$-limited functions are multivariate generalization of band-limited functions whose Fourier transforms are supported within a compact region $R\subset\mathbb{R}^{n}$. In this work, we generalize sampling and interpolation theorems for band-limited functions to $R$-limited functions. More precisely, we investigated the following question: "For a function compactly supported within a region similar to $R$, does there exist an $R$-limited function that agrees with the function over its support for a desired accuracy?". Starting with the Fourier domain definition of an $R$-limited function, we write the equivalent convolution and a discrete Fourier transform representations for $R$-limited functions through approximation of the convolution kernel using a discrete subset of Fourier basis. The accuracy of the approximation of the convolution kernel determines the accuracy of the discrete Fourier representation. Construction of the discretization can be achieved using the tools from approximation theory as demonstrated in the appendices. The main contribution of this work is proving the equivalence between the discretization of the Fourier and convolution representations of $R$-limited functions. Here discrete convolution representation is restricted to shifts over a compactly supported region similar to $R$. We show that discrete shifts for the convolution representation are equivalent to the spectral parameters used in discretization of the Fourier representation of the convolution kernel. This result is a generalization of the cardinal theorem of interpolation of band-limited functions. The error corresponding to discrete convolution representation is also bounded by the approximation of the convolution kernel using discretized Fourier basis.
The Satisfiability Problem for Boolean Set Theory with a Choice Correspondence
Venue: arXiv cs.LO 2017
Year: 2017

Given a set U of alternatives, a choice (correspondence) on U is a contractive map c defined on a family Omega of nonempty subsets of U. Semantically, a choice c associates to each menu A in Omega a nonempty subset c(A) of A comprising all elements of A that are deemed selectable by an agent. A choice on U is total if its domain is the powerset of U minus the empty set, and partial otherwise. According to the theory of revealed preferences, a choice is rationalizable if it can be retrieved from a binary relation on U by taking all maximal elements of each menu. It is well-known that rationalizable choices are characterized by the satisfaction of suitable axioms of consistency, which codify logical rules of selection within menus. For instance, WARP (Weak Axiom of Revealed Preference) characterizes choices rationalizable by a transitive relation. Here we study the satisfiability problem for unquantified formulae of an elementary fragment of set theory involving a choice function symbol c, the Boolean set operators and the singleton, the equality and inclusion predicates, and the propositional connectives. In particular, we consider the cases in which the interpretation of c satisfies any combination of two specific axioms of consistency, whose conjunction is equivalent to WARP. In two cases we prove that the related satisfiability problem is NP-complete, whereas in the remaining cases we obtain NP-completeness under the additional assumption that the number of choice terms is constant.
Robust Exponential Worst Cases for Divide-et-Impera Algorithms for Parity Games
Venue: arXiv cs.LO 2017
Year: 2017

The McNaughton-Zielonka divide et impera algorithm is the simplest and most flexible approach available in the literature for determining the winner in a parity game. Despite its theoretical worst-case complexity and the negative reputation as a poorly effective algorithm in practice, it has been shown to rank among the best techniques for the solution of such games. Also, it proved to be resistant to a lower bound attack, even more than the strategy improvements approaches, and only recently a family of games on which the algorithm requires exponential time has been provided by Friedmann. An easy analysis of this family shows that a simple memoization technique can help the algorithm solve the family in polynomial time. The same result can also be achieved by exploiting an approach based on the dominion-decomposition techniques proposed in the literature. These observations raise the question whether a suitable combination of dynamic programming and game-decomposition techniques can improve on the exponential worst case of the original algorithm. In this paper we answer this question negatively, by providing a robustly exponential worst case, showing that no intertwining of the above mentioned techniques can help mitigating the exponential nature of the divide et impera approaches.
Dynamics and Coalitions in Sequential Games
Venue: arXiv cs.GT 2017
Year: 2017

We consider N-player non-zero sum games played on finite trees (i.e., sequential games), in which the players have the right to repeatedly update their respective strategies (for instance, to improve the outcome wrt to the current strategy profile). This generates a dynamics in the game which may eventually stabilise to a Nash Equilibrium (as with Kukushkin's lazy improvement), and we argue that it is interesting to study the conditions that guarantee such a dynamics to terminate. We build on the works of Le Roux and Pauly who have studied extensively one such dynamics, namely the Lazy Improvement Dynamics. We extend these works by first defining a turn-based dynamics, proving that it terminates on subgame perfect equilibria, and showing that several variants do not terminate. Second, we define a variant of Kukushkin's lazy improvement where the players may now form coalitions to change strategies. We show how properties of the players' preferences on the outcomes affect the termination of this dynamics, and we thereby characterise classes of games where it always terminates (in particular two-player games).
Model Checking Social Network Models
Venue: arXiv cs.LO 2017
Year: 2017

A social network service is a platform to build social relations among people sharing similar interests and activities. The underlying structure of a social networks service is the social graph, where nodes represent users and the arcs represent the users' social links and other kind of connections. One important concern in social networks is privacy: what others are (not) allowed to know about us. The "logic of knowledge" (epistemic logic) is thus a good formalism to define, and reason about, privacy policies. In this paper we consider the problem of verifying knowledge properties over social network models (SNMs), that is social graphs enriched with knowledge bases containing the information that the users know. More concretely, our contributions are: i) We prove that the model checking problem for epistemic properties over SNMs is decidable; ii) We prove that a number of properties of knowledge that are sound w.r.t. Kripke models are also sound w.r.t. SNMs; iii) We give a satisfaction-preserving encoding of SNMs into canonical Kripke models, and we also characterise which Kripke models may be translated into SNMs; iv) We show that, for SNMs, the model checking problem is cheaper than the one based on standard Kripke models. Finally, we have developed a proof-of-concept implementation of the model-checking algorithm for SNMs.
CNN for Very Fast Ground Segmentation in Velodyne LiDAR Data
Venue: arXiv cs.RO 2017
Year: 2017

This paper presents a novel method for ground segmentation in Velodyne point clouds. We propose an encoding of sparse 3D data from the Velodyne sensor suitable for training a convolutional neural network (CNN). This general purpose approach is used for segmentation of the sparse point cloud into ground and non-ground points. The LiDAR data are represented as a multi-channel 2D signal where the horizontal axis corresponds to the rotation angle and the vertical axis the indexes channels (i.e. laser beams). Multiple topologies of relatively shallow CNNs (i.e. 3-5 convolutional layers) are trained and evaluated using a manually annotated dataset we prepared. The results show significant improvement of performance over the state-of-the-art method by Zhang et al. in terms of speed and also minor improvements in terms of accuracy.
Real-time convolutional networks for sonar image classification in low-power embedded systems
Venue: arXiv cs.CV 2017
Year: 2017

Deep Neural Networks have impressive classification performance, but this comes at the expense of significant computational resources at inference time. Autonomous Underwater Vehicles use low-power embedded systems for sonar image perception, and cannot execute large neural networks in real-time. We propose the use of max-pooling aggressively, and we demonstrate it with a Fire-based module and a new Tiny module that includes max-pooling in each module. By stacking them we build networks that achieve the same accuracy as bigger ones, while reducing the number of parameters and considerably increasing computational performance. Our networks can classify a 96x96 sonar image with 98.8 - 99.7 accuracy on only 41 to 61 milliseconds on a Raspberry Pi 2, which corresponds to speedups of 28.6 - 19.7.
Simulating Cellular Communications in Vehicular Networks: Making SimuLTE Interoperable with Veins
Venue: arXiv cs.NI 2017
Year: 2017

The evolution of cellular technologies toward 5G progressively enables efficient and ubiquitous communications in an increasing number of fields. Among these, vehicular networks are being considered as one of the most promising and challenging applications, requiring support for communications in high-speed mobility and delay-constrained information exchange in proximity. In this context, simulation frameworks under the OMNeT++ umbrella are already available: SimuLTE and Veins for cellular and vehicular systems, respectively. In this paper, we describe the modifications that make SimuLTE interoperable with Veins and INET, which leverage the OMNeT++ paradigm, and allow us to achieve our goal without any modification to either of the latter two. We discuss the limitations of the previous solution, namely VeinsLTE, which integrates all three in a single framework, thus preventing independent evolution and upgrades of each building block.
Sparsity-Based Super Resolution for SEM Images
Venue: arXiv cs.CV 2017
Year: 2017

The scanning electron microscope (SEM) produces an image of a sample by scanning it with a focused beam of electrons. The electrons interact with the atoms in the sample, which emit secondary electrons that contain information about the surface topography and composition. The sample is scanned by the electron beam point by point, until an image of the surface is formed. Since its invention in 1942, SEMs have become paramount in the discovery and understanding of the nanometer world, and today it is extensively used for both research and in industry. In principle, SEMs can achieve resolution better than one nanometer. However, for many applications, working at sub-nanometer resolution implies an exceedingly large number of scanning points. For exactly this reason, the SEM diagnostics of microelectronic chips is performed either at high resolution (HR) over a small area or at low resolution (LR) while capturing a larger portion of the chip. Here, we employ sparse coding and dictionary learning to algorithmically enhance LR SEM images of microelectronic chips up to the level of the HR images acquired by slow SEM scans, while considerably reducing the noise. Our methodology consists of two steps: an offline stage of learning a joint dictionary from a sequence of LR and HR images of the same region in the chip, followed by a fast-online super-resolution step where the resolution of a new LR image is enhanced. We provide several examples with typical chips used in the microelectronics industry, as well as a statistical study on arbitrary images with characteristic structural features. Conceptually, our method works well when the images have similar characteristics. This work demonstrates that employing sparsity concepts can greatly improve the performance of SEM, thereby considerably increasing the scanning throughput without compromising on analysis quality and resolution.
Visual Cues to Improve Myoelectric Control of Upper Limb Prostheses
Venue: arXiv cs.CV 2017
Year: 2017

The instability of myoelectric signals over time complicates their use to control highly articulated prostheses. To address this problem, studies have tried to combine surface electromyography with modalities that are less affected by the amputation and environment, such as accelerometry or gaze information. In the latter case, the hypothesis is that a subject looks at the object he or she intends to manipulate and that knowing this object's affordances allows to constrain the set of possible grasps. In this paper, we develop an automated way to detect stable fixations and show that gaze information is indeed helpful in predicting hand movements. In our multimodal approach, we automatically detect stable gazes and segment an object of interest around the subject's fixation in the visual frame. The patch extracted around this object is subsequently fed through an off-the-shelf deep convolutional neural network to obtain a high level feature representation, which is then combined with traditional surface electromyography in the classification stage. Tests have been performed on a dataset acquired from five intact subjects who performed ten types of grasps on various objects as well as in a functional setting. They show that the addition of gaze information increases the classification accuracy considerably. Further analysis demonstrates that this improvement is consistent for all grasps and concentrated during the movement onset and offset.
Towards a Dedicated Computer Vision Tool set for Crowd Simulation Models
Venue: arXiv cs.CV 2017
Year: 2017

As the population of world is increasing, and even more concentrated in urban areas, ensuring public safety is becoming a taunting job for security personnel and crowd managers. Mass events like sports, festivals, concerts, political gatherings attract thousand of people in a constraint environment,therefore adequate safety measures should be adopted. Despite safety measures, crowd disasters still occur frequently. Understanding underlying dynamics and behavior of crowd is becoming areas of interest for most of computer scientists. In recent years, researchers developed several models for understanding crowd dynamics. These models should be properly calibrated and validated by means of data acquired in the field. In this paper, we developed a computer vision tool set that can be helpful not only in initializing the crowd simulation models but can also validate the simulation results. The main features of proposed tool set are: (1) Crowd flow segmentation and crowd counting, (2) Identifying source/sink location for understanding crowd behavior, (3) Group detection and tracking in crowds.
Deep Galaxy: Classification of Galaxies based on Deep Convolutional Neural Networks
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, a deep convolutional neural network architecture for galaxies classification is presented. The galaxy can be classified based on its features into main three categories Elliptical, Spiral, and Irregular. The proposed deep galaxies architecture consists of 8 layers, one main convolutional layer for features extraction with 96 filters, followed by two principles fully connected layers for classification. It is trained over 1356 images and achieved 97.272% in testing accuracy. A comparative result is made and the testing accuracy was compared with other related works. The proposed architecture outperformed other related works in terms of testing accuracy.
Uncertainty-Aware Learning from Demonstration using Mixture Density Networks with Sampling-Free Variance Modeling
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we propose an uncertainty-aware learning from demonstration method by presenting a novel uncertainty estimation method utilizing a mixture density network appropriate for modeling complex and noisy human behaviors. The proposed uncertainty acquisition can be done with a single forward path without Monte Carlo sampling and is suitable for real-time robotics applications. The properties of the proposed uncertainty measure are analyzed through three different synthetic examples, absence of data, heavy measurement noise, and composition of functions scenarios. We show that each case can be distinguished using the proposed uncertainty measure and presented an uncertainty-aware learn- ing from demonstration method of an autonomous driving using this property. The proposed uncertainty-aware learning from demonstration method outperforms other compared methods in terms of safety using a complex real-world driving dataset.
DeepFeat: A Bottom Up and Top Down Saliency Model Based on Deep Features of Convolutional Neural Nets
Venue: arXiv cs.CV 2017
Year: 2017

A deep feature based saliency model (DeepFeat) is developed to leverage the understanding of the prediction of human fixations. Traditional saliency models often predict the human visual attention relying on few level image cues. Although such models predict fixations on a variety of image complexities, their approaches are limited to the incorporated features. In this study, we aim to provide an intuitive interpretation of convolu- tional neural network deep features by combining low and high level visual factors. We exploit four evaluation metrics to evaluate the correspondence between the proposed framework and the ground-truth fixations. The key findings of the results demon- strate that the DeepFeat algorithm, incorporation of bottom up and top down saliency maps, outperforms the individual bottom up and top down approach. Moreover, in comparison to nine 9 state-of-the-art saliency models, our proposed DeepFeat model achieves satisfactory performance based on all four evaluation metrics.
Super-speeds with Zero-RAM: Next Generation Large-Scale Optimization in Your Laptop!
Venue: arXiv cs.DC 2017
Year: 2017

This article presents the novel breakthrough general purpose algorithm for large scale optimization problems. The novel algorithm is capable of achieving breakthrough speeds for very large-scale optimization on general purpose laptops and embedded systems. Application of the algorithm to the Griewank function was possible in up to 1 billion decision variables in double precision took only 64485 seconds (~18 hours) to solve, while consuming 7,630 MB (7.6 GB) or RAM on a single threaded laptop CPU. It shows that the algorithm is computationally and memory (space) linearly efficient, and can find the optimal or near-optimal solution in a fraction of the time and memory that many conventional algorithms require. It is envisaged that this will open up new possibilities of real-time large-scale problems on personal laptops and embedded systems.
A Simple Two-stage Equalizer With Simplified Orthogonal Time Frequency Space Modulation Over Rapidly Time-varying Channels
Venue: arXiv cs.IT 2017
Year: 2017

In this work, we derive a equivalent delay-Doppler channel matrix of the Orthogonal Time Frequency Space (OTFS) modulation that has not been studied in previous literature. It has the similar structure as the banded channel matrix of OFDM systems over rapidly time-varying channels. However, the band in the equivalent channel matrix will no longer spread with the increase of the Doppler spread once the length of maximum channel delay spread and the OTFS frame duration are deter- mined. Furthermore, the equivalent channel matrix can simplify the OTFS modulation in the transmitter side. Incorporating the equivalent channel matrix, we propose a simple two-stage equal- izer in 1 dimensional operations for OTFS modulation. First, the receive signal is equalized using the conventional OFDM single- tap equalizer in the frequency domain. The multipath effects can be removed. In the second stage, another low complexity delay- Doppler domain equalizer is employed to eliminate the effects of the residual interference caused by the Doppler spread with the equivalent channel matrix. The simulation results demonstrate that the proposed method is superior to the conventional single- tap equalizer and full minimum mean squared error (MMSE) equalizer of OFDM systems in terms of BER in high Doppler spread scenarios.
"Breaking" Disasters: Predicting and Characterizing the Global News Value of Natural and Man-made Disasters
Venue: arXiv cs.SI 2017
Year: 2017

Due to their often unexpected nature, natural and man-made disasters are difficult to monitor and detect for journalists and disaster management response teams. Journalists are increasingly relying on signals from social media to detect such stories in their early stage of development. Twitter, which features a vast network of local news outlets, is a major source of early signal for disaster detection. Journalists who work for global desks often follow these sources via Twitter's lists, but have to comb through thousands of small-scale or low-impact stories to find events that may be globally relevant. These are events that have a large scope, high impact, or potential geo-political relevance. We propose a model for automatically identifying events from local news sources that may break on a global scale within the next 24 hours. The results are promising and can be used in a predictive setting to help journalists manage their sources more effectively, or in a descriptive manner to analyze media coverage of disasters. Through the feature evaluation process, we also address the question: "what makes a disaster event newsworthy on a global scale?" As part of our data collection process, we have created a list of local sources of disaster/accident news on Twitter, which we have made publicly available.