OpenRaiser/Intern-Atlas huggingface dataset:
A Modified Abramov-Petkovsek Reduction and Creative Telescoping for Hypergeometric Terms
Venue: arXiv cs.SC 2015
Year: 2015

The Abramov-Petkovsek reduction computes an additive decomposition of a hypergeometric term, which extends the functionality of the Gosper algorithm for indefinite hypergeometric summation. We modify the Abramov-Petkovsek reduction so as to decompose a hypergeometric term as the sum of a summable term and a non-summable one. The outputs of the Abramov-Petkovsek reduction and our modified version share the same required properties. The modified reduction does not solve any auxiliary linear difference equation explicitly. It is also more efficient than the original reduction according to computational experiments. Based on this reduction, we design a new algorithm to compute minimal telescopers for bivariate hypergeometric terms. The new algorithm can avoid the costly computation of certificates.
Community Detection from Location-Tagged Networks
Venue: arXiv cs.SI 2015
Year: 2015

Many real world systems or web services can be represented as a network such as social networks and transportation networks. In the past decade, many algorithms have been developed to detect the communities in a network using connections between nodes. However in many real world networks, the locations of nodes have great influence on the community structure. For example, in a social network, more connections are established between geographically proximate users. The impact of locations on community has not been fully investigated by the research literature. In this paper, we propose a community detection method which takes locations of nodes into consideration. The goal is to detect communities with both geographic proximity and network closeness. We analyze the distribution of the distances between connected and unconnected nodes to measure the influence of location on the network structure on two real location-tagged social networks. We propose a method to determine if a location-based community detection method is suitable for a given network. We propose a new community detection algorithm that pushes the location information into the community detection. We test our proposed method on both synthetic data and real world network datasets. The results show that the communities detected by our method distribute in a smaller area compared with the traditional methods and have the similar or higher tightness on network connections.
Slice Sampling for Probabilistic Programming
Venue: arXiv cs.AI 2015
Year: 2015

We introduce the first, general purpose, slice sampling inference engine for probabilistic programs. This engine is released as part of StocPy, a new Turing-Complete probabilistic programming language, available as a Python library. We present a transdimensional generalisation of slice sampling which is necessary for the inference engine to work on traces with different numbers of random variables. We show that StocPy compares favourably to other PPLs in terms of flexibility and usability, and that slice sampling can outperform previously introduced inference methods. Our experiments include a logistic regression, HMM, and Bayesian Neural Net.
Deep Convolutional Neural Networks for Action Recognition Using Depth Map Sequences
Venue: arXiv cs.CV 2015
Year: 2015

Recently, deep learning approach has achieved promising results in various fields of computer vision. In this paper, a new framework called Hierarchical Depth Motion Maps (HDMM) + 3 Channel Deep Convolutional Neural Networks (3ConvNets) is proposed for human action recognition using depth map sequences. Firstly, we rotate the original depth data in 3D pointclouds to mimic the rotation of cameras, so that our algorithms can handle view variant cases. Secondly, in order to effectively extract the body shape and motion information, we generate weighted depth motion maps (DMM) at several temporal scales, referred to as Hierarchical Depth Motion Maps (HDMM). Then, three channels of ConvNets are trained on the HDMMs from three projected orthogonal planes separately. The proposed algorithms are evaluated on MSRAction3D, MSRAction3DExt, UTKinect-Action and MSRDailyActivity3D datasets respectively. We also combine the last three datasets into a larger one (called Combined Dataset) and test the proposed method on it. The results show that our approach can achieve state-of-the-art results on the individual datasets and without dramatical performance degradation on the Combined Dataset.
On the Uniqueness of Sparse Time-Frequency Representation of Multiscale Data
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we analyze the uniqueness of the sparse time frequency decomposition and investigate the efficiency of the nonlinear matching pursuit method. Under the assumption of scale separation, we show that the sparse time frequency decomposition is unique up to an error that is determined by the scale separation property of the signal. We further show that the unique decomposition can be obtained approximately by the sparse time frequency decomposition using nonlinear matching pursuit.
Static Analysis of File-Processing Programs using File Format Specifications
Venue: arXiv cs.PL 2015
Year: 2015

Programs that process data that reside in files are widely used in varied domains, such as banking, healthcare, and web-traffic analysis. Precise static analysis of these programs in the context of software verification and transformation tasks is a challenging problem. Our key insight is that static analysis of file-processing programs can be made more useful if knowledge of the input file formats of these programs is made available to the analysis. We propose a generic framework that is able to perform any given underlying abstract interpretation on the program, while restricting the attention of the analysis to program paths that are potentially feasible when the program's input conforms to the given file format specification. We describe an implementation of our approach, and present empirical results using real and realistic programs that show how our approach enables novel verification and transformation tasks, and also improves the precision of standard analysis problems.
Distributed Data Association in Smart Camera Networks via Dual Decomposition
Venue: arXiv cs.CV 2015
Year: 2015

