OpenRaiser/Intern-Atlas huggingface dataset:
Two Timescale Convergent Q-learning for Sleep--Scheduling in Wireless Sensor Networks
Venue: arXiv cs.SY 2014
Year: 2014

In this paper, we consider an intrusion detection application for Wireless Sensor Networks (WSNs). We study the problem of scheduling the sleep times of the individual sensors to maximize the network lifetime while keeping the tracking error to a minimum. We formulate this problem as a partially-observable Markov decision process (POMDP) with continuous state-action spaces, in a manner similar to (Fuemmeler and Veeravalli [2008]). However, unlike their formulation, we consider infinite horizon discounted and average cost objectives as performance criteria. For each criterion, we propose a convergent on-policy Q-learning algorithm that operates on two timescales, while employing function approximation to handle the curse of dimensionality associated with the underlying POMDP. Our proposed algorithm incorporates a policy gradient update using a one-simulation simultaneous perturbation stochastic approximation (SPSA) estimate on the faster timescale, while the Q-value parameter (arising from a linear function approximation for the Q-values) is updated in an on-policy temporal difference (TD) algorithm-like fashion on the slower timescale. The feature selection scheme employed in each of our algorithms manages the energy and tracking components in a manner that assists the search for the optimal sleep-scheduling policy. For the sake of comparison, in both discounted and average settings, we also develop a function approximation analogue of the Q-learning algorithm. This algorithm, unlike the two-timescale variant, does not possess theoretical convergence guarantees. Finally, we also adapt our algorithms to include a stochastic iterative estimation scheme for the intruder's mobility model. Our simulation results on a 2-dimensional network setting suggest that our algorithms result in better tracking accuracy at the cost of only a few additional sensors, in comparison to a recent prior work.
Shape Primitive Histogram: A Novel Low-Level Face Representation for Face Recognition
Venue: arXiv cs.CV 2014
Year: 2014

We further exploit the representational power of Haar wavelet and present a novel low-level face representation named Shape Primitives Histogram (SPH) for face recognition. Since human faces exist abundant shape features, we address the face representation issue from the perspective of the shape feature extraction. In our approach, we divide faces into a number of tiny shape fragments and reduce these shape fragments to several uniform atomic shape patterns called Shape Primitives. A convolution with Haar Wavelet templates is applied to each shape fragment to identify its belonging shape primitive. After that, we do a histogram statistic of shape primitives in each spatial local image patch for incorporating the spatial information. Finally, each face is represented as a feature vector via concatenating all the local histograms of shape primitives. Four popular face databases, namely ORL, AR, Yale-B and LFW-a databases, are employed to evaluate SPH and experimentally study the choices of the parameters. Extensive experimental results demonstrate that the proposed approach outperform the state-of-the-arts.
Collaborative Discriminant Locality Preserving Projections With its Application to Face Recognition
Venue: arXiv cs.CV 2014
Year: 2014

We present a novel Discriminant Locality Preserving Projections (DLPP) algorithm named Collaborative Discriminant Locality Preserving Projection (CDLPP). In our algorithm, the discriminating power of DLPP are further exploited from two aspects. On the one hand, the global optimum of class scattering is guaranteed via using the between-class scatter matrix to replace the original denominator of DLPP. On the other hand, motivated by collaborative representation, an $L_2$-norm constraint is imposed to the projections to discover the collaborations of dimensions in the sample space. We apply our algorithm to face recognition. Three popular face databases, namely AR, ORL and LFW-A, are employed for evaluating the performance of CDLPP. Extensive experimental results demonstrate that CDLPP significantly improves the discriminating power of DLPP and outperforms the state-of-the-arts.
An Effective End-User Development Approach Through Domain-Specific Mashups for Research Impact Evaluation
Venue: arXiv cs.DL 2014
Year: 2014

