OpenRaiser/Intern-Atlas huggingface dataset:
Pattern Formation Problem for Synchronous Mobile Robots in the Three Dimensional Euclidean Space
Venue: arXiv cs.DC 2016
Year: 2016

We consider a swarm of autonomous mobile robots each of which is an anonymous point in the three-dimensional Euclidean space (3D-space) and synchronously executes a common distributed algorithm. We investigate the pattern formation problem that requires the robots to form a given target pattern from an initial configuration and characterize the problem by showing a necessary and sufficient condition for the robots to form a given target pattern. The pattern formation problem in the two dimensional Euclidean space (2D-space) has been investigated by Suzuki and Yamashita (SICOMP 1999, TCS 2010), and Fujinaga et al. (SICOMP 2015). The symmetricity $ρ(P)$ of a configuration (i.e., the positions of robots) $P$ is intuitively the order of the cyclic group that acts on $P$. It has been shown that fully-synchronous (FSYNC) robots can form a target pattern $F$ from an initial configuration $P$ if and only if $ρ(P)$ divides $ρ(F)$. We extend the notion of symmetricity to 3D-space by using the rotation groups each of which is defined by a set of rotation axes and their arrangement. We define the symmetricity $\varrho(P)$ of configuration $P$ in 3D-space as the set of rotation groups that acts on $P$ and whose rotation axes do not contain any robot. We show the following necessary and sufficient condition for the pattern formation problem which is a natural extension of the existing results of the pattern formation problem in 2D-space: FSYNC robots in 3D-space can form a target pattern $F$ from an initial configuration $P$ if and only if $\varrho(P) \subseteq \varrho(F)$. For solvable instances, we present a pattern formation algorithm for oblivious FSYNC robots. The insight of this paper is that symmetry of mobile robots in 3D-space is sometimes lower than the symmetry of their positions and the robots can show their symmetry by their movement.
Generative Adversarial Networks in Estimation of Distribution Algorithms for Combinatorial Optimization
Venue: arXiv cs.NE 2016
Year: 2016

Estimation of Distribution Algorithms (EDAs) require flexible probability models that can be efficiently learned and sampled. Generative Adversarial Networks (GAN) are generative neural networks which can be trained to implicitly model the probability distribution of given data, and it is possible to sample this distribution. We integrate a GAN into an EDA and evaluate the performance of this system when solving combinatorial optimization problems with a single objective. We use several standard benchmark problems and compare the results to state-of-the-art multivariate EDAs. GAN-EDA doe not yield competitive results - the GAN lacks the ability to quickly learn a good approximation of the probability distribution. A key reason seems to be the large amount of noise present in the first EDA generations.
Fast Single Image Super-Resolution
Venue: arXiv cs.CV 2016
Year: 2016

This paper addresses the problem of single image super-resolution (SR), which consists of recovering a high resolution image from its blurred, decimated and noisy version. The existing algorithms for single image SR use different strategies to handle the decimation and blurring operators. In addition to the traditional first-order gradient methods, recent techniques investigate splitting-based methods dividing the SR problem into up-sampling and deconvolution steps that can be easily solved. Instead of following this splitting strategy, we propose to deal with the decimation and blurring operators simultaneously by taking advantage of their particular properties in the frequency domain, leading to a new fast SR approach. Specifically, an analytical solution can be obtained and implemented efficiently for the Gaussian prior or any other regularization that can be formulated into an $\ell_2$-regularized quadratic model, i.e., an $\ell_2$-$\ell_2$ optimization problem. Furthermore, the flexibility of the proposed SR scheme is shown through the use of various priors/regularizations, ranging from generic image priors to learning-based approaches. In the case of non-Gaussian priors, we show how the analytical solution derived from the Gaussian case can be embedded intotraditional splitting frameworks, allowing the computation cost of existing algorithms to be decreased significantly. Simulation results conducted on several images with different priors illustrate the effectiveness of our fast SR approach compared with the existing techniques.
Multimodal Hierarchical Dirichlet Process-based Active Perception
Venue: arXiv cs.RO 2016
Year: 2016

