OpenRaiser/Intern-Atlas huggingface dataset:
SUPER: Sparse signals with Unknown Phases Efficiently Recovered
Venue: arXiv cs.IT 2014
Year: 2014

Suppose ${\bf x}$ is any exactly $k$-sparse vector in $\mathbb{C}^{n}$. We present a class of phase measurement matrix $A$ in $\mathbb{C}^{m\times n}$, and a corresponding algorithm, called SUPER, that can resolve ${\bf x}$ up to a global phase from intensity measurements $|A{\bf x}|$ with high probability over $A$. Here $|A{\bf x}|$ is a vector of component-wise magnitudes of $A{\bf x}$. The SUPER algorithm is the first to simultaneously have the following properties: (a) it requires only ${\cal O}(k)$ (order-optimal) measurements, (b) the computational complexity of decoding is ${\cal O}(k\log k)$ (near order-optimal) arithmetic operations.
Super-Resolution Compressed Sensing: An Iterative Reweighted Algorithm for Joint Parameter Learning and Sparse Signal Recovery
Venue: arXiv cs.IT 2014
Year: 2014

In many practical applications such as direction-of-arrival (DOA) estimation and line spectral estimation, the sparsifying dictionary is usually characterized by a set of unknown parameters in a continuous domain. To apply the conventional compressed sensing to such applications, the continuous parameter space has to be discretized to a finite set of grid points. Discretization, however, incurs errors and leads to deteriorated recovery performance. To address this issue, we propose an iterative reweighted method which jointly estimates the unknown parameters and the sparse signals. Specifically, the proposed algorithm is developed by iteratively decreasing a surrogate function majorizing a given objective function, which results in a gradual and interweaved iterative process to refine the unknown parameters and the sparse signal. Numerical results show that the algorithm provides superior performance in resolving closely-spaced frequency components.
Intelligent Techniques for Resolving Conflicts of Knowledge in Multi-Agent Decision Support Systems
Venue: arXiv cs.MA 2014
Year: 2014

This paper focuses on some of the key intelligent techniques for conflict resolution in Multi-Agent Decision Support Systems.
On the Succinctness of Query Rewriting over OWL 2 QL Ontologies with Shallow Chases
Venue: arXiv cs.LO 2014
Year: 2014

We investigate the size of first-order rewritings of conjunctive queries over OWL 2 QL ontologies of depth 1 and 2 by means of hypergraph programs computing Boolean functions. Both positive and negative results are obtained. Conjunctive queries over ontologies of depth 1 have polynomial-size nonrecursive datalog rewritings; tree-shaped queries have polynomial positive existential rewritings; however, in the worst case, positive existential rewritings can only be of superpolynomial size. Positive existential and nonrecursive datalog rewritings of queries over ontologies of depth 2 suffer an exponential blowup in the worst case, while first-order rewritings are superpolynomial unless $\text{NP} \subseteq \text{P}/\text{poly}$. We also analyse rewritings of tree-shaped queries over arbitrary ontologies and observe that the query entailment problem for such queries is fixed-parameter tractable.
Attacks And Counterattacks On Wireless Sensor Networks
Venue: arXiv cs.NI 2014
Year: 2014

WSN is formed by autonomous nodes with partial memory, communication range, power, and bandwidth. Their occupation depends on inspecting corporal and environmental conditions and communing through a system and performing data processing. The application field is vast, comprising military, ecology, healthcare, home or commercial and require a highly secured communication. The paper analyses different types of attacks and counterattacks and provides solutions for the WSN threats
Detection and Decoding for 2D Magnetic Recording Channels with 2D Intersymbol Interference
Venue: arXiv cs.IT 2014
Year: 2014

This paper considers iterative detection and decoding on the concatenated communication channel consisting of a two-dimensional magnetic recording (TDMR) channel modeled by the four-grain rectangular discrete grain model (DGM) proposed by Kavcic et. al., followed by a two-dimensional intersymbol interference (2D-ISI) channel modeled by linear convolution of the DGM model's output with a finite-extent 2D blurring mask followed by addition of white Gaussian noise. An iterative detection and decoding scheme combines TDMR detection, 2D-ISI detection, and soft-in/soft-out (SISO) channel decoding in a structure with two iteration loops. In the first loop, the 2D-ISI channel detector exchanges log-likelihood ratios (LLRs) with the TDMR detector. In the second loop, the TDMR detector exchanges LLRs with a serially concatenated convolutional code (SCCC) decoder. Simulation results for the concatenated TDMR and 2 x 2 averaging mask ISI channel with 10 dB SNR show that densities of 0.48 user bits per grain and above can be achieved, corresponding to an areal density of about 9.6 Terabits per square inch, over the entire range of grain probabilities in the TDMR model.
Solving the Minimum Common String Partition Problem with the Help of Ants
Venue: arXiv cs.AI 2014
Year: 2014

