OpenRaiser/Intern-Atlas huggingface dataset:
Solvability of Matrix-Exponential Equations
Venue: arXiv cs.DM 2016
Year: 2016

We consider a continuous analogue of Babai et al.'s and Cai et al.'s problem of solving multiplicative matrix equations. Given $k+1$ square matrices $A_{1}, \ldots, A_{k}, C$, all of the same dimension, whose entries are real algebraic, we examine the problem of deciding whether there exist non-negative reals $t_{1}, \ldots, t_{k}$ such that \begin{align*} \prod \limits_{i=1}^{k} \exp(A_{i} t_{i}) = C . \end{align*} We show that this problem is undecidable in general, but decidable under the assumption that the matrices $A_{1}, \ldots, A_{k}$ commute. Our results have applications to reachability problems for linear hybrid automata. Our decidability proof relies on a number of theorems from algebraic and transcendental number theory, most notably those of Baker, Kronecker, Lindemann, and Masser, as well as some useful geometric and linear-algebraic results, including the Minkowski-Weyl theorem and a new (to the best of our knowledge) result about the uniqueness of strictly upper triangular matrix logarithms of upper unitriangular matrices. On the other hand, our undecidability result is shown by reduction from Hilbert's Tenth Problem.
Habits vs Environment: What really causes asthma?
Venue: arXiv cs.CY 2016
Year: 2016

Despite considerable number of studies on risk factors for asthma onset, very little is known about their relative importance. To have a full picture of these factors, both categories, personal and environmental data, have to be taken into account simultaneously, which is missing in previous studies. We propose a framework to rank the risk factors from heterogeneous data sources of the two categories. Established on top of EventShop and Personal EventShop, this framework extracts about 400 features, and analyzes them by employing a gradient boosting tree. The features come from sources including personal profile and life-event data, and environmental data on air pollution, weather and PM2.5 emission sources. The top ranked risk factors derived from our framework agree well with the general medical consensus. Thus, our framework is a reliable approach, and the discovered rankings of relative importance of risk factors can provide insights for the prevention of asthma.
Bitcoin and Decentralized Trust Protocols
Venue: arXiv cs.CY 2016
Year: 2016

Bitcoin is the first decentralized peer-to-peer (P2P) electronic currency. It was created in November 2008 by Satoshi Nakamoto. Nakamoto released the first implementation of the protocol in an open source client software and the genesis of bitcoins began on January 9th 2009. The Bitcoin protocol is based on clever ideas which solve a form of the Byzantine Generals Problem and sets the foundation for Decentralized Trust Protocols. Still in its infancy, the currency and the protocol have the potential to disrupt the international financial system and other sectors where business is based on trusted third parties. The security of the bitcoin protocol relies on strong cryptography and one way hashing algorithms.
Magnetometer calibration using inertial sensors
Venue: arXiv cs.SY 2016
Year: 2016

In this work we present a practical algorithm for calibrating a magnetometer for the presence of magnetic disturbances and for magnetometer sensor errors. To allow for combining the magnetometer measurements with inertial measurements for orientation estimation, the algorithm also corrects for misalignment between the magnetometer and the inertial sensor axes. The calibration algorithm is formulated as the solution to a maximum likelihood problem and the computations are performed offline. The algorithm is shown to give good results using data from two different commercially available sensor units. Using the calibrated magnetometer measurements in combination with the inertial sensors to determine the sensor's orientation is shown to lead to significantly improved heading estimates.
Effects of Content Popularity on the Performance of Content-Centric Opportunistic Networking: An Analytical Approach and Applications
Venue: arXiv cs.NI 2016
Year: 2016

