OpenRaiser/Intern-Atlas huggingface dataset:
Observers for invariant systems on Lie groups with biased input measurements and homogeneous outputs
Venue: arXiv cs.SY 2015
Year: 2015

This paper provides a new observer design methodology for invariant systems whose state evolves on a Lie group with outputs in a collection of related homogeneous spaces and where the measurement of system input is corrupted by an unknown constant bias. The key contribution of the paper is to study the combined state and input bias estimation problem in the general setting of Lie groups, a question for which only case studies of specific Lie groups are currently available. We show that any candidate observer (with the same state space dimension as the observed system) results in non-autonomous error dynamics, except in the trivial case where the Lie-group is Abelian. This precludes the application of the standard non-linear observer design methodologies available in the literature and leads us to propose a new design methodology based on employing invariant cost functions and general gain mappings. We provide a rigorous and general stability analysis for the case where the underlying Lie group allows a faithful matrix representation. We demonstrate our theory in the example of rigid body pose estimation and show that the proposed approach unifies two competing pose observers published in prior literature.
A Lower Bound on Supporting Predecessor Search in $k$ sorted Arrays
Venue: arXiv cs.DS 2015
Year: 2015

We seek to perform efficient queries for the predecessor among $n$ values stored in $k$ sorted arrays. Evading the $Ω(n \log k)$ lower bound from merging $k$ arrays, we support predecessor queries in $O(\log n)$ time after $O(n \log(\frac{k}{\log n}))$ construction time. By applying Ben-Or's technique, we establish that this is optimal for strict predecessor queries, i.e., every data structure supporting $O(\log n)$-time strict predecessor queries requires $Ω(n \log(\frac{k}{\log n}))$ construction time. Our approach generalizes as a template for deriving similar lower bounds on the construction time of data structures with some desired query time.
Compositional Safety Verification with Max-SMT
Venue: arXiv cs.LO 2015
Year: 2015

We present an automated compositional program verification technique for safety properties based on conditional inductive invariants. For a given program part (e.g., a single loop) and a postcondition $φ$, we show how to, using a Max-SMT solver, an inductive invariant together with a precondition can be synthesized so that the precondition ensures the validity of the invariant and that the invariant implies $φ$. From this, we build a bottom-up program verification framework that propagates preconditions of small program parts as postconditions for preceding program parts. The method recovers from failures to prove the validity of a precondition, using the obtained intermediate results to restrict the search space for further proof attempts. As only small program parts need to be handled at a time, our method is scalable and distributable. The derived conditions can be viewed as implicit contracts between different parts of the program, and thus enable an incremental program analysis.
Complexity and Compilation of GZ-Aggregates in Answer Set Programming
Venue: arXiv cs.AI 2015
Year: 2015

Gelfond and Zhang recently proposed a new stable model semantics based on Vicious Circle Principle in order to improve the interpretation of logic programs with aggregates. The paper focuses on this proposal, and analyzes the complexity of both coherence testing and cautious reasoning under the new semantics. Some surprising results highlight similarities and differences versus mainstream stable model semantics for aggregates. Moreover, the paper reports on the design of compilation techniques for implementing the new semantics on top of existing ASP solvers, which eventually lead to realize a prototype system that allows for experimenting with Gelfond-Zhang's aggregates. To appear in Theory and Practice of Logic Programming (TPLP), Proceedings of ICLP 2015.
Reducing Complexity in Next-Generation MU-MIMO Systems
Venue: arXiv cs.IT 2015
Year: 2015

Recently, several advanced multi-antenna radio communications technologies have emerged to meet the increased capacity demands in wireless multi-user networks. Despite their great potential, the extent of these techniques' practical applicability still remains questionable, since they have to face either backhaul limitations or cost and hardware constraints. In this paper, we propose a new system solution which includes network architecture, antenna technology and radio transmission protocol to reduce drastically the hardware complexity and cost as well as the channel state information / user data feedback requirements of multi-user multi-antenna wireless networks. We focus on the forward link of an interference channel in a cloud radio access network setup wherein an arbitrary number of remote radio heads are each equipped with a single radio frequency module parasitic antenna array and wish to send data to their respective single-antenna user terminals, while co-existing in time and frequency. Base stations select cooperatively the optimal combination of pre-determined beams prior transmission. Our proposed approach is able to achieve the aforementioned goals, while offering significant downlink sum-rate gains due to the available spatial degrees of freedom.
HT-Ring Paxos: Theory of High Throughput State-Machine Replication for Clustered Data Centers
Venue: arXiv cs.DC 2015
Year: 2015