Over the last decade, there has been growing interest in the assessment of the performance of researchers, research groups, universities and even countries. The assessment of productivity is an instrument to select and promote personnel, assign research grants and measure the results of research projects. One particular assessment approach is bibliometrics i.e., the quantitative analysis of scientific publications through citation and content analysis. However, there is little consensus today on how research evaluation should be performed, and it is commonly acknowledged that the quantitative metrics available today are largely unsatisfactory. A number of different scientific data sources available on the Web (e.g., DBLP, Google Scholar) that are used for such analysis purposes. Taking data from these diverse sources, performing the analysis and visualizing results in different ways is not a trivial and straight forward task. Moreover, people involved in such evaluation processes are not always IT experts and hence not capable to crawl data sources, merge them and compute the needed evaluation procedures. The recent emergence of mashup tools has refueled research on end-user development, i.e., on enabling end-users without programming skills to produce their own applications. We believe that the heart of the problem is that it is impractical to design tools that are generic enough to cover a wide range of application domains, powerful enough to enable the specification of non-trivial logic, and simple enough to be actually accessible to non-programmers. This thesis presents a novel approach for an effective end-user development, specifically for non-programmers. That is, we introduce a domain-specific approach to mashups that "speaks the language of users"., i.e., that is aware of the terminology, concepts, rules, and conventions (the domain) the user is comfortable with.
Effect of Carouseling on Angular Rate Sensor Error Processes
Venue: arXiv cs.OH 2014
Year: 2014

Carouseling is an efficient method to mitigate the measurement errors of inertial sensors, particularly MEMS gyroscopes. In this article, the effect of carouseling on the most significant stochastic error processes of a MEMS gyroscope, i.e., additive bias, white noise, 1/f noise, and rate random walk, is investigated. Variance propagation equations for these processes under averaging and carouseling are defined. Furthermore, a novel approach to generating 1/f noise is presented. The experimental results show that carouseling reduces the contributions of additive bias, 1/f noise, and rate random walk significantly in comparison with plain averaging, which can be utilized to improve the accuracy of dead reckoning systems.
Connectivity-preserving Geometry Images
Venue: arXiv cs.GR 2014
Year: 2014

We propose connectivity-preserving geometry images (CGIMs), which map a three-dimensional mesh onto a rectangular regular array of an image, such that the reconstructed mesh produces no sampling errors, but merely round-off errors. We obtain a V-matrix with respect to the original mesh, whose elements are vertices of the mesh, which intrinsically preserves the vertex-set and the connectivity of the original mesh in the sense of allowing round-off errors. We generate a CGIM array by using the Cartesian coordinates of corresponding vertices of the V-matrix. To reconstruct a mesh, we obtain a vertex-set and an edge-set by collecting all the elements with different pixels, and all different pairwise adjacent elements from the CGIM array respectively. Compared with traditional geometry images, CGIMs achieve minimum reconstruction errors with an efficient parametrization-free algorithm via elementary permutation techniques. We apply CGIMs to lossy compression of meshes, and the experimental results show that CGIMs perform well in reconstruction precision and detail preservation.
Models for the modern power grid
Venue: arXiv cs.SY 2014
Year: 2014

This article reviews different kinds of models for the electric power grid that can be used to understand the modern power system, the smart grid. From the physical network to abstract energy markets, we identify in the literature different aspects that co-determine the spatio-temporal multilayer dynamics of power system. We start our review by showing how the generation, transmission and distribution characteristics of the traditional power grids are already subject to complex behaviour appearing as a result of the the interplay between dynamics of the nodes and topology, namely synchronisation and cascade effects. When dealing with smart grids, the system complexity increases even more: on top of the physical network of power lines and controllable sources of electricity, the modernisation brings information networks, renewable intermittent generation, market liberalisation, prosumers, among other aspects. In this case, we forecast a dynamical co-evolution of the smart grid and other kind of networked systems that cannot be understood isolated. This review compiles recent results that model electric power grids as complex systems, going beyond pure technological aspects. From this perspective, we then indicate possible ways to incorporate the diverse co-evolving systems into the smart grid model using, for example, network theory and multi-agent simulation.
The Empirical Implications of Privacy-Aware Choice
Venue: arXiv cs.GT 2014
Year: 2014