Mobile users are envisioned to exploit direct communication opportunities between their portable devices, in order to enrich the set of services they can access through cellular or WiFi networks. Sharing contents of common interest or providing access to resources or services between peers can enhance a mobile node's capabilities, offload the cellular network, and disseminate information to nodes without Internet access. Interest patterns, i.e. how many nodes are interested in each content or service (popularity), as well as how many users can provide a content or service (availability) impact the performance and feasibility of envisioned applications. In this paper, we establish an analytical framework to study the effects of these factors on the delay and success probability of a content/service access request through opportunistic communication. We also apply our framework to the mobile data offloading problem and provide insights for the optimization of its performance. We validate our model and results through realistic simulations, using datasets of real opportunistic networks.
Marketing Impact on Diffusion in Social Networks
Venue: arXiv cs.SI 2016
Year: 2016

The paper proposes a way to add marketing into the standard threshold model of social networks. Within this framework, the paper studies logical properties of the influence relation between sets of agents in social networks. Two different forms of this relation are considered: one for promotional marketing and the other for preventive marketing. In each case a sound and complete logical system describing properties of the influence relation is proposed. Both systems could be viewed as extensions of Armstrong's axioms of functional dependency from the database theory.
Review and Analysis of Networking Challenges in Cloud Computing
Venue: arXiv cs.NI 2016
Year: 2016

Cloud Computing offers virtualized computing, storage, and networking resources, over the Internet, to organizations and individual users in a completely dynamic way. These cloud resources are cheaper, easier to manage, and more elastic than sets of local, physical, ones. This encourages customers to outsource their applications and services to the cloud. The migration of both data and applications outside the administrative domain of customers into a shared environment imposes transversal, functional problems across distinct platforms and technologies. This article provides a contemporary discussion of the most relevant functional problems associated with the current evolution of Cloud Computing, mainly from the network perspective. The paper also gives a concise description of Cloud Computing concepts and technologies. It starts with a brief history about cloud computing, tracing its roots. Then, architectural models of cloud services are described, and the most relevant products for Cloud Computing are briefly discussed along with a comprehensive literature review. The paper highlights and analyzes the most pertinent and practical network issues of relevance to the provision of high-assurance cloud services through the Internet, including security. Finally, trends and future research directions are also presented.
Disaggregation of SMAP L3 Brightness Temperatures to 9km using Kernel Machines
Venue: arXiv cs.CV 2016
Year: 2016

In this study, a machine learning algorithm is used for disaggregation of SMAP brightness temperatures (T$_{\textrm{B}}$) from 36km to 9km. It uses image segmentation to cluster the study region based on meteorological and land cover similarity, followed by a support vector machine based regression that computes the value of the disaggregated T$_{\textrm{B}}$ at all pixels. High resolution remote sensing products such as land surface temperature, normalized difference vegetation index, enhanced vegetation index, precipitation, soil texture, and land-cover were used for disaggregation. The algorithm was implemented in Iowa, United States, from April to July 2015, and compared with the SMAP L3_SM_AP T$_{\textrm{B}}$ product at 9km. It was found that the disaggregated T$_{\textrm{B}}$ were very similar to the SMAP-T$_{\textrm{B}}$ product, even for vegetated areas with a mean difference $\leq$ 5K. However, the standard deviation of the disaggregation was lower by 7K than that of the AP product. The probability density functions of the disaggregated T$_{\textrm{B}}$ were similar to the SMAP-T$_{\textrm{B}}$. The results indicate that this algorithm may be used for disaggregating T$_{\textrm{B}}$ using complex non-linear correlations on a grid.
Fusion of Array Operations at Runtime
Venue: arXiv cs.DC 2016
Year: 2016

We address the problem of fusing array operations based on criteria such as shape compatibility, data reusability, and communication. We formulate the problem as a graph partition problem that is general enough to handle loop fusion, combinator fusion, and other types of subroutines.
Selecting Efficient Features via a Hyper-Heuristic Approach
Venue: arXiv cs.CV 2016
Year: 2016

