OpenRaiser/Intern-Atlas huggingface dataset:
A Generalized Cheeger Inequality
Venue: arXiv cs.DM 2014
Year: 2014

The generalized conductance $ϕ(G,H)$ between two graphs $G$ and $H$ on the same vertex set $V$ is defined as the ratio $$ ϕ(G,H) = \min_{S\subseteq V} \frac{cap_G(S,\bar{S})}{ cap_H(S,\bar{S})}, $$ where $cap_G(S,\bar{S})$ is the total weight of the edges crossing from $S$ to $\bar{S}=V-S$. We show that the minimum generalized eigenvalue $λ(L_G,L_H)$ of the pair of Laplacians $L_G$ and $L_H$ satisfies $$ λ(L_G,L_H) \geq ϕ(G,H) ϕ(G)/8, $$ where $ϕ(G)$ is the usual conductance of $G$. A generalized cut that meets this bound can be obtained from the generalized eigenvector corresponding to $λ(L_G,L_H)$. The inequality complements a recent proof that $ϕ(G)$ cannot be replaced by $Θ(ϕ(G,H))$ in the above inequality, unless the Unique Games Conjecture is false.
Generalization of Gabidulin Codes over Fields of Rational Functions
Venue: arXiv cs.SC 2014
Year: 2014

We transpose the theory of rank metric and Gabidulin codes to the case of fields which are not finite fields. The Frobenius automorphism is replaced by any element of the Galois group of a cyclic algebraic extension of a base field. We use our framework to define Gabidulin codes over the field of rational functions using algebraic function fields with a cyclic Galois group. This gives a linear subspace of matrices whose coefficients are rational function, such that the rank of each of this matrix is lower bounded, where the rank is comprised in term of linear combination with rational functions. We provide two examples based on Kummer and Artin-Schreier extensions.The matrices that we obtain may be interpreted as generating matrices of convolutional codes.
Learning Temporal Dependencies in Data Using a DBN-BLSTM
Venue: arXiv cs.LG 2014
Year: 2014

Since the advent of deep learning, it has been used to solve various problems using many different architectures. The application of such deep architectures to auditory data is also not uncommon. However, these architectures do not always adequately consider the temporal dependencies in data. We thus propose a new generic architecture called the Deep Belief Network - Bidirectional Long Short-Term Memory (DBN-BLSTM) network that models sequences by keeping track of the temporal information while enabling deep representations in the data. We demonstrate this new architecture by applying it to the task of music generation and obtain state-of-the-art results.
Semantic Part Segmentation using Compositional Model combining Shape and Appearance
Venue: arXiv cs.CV 2014
Year: 2014

In this paper, we study the problem of semantic part segmentation for animals. This is more challenging than standard object detection, object segmentation and pose estimation tasks because semantic parts of animals often have similar appearance and highly varying shapes. To tackle these challenges, we build a mixture of compositional models to represent the object boundary and the boundaries of semantic parts. And we incorporate edge, appearance, and semantic part cues into the compositional model. Given part-level segmentation annotation, we develop a novel algorithm to learn a mixture of compositional models under various poses and viewpoints for certain animal classes. Furthermore, a linear complexity algorithm is offered for efficient inference of the compositional model using dynamic programming. We evaluate our method for horse and cow using a newly annotated dataset on Pascal VOC 2010 which has pixelwise part labels. Experimental results demonstrate the effectiveness of our method.
Multi-User Diversity with Optimal Power Allocation in Spectrum Sharing under Average Interference Power Constraint
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we investigate the performance of multi-user diversity (MUD) with optimal power allocation (OPA) in spectrum sharing (SS) under average interference power (AIP) constraint. In particular, OPA through average transmit power constraint in conjunction with the AIP constraint is assumed to maximize the ergodic secondary capacity. The solution of this problem requires the calculation of two Lagrange multipliers instead of one as obtained for the peak interference power (PIP) constraint and calculated using the well known water-filling algorithm. To this end, an algorithm based on bisection method is devised in order to calculate both Lagrange multipliers iteratively. Moreover, Rayleigh and Nakagami-$m$ fading channels with one and multiple primary users are considered to derive the required end-to-end SNR analysis. Numerical results are depicted to corroborate our performance analysis and compare it with the PIP case highlighting hence, the impact of the AIP constraint compared to the PIP constraint application.
Perona-Malik equation and its numerical properties
Venue: arXiv cs.NA 2014
Year: 2014