This paper initiates the study of the testable implications of choice data in settings where agents have privacy preferences. We adapt the standard conceptualization of consumer choice theory to a situation where the consumer is aware of, and has preferences over, the information revealed by her choices. The main message of the paper is that little can be inferred about consumers' preferences once we introduce the possibility that the consumer has concerns about privacy. This holds even when consumers' privacy preferences are assumed to be monotonic and separable. This motivates the consideration of stronger assumptions and, to that end, we introduce an additive model for privacy preferences that does have testable implications.
Distributed Iterative Detection Based on Reduced Message Passing for Networked MIMO Cellular Systems
Venue: arXiv cs.IT 2014
Year: 2014

This paper considers base station cooperation (BSC) strategies for the uplink of a multi-user multi-cell high frequency reuse scenario where distributed iterative detection (DID) schemes with soft/hard interference cancellation algorithms are studied. The conventional distributed detection scheme exchanges {soft symbol estimates} with all cooperating BSs. Since a large amount of information needs to be shared via the backhaul, the exchange of hard bit information is preferred, however a performance degradation is experienced. In this paper, we consider a reduced message passing (RMP) technique in which each BS generates a detection list with the probabilities for the desired symbol that are sorted according to the calculated probability. The network then selects the best {detection candidates} from the lists and conveys the index of the constellation symbols (instead of double-precision values) among the cooperating cells. The proposed DID-RMP achieves an inter-cell-interference (ICI) suppression with low backhaul traffic overhead compared with {the conventional soft bit exchange} and outperforms the previously reported hard/soft information exchange algorithms.
On Minimum Average Stretch Spanning Trees in Polygonal 2-trees
Venue: arXiv cs.DS 2014
Year: 2014

A spanning tree of an unweighted graph is a minimum average stretch spanning tree if it minimizes the ratio of sum of the distances in the tree between the end vertices of the graph edges and the number of graph edges. We consider the problem of computing a minimum average stretch spanning tree in polygonal 2-trees, a super class of 2-connected outerplanar graphs. For a polygonal 2-tree on $n$ vertices, we present an algorithm to compute a minimum average stretch spanning tree in $O(n \log n)$ time. This algorithm also finds a minimum fundamental cycle basis in polygonal 2-trees.
UROP: A Simple, Near-Optimal Scheduling Policy for Energy Harvesting Sensors
Venue: arXiv cs.IT 2014
Year: 2014

This paper considers a single-hop wireless network where a central node (or fusion center, FC) collects data from a set of m energy harvesting (EH) nodes (e.g. nodes of a wireless sensor network). In each time slot, k of m nodes can be scheduled by the FC for transmission over k orthogonal channels. FC has no knowledge about EH processes and current battery states of nodes; however, it knows outcomes of previous transmission attempts. The objective is to find a low complexity scheduling policy that maximizes total throughput of the data backlogged system using the harvested energy, for all types (uniform, non-uniform, independent, correlated (i.e. Markovian), etc.) EH processes. Energy is assumed to be stored losslessly in the nodes batteries, up to a storage capacity (the infinite capacity case is also considered.) The problem is treated in finite and infinite problem horizons. A low-complexity policy, UROP (Uniformizing Random Ordered Policy) is proposed, whose near optimality is shown. Numerical examples indicate that under a reasonable-sized battery capacity, UROP uses the arriving energy with almost perfect efficiency. As the problem is a restless multi-armed bandit (RMAB) problem with an average reward criterion, UROP may have a wider application area than communication networks.
Solving Poisson Equation by Genetic Algorithms
Venue: arXiv cs.NE 2014
Year: 2014

This paper deals with a method for solving Poisson Equation (PE) based on genetic algorithms and grammatical evolution. The method forms generations of solutions expressed in an analytical form. Several examples of PE are tested and in most cases the exact solution is recovered. But, when the solution cannot be expressed in an analytical form, our method produces a satisfactory solution with a good level of accuracy
More Algorithms for Provable Dictionary Learning
Venue: arXiv cs.DS 2014
Year: 2014