One of the fundamental requirements for visual surveillance using smart camera networks is the correct association of each persons observations generated on different cameras. Recently, distributed data association that involves only local information processing on each camera node and mutual information exchanging between neighboring cameras has attracted many research interests due to its superiority in large scale applications. In this paper, we formulate the problem of data association in smart camera networks as an Integer Programming problem by introducing a set of linking variables, and propose two distributed algorithms, namely L-DD and Q-DD, to solve the Integer Programming problem using dual decomposition technique. In our algorithms, the original IP problem is decomposed into several sub-problems, which can be solved locally and efficiently on each smart camera, and then different sub-problems reach consensus on their solutions in a rigorous way by adjusting their parameters based on projected sub-gradient optimization. The proposed methods are simple and flexible, in that (i) we can incorporate any feature extraction and matching technique into our framework to measure the similarity between two observations, which is used to define the cost of each link, and (ii) we can decompose the original problem in any way as long as the resulting sub-problem can be solved independently on individual camera. We show the competitiveness of our methods in both accuracy and speed by theoretical analysis and experimental comparison with state of the art algorithms on two real data sets collected by camera networks in our campus garden and office building.
Interference Aligned Space-Time Transmission with Diversity for the $2 \times 2$ X-Network
Venue: arXiv cs.IT 2015
Year: 2015

The sum degrees of freedom (DoF) of the two-transmitter, two-receiver multiple-input multiple-output (MIMO) X-Network ($2 \times 2$ MIMO X-Network) with $M$ antennas at each node is known to be $\frac{4M}{3}$. Transmission schemes which couple local channel-state-information-at-the-transmitter (CSIT) based precoding with space-time block coding to achieve the sum-DoF of this network are known specifically for $M=2,4$. These schemes have been proven to guarantee a diversity gain of $M$ when a finite-sized input constellation is employed. In this paper, an explicit transmission scheme that achieves the $\frac{4M}{3}$ sum-DoF of the $2 \times 2$ X-Network for arbitrary $M$ is presented. The proposed scheme needs only local CSIT unlike the Jafar-Shamai scheme which requires the availability of global CSIT in order to achieve the $\frac{4M}{3}$ sum-DoF. Further, it is shown analytically that the proposed scheme guarantees a diversity gain of $M+1$ when finite-sized input constellations are employed.
Transformation From Legal-marking Set to Admissible-marking Set of Petri Nets With Uncontrollable Transitions
Venue: arXiv cs.FL 2015
Year: 2015

Linear constraint transformation is an essential step to solve the forbidden state problem in Petri nets that contain uncontrollable transitions. This work studies the equivalent transformation from a legal-marking set to its admissible-marking set given such a net. First, the concepts of an escaping-marking set and a transforming marking set are defined. Based on them, two algorithms are given to compute the admissible-marking set and the transforming marking set, which establish the theoretical foundation for the equivalent transformation of linear constraints. Second, the theory about the equivalent transformation of a disjunction of linear constraints imposed to Petri nets with uncontrollable transitions is established. Third, two rules are given to decide the priority of transitions for transformation. Finally, the transformation procedure from a given linear constraint to a logic expression of linear constraints that can describe its entire admissible-marking set is illustrated via two examples.
Constructing Binary Descriptors with a Stochastic Hill Climbing Search
Venue: arXiv cs.CV 2015
Year: 2015

Binary descriptors of image patches provide processing speed advantages and require less storage than methods that encode the patch appearance with a vector of real numbers. We provide evidence that, despite its simplicity, a stochastic hill climbing bit selection procedure for descriptor construction defeats recently proposed alternatives on a standard discriminative power benchmark. The method is easy to implement and understand, has no free parameters that need fine tuning, and runs fast.
What do we learn about development from baby robots?
Venue: arXiv cs.AI 2015
Year: 2015