Implementations of state-machine replication (SMR) prevalently use the variants of Paxos. Some of the recent variants of Paxos like, Ring Paxos, Multi-Ring Paxos, S-Paxos and HT-Paxos achieve significantly high throughput. However, to meet the growing demand of high throughput, we are proposing HT-Ring Paxos, a variant of Paxos that is basically derived from the classical Paxos. Moreover, it also adopts some fundamental concepts of Ring Paxos, S-Paxos and HT-Paxos for increasing throughput. Furthermore, HT-Ring Paxos is best suitable for clustered data centers and achieves comparatively high throughput among all variants of Paxos. However, similar to Ring Paxos, latency of the HT-Ring Paxos is quite high as compared with other variants of Paxos.
On the Computability of Solomonoff Induction and Knowledge-Seeking
Venue: arXiv cs.AI 2015
Year: 2015

Solomonoff induction is held as a gold standard for learning, but it is known to be incomputable. We quantify its incomputability by placing various flavors of Solomonoff's prior M in the arithmetical hierarchy. We also derive computability bounds for knowledge-seeking agents, and give a limit-computable weakly asymptotically optimal reinforcement learning agent.
Energy-efficient Traffic Bypassing in LTE HetNets with Mobile Relays
Venue: arXiv cs.NI 2015
Year: 2015

One of the core technologies being standardized by 3GPP for LTE-A is the introduction of Relay Nodes (RNs). RNs are intended for ensuring coverage at cell edges as well as for the provision of enhanced capacity at hot spot areas. An extension to this concept is the Mobile Relay (MR). MRs can be mounted on vehicles and the original idea is to serve users inside high speed trains thus counter fighting the inherent severe fading and vehicle penetration loss. In this work we present a framework for exploiting Mobile Relay (MRs) even at low speeds in urban environments for bypassing traffic from nearby users, either within or outside the vehicles. In particular we show that apart from increased capacity and good quality coverage this approach achieves important energy savings for the mobile terminals.
ALEVS: Active Learning by Statistical Leverage Sampling
Venue: arXiv cs.LG 2015
Year: 2015

Active learning aims to obtain a classifier of high accuracy by using fewer label requests in comparison to passive learning by selecting effective queries. Many active learning methods have been developed in the past two decades, which sample queries based on informativeness or representativeness of unlabeled data points. In this work, we explore a novel querying criterion based on statistical leverage scores. The statistical leverage scores of a row in a matrix are the squared row-norms of the matrix containing its (top) left singular vectors and is a measure of influence of the row on the matrix. Leverage scores have been used for detecting high influential points in regression diagnostics and have been recently shown to be useful for data analysis and randomized low-rank matrix approximation algorithms. We explore how sampling data instances with high statistical leverage scores perform in active learning. Our empirical comparison on several binary classification datasets indicate that querying high leverage points is an effective strategy.
Achievable Rate of Rician Large-Scale MIMO Channels with Transceiver Hardware Impairments
Venue: arXiv cs.IT 2015
Year: 2015