In this paper, we consider the problem of finding a minimum common partition of two strings. The problem has its application in genome comparison. As it is an NP-hard, discrete combinatorial optimization problem, we employ a metaheuristic technique, namely, MAX-MIN ant system to solve this problem. To achieve better efficiency we first map the problem instance into a special kind of graph. Subsequently, we employ a MAX-MIN ant system to achieve high quality solutions for the problem. Experimental results show the superiority of our algorithm in comparison with the state of art algorithm in the literature. The improvement achieved is also justified by standard statistical test.
Excess Risk Bounds for Exponentially Concave Losses
Venue: arXiv cs.LG 2014
Year: 2014

The overarching goal of this paper is to derive excess risk bounds for learning from exp-concave loss functions in passive and sequential learning settings. Exp-concave loss functions encompass several fundamental problems in machine learning such as squared loss in linear regression, logistic loss in classification, and negative logarithm loss in portfolio management. In batch setting, we obtain sharp bounds on the performance of empirical risk minimization performed in a linear hypothesis space and with respect to the exp-concave loss functions. We also extend the results to the online setting where the learner receives the training examples in a sequential manner. We propose an online learning algorithm that is a properly modified version of online Newton method to obtain sharp risk bounds. Under an additional mild assumption on the loss function, we show that in both settings we are able to achieve an excess risk bound of $O(d\log n/n)$ that holds with a high probability.
Proximity-Based Non-uniform Abstractions for Approximate Planning
Venue: arXiv cs.AI 2014
Year: 2014

In a deterministic world, a planning agent can be certain of the consequences of its planned sequence of actions. Not so, however, in dynamic, stochastic domains where Markov decision processes are commonly used. Unfortunately these suffer from the curse of dimensionality: if the state space is a Cartesian product of many small sets (dimensions), planning is exponential in the number of those dimensions. Our new technique exploits the intuitive strategy of selectively ignoring various dimensions in different parts of the state space. The resulting non-uniformity has strong implications, since the approximation is no longer Markovian, requiring the use of a modified planner. We also use a spatial and temporal proximity measure, which responds to continued planning as well as movement of the agent through the state space, to dynamically adapt the abstraction as planning progresses. We present qualitative and quantitative results across a range of experimental domains showing that an agent exploiting this novel approximation method successfully finds solutions to the planning problem using much less than the full state space. We assess and analyse the features of domains which our method can exploit.
Learning and Reasoning with Action-Related Places for Robust Mobile Manipulation
Venue: arXiv cs.RO 2014
Year: 2014

We propose the concept of Action-Related Place (ARPlace) as a powerful and flexible representation of task-related place in the context of mobile manipulation. ARPlace represents robot base locations not as a single position, but rather as a collection of positions, each with an associated probability that the manipulation action will succeed when located there. ARPlaces are generated using a predictive model that is acquired through experience-based learning, and take into account the uncertainty the robot has about its own location and the location of the object to be manipulated. When executing the task, rather than choosing one specific goal position based only on the initial knowledge about the task context, the robot instantiates an ARPlace, and bases its decisions on this ARPlace, which is updated as new information about the task becomes available. To show the advantages of this least-commitment approach, we present a transformational planner that reasons about ARPlaces in order to optimize symbolic plans. Our empirical evaluation demonstrates that using ARPlaces leads to more robust and efficient mobile manipulation in the face of state estimation uncertainty on our simulated robot.
Exploiting Model Equivalences for Solving Interactive Dynamic Influence Diagrams
Venue: arXiv cs.AI 2014
Year: 2014

We focus on the problem of sequential decision making in partially observable environments shared with other agents of uncertain types having similar or conflicting objectives. This problem has been previously formalized by multiple frameworks one of which is the interactive dynamic influence diagram (I-DID), which generalizes the well-known influence diagram to the multiagent setting. I-DIDs are graphical models and may be used to compute the policy of an agent given its belief over the physical state and others models, which changes as the agent acts and observes in the multiagent setting. As we may expect, solving I-DIDs is computationally hard. This is predominantly due to the large space of candidate models ascribed to the other agents and its exponential growth over time. We present two methods for reducing the size of the model space and stemming its exponential growth. Both these methods involve aggregating individual models into equivalence classes. Our first method groups together behaviorally equivalent models and selects only those models for updating which will result in predictive behaviors that are distinct from others in the updated model space. The second method further compacts the model space by focusing on portions of the behavioral predictions. Specifically, we cluster actionally equivalent models that prescribe identical actions at a single time step. Exactly identifying the equivalences would require us to solve all models in the initial set. We avoid this by selectively solving some of the models, thereby introducing an approximation. We discuss the error introduced by the approximation, and empirically demonstrate the improved efficiency in solving I-DIDs due to the equivalences.
Cloning in Elections: Finding the Possible Winners
Venue: arXiv cs.GT 2014
Year: 2014