In this paper, we propose an active perception method for recognizing object categories based on the multimodal hierarchical Dirichlet process (MHDP). The MHDP enables a robot to form object categories using multimodal information, e.g., visual, auditory, and haptic information, which can be observed by performing actions on an object. However, performing many actions on a target object requires a long time. In a real-time scenario, i.e., when the time is limited, the robot has to determine the set of actions that is most effective for recognizing a target object. We propose an MHDP-based active perception method that uses the information gain (IG) maximization criterion and lazy greedy algorithm. We show that the IG maximization criterion is optimal in the sense that the criterion is equivalent to a minimization of the expected Kullback--Leibler divergence between a final recognition state and the recognition state after the next set of actions. However, a straightforward calculation of IG is practically impossible. Therefore, we derive an efficient Monte Carlo approximation method for IG by making use of a property of the MHDP. We also show that the IG has submodular and non-decreasing properties as a set function because of the structure of the graphical model of the MHDP. Therefore, the IG maximization problem is reduced to a submodular maximization problem. This means that greedy and lazy greedy algorithms are effective and have a theoretical justification for their performance. We conducted an experiment using an upper-torso humanoid robot and a second one using synthetic data. The experimental results show that the method enables the robot to select a set of actions that allow it to recognize target objects quickly and accurately. The results support our theoretical outcomes.
Off-the-Grid Recovery of Piecewise Constant Images from Few Fourier Samples
Venue: arXiv cs.CV 2016
Year: 2016

We introduce a method to recover a continuous domain representation of a piecewise constant two-dimensional image from few low-pass Fourier samples. Assuming the edge set of the image is localized to the zero set of a trigonometric polynomial, we show the Fourier coefficients of the partial derivatives of the image satisfy a linear annihilation relation. We present necessary and sufficient conditions for unique recovery of the image from finite low-pass Fourier samples using the annihilation relation. We also propose a practical two-stage recovery algorithm which is robust to model-mismatch and noise. In the first stage we estimate a continuous domain representation of the edge set of the image. In the second stage we perform an extrapolation in Fourier domain by a least squares two-dimensional linear prediction, which recovers the exact Fourier coefficients of the underlying image. We demonstrate our algorithm on the super-resolution recovery of MRI phantoms and real MRI data from low-pass Fourier samples, which shows benefits over standard approaches for single-image super-resolution MRI.
Long-Range Communications in Unlicensed Bands: the Rising Stars in the IoT and Smart City Scenarios
Venue: arXiv cs.NI 2016
Year: 2016

Connectivity is probably the most basic building block of the Internet of Things (IoT) paradigm. Up to know, the two main approaches to provide data access to the \emph{things} have been based either on multi-hop mesh networks using short-range communication technologies in the unlicensed spectrum, or on long-range, legacy cellular technologies, mainly 2G/GSM, operating in the corresponding licensed frequency bands. Recently, these reference models have been challenged by a new type of wireless connectivity, characterized by low-rate, long-range transmission technologies in the unlicensed sub-GHz frequency bands, used to realize access networks with star topology which are referred to a \emph{Low-Power Wide Area Networks} (LPWANs). In this paper, we introduce this new approach to provide connectivity in the IoT scenario, discussing its advantages over the established paradigms in terms of efficiency, effectiveness, and architectural design, in particular for the typical Smart Cities applications.
Modeling and Analyzing the Coexistence of Wi-Fi and LTE in Unlicensed Spectrum
Venue: arXiv cs.IT 2016
Year: 2016