Understanding infant development is one of the greatest scientific challenges of contemporary science. A large source of difficulty comes from the fact that the development of skills in infants results from the interactions of multiple mechanisms at multiple spatio-temporal scales. The concepts of "innate" or "acquired" are not any more adequate tools for explanations, which call for a shift from reductionist to systemic accounts. To address this challenge, building and experimenting with robots modeling the growing infant brain and body is crucial. Systemic explanations of pattern formation in sensorimotor, cognitive and social development, viewed as a complex dynamical system, require the use of formal models based on mathematics, algorithms and robots. Formulating hypothesis about development using such models, and exploring them through experiments, allows us to consider in detail the interaction between many mechanisms and parameters. This complements traditional experimental methods in psychology and neuroscience where only a few variables can be studied at the same time. Furthermore, the use of robots is of particular importance. The laws of physics generate everywhere around us spontaneous patterns in the inorganic world. They also strongly impact the living, and in particular constrain and guide infant development through the properties of its (changing) body in interaction with the physical environment. Being able to consider the body as an experimental variable, something that can be systematically changed in order to study the impact on skill formation, has been a dream to many developmental scientists. This is today becoming possible with developmental robotics.
Support Recovery with Orthogonal Matching Pursuit in the Presence of Noise: A New Analysis
Venue: arXiv cs.IT 2015
Year: 2015

Support recovery of sparse signals from compressed linear measurements is a fundamental problem in compressed sensing (CS). In this paper, we study the orthogonal matching pursuit (OMP) algorithm for the recovery of support under noise. We consider two signal-to-noise ratio (SNR) settings: i) the SNR depends on the sparsity level $K$ of input signals, and ii) the SNR is an absolute constant independent of $K$. For the first setting, we establish necessary and sufficient conditions for the exact support recovery with OMP, expressed as lower bounds on the SNR. Our results indicate that in order to ensure the exact support recovery of all $K$-sparse signals with the OMP algorithm, the SNR must at least scale linearly with the sparsity level $K$. In the second setting, since the necessary condition on the SNR is not fulfilled, the exact support recovery with OMP is impossible. However, our analysis shows that recovery with an arbitrarily small but constant fraction of errors is possible with the OMP algorithm. This result may be useful for some practical applications where obtaining some large fraction of support positions is adequate.
Subtropical Real Root Finding
Venue: arXiv cs.SC 2015
Year: 2015

We describe a new incomplete but terminating method for real root finding for large multivariate polynomials. We take an abstract view of the polynomial as the set of exponent vectors associated with sign information on the coefficients. Then we employ linear programming to heuristically find roots. There is a specialized variant for roots with exclusively positive coordinates, which is of considerable interest for applications in chemistry and systems biology. An implementation of our method combining the computer algebra system Reduce with the linear programming solver Gurobi has been successfully applied to input data originating from established mathematical models used in these areas. We have solved several hundred problems with up to more than 800000 monomials in up to 10 variables with degrees up to 12. Our method has failed due to its incompleteness in less than 8 percent of the cases.
Project Monitomation Version 1
Venue: arXiv cs.NI 2015
Year: 2015

Project Monitomation is a unique implementation which focuses on justifying the capability of smart wireless networks based on IEEE 802.15.4 standard, for low power, short range Personal Area Network (PAN) communication. Through this project wireless text messaging, device control & network monitoring is implemented to demonstrate the future of Internet of things .
Regroupement sémantique de définitions en espagnol
Venue: arXiv cs.IR 2015
Year: 2015

This article focuses on the description and evaluation of a new unsupervised learning method of clustering of definitions in Spanish according to their semantic. Textual Energy was used as a clustering measure, and we study an adaptation of the Precision and Recall to evaluate our method.
Controller Synthesis for Linear Time-varying Systems with Adversaries
Venue: arXiv cs.SY 2015
Year: 2015

We present a controller synthesis algorithm for a discrete time reach-avoid problem in the presence of adversaries. Our model of the adversary captures typical malicious attacks envisioned on cyber-physical systems such as sensor spoofing, controller corruption, and actuator intrusion. After formulating the problem in a general setting, we present a sound and complete algorithm for the case with linear dynamics and an adversary with a budget on the total L2-norm of its actions. The algorithm relies on a result from linear control theory that enables us to decompose and precisely compute the reachable states of the system in terms of a symbolic simulation of the adversary-free dynamics and the total uncertainty induced by the adversary. With this decomposition, the synthesis problem eliminates the universal quantifier on the adversary's choices and the symbolic controller actions can be effectively solved using an SMT solver. The constraints induced by the adversary are computed by solving second-order cone programmings. The algorithm is later extended to synthesize state-dependent controller and to generate attacks for the adversary. We present preliminary experimental results that show the effectiveness of this approach on several example problems.
Pilot-Abstraction: A Valid Abstraction for Data-Intensive Applications on HPC, Hadoop and Cloud Infrastructures?
Venue: arXiv cs.DC 2015
Year: 2015