This work concerns the Perona-Malik equation, which plays essential role in image processing. The first part gives a survey of results on existance, uniqueness and stability of solutions, the second part introduces discretisations of equation and deals with an analysis of discrete problem. In the last part I present some numerical results, in particular with algorithms applied to real images.
Reverse Engineering Chemical Reaction Networks from Time Series Data
Venue: arXiv cs.NE 2014
Year: 2014

The automated inference of physically interpretable (bio)chemical reaction network models from measured experimental data is a challenging problem whose solution has significant commercial and academic ramifications. It is demonstrated, using simulations, how sets of elementary reactions comprising chemical reaction networks, as well as their rate coefficients, may be accurately recovered from non-equilibrium time series concentration data, such as that obtained from laboratory scale reactors. A variant of an evolutionary algorithm called differential evolution in conjunction with least squares techniques is used to search the space of reaction networks in order to infer both the reaction network topology and its rate parameters. Properties of the stoichiometric matrices of trial networks are used to bias the search towards physically realisable solutions. No other information, such as chemical characterisation of the reactive species is required, although where available it may be used to improve the search process.
Renewable Energy-Aware Information-Centric Networking
Venue: arXiv cs.NI 2014
Year: 2014

The ICT industry today is placed as one of the major consumers of energy, where recent reports have also shown that the industry is a major contributor to global carbon emissions. While renewable energy-aware data centers have been proposed, these solutions have certain limitations. The primary limitation is due to the design of data centers which focus on large-size facilities located in selected locations. This paper addresses this problem, by utilizing in-network caching with each router having storage and being powered by renewable energy sources (wind and solar). Besides placing contents closer to end users, utilizing in-network caching could potentially increase probability of capturing renewable energy in diverse geographical locations. Our proposed solution is dual- layered: on the first layer a distributed gradient-based routing protocol is used to discover the paths along routers that are powered by the highest renewable energy, and on the second layer, a caching mechanism will pull the contents from the data centre and place them on routers of the paths that are discovered by our routing protocol. Through our experiments on a testbed utilizing real meteorological data, our proposed solution has demonstrated increased quantity of renewable energy consumption, while reducing the workload on the data centers.
Using Python to Dive into Signalling Data with CellNOpt and BioServices
Venue: arXiv cs.CE 2014
Year: 2014

Systems biology is an inter-disciplinary field that studies systems of biological components at different scales, which may be molecules, cells or entire organism. In particular, systems biology methods are applied to understand functional deregulations within human cells (e.g., cancers). In this context, we present several python packages linked to CellNOptR (R package), which is used to build predictive logic models of signalling networks by training networks (derived from literature) to signalling (phospho-proteomic) data. The first package (cellnopt.wrapper) is a wrapper based on RPY2 that allows a full access to CellNOptR functionalities within Python. The second one (cellnopt.core) was designed to ease the manipulation and visualisation of data structures used in CellNOptR, which was achieved by using Pandas, NetworkX and matplotlib. Systems biology also makes extensive use of web resources and services. We will give an overview and status of BioServices, which allows one to access programmatically to web resources used in life science and how it can be combined with CellNOptR.
Managing shop floor systems Using RFID in the Middle East
Venue: arXiv cs.CY 2014
Year: 2014