By Emerging huge databases and the need to efficient learning algorithms on these datasets, new problems have appeared and some methods have been proposed to solve these problems by selecting efficient features. Feature selection is a problem of finding efficient features among all features in which the final feature set can improve accuracy and reduce complexity. One way to solve this problem is to evaluate all possible feature subsets. However, evaluating all possible feature subsets is an exhaustive search and thus it has high computational complexity. Until now many heuristic algorithms have been studied for solving this problem. Hyper-heuristic is a new heuristic approach which can search the solution space effectively by applying local searches appropriately. Each local search is a neighborhood searching algorithm. Since each region of the solution space can have its own characteristics, it should be chosen an appropriate local search and apply it to current solution. This task is tackled to a supervisor. The supervisor chooses a local search based on the functional history of local searches. By doing this task, it can trade of between exploitation and exploration. Since the existing heuristic cannot trade of between exploration and exploitation appropriately, the solution space has not been searched appropriately in these methods and thus they have low convergence rate. For the first time, in this paper use a hyper-heuristic approach to find an efficient feature subset. In the proposed method, genetic algorithm is used as a supervisor and 16 heuristic algorithms are used as local searches. Empirical study of the proposed method on several commonly used data sets from UCI data sets indicates that it outperforms recent existing methods in the literature for feature selection.
Automatic 3D modelling of craniofacial form
Venue: arXiv cs.CV 2016
Year: 2016

Three-dimensional models of craniofacial variation over the general population are useful for assessing pre- and post-operative head shape when treating various craniofacial conditions, such as craniosynostosis. We present a new method of automatically building both sagittal profile models and full 3D surface models of the human head using a range of techniques in 3D surface image analysis; in particular, automatic facial landmarking using supervised machine learning, global and local symmetry plane detection using a variant of trimmed iterative closest points, locally-affine template warping (for full 3D models) and a novel pose normalisation using robust iterative ellipse fitting. The PCA-based models built using the new pose normalisation are more compact than those using Generalised Procrustes Analysis and we demonstrate their utility in a clinical case study.
Safe and Secure Wireless Power Transfer Networks: Challenges and Opportunities in RF-Based Systems
Venue: arXiv cs.NI 2016
Year: 2016

RF-based wireless power transfer networks (WPTNs) are deployed to transfer power to embedded devices over the air via RF waves. Up until now, a considerable amount of effort has been devoted by researchers to design WPTNs that maximize several objectives such as harvested power, energy outage and charging delay. However, inherent security and safety issues are generally overlooked and these need to be solved if WPTNs are to be become widespread. This article focuses on safety and security problems related WPTNs and highlight their cruciality in terms of efficient and dependable operation of RF-based WPTNs. We provide a overview of new research opportunities in this emerging domain.
Computing with Polynomial Ordinary Differential Equations
Venue: arXiv cs.CC 2016
Year: 2016

In 1941, Claude Shannon introduced the General Purpose Analog Computer(GPAC) as a mathematical model of Differential Analysers, that is to say as a model of continuous-time analog (mechanical, and later one electronic) machines of that time. Following Shannon's arguments, functions generated by GPACs must be differentially algebraic. As it is known that some computable functions like Euler's $Γ(x)=\int_{0}^{\infty}t^{x-1}e^{-t}dt$ or Riemann's Zeta function $ζ(x)=\sum_{k=0}^\infty \frac1{k^x}$ are not differentially algebraic, this argument has been often used to demonstrate in the past that the GPAC is less powerful than digital computation. It was proved in JOC2007, that if a more modern notion of computation is considered, i.e. in particular if computability is not restricted to real-time generation of functions, the GPAC is actually equivalent to Turing machines. Our purpose is first to discuss the robustness of the notion of computation involved in JOC2007, by establishing that natural variants of the notion of computation from this paper leads to the same computability result. Second, to go considerations about (time) complexity, we explore several natural variants for measuring time/space complexity of a computation. Rather surprisingly, whereas defining a robust time complexity for general continuous time systems is a well known open problem, we prove that all variants are actually equivalent even at the complexity level. As a consequence, it seems that a robust and well defined notion of time complexity exists for the GPAC, or equivalently for computations by polynomial ordinary differential equations. Another side effect of our proof is also that we show in some way that polynomial ordinary differential equations can be used as a kind of programming model, and that there is a rather nice and robust notion of ODE programming.
Pachinko
Venue: arXiv cs.CG 2016
Year: 2016