We consider the problem of manipulating elections by cloning candidates. In our model, a manipulator can replace each candidate c by several clones, i.e., new candidates that are so similar to c that each voter simply replaces c in his vote with a block of these new candidates, ranked consecutively. The outcome of the resulting election may then depend on the number of clones as well as on how each voter orders the clones within the block. We formalize what it means for a cloning manipulation to be successful (which turns out to be a surprisingly delicate issue), and, for a number of common voting rules, characterize the preference profiles for which a successful cloning manipulation exists. We also consider the model where there is a cost associated with producing each clone, and study the complexity of finding a minimum-cost cloning manipulation. Finally, we compare cloning with two related problems: the problem of control by adding candidates and the problem of possible (co)winners when new alternatives can join.
Completeness Guarantees for Incomplete Ontology Reasoners: Theory and Practice
Venue: arXiv cs.AI 2014
Year: 2014

To achieve scalability of query answering, the developers of Semantic Web applications are often forced to use incomplete OWL 2 reasoners, which fail to derive all answers for at least one query, ontology, and data set. The lack of completeness guarantees, however, may be unacceptable for applications in areas such as health care and defence, where missing answers can adversely affect the applications functionality. Furthermore, even if an application can tolerate some level of incompleteness, it is often advantageous to estimate how many and what kind of answers are being lost. In this paper, we present a novel logic-based framework that allows one to check whether a reasoner is complete for a given query Q and ontology T---that is, whether the reasoner is guaranteed to compute all answers to Q w.r.t. T and an arbitrary data set A. Since ontologies and typical queries are often fixed at application design time, our approach allows application developers to check whether a reasoner known to be incomplete in general is actually complete for the kinds of input relevant for the application. We also present a technique that, given a query Q, an ontology T, and reasoners R_1 and R_2 that satisfy certain assumptions, can be used to determine whether, for each data set A, reasoner R_1 computes more answers to Q w.r.t. T and A than reasoner R_2. This allows application developers to select the reasoner that provides the highest degree of completeness for Q and T that is compatible with the applications scalability requirements. Our results thus provide a theoretical and practical foundation for the design of future ontology-based information systems that maximise scalability while minimising or even eliminating incompleteness of query answers.
Modelling Observation Correlations for Active Exploration and Robust Object Detection
Venue: arXiv cs.RO 2014
Year: 2014

Today, mobile robots are expected to carry out increasingly complex tasks in multifarious, real-world environments. Often, the tasks require a certain semantic understanding of the workspace. Consider, for example, spoken instructions from a human collaborator referring to objects of interest; the robot must be able to accurately detect these objects to correctly understand the instructions. However, existing object detection, while competent, is not perfect. In particular, the performance of detection algorithms is commonly sensitive to the position of the sensor relative to the objects in the scene. This paper presents an online planning algorithm which learns an explicit model of the spatial dependence of object detection and generates plans which maximize the expected performance of the detection, and by extension the overall plan performance. Crucially, the learned sensor model incorporates spatial correlations between measurements, capturing the fact that successive measurements taken at the same or nearby locations are not independent. We show how this sensor model can be incorporated into an efficient forward search algorithm in the information space of detected objects, allowing the robot to generate motion plans efficiently. We investigate the performance of our approach by addressing the tasks of door and text detection in indoor environments and demonstrate significant improvement in detection performance during task execution over alternative methods in simulated and real robot experiments.
HERMES: A Hierarchical Broadcast-Based Silicon Photonic Interconnect for Scalable Many-Core Systems
Venue: arXiv cs.AR 2014
Year: 2014

Optical interconnection networks, as enabled by recent advances in silicon photonic device and fabrication technology, have the potential to address on-chip and off-chip communication bottlenecks in many-core systems. Although several designs have shown superior power efficiency and performance compared to electrical alternatives, these networks will not scale to the thousands of cores required in the future. In this paper, we introduce Hermes, a hybrid network composed of an optimized broadcast for power-efficient low-latency global-scale coordination and circuit-switch sub-networks for high-throughput data delivery. This network will scale for use in thousand core chip systems. At the physical level, SoI-based adiabatic coupler has been designed to provide low-loss and compact optical power splitting. Based on the adiabatic coupler, a topology based on 2-ary folded butterfly is designed to provide linear power division in a thousand core layout with minimal cross-overs. To address the network agility and provide for efficient use of optical bandwidth, a flow control and routing mechanism is introduced to dynamically allocate bandwidth and provide fairness usage of network resources. At the system level, bloom filter-based filtering for localization of communication are designed for reducing global traffic. In addition, a novel greedy-based data and workload migration are leveraged to increase the locality of communication in a NUCA (non-uniform cache access) architecture. First order analytic evaluation results have indicated that Hermes is scalable to at least 1024 cores and offers significant performance improvement and power savings over prior silicon photonic designs.
Time series modeling and large scale global solar radiation forecasting from geostationary satellites data
Venue: arXiv cs.CE 2014
Year: 2014