The controllability of a factory is highly dependent on the capability of a given enterprise planning system to interact with the shop floor, and the capability of any authorized user to review the operation plans, as well as the status of any sales order on the shop floor. We have called the concept E-manufacturing, which is a concept to improve the controllability of a factory by connecting the Enterprise Resource Planning (ERP) system to the shop floor control (SFC) system through the Internet. Business systems and plant systems must be coupled to reduce decision cycle times and increase plant productivity, as well as eliminating human intervention to improve accuracy and data availability speed. This paper is the output of a project funded by the Egyptian Ministry of Scientific Research and Technology, through the Electronic Research Institute. The overall objective of the ministerial program is bridging the gap between R&D and manufacturing to fulfill the immediate technological needs of the Egyptian industry and economy, and building a national technology know-how expertise. This is achieved, in this project, by addressing the development of an E-Manufacturing system using available RFID state-of-the-art technology. The specific objective is developing an end product for Egyptian industry that manages real-time interaction with back end ERP systems to correct delays on the shop floor, improving real-time operation, reducing cost, and allow real-time visibility, through the intelligent usage of the RFID.The end product is a fully working system tested in the factory of the manufacturing partner MOBICA. This report addresses the logical and technical structure,as well as the technology constraints that should be considered in such systems, and the implementation stages of the project
Serving Content with Unknown Demand:the High-Dimensional Regime
Venue: arXiv cs.NI 2014
Year: 2014

In this paper we look at content placement in the high-dimensional regime: there are n servers, and O(n) distinct types of content. Each server can store and serve O(1) types at any given time. Demands for these content types arrive, and have to be served in an online fashion; over time, there are a total of O(n) of these demands. We consider the algorithmic task of content placement: determining which types of content should be on which server at any given time, in the setting where the demand statistics (i.e. the relative popularity of each type of content) are not known a-priori, but have to be inferred from the very demands we are trying to satisfy. This is the high- dimensional regime because this scaling (everything being O(n)) prevents consistent estimation of demand statistics; it models many modern settings where large numbers of users, servers and videos/webpages interact in this way. We characterize the performance of any scheme that separates learning and placement (i.e. which use a portion of the demands to gain some estimate of the demand statistics, and then uses the same for the remaining demands), showing it is order-wise strictly suboptimal. We then study a simple adaptive scheme - which myopically attempts to store the most recently requested content on idle servers - and show it outperforms schemes that separate learning and placement. Our results also generalize to the setting where the demand statistics change with time. Overall, our results demonstrate that separating the estimation of demand, and the subsequent use of the same, is strictly suboptimal.
GRAPHITE: An Extensible Graph Traversal Framework for Relational Database Management Systems
Venue: arXiv cs.DB 2014
Year: 2014

Graph traversals are a basic but fundamental ingredient for a variety of graph algorithms and graph-oriented queries. To achieve the best possible query performance, they need to be implemented at the core of a database management system that aims at storing, manipulating, and querying graph data. Increasingly, modern business applications demand native graph query and processing capabilities for enterprise-critical operations on data stored in relational database management systems. In this paper we propose an extensible graph traversal framework (GRAPHITE) as a central graph processing component on a common storage engine inside a relational database management system. We study the influence of the graph topology on the execution time of graph traversals and derive two traversal algorithm implementations specialized for different graph topologies and traversal queries. We conduct extensive experiments on GRAPHITE for a large variety of real-world graph data sets and input configurations. Our experiments show that the proposed traversal algorithms differ by up to two orders of magnitude for different input configurations and therefore demonstrate the need for a versatile framework to efficiently process graph traversals on a wide range of different graph topologies and types of queries. Finally, we highlight that the query performance of our traversal implementations is competitive with those of two native graph database management systems.
Parametric Sensitivity Analysis for Stochastic Molecular Systems using Information Theoretic Metrics
Venue: arXiv cs.IT 2014
Year: 2014