Inspired by the Japanese game Pachinko, we study simple (perfectly "inelastic" collisions) dynamics of a unit ball falling amidst point obstacles (pins) in the plane. A classic example is that a checkerboard grid of pins produces the binomial distribution, but what probability distributions result from different pin placements? In the 50-50 model, where the pins form a subset of this grid, not all probability distributions are possible, but surprisingly the uniform distribution is possible for $\{1,2,4,8,16\}$ possible drop locations. Furthermore, every probability distribution can be approximated arbitrarily closely, and every dyadic probability distribution can be divided by a suitable power of $2$ and then constructed exactly (along with extra "junk" outputs). In a more general model, if a ball hits a pin off center, it falls left or right accordingly. Then we prove a universality result: any distribution of $n$ dyadic probabilities, each specified by $k$ bits, can be constructed using $O(n k^2)$ pins, which is close to the information-theoretic lower bound of $Ω(n k)$.
Shift-Invariant and Sampling Spaces Associated with the Special Affine Fourier Transform
Venue: arXiv cs.IT 2016
Year: 2016

The Special Affine Fourier Transformation or the SAFT generalizes a number of well known unitary transformations as well as signal processing and optics related mathematical operations. Shift-invariant spaces also play an important role in sampling theory, multiresolution analysis, and many other areas of signal and image processing. Shannon's sampling theorem, which is at the heart of modern digital communications, is a special case of sampling in shift-invariant spaces. Furthermore, it is well known that the Poisson summation formula is equivalent to the sampling theorem and that the Zak transform is closely connected to the sampling theorem and the Poisson summation formula. These results have been known to hold in the Fourier transform domain for decades and were recently shown to hold in the Fractional Fourier transform domain by A. Bhandari and A. Zayed. The main goal of this article is to show that these results also hold true in the SAFT domain. We provide a short, self-contained proof of Shannon's theorem for functions bandlimited in the SAFT domain and then show that sampling in the SAFT domain is equivalent to orthogonal projection of functions onto a subspace of bandlimited basis associated with the SAFT domain. This interpretation of sampling leads to least-squares optimal sampling theorem. Furthermore, we show that this approximation procedure is linked with convolution and semi-discrete convolution operators that are associated with the SAFT domain. We conclude the article with an application of fractional delay filtering of SAFT bandlimited functions.
3D digital reassembling of archaeological ceramic pottery fragments based on their thickness profile
Venue: arXiv cs.GR 2016
Year: 2016

The reassembly of a broken archaeological ceramic pottery is an open and complex problem, which remains a scientific process of extreme interest for the archaeological community. Usually, the solutions suggested by various research groups and universities depend on various aspects such as the matching process of the broken surfaces, the outline of sherds or their colors and geometric characteris-tics, their axis of symmetry, the corners of their contour, the theme portrayed on the surface, the concentric circular rills that are left during the base construction in the inner pottery side by the fingers of the potter artist etc. In this work the reassembly process is based on a different and more secure idea, since it is based on the thick-ness profile, which is appropriately identified in every fragment. Specifically, our approach is based on information encapsulated in the inner part of the sherd (i.e. thickness), which is not -or at least not heavily- affected by the presence of harsh environmental conditions, but is safely kept within the sherd itself. Our method is verified in various use case experiments, using cutting edge technologies such as 3D representations and precise measurements on surfaces from the acquired 3D models.
Distributed Simulation of Continuous Random Variables
Venue: arXiv cs.IT 2016
Year: 2016