HPC environments have traditionally been designed to meet the compute demand of scientific applications and data has only been a second order concern. With science moving toward data-driven discoveries relying more on correlations in data to form scientific hypotheses, the limitations of HPC approaches become apparent: Architectural paradigms such as the separation of storage and compute are not optimal for I/O intensive workloads (e.g. for data preparation, transformation and SQL). While there are many powerful computational and analytical libraries available on HPC (e.g. for scalable linear algebra), they generally lack the usability and variety of analytical libraries found in other environments (e.g. the Apache Hadoop ecosystem). Further, there is a lack of abstractions that unify access to increasingly heterogeneous infrastructure (HPC, Hadoop, clouds) and allow reasoning about performance trade-offs in this complex environment. At the same time, the Hadoop ecosystem is evolving rapidly and has established itself as de-facto standard for data-intensive workloads in industry and is increasingly used to tackle scientific problems. In this paper, we explore paths to interoperability between Hadoop and HPC, examine the differences and challenges, such as the different architectural paradigms and abstractions, and investigate ways to address them. We propose the extension of the Pilot-Abstraction to Hadoop to serve as interoperability layer for allocating and managing resources across different infrastructures. Further, in-memory capabilities have been deployed to enhance the performance of large-scale data analytics (e.g. iterative algorithms) for which the ability to re-use data across iterations is critical. As memory naturally fits in with the Pilot concept of retaining resources for a set of tasks, we propose the extension of the Pilot-Abstraction to in-memory resources.
Error Correcting Index Codes and Matroids
Venue: arXiv cs.IT 2015
Year: 2015

The connection between index coding and matroid theory have been well studied in the recent past. El Rouayheb et al. established a connection between multilinear representation of matroids and wireless index coding. Muralidharan and Rajan showed that a vector linear solution to an index coding problem exists if and only if there exists a representable discrete polymatroid satisfying certain conditions. Recently index coding with erroneous transmission was considered by Dau et al.. Error correcting index codes in which all receivers are able to correct a fixed number of errors was studied. In this paper we consider a more general scenario in which each receiver is able to correct a desired number of errors, calling such index codes differential error correcting index codes. A link between differential error correcting index codes and certain matroids is established. We define matroidal differential error correcting index codes and we show that a scalar linear differential error correcting index code exists if and only if it is matroidal differential error correcting index code associated with a representable matroid.
Enabling High-Level Application Development for the Internet of Things
Venue: arXiv cs.SE 2015
Year: 2015

Application development in the Internet of Things (IoT) is challenging because it involves dealing with a wide range of related issues such as lack of separation of concerns, and lack of high-level of abstractions to address both the large scale and heterogeneity. Moreover, stakeholders involved in the application development have to address issues that can be attributed to different life-cycles phases. when developing applications. First, the application logic has to be analyzed and then separated into a set of distributed tasks for an underlying network. Then, the tasks have to be implemented for the specific hardware. Apart from handling these issues, they have to deal with other aspects of life-cycle such as changes in application requirements and deployed devices. Several approaches have been proposed in the closely related fields of wireless sensor network, ubiquitous and pervasive computing, and software engineering in general to address the above challenges. However, existing approaches only cover limited subsets of the above mentioned challenges when applied to the IoT. This paper proposes an integrated approach for addressing the above mentioned challenges. The main contributions of this paper are: (1) a development methodology that separates IoT application development into different concerns and provides a conceptual framework to develop an application, (2) a development framework that implements the development methodology to support actions of stakeholders. The development framework provides a set of modeling languages to specify each development concern and abstracts the scale and heterogeneity related complexity. It integrates code generation, task-mapping, and linking techniques to provide automation. Code generation supports the application development phase by producing a programming framework that allows stakeholders to focus on the application logic, while our mapping and linking techniques together support the deployment phase by producing device-specific code to result in a distributed system collaboratively hosted by individual devices. Our evaluation based on two realistic scenarios shows that the use of our approach improves the productivity of stakeholders involved in the application development.
Discrete-Time Models for Implicit Port-Hamiltonian Systems
Venue: arXiv cs.SY 2015
Year: 2015

Implicit representations of finite-dimensional port-Hamiltonian systems are studied from the perspective of their use in numerical simulation and control design. Implicit representations arise when a system is modeled in Cartesian coordinates and when the system constraints are applied in the form of additional algebraic equations (the system model is in a DAE form). Such representations lend themselves better to sample-data approximations. An implicit representation of a port-Hamiltonian system is given and it is shown how to construct a sampled-data model that preserves the port-Hamiltonian structure under sample and hold.