Transceiver hardware impairments (e.g., phase noise, in-phase/quadrature-phase (I/Q) imbalance, amplifier non-linearities, and quantization errors) have obvious degradation effects on the performance of wireless communications. While prior works have improved our knowledge on the influence of hardware impairments of single-user multiple-input multiple-output (MIMO) systems over Rayleigh fading channels, an analysis encompassing the Rician fading channel is not yet available. In this paper, we pursue a detailed analysis of regular and large-scale (LS) MIMO systems over Rician fading channels by deriving new, closed-form expressions for the achievable rate to provide several important insights for practical system design. More specifically, for regular MIMO systems with hardware impairments, there is always a finite achievable rate ceiling, which is irrespective of the transmit power and fading conditions. For LS-MIMO systems, it is interesting to find that the achievable rate loss depends on the Rician $K$-factor, which reveals that the favorable propagation in LS-MIMO systems can remove the influence of hardware impairments. However, we show that the non-ideal LS-MIMO system can still achieve high spectral efficiency due to its huge degrees of freedom.
Learning Action Models: Qualitative Approach
Venue: arXiv cs.LG 2015
Year: 2015

In dynamic epistemic logic, actions are described using action models. In this paper we introduce a framework for studying learnability of action models from observations. We present first results concerning propositional action models. First we check two basic learnability criteria: finite identifiability (conclusively inferring the appropriate action model in finite time) and identifiability in the limit (inconclusive convergence to the right action model). We show that deterministic actions are finitely identifiable, while non-deterministic actions require more learning power-they are identifiable in the limit. We then move on to a particular learning method, which proceeds via restriction of a space of events within a learning-specific action model. This way of learning closely resembles the well-known update method from dynamic epistemic logic. We introduce several different learning methods suited for finite identifiability of particular types of deterministic actions.
Sub-exponential Approximation Schemes for CSPs: from Dense to Almost Sparse
Venue: arXiv cs.CC 2015
Year: 2015

It has long been known, since the classical work of (Arora, Karger, Karpinski, JCSS~99), that \MC\ admits a PTAS on dense graphs, and more generally, \kCSP\ admits a PTAS on "dense" instances with $Ω(n^k)$ constraints. In this paper we extend and generalize their exhaustive sampling approach, presenting a framework for $(1-\eps)$-approximating any \kCSP\ problem in \emph{sub-exponential} time while significantly relaxing the denseness requirement on the input instance. Specifically, we prove that for any constants $δ\in (0, 1]$ and $\eps > 0$, we can approximate \kCSP\ problems with $Ω(n^{k-1+δ})$ constraints within a factor of $(1-\eps)$ in time $2^{O(n^{1-δ}\ln n /\eps^3)}$. The framework is quite general and includes classical optimization problems, such as \MC, {\sc Max}-DICUT, \kSAT, and (with a slight extension) $k$-{\sc Densest Subgraph}, as special cases. For \MC\ in particular (where $k=2$), it gives an approximation scheme that runs in time sub-exponential in $n$ even for "almost-sparse" instances (graphs with $n^{1+δ}$ edges). We prove that our results are essentially best possible, assuming the ETH. First, the density requirement cannot be relaxed further: there exists a constant $r < 1$ such that for all $δ> 0$, \kSAT\ instances with $O(n^{k-1})$ clauses cannot be approximated within a ratio better than $r$ in time $2^{O(n^{1-δ})}$. Second, the running time of our algorithm is almost tight \emph{for all densities}. Even for \MC\ there exists $r<1$ such that for all $δ' > δ>0$, \MC\ instances with $n^{1+δ}$ edges cannot be approximated within a ratio better than $r$ in time $2^{n^{1-δ'}}$.
Time-triggered smart transducer networks
Venue: arXiv cs.NI 2015
Year: 2015

The time-triggered approach is a well-suited approach for building distributed hard real-time systems. Since many applications of transducer networks have real-time requirements, a time-triggered communication interface for smart transducers is desirable, however such a time-triggered interface must still support features for monitoring, maintenance, plug-and-play, etc. The approach of the OMG Smart Transducer Interface consists of clusters of time-triggered smart transducer nodes that contain special interfaces supporting configuration, diagnostics, and maintenance without affecting the deterministic real-time communication. This paper discusses the applicability of the time-triggered approach for smart transducer networks and presents a case study application of a time-triggered smart transducer network.
A quadrilateral 'mini' finite element for the Stokes problem using a single bubble function
Venue: arXiv cs.NA 2015
Year: 2015