We leverage stochastic geometry to characterize key performance metrics for neighboring Wi-Fi and LTE networks in unlicensed spectrum. Our analysis focuses on a single unlicensed frequency band, where the locations for the Wi-Fi access points (APs) and LTE eNodeBs (eNBs) are modeled as two independent homogeneous Poisson point processes. Three LTE coexistence mechanisms are investigated: (1) LTE with continuous transmission and no protocol modifications; (2) LTE with discontinuous transmission; and (3) LTE with listen-before-talk (LBT) and random back-off (BO). For each scenario, we have derived the medium access probability (MAP), the signal-to-interference-plus-noise ratio (SINR) coverage probability, the density of successful transmissions (DST), and the rate coverage probability for both Wi-Fi and LTE. Compared to the baseline scenario where one Wi-Fi network coexists with an additional Wi-Fi network, our results show that Wi-Fi performance is severely degraded when LTE transmits continuously. However, LTE is able to improve the DST and rate coverage probability of Wi-Fi while maintaining acceptable data rate performance when it adopts one or more of the following coexistence features: a shorter transmission duty cycle, lower channel access priority, or more sensitive clear channel assessment (CCA) thresholds.
On the evaluation potential of quality functions in community detection for different contexts
Venue: arXiv cs.SI 2016
Year: 2016

Due to nowadays networks' sizes, the evaluation of a community detection algorithm can only be done using quality functions. These functions measure different networks/graphs structural properties, each of them corresponding to a different definition of a community. Since there exists many definitions for a community, choosing a quality function may be a difficult task, even if the networks' statistics/origins can give some clues about which one to choose. In this paper, we apply a general methodology to identify different contexts, i.e. groups of graphs where the quality functions behave similarly. In these contexts we identify the best quality functions, i.e. quality functions whose results are consistent with expectations from real life applications.
A vertex similarity index for better personalized recommendation
Venue: arXiv cs.IR 2016
Year: 2016

Recommender systems benefit us in tackling the problem of information overload by predicting our potential choices among diverse niche objects. So far, a variety of personalized recommendation algorithms have been proposed and most of them are based on similarities, such as collaborative filtering and mass diffusion. Here, we propose a novel vertex similarity index named CosRA, which combines advantages of both the cosine index and the resource-allocation (RA) index. By applying the CosRA index to real recommender systems including MovieLens, Netflix and RYM, we show that the CosRA-based method has better performance in accuracy, diversity and novelty than some benchmark methods. Moreover, the CosRA index is free of parameters, which is a significant advantage in real applications. Further experiments show that the introduction of two turnable parameters cannot remarkably improve the overall performance of the CosRA index.
Exact Inference Techniques for the Analysis of Bayesian Attack Graphs
Venue: arXiv cs.CR 2016
Year: 2016

Attack graphs are a powerful tool for security risk assessment by analysing network vulnerabilities and the paths attackers can use to compromise network resources. The uncertainty about the attacker's behaviour makes Bayesian networks suitable to model attack graphs to perform static and dynamic analysis. Previous approaches have focused on the formalization of attack graphs into a Bayesian model rather than proposing mechanisms for their analysis. In this paper we propose to use efficient algorithms to make exact inference in Bayesian attack graphs, enabling the static and dynamic network risk assessments. To support the validity of our approach we have performed an extensive experimental evaluation on synthetic Bayesian attack graphs with different topologies, showing the computational advantages in terms of time and memory use of the proposed techniques when compared to existing approaches.
A novel mutation operator based on the union of fitness and design spaces information for Differential Evolution
Venue: arXiv cs.NE 2016
Year: 2016

Differential Evolution (DE) is one of the most successful and powerful evolutionary algorithms for global optimization problem. The most important operator in this algorithm is mutation operator which parents are selected randomly to participate in it. Recently, numerous papers are tried to make this operator more intelligent by selection of parents for mutation intelligently. The intelligent selection for mutation vectors is performed by applying design space (also known as decision space) criterion or fitness space criterion, however, in both cases, half of valuable information of the problem space is disregarded. In this article, a Universal Differential Evolution (UDE) is proposed which takes advantage of both design and fitness spaces criteria for intelligent selection of mutation vectors. The experimental analysis on UDE are performed on CEC2005 benchmarks and the results stated that UDE significantly improved the performance of differential evolution in comparison with other methods that only use one criterion for intelligent selection.
Analyzing Uplink SINR and Rate in Massive MIMO Systems Using Stochastic Geometry
Venue: arXiv cs.IT 2016
Year: 2016