In this paper we extend the parametric sensitivity analysis (SA) methodology proposed in Ref. [Y. Pantazis and M. A. Katsoulakis, J. Chem. Phys. 138, 054115 (2013)] to continuous time and continuous space Markov processes represented by stochastic differential equations and, particularly, stochastic molecular dynamics as described by the Langevin equation. The utilized SA method is based on the computation of the information-theoretic (and thermodynamic) quantity of relative entropy rate (RER) and the associated Fisher information matrix (FIM) between path distributions. A major advantage of the pathwise SA method is that both RER and pathwise FIM depend only on averages of the force field therefore they are tractable and computable as ergodic averages from a single run of the molecular dynamics simulation both in equilibrium and in non-equilibrium steady state regimes. We validate the performance of the extended SA method to two different molecular stochastic systems, a standard Lennard-Jones fluid and an all-atom methane liquid and compare the obtained parameter sensitivities with parameter sensitivities on three popular and well-studied observable functions, namely, the radial distribution function, the mean squared displacement and the pressure. Results show that the RER-based sensitivities are highly correlated with the observable-based sensitivities.
Compression of Video Tracking and Bandwidth Balancing Routing in Wireless Multimedia Sensor Networks
Venue: arXiv cs.NI 2014
Year: 2014

There has been a tremendous growth in multimedia applications over wireless networks. Wireless Multimedia Sensor Networks(WMSNs) have become the premier choice in many research communities and industry. Many state-of-art applications, such as surveillance, traffic monitoring, and remote heath care are essentially video tracking and transmission in WMSNs. The transmission speed is constrained by big size of video data and fixed bandwidth allocation in constant routing path. In this paper, we present a CamShift based algorithm to compress the tracking of videos. Then we propose a bandwidth balancing strategy in which each sensor node is able to dynamically select the node for next hop with the highest potential bandwidth capacity to resume communication. Key to the strategy is that each node merely maintains two parameters that contains its historical bandwidth varying trend and then predicts its near future bandwidth capacity. Then forwarding node selects the next hop with the highest potential bandwidth capacity. Simulations demonstrate that our approach significantly increases the data received by sink node and decreases the delay on video transmission in Wireless Multimedia Sensor Network environment.
Qualitative shape representation based on the qualitative relative direction and distance calculus eOPRAm
Venue: arXiv cs.AI 2014
Year: 2014

This document serves as a brief technical report, detailing the processes used to represent and reconstruct simplified polygons using qualitative spatial descriptions, as defined by the eOPRAm qualitative spatial calculus.
On the Shadow Simplex Method for Curved Polyhedra
Venue: arXiv cs.DS 2014
Year: 2014

We study the simplex method over polyhedra satisfying certain "discrete curvature" lower bounds, which enforce that the boundary always meets vertices at sharp angles. Motivated by linear programs with totally unimodular constraint matrices, recent results of Bonifas et al (SOCG 2012), Brunsch and Röglin (ICALP 2013), and Eisenbrand and Vempala (2014) have improved our understanding of such polyhedra. We develop a new type of dual analysis of the shadow simplex method which provides a clean and powerful tool for improving all previously mentioned results. Our methods are inspired by the recent work of Bonifas and the first named author (SODA 2015), who analyzed a remarkably similar process as part of an algorithm for the Closest Vector Problem with Preprocessing. For our first result, we obtain a constructive diameter bound of $O(\frac{n^2}δ \ln \frac{n}δ)$ for $n$-dimensional polyhedra with curvature parameter $δ\in [0,1]$. For the class of polyhedra arising from totally unimodular constraint matrices, this implies a bound of $O(n^3 \ln n)$. For linear optimization, given an initial feasible vertex, we show that an optimal vertex can be found using an expected $O(\frac{n^3}δ \ln \frac{n}δ)$ simplex pivots, each requiring $O(m n)$ time to compute. An initial feasible solution can be found using $O(\frac{m n^3}δ \ln \frac{n}δ)$ pivot steps.
An Uplink Interference Analysis for Massive MIMO Systems with MRC and ZF Receivers
Venue: arXiv cs.IT 2014
Year: 2014