We consider a quadrilateral 'mini' finite element for approximating the solution of Stokes equations using a quadrilateral mesh. We use the standard bilinear finite element space enriched with element-wise defined bubble functions for the velocity and the standard bilinear finite element space for the pressure space. With a simple modification of the standard bubble function we show that a single bubble function is sufficient to ensure the inf-sup condition. We have thus improved an earlier result on the quadrilateral 'mini' element, where more than one bubble function are used to get the stability.
Coded Index Modulation for Non-DC-Biased OFDM in Multiple LED Visible Light Communication
Venue: arXiv cs.IT 2015
Year: 2015

Use of multiple light emitting diodes (LED) is an attractive way to increase spectral efficiency in visible light communications (VLC). A non-DC-biased OFDM (NDC OFDM) scheme that uses two LEDs has been proposed in the literature recently. NDC OFDM has been shown to perform better than other OFDM schemes for VLC like DC-biased OFDM (DCO OFDM) and asymmetrically clipped OFDM (ACO OFDM) in multiple LEDs settings. In this paper, we propose an efficient multiple LED OFDM scheme for VLC which uses {\em coded index modulation}. The proposed scheme uses two transmitter blocks, each having a pair of LEDs. Within each block, NDC OFDM signaling is done. The selection of which block is activated in a signaling interval is decided by information bits (i.e., index bits). In order to improve the reliability of the index bits at the receiver (which is critical because of high channel correlation in multiple LEDs settings), we propose to use coding on the index bits alone. We call the proposed scheme as CI-NDC OFDM (coded index NDC OFDM) scheme. Simulation results show that, for the same spectral efficiency, CI-NDC OFDM that uses LDPC coding on the index bits performs better than NDC OFDM.
Exploratory topic modeling with distributional semantics
Venue: arXiv cs.IR 2015
Year: 2015

As we continue to collect and store textual data in a multitude of domains, we are regularly confronted with material whose largely unknown thematic structure we want to uncover. With unsupervised, exploratory analysis, no prior knowledge about the content is required and highly open-ended tasks can be supported. In the past few years, probabilistic topic modeling has emerged as a popular approach to this problem. Nevertheless, the representation of the latent topics as aggregations of semi-coherent terms limits their interpretability and level of detail. This paper presents an alternative approach to topic modeling that maps topics as a network for exploration, based on distributional semantics using learned word vectors. From the granular level of terms and their semantic similarity relations global topic structures emerge as clustered regions and gradients of concepts. Moreover, the paper discusses the visual interactive representation of the topic map, which plays an important role in supporting its exploration.
RBIR Based on Signature Graph
Venue: arXiv cs.CV 2015
Year: 2015