This paper proposes a stochastic geometry framework to analyze the SINR and rate performance in a large-scale uplink massive MIMO network. Based on the model, expressions are derived for spatial average SINR distributions over user and base station distributions with maximum ratio combining (MRC) and zero-forcing (ZF) receivers. We show that using massive MIMO, the uplink SINR in certain urban marco-cell scenarios is limited by interference. In the interference-limited regime, the results reveal that for MRC receivers, a super-linear (polynomial) scaling law between the number of base station antennas and scheduled users per cell preserves the uplink SIR distribution, while a linear scaling applies to ZF receivers. ZF receivers are shown to outperform MRC receivers in the SIR coverage, and the performance gap is quantified in terms of the difference in the number of antennas to achieve the same SIR distribution. Numerical results verify the analysis. It is found that the optimal compensation fraction in fractional power control to optimize rate is generally different for MRC and ZF receivers. Besides, simulations show that the scaling results derived from the proposed framework apply to the networks where base stations are distributed according to a hexagonal lattice.
Dreaming More Data: Class-dependent Distributions over Diffeomorphisms for Learned Data Augmentation
Venue: arXiv cs.CV 2016
Year: 2016

Data augmentation is a key element in training high-dimensional models. In this approach, one synthesizes new observations by applying pre-specified transformations to the original training data; e.g.~new images are formed by rotating old ones. Current augmentation schemes, however, rely on manual specification of the applied transformations, making data augmentation an implicit form of feature engineering. With an eye towards true end-to-end learning, we suggest learning the applied transformations on a per-class basis. Particularly, we align image pairs within each class under the assumption that the spatial transformation between images belongs to a large class of diffeomorphisms. We then learn a class-specific probabilistic generative models of the transformations in a Riemannian submanifold of the Lie group of diffeomorphisms. We demonstrate significant performance improvements in training deep neural nets over manually-specified augmentation schemes. Our code and augmented datasets are available online.
TagBook: A Semantic Video Representation without Supervision for Event Detection
Venue: arXiv cs.CV 2016
Year: 2016

We consider the problem of event detection in video for scenarios where only few, or even zero examples are available for training. For this challenging setting, the prevailing solutions in the literature rely on a semantic video representation obtained from thousands of pre-trained concept detectors. Different from existing work, we propose a new semantic video representation that is based on freely available social tagged videos only, without the need for training any intermediate concept detectors. We introduce a simple algorithm that propagates tags from a video's nearest neighbors, similar in spirit to the ones used for image retrieval, but redesign it for video event detection by including video source set refinement and varying the video tag assignment. We call our approach TagBook and study its construction, descriptiveness and detection performance on the TRECVID 2013 and 2014 multimedia event detection datasets and the Columbia Consumer Video dataset. Despite its simple nature, the proposed TagBook video representation is remarkably effective for few-example and zero-example event detection, even outperforming very recent state-of-the-art alternatives building on supervised representations.
A Still Simpler Way of Introducing the Interior-Point Method for Linear Programming
Venue: arXiv cs.DS 2016
Year: 2016

Linear programming is now included in algorithm undergraduate and postgraduate courses for computer science majors. We give a self-contained treatment of an interior-point method which is particularly tailored to the typical mathematical background of CS students. In particular, only limited knowledge of linear algebra and calculus is assumed.
Strategic Bidding in an Accumulating Priority Queue: Equilibrium Analysis
Venue: arXiv cs.GT 2016
Year: 2016