In dictionary learning, also known as sparse coding, the algorithm is given samples of the form $y = Ax$ where $x\in \mathbb{R}^m$ is an unknown random sparse vector and $A$ is an unknown dictionary matrix in $\mathbb{R}^{n\times m}$ (usually $m > n$, which is the overcomplete case). The goal is to learn $A$ and $x$. This problem has been studied in neuroscience, machine learning, visions, and image processing. In practice it is solved by heuristic algorithms and provable algorithms seemed hard to find. Recently, provable algorithms were found that work if the unknown feature vector $x$ is $\sqrt{n}$-sparse or even sparser. Spielman et al. \cite{DBLP:journals/jmlr/SpielmanWW12} did this for dictionaries where $m=n$; Arora et al. \cite{AGM} gave an algorithm for overcomplete ($m >n$) and incoherent matrices $A$; and Agarwal et al. \cite{DBLP:journals/corr/AgarwalAN13} handled a similar case but with weaker guarantees. This raised the problem of designing provable algorithms that allow sparsity $\gg \sqrt{n}$ in the hidden vector $x$. The current paper designs algorithms that allow sparsity up to $n/poly(\log n)$. It works for a class of matrices where features are individually recoverable, a new notion identified in this paper that may motivate further work. The algorithm runs in quasipolynomial time because they use limited enumeration.
ICT in Local Self Governance: A Study of Rural India
Venue: arXiv cs.CY 2014
Year: 2014

The concept of local self-governance is not new as it has its roots in ancient time even before the era of Mauryan emperors. This paper depicts the journey of local self-governance from antediluvian time to 21st century. Further, in the current scenario Information and Communication Technology (ICT) has emerged as a successful tool for dissemination of various e-governance services and in this regard the Government of India has formulated NeGP with adequate service delivery mechanism. With the inculcation of ICT, various applications were designed by central as well as state governments which lead towards strengthening of PRIs for rural reform. This paper also throws some light on necessity of ICT in self-governance along with some case studies.
Message Encoding for Spread and Orbit Codes
Venue: arXiv cs.IT 2014
Year: 2014

Spread codes and orbit codes are special families of constant dimension subspace codes. These codes have been well-studied for their error correction capability and transmission rate, but the question of how to encode messages has not been investigated. In this work we show how the message space can be chosen for a given code and how message en- and decoding can be done.
Nonuniform Graph Partitioning with Unrelated Weights
Venue: arXiv cs.DS 2014
Year: 2014

We give a bi-criteria approximation algorithm for the Minimum Nonuniform Partitioning problem, recently introduced by Krauthgamer, Naor, Schwartz and Talwar (2014). In this problem, we are given a graph $G=(V,E)$ on $n$ vertices and $k$ numbers $ρ_1,\dots, ρ_k$. The goal is to partition the graph into $k$ disjoint sets $P_1,\dots, P_k$ satisfying $|P_i|\leq ρ_i n$ so as to minimize the number of edges cut by the partition. Our algorithm has an approximation ratio of $O(\sqrt{\log n \log k})$ for general graphs, and an $O(1)$ approximation for graphs with excluded minors. This is an improvement upon the $O(\log n)$ algorithm of Krauthgamer, Naor, Schwartz and Talwar (2014). Our approximation ratio matches the best known ratio for the Minimum (Uniform) $k$-Partitioning problem. We extend our results to the case of "unrelated weights" and to the case of "unrelated $d$-dimensional weights". In the former case, different vertices may have different weights and the weight of a vertex may depend on the set $P_i$ the vertex is assigned to. In the latter case, each vertex $u$ has a $d$-dimensional weight $r(u,i) = (r_1(u,i), \dots, r_d(u,i))$ if $u$ is assigned to $P_i$. Each set $P_i$ has a $d$-dimensional capacity $c(i) = (c_1(i),\dots, c_d(i))$. The goal is to find a partition such that $\sum_{u\in {P_i}} r(u,i) \leq c(i)$ coordinate-wise.
Undecidable properties of self-affine sets and multi-tape automata
Venue: arXiv cs.FL 2014
Year: 2014