This paper considers an uplink cellular system, in which each base station (BS) is equipped with a large number of antennas to serve multiple single-antenna user equipments (UEs) simultaneously. Uplink training with pilot reusing is adopted to acquire the channel state information (CSI) and maximum ratio combining (MRC) or zero forcing (ZF) reception is used for handling multiuser interference. Leveraging stochastic geometry to model the spatial distribution of UEs, we analyze the statistical distributions of the interferences experienced by a typical uplink: intra-cell interference, inter-cell interference and interference due to pilot contamination. For a practical but still large number of BS antennas, a key observation for MRC reception is that it is the intra-cell interference that accounts for the dominant portion of the total interference. In addition, the interference due to pilot contamination tends to have a much wider distribution range than the inter-cell interference when shadowing is strong, although their mean powers are roughly equal. For ZF reception, on the other hand, we observe a significant reduction of the intra-cell interference compared to MRC reception, while the inter-cell interference and the interference due to pilot contamination remains almost the same, thus demonstrating a substantial superiority over MRC reception.
An Improved Approximation Algorithm for the Traveling Salesman Problem with Relaxed Triangle Inequality
Venue: arXiv cs.DS 2014
Year: 2014

Given a complete edge-weighted graph G, we present a polynomial time algorithm to compute a degree-four-bounded spanning Eulerian subgraph of 2G that has at most 1.5 times the weight of an optimal TSP solution of G. Based on this algorithm and a novel use of orientations in graphs, we obtain a (3 beta/4 + 3 beta^2/4)-approximation algorithm for TSP with beta-relaxed triangle inequality (beta-TSP), where beta >= 1. A graph G is an instance of beta-TSP, if it is a complete graph with non-negative edge weights that are restricted as follows. For each triple of vertices u,v,w in V(G), c({u,v}) <= beta (c({u,w}) + c({w,v})).
Information-theoretic applications of the logarithmic probability comparison bound
Venue: arXiv cs.IT 2014
Year: 2014

A well-known technique in estimating probabilities of rare events in general and in information theory in particular (used, e.g., in the sphere-packing bound), is that of finding a reference probability measure under which the event of interest has probability of order one and estimating the probability in question by means of the Kullback-Leibler divergence. A method has recently been proposed in [2], that can be viewed as an extension of this idea in which the probability under the reference measure may itself be decaying exponentially, and the Renyi divergence is used instead. The purpose of this paper is to demonstrate the usefulness of this approach in various information-theoretic settings. For the problem of channel coding, we provide a general methodology for obtaining matched, mismatched and robust error exponent bounds, as well as new results in a variety of particular channel models. Other applications we address include rate-distortion coding and the problem of guessing.
A New Way to Factorize Linear Cameras
Venue: arXiv cs.CV 2014
Year: 2014

The implementation details of factorizing the 3x4 projection matrices of linear cameras into their left matrix factors and the 4x4 homogeneous central(also parallel for infinite center cases) projection factors are presented in this work. Any full row rank 3x4 real matrix can be factorized into such basic matrices which will be called LC factors. A further extension to multiple view midpoint triangulation, for both pinhole and affine camera cases, is also presented based on such camera factorizations.
Time Bounds for Streaming Problems
Venue: arXiv cs.DS 2014
Year: 2014

We give tight cell-probe bounds for the time to compute convolution, multiplication and Hamming distance in a stream. The cell probe model is a particularly strong computational model and subsumes, for example, the popular word RAM model. We first consider online convolution where the task is to output the inner product between a fixed $n$-dimensional vector and a vector of the $n$ most recent values from a stream. One symbol of the stream arrives at a time and the each output must be computed before the next symbols arrives. Next we show bounds for online multiplication where the stream consists of pairs of digits, one from each of two $n$ digit numbers that are to be multiplied. One pair arrives at a time and the task is to output a single new digit from the product before the next pair of digits arrives. Finally we look at the online Hamming distance problem where the Hamming distance is outputted instead of the inner product. For each of these three problems, we give a lower bound of $Ω(\fracδ{w}\log n)$ time on average per output, where $δ$ is the number of bits needed to represent an input symbol and $w$ is the cell or word size. We argue that these bound are in fact tight within the cell probe model.