We study the strategic purchasing of priorities in a time-dependent accumulating priority M/G/$1$ queue. We formulate a non-cooperative game in which customers purchase priority coefficients with the goal of reducing waiting costs in exchange. The priority of each customer in the queue is a linear function of the individual waiting time, with the purchased coefficient being the slope. The unique pure Nash equilibrium is solved explicitly for the case with homogeneous customers. A general characterisation of the Nash equilibrium is provided for the heterogeneous case. It is shown that both avoid the crowd and follow the crowd behaviours are prevalent, within class types and between them. We further present a pricing mechanism that ensures the order of the accumulating priority rates in equilibrium follows a $Cμ$ type rule and improves overall efficiency.
Cooperative Local Caching under Heterogeneous File Preferences
Venue: arXiv cs.IT 2016
Year: 2016

Local caching is an effective scheme for leveraging the memory of the mobile terminal (MT) and short range communications to save the bandwidth usage and reduce the download delay in the cellular communication system. Specifically, the MTs first cache in their local memories in off-peak hours and then exchange the requested files with each other in the vicinity during peak hours. However, prior works largely overlook MTs' heterogeneity in file preferences and their selfish behaviours. In this paper, we practically categorize the MTs into different interest groups according to the MTs' preferences. Each group of MTs aims to increase the probability of successful file discovery from the neighbouring MTs (from the same or different groups). Hence, we define the groups' utilities as the probability of successfully discovering the file in the neighbouring MTs, which should be maximized by deciding the caching strategies of different groups. By modelling MTs' mobilities as homogeneous Poisson point processes (HPPPs), we analytically characterize MTs' utilities in closed-form. We first consider the fully cooperative case where a centralizer helps all groups to make caching decisions. We formulate the problem as a weighted-sum utility maximization problem, through which the maximum utility trade-offs of different groups are characterized. Next, we study two benchmark cases under selfish caching, namely, partial and no cooperation, with and without inter-group file sharing, respectively. The optimal caching distributions for these two cases are derived. Finally, numerical examples are presented to compare the utilities under different cases and show the effectiveness of the fully cooperative local caching compared to the two benchmark cases.
Tensor vs Matrix Methods: Robust Tensor Decomposition under Block Sparse Perturbations
Venue: arXiv cs.LG 2016
Year: 2016

Robust tensor CP decomposition involves decomposing a tensor into low rank and sparse components. We propose a novel non-convex iterative algorithm with guaranteed recovery. It alternates between low-rank CP decomposition through gradient ascent (a variant of the tensor power method), and hard thresholding of the residual. We prove convergence to the globally optimal solution under natural incoherence conditions on the low rank component, and bounded level of sparse perturbations. We compare our method with natural baselines which apply robust matrix PCA either to the {\em flattened} tensor, or to the matrix slices of the tensor. Our method can provably handle a far greater level of perturbation when the sparse tensor is block-structured. This naturally occurs in many applications such as the activity detection task in videos. Our experiments validate these findings. Thus, we establish that tensor methods can tolerate a higher level of gross corruptions compared to matrix methods.
When Two Choices Are not Enough: Balancing at Scale in Distributed Stream Processing
Venue: arXiv cs.DC 2016
Year: 2016

Carefully balancing load in distributed stream processing systems has a fundamental impact on execution latency and throughput. Load balancing is challenging because real-world workloads are skewed: some tuples in the stream are associated to keys which are significantly more frequent than others. Skew is remarkably more problematic in large deployments: more workers implies fewer keys per worker, so it becomes harder to "average out" the cost of hot keys with cold keys. We propose a novel load balancing technique that uses a heaving hitter algorithm to efficiently identify the hottest keys in the stream. These hot keys are assigned to $d \geq 2$ choices to ensure a balanced load, where $d$ is tuned automatically to minimize the memory and computation cost of operator replication. The technique works online and does not require the use of routing tables. Our extensive evaluation shows that our technique can balance real-world workloads on large deployments, and improve throughput and latency by $\mathbf{150\%}$ and $\mathbf{60\%}$ respectively over the previous state-of-the-art when deployed on Apache Storm.