This paper approaches the image retrieval system on the base of visual features local region RBIR (region-based image retrieval). First of all, the paper presents a method for extracting the interest points based on Harris-Laplace to create the feature region of the image. Next, in order to reduce the storage space and speed up query image, the paper builds the binary signature structure to describe the visual content of image. Based on the image's binary signature, the paper builds the SG (signature graph) to classify and store image's binary signatures. Since then, the paper builds the image retrieval algorithm on SG through the similar measure EMD (earth mover's distance) between the image's binary signatures. Last but not least, the paper gives an image retrieval model RBIR, experiments and assesses the image retrieval method on Corel image database over 10,000 images.
Analysis of the South Slavic Scripts by Run-Length Features of the Image Texture
Venue: arXiv cs.CV 2015
Year: 2015

The paper proposes an algorithm for the script recognition based on the texture characteristics. The image texture is achieved by coding each letter with the equivalent script type (number code) according to its position in the text line. Each code is transformed into equivalent gray level pixel creating an 1-D image. Then, the image texture is subjected to the run-length analysis. This analysis extracts the run-length features, which are classified to make a distinction between the scripts under consideration. In the experiment, a custom oriented database is subject to the proposed algorithm. The database consists of some text documents written in Cyrillic, Latin and Glagolitic scripts. Furthermore, it is divided into training and test parts. The results of the experiment show that 3 out of 5 run-length features can be used for effective differentiation between the analyzed South Slavic scripts.
Election algorithms with random delays in trees
Venue: arXiv cs.DC 2015
Year: 2015

The election is a classical problem in distributed algorithmic. It aims to design and to analyze a distributed algorithm choosing a node in a graph, here, in a tree. In this paper, a class of randomized algorithms for the election is studied. The election amounts to removing leaves one by one until the tree is reduced to a unique node which is then elected. The algorithm assigns to each leaf a probability distribution (that may depends on the information transmitted by the eliminated nodes) used by the leaf to generate its remaining random lifetime. In the general case, the probability of each node to be elected is given. For two categories of algorithms, close formulas are provided.
Energy-based Modulation for Noncoherent Massive SIMO Systems
Venue: arXiv cs.IT 2015
Year: 2015

An uplink system with a single antenna transmitter and a single receiver with a large number of antennas is considered. We propose an energy-detection-based single-shot noncoherent communication scheme which does not use the instantaneous channel state information (CSI), but rather only the knowledge of the channel statistics. The suggested system uses a transmitter that modulates information on the power of the symbols, and a receiver which measures only the average energy across the antennas. We propose constellation designs which are asymptotically optimal with respect to symbol error rate (SER) with an increasing number of antennas, for any finite signal to noise ratio (SNR) at the receiver, under different assumptions on the availability of CSI statistics (exact channel fading distribution or the first few moments of the channel fading distribution). We also consider the case of imperfect knowledge of the channel statistics and describe in detail the case when there is a bounded uncertainty on the moments of the fading distribution. We present numerical results on the SER performance achieved by these designs in typical scenarios and find that they may outperform existing noncoherent constellations, e.g., conventional Amplitude Shift Keying (ASK), and pilot-based schemes, e.g., Pulse Amplitude Modulation (PAM). We also observe that an optimized constellation for a specific channel distribution makes it very sensitive to uncertainties in the channel statistics. In particular, constellation designs based on optimistic channel conditions could lead to significant performance degradation in terms of the achieved symbol error rates.
Deterministic hierarchical networks
Venue: arXiv cs.SI 2015
Year: 2015

It has been shown that many networks associated with complex systems are small-world (they have both a large local clustering coefficient and a small diameter) and they are also scale-free (the degrees are distributed according to a power law). Moreover, these networks are very often hierarchical, as they describe the modularity of the systems that are modeled. Most of the studies for complex networks are based on stochastic methods. However, a deterministic method, with an exact determination of the main relevant parameters of the networks, has proven useful. Indeed, this approach complements and enhances the probabilistic and simulation techniques and, therefore, it provides a better understanding of the systems modeled. In this paper we find the radius, diameter, clustering coefficient and degree distribution of a generic family of deterministic hierarchical small-world scale-free networks that has been considered for modeling real-life complex systems.
A theory of probabilistic automata, part 1
Venue: arXiv cs.FL 2015
Year: 2015

In the book we present main concepts of probabilistic automata theory.
Geometric approach to the MacWilliams Extension Theorem for codes over modules
Venue: arXiv cs.IT 2015
Year: 2015

The MacWilliams Extension Theorem states that each linear Hamming isometry of a linear code extends to a monomial map. In this paper an analogue of the extension theorem for linear codes over a module alphabet is observed. A geometric approach to the extendability of isometries is described. For a matrix module alphabet we found the minimum length of a code for which an unextendable Hamming isometry exists. We also proved an extension theorem for MDS codes over a module alphabet.
Data Hiding in Video using Triangularization LSB Technique
Venue: arXiv cs.MM 2015
Year: 2015

The importance of data hiding in the field of Information Technology is a widely accepted. The challenge is to be able to pass information in a manner that the very existence of the message is unknown in order to repel attention of the potential attacker. Steganography is a technique that has been widely used to achieve this objective. However Steganography is often found to be lacking when it comes to hiding bulk data. Attempting to hide data in a video overcomes this problem because of the large sized cover object (video) as compared to an image in the case of steganography. This paper attempts to propose a scheme using which data can be hidden in a video. We focus on the Triangularization method and make use of the Least Significant Bit (LSB) technique in hiding messages in a video.