When a territory is poorly instrumented, geostationary satellites data can be useful to predict global solar radiation. In this paper, we use geostationary satellites data to generate 2-D time series of solar radiation for the next hour. The results presented in this paper relate to a particular territory, the Corsica Island, but as data used are available for the entire surface of the globe, our method can be easily exploited to another place. Indeed 2-D hourly time series are extracted from the HelioClim-3 surface solar irradiation database treated by the Heliosat-2 model. Each point of the map have been used as training data and inputs of artificial neural networks (ANN) and as inputs for two persistence models (scaled or not). Comparisons between these models and clear sky estimations were proceeded to evaluate the performances. We found a normalized root mean square error (nRMSE) close to 16.5% for the two best predictors (scaled persistence and ANN) equivalent to 35-45% related to ground measurements. Finally in order to validate our 2-D predictions maps, we introduce a new error metric called the gamma index which is a criterion for comparing data from two matrixes in medical physics. As first results, we found that in winter and spring, scaled persistence gives the best results (gamma index test passing rate is respectively 67.7% and 86%), in autumn simple persistence is the best predictor (95.3%) and ANN is the best in summer (99.8%).
A Gray Code for cross-bifix-free sets
Venue: arXiv cs.IT 2014
Year: 2014

A cross-bifix-free set of words is a set in which no prefix of any length of any word is the suffix of any other word in the set. A construction of cross-bifix-free sets has recently been proposed by Chee {\it et al.} in 2013 within a constant factor of optimality. We propose a \emph{trace partitioned} Gray code for these cross-bifix-free sets and a CAT algorithm generating it.
An algorithm for calculating steady state probabilities of $M|E_r|c|K$ queueing systems
Venue: arXiv cs.SY 2014
Year: 2014

This paper presents a method for calculating steady state probabilities of $M|E_r|c|K$ queueing systems. The infinitesimal generator matrix is used to define all possible states in the system and their transition probabilities. While this matrix can be written down immediately for many other $M|PH|c|K$ queueing systems with phase-type service times (e.g. Coxian, Hypoexponential, \ldots), it requires a more careful analysis for systems with Erlangian service times. The constructed matrix may then be used to calculate steady state probabilities using an iterative algorithm. The resulting steady state probabilities can be used to calculate various performance measures, e.g. the average queue length. Additionally, computational issues of the implementation are discussed and an example from the field of telecommunication call-center queue length will be outlined to substantiate the applicability of these efforts. In the appendix, tables of the average queueing length given a specific number of service channels, traffic density, and system size are presented.
Computing low-degree factors of lacunary polynomials: a Newton-Puiseux approach
Venue: arXiv cs.SC 2014
Year: 2014

We present a new algorithm for the computation of the irreducible factors of degree at most $d$, with multiplicity, of multivariate lacunary polynomials over fields of characteristic zero. The algorithm reduces this computation to the computation of irreducible factors of degree at most $d$ of univariate lacunary polynomials and to the factorization of low-degree multivariate polynomials. The reduction runs in time polynomial in the size of the input polynomial and in $d$. As a result, we obtain a new polynomial-time algorithm for the computation of low-degree factors, with multiplicity, of multivariate lacunary polynomials over number fields, but our method also gives partial results for other fields, such as the fields of $p$-adic numbers or for absolute or approximate factorization for instance. The core of our reduction uses the Newton polygon of the input polynomial, and its validity is based on the Newton-Puiseux expansion of roots of bivariate polynomials. In particular, we bound the valuation of $f(X,ϕ)$ where $f$ is a lacunary polynomial and $ϕ$ a Puiseux series whose vanishing polynomial has low degree.
Verification of agent knowledge in dynamic access control policies
Venue: arXiv cs.LO 2014
Year: 2014

We develop a modeling technique based on interpreted systems in order to verify temporal-epistemic properties over access control policies. This approach enables us to detect information flow vulnerabilities in dynamic policies by verifying the knowledge of the agents gained by both reading and reasoning about system information. To overcome the practical limitations of state explosion in model-checking temporal-epistemic properties, we introduce a novel abstraction and refinement technique for temporal-epistemic safety properties in ACTLK (ACTL with knowledge modality K) and a class of interesting properties that does fall in this category.