We study the decidability of the topological properties of some objects coming from fractal geometry. We prove that having empty interior is undecidable for the sets defined by two-dimensional graph-directed iterated function systems. These results are obtained by studying a particular class of self-affine sets associated with multi-tape automata. We first establish the undecidability of some language-theoretical properties of such automata, which then translate into undecidability results about their associated self-affine sets.
Multimodal Optimization by Sparkling Squid Populations
Venue: arXiv cs.NE 2014
Year: 2014

The swarm intelligence of animals is a natural paradigm to apply to optimization problems. Ant colony, bee colony, firefly and bat algorithms are amongst those that have been demonstrated to efficiently to optimize complex constraints. This paper proposes the new Sparkling Squid Algorithm (SSA) for multimodal optimization, inspired by the intelligent swarm behavior of its namesake. After an introduction, formulation and discussion of its implementation, it will be compared to other popular metaheuristics. Finally, applications to well - known problems such as image registration and the traveling salesperson problem will be discussed.
Maintaining partial sums in logarithmic time
Venue: arXiv cs.DS 2014
Year: 2014

We present a data structure that allows to maintain in logarithmic time all partial sums of elements of a linear array during incremental changes of element's values.
A Class of LTI Distributed Observers for LTI Plants: Necessary and Sufficient Conditions for Stabilizability
Venue: arXiv cs.SY 2014
Year: 2014

Consider that an autonomous linear time-invariant (LTI) plant is given and that a network of LTI observers assesses its output vector. The dissemination of information within the network is dictated by a pre-specified directed graph in which each vertex represents an observer. Each observer computes its own state estimate using only the portion of the output vector accessible to it and the state estimates of other observers that are transmitted to it by its neighbors, according to the graph. This paper proposes an update rule that is a natural generalization of consensus, and for which we determine necessary and sufficient conditions for the existence of parameters for the update rule that lead to asymptotic omniscience of the state of the plant at all observers. The conditions reduce to certain detectability requirements that imply that if omniscience is not possible under the proposed scheme then it is not viable under any other scheme that is subject to the same communication graph, including nonlinear and time-varying ones.
Actions and Events in Concurrent Systems Design
Venue: arXiv cs.SE 2014
Year: 2014

In this work, having in mind the construction of concurrent systems from components, we discuss the difference between actions and events. For this discussion, we propose an(other) architecture description language in which actions and events are made explicit in the description of a component and a system. Our work builds from the ideas set forth by the categorical approach to the construction of software based systems from components advocated by Goguen and Burstall, in the context of institutions, and by Fiadeiro and Maibaum, in the context of temporal logic. In this context, we formalize a notion of a component as an element of an indexed category and we elicit a notion of a morphism between components as morphisms of this category. Moreover, we elaborate on how this formalization captures, in a convenient manner, the underlying structure of a component and the basic interaction mechanisms for putting components together. Further, we advance some ideas on how certain matters related to the openness and the compositionality of a component/system may be described in terms of classes of morphisms, thus potentially supporting a compositional rely/guarantee reasoning.
"Information-Friction" and its implications on minimum energy required for communication
Venue: arXiv cs.IT 2014
Year: 2014

Just as there are frictional losses associated with moving masses on a surface, what if there were frictional losses associated with moving information on a substrate? Indeed, many modes of communication suffer from such frictional losses. We propose to model these losses as proportional to "bit-meters," i.e., the product of mass of information (i.e., the number of bits) and the distance of information transport. We use this "information- friction" model to understand fundamental energy requirements on encoding and decoding in communication circuitry. First, for communication across a binary input AWGN channel, we arrive at fundamental limits on bit-meters (and thus energy consumption) for decoding implementations that have a predetermined input-independent length of messages. For encoding, we relax the fixed-length assumption and derive bounds for flexible-message- length implementations. Using these lower bounds we show that the total (transmit + encoding + decoding) energy-per-bit must diverge to infinity as the target error probability is lowered to zero. Further, the closer the communication rate is maintained to the channel capacity (as the target error-probability is lowered to zero), the faster the required decoding energy diverges to infinity.