We establish the first known upper bound on the exact and Wyner's common information of $n$ continuous random variables in terms of the dual total correlation between them (which is a generalization of mutual information). In particular, we show that when the pdf of the random variables is log-concave, there is a constant gap of $n^{2}\log e+9n\log n$ between this upper bound and the dual total correlation lower bound that does not depend on the distribution. The upper bound is obtained using a computationally efficient dyadic decomposition scheme for constructing a discrete common randomness variable $W$ from which the $n$ random variables can be simulated in a distributed manner. We then bound the entropy of $W$ using a new measure, which we refer to as the erosion entropy.
Improving GPU-accelerated Adaptive IDW Interpolation Algorithm Using Fast kNN Search
Venue: arXiv cs.DC 2016
Year: 2016

This paper presents an efficient parallel Adaptive Inverse Distance Weighting (AIDW) interpolation algorithm on modern Graphics Processing Unit (GPU). The presented algorithm is an improvement of our previous GPU-accelerated AIDW algorithm by adopting fast k-Nearest Neighbors (kNN) search. In AIDW, it needs to find several nearest neighboring data points for each interpolated point to adaptively determine the power parameter; and then the desired prediction value of the interpolated point is obtained by weighted interpolating using the power parameter. In this work, we develop a fast kNN search approach based on the space-partitioning data structure, even grid, to improve the previous GPU-accelerated AIDW algorithm. The improved algorithm is composed of the stages of kNN search and weighted interpolating. To evaluate the performance of the improved algorithm, we perform five groups of experimental tests. Experimental results show that: (1) the improved algorithm can achieve a speedup of up to 1017 over the corresponding serial algorithm; (2) the improved algorithm is at least two times faster than our previous GPU-accelerated AIDW algorithm; and (3) the utilization of fast kNN search can significantly improve the computational efficiency of the entire GPU-accelerated AIDW algorithm.
Role of Large Scale Channel Information on Predictive Resource Allocation
Venue: arXiv cs.IT 2016
Year: 2016

When the future achievable rate is perfectly known, predictive resource allocation can provide high performance gain over traditional resource allocation for the traffic without stringent delay requirement. However, future channel information is hard to obtain in wireless channels, especially the small-scale fading gains. In this paper, we analytically demonstrate that the future large-scale channel information can capture almost all the performance gain from knowing the future channel by taking an energy-saving resource allocation as an example. This result is important for practical systems, since large-scale channel gains can be easily estimated from the predicted trajectory of mobile users and radio map. Simulation results validate our analysis and illustrate the impact of the estimation errors of large-scale channel gains on energy saving.
A Hybrid Channel Model based on WINNER for Vehicle-to-X Application
Venue: arXiv cs.IT 2016
Year: 2016

V2V and V2I channel modeling became recently more of interest. To provide realistic radio channels either expensive measurements or complex ray tracing simulations are mostly used. Stochastic channel models are of low complexity but do not offer that deterministic repeatable realism. Based on the WINNER channel model and a simple single path model, a hybrid model has been developed. The concept relies on a layered structure featuring high flexibility and scalability.
Unshuffling Permutations
Venue: arXiv cs.DS 2016
Year: 2016

A permutation is said to be a square if it can be obtained by shuffling two order-isomorphic patterns. The definition is intended to be the natural counterpart to the ordinary shuffle of words and languages. In this paper, we tackle the problem of recognizing square permutations from both the point of view of algebra and algorithms. On the one hand, we present some algebraic and combinatorial properties of the shuffle product of permutations. We follow an unusual line consisting in defining the shuffle of permutations by means of an unshuffling operator, known as a coproduct. This strategy allows to obtain easy proofs for algebraic and combinatorial properties of our shuffle product. We besides exhibit a bijection between square $(213,231)$-avoiding permutations and square binary words. On the other hand, by using a pattern avoidance criterion on oriented perfect matchings, we prove that recognizing square permutations is $\mathbf{NP}$-complete.