OpenRaiser/Intern-Atlas huggingface dataset:
Phase-Noise Mitigation in OFDM by Best Match Trajectories
Venue: arXiv cs.IT 2015
Year: 2015

This paper proposes a novel approach to phase-noise compensation. The basic idea is to approximate the phase-noise statistics by a finite number of realizations, i.e., a phase-noise codebook. The receiver then uses an augmented received signal model, where the codebook index is estimated along with other parameters. The realization of the basic idea depends on the details of the air interface, the phase-noise statistics, the propagation scenario and the computational constraints. In this paper, we will focus on a MQAM-OFDM system with pilot sub-carriers within each OFDM symbol. The channel is frequency selective, fading and unknown. A decision-feedback method is employed to further enhance performance of the system. Simulation results are shown for uncoded and coded systems to illustrate the performance of the algorithm, which is also compared with previously employed methods. Our simulations show that for a 16-QAM coded OFDM system over a frequency selective Rayleigh fading channel affected by phase noise with root-mean-square (RMS) of 14.4 degrees per OFDM symbol, the proposed algorithm is 1.5dB from the ideal phase-noise free case at a BER of $10^{-4}$. The performance of the best reference scheme is 2.5dB from the ideal case at BER of $10^{-4}$. The proposed scheme is also computationally attractive.
Embedding AC Power Flow with Voltage Control in the Complex Plane : The Case of Analytic Continuation via Padé Approximants
Venue: arXiv cs.SY 2015
Year: 2015

This paper proposes a method to embed the AC power flow problem with voltage magnitude constraints in the complex plane. Modeling the action of network controllers that regulate the magnitude of voltage phasors is a challenging task in the complex plane as it has to preserve the framework of holomorphicity for obtention of these complex variables with fixed magnitude. Hence this paper presents a significant step in the development of the idea of Holomorphic Embedding Load Flow Method (HELM), introduced in 2012, that exploits the theory of analytic continuation, especially the monodromy theorem for resolving issues that have plagued conventional numerical methods for decades. This paper also illustrates the indispensable role of Padé approximants for analytic continuation of complex functions, expressed as power series, beyond the boundary of convergence of the series. Later the paper demonstrates the superiority of the proposed method over the well-established Newton-Raphson as well as the recently developed semidefinite and moment relaxation of power flow problems.
Maximum entropy properties of discrete-time first-order stable spline kernel
Venue: arXiv cs.SY 2015
Year: 2015

The first order stable spline (SS-1) kernel is used extensively in regularized system identification. In particular, the stable spline estimator models the impulse response as a zero-mean Gaussian process whose covariance is given by the SS-1 kernel. In this paper, we discuss the maximum entropy properties of this prior. In particular, we formulate the exact maximum entropy problem solved by the SS-1 kernel without Gaussian and uniform sampling assumptions. Under general sampling schemes, we also explicitly derive the special structure underlying the SS-1 kernel (e.g. characterizing the tridiagonal nature of its inverse), also giving to it a maximum entropy covariance completion interpretation. Along the way similar maximum entropy properties of the Wiener kernel are also given.
Wiggins: Detecting Valuable Information in Dynamic Networks Using Limited Resources
Venue: arXiv cs.SI 2015
Year: 2015

Detecting new information and events in a dynamic network by probing individual nodes has many practical applications: discovering new webpages, analyzing influence properties in network, and detecting failure propagation in electronic circuits or infections in public drinkable water systems. In practice, it is infeasible for anyone but the owner of the network (if existent) to monitor all nodes at all times. In this work we study the constrained setting when the observer can only probe a small set of nodes at each time step to check whether new pieces of information (items) have reached those nodes. We formally define the problem through an infinite time generating process that places new items in subsets of nodes according to an unknown probability distribution. Items have an exponentially decaying novelty, modeling their decreasing value. The observer uses a probing schedule (i.e., a probability distribution over the set of nodes) to choose, at each time step, a small set of nodes to check for new items. The goal is to compute a schedule that minimizes the average novelty of undetected items. We present an algorithm, WIGGINS, to compute the optimal schedule through convex optimization, and then show how it can be adapted when the parameters of the problem must be learned or change over time. We also present a scalable variant of WIGGINS for the MapReduce framework. The results of our experimental evaluation on real social networks demonstrate the practicality of our approach.
The Algorithm of Pipelined Gossiping
Venue: arXiv cs.DC 2015
Year: 2015

A family of gossiping algorithms depending on a parameter permutation is introduced, formalized, and discussed. Several of its members are analyzed and their asymptotic behaviour is revealed, including a member whose model and performance closely follows the one of hardware pipelined processors. This similarity is exposed. An optimizing algorithm is finally proposed and discussed as a general strategy to increase the performance of the base algorithms.
Multiple Measurements and Joint Dimensionality Reduction for Large Scale Image Search with Short Vectors - Extended Version
Venue: arXiv cs.CV 2015
Year: 2015

This paper addresses the construction of a short-vector (128D) image representation for large-scale image and particular object retrieval. In particular, the method of joint dimensionality reduction of multiple vocabularies is considered. We study a variety of vocabulary generation techniques: different k-means initializations, different descriptor transformations, different measurement regions for descriptor extraction. Our extensive evaluation shows that different combinations of vocabularies, each partitioning the descriptor space in a different yet complementary manner, results in a significant performance improvement, which exceeds the state-of-the-art.
Preprint Imagining In-Air Interaction for Hemiplegia Sufferer
Venue: arXiv cs.HC 2015
Year: 2015

This is the preprint version of our paper on 2015 International Conference on Virtual Rehabilitation (ICVR2015). In this paper, we described the imagination scenarios of a touch-less interaction technology for hemiplegia, which can support either hand or foot interaction with the smartphone or head mounted device (HMD). The computer vision interaction technology is implemented in our previous work, which provides a core support for gesture interaction by accurately detecting and tracking the hand or foot gesture. The patients interact with the application using hand/foot gesture motion in the camera view.
Tight Bounds on Low-degree Spectral Concentration of Submodular and XOS functions
Venue: arXiv cs.DS 2015
Year: 2015

Submodular and fractionally subadditive (or equivalently XOS) functions play a fundamental role in combinatorial optimization, algorithmic game theory and machine learning. Motivated by learnability of these classes of functions from random examples, we consider the question of how well such functions can be approximated by low-degree polynomials in $\ell_2$ norm over the uniform distribution. This question is equivalent to understanding of the concentration of Fourier weight on low-degree coefficients, a central concept in Fourier analysis. We show that 1. For any submodular function $f:\{0,1\}^n \rightarrow [0,1]$, there is a polynomial of degree $O(\log (1/ε) / ε^{4/5})$ approximating $f$ within $ε$ in $\ell_2$, and there is a submodular function that requires degree $Ω(1/ε^{4/5})$. 2. For any XOS function $f:\{0,1\}^n \rightarrow [0,1]$, there is a polynomial of degree $O(1/ε)$ and there exists an XOS function that requires degree $Ω(1/ε)$. This improves on previous approaches that all showed an upper bound of $O(1/ε^2)$ for submodular and XOS functions. The best previous lower bound was $Ω(1/ε^{2/3})$ for monotone submodular functions. Our techniques reveal new structural properties of submodular and XOS functions and the upper bounds lead to nearly optimal PAC learning algorithms for these classes of functions.
Coherent branching feature bisimulation
Venue: arXiv cs.LO 2015
Year: 2015

Progress in the behavioral analysis of software product lines at the family level benefits from further development of the underlying semantical theory. Here, we propose a behavioral equivalence for feature transition systems (FTS) generalizing branching bisimulation for labeled transition systems (LTS). We prove that branching feature bisimulation for an FTS of a family of products coincides with branching bisimulation for the LTS projection of each the individual products. For a restricted notion of coherent branching feature bisimulation we furthermore present a minimization algorithm and show its correctness. Although the minimization problem for coherent branching feature bisimulation is shown to be intractable, application of the algorithm in the setting of a small case study results in a significant speed-up of model checking of behavioral properties.
Handshaking Protocol for Distributed Implementation of Reo
Venue: arXiv cs.DC 2015
Year: 2015

Reo, an exogenous channel-based coordination language, is a model for service coordination wherein services communicate through connectors formed by joining binary communication channels. In order to establish transactional communication among services as prescribed by connector semantics, distributed ports exchange handshaking messages signalling which parties are ready to provide or consume data. In this paper, we present a formal implementation model for distributed Reo with communication delays and outline ideas for its proof of correctness. To reason about Reo implementation formally, we introduce Timed Action Constraint Automata (TACA) and explain how to compare TACA with existing automata-based semantics for Reo. We use TACA to describe handshaking behavior of Reo modeling primitives and argue that in any distributed circuit remote Reo nodes and channels exposing such behavior commit to perform transitions envisaged by the network semantics.
Inferring Unusual Crowd Events From Mobile Phone Call Detail Records
Venue: arXiv cs.SI 2015
Year: 2015

The pervasiveness and availability of mobile phone data offer the opportunity of discovering usable knowledge about crowd behaviors in urban environments. Cities can leverage such knowledge in order to provide better services (e.g., public transport planning, optimized resource allocation) and safer cities. Call Detail Record (CDR) data represents a practical data source to detect and monitor unusual events considering the high level of mobile phone penetration, compared with GPS equipped and open devices. In this paper, we provide a methodology that is able to detect unusual events from CDR data that typically has low accuracy in terms of space and time resolution. Moreover, we introduce a concept of unusual event that involves a large amount of people who expose an unusual mobility behavior. Our careful consideration of the issues that come from coarse-grained CDR data ultimately leads to a completely general framework that can detect unusual crowd events from CDR data effectively and efficiently. Through extensive experiments on real-world CDR data for a large city in Africa, we demonstrate that our method can detect unusual events with 16% higher recall and over 10 times higher precision, compared to state-of-the-art methods. We implement a visual analytics prototype system to help end users analyze detected unusual crowd events to best suit different application scenarios. To the best of our knowledge, this is the first work on the detection of unusual events from CDR data with considerations of its temporal and spatial sparseness and distinction between user unusual activities and daily routines.
Coloring Graphs having Few Colorings over Path Decompositions
Venue: arXiv cs.DS 2015
Year: 2015

Lokshtanov, Marx, and Saurabh SODA 2011 proved that there is no $(k-ε)^{\operatorname{pw}(G)}\operatorname{poly}(n)$ time algorithm for deciding if an $n$-vertex graph $G$ with pathwidth $\operatorname{pw}(G)$ admits a proper vertex coloring with $k$ colors unless the Strong Exponential Time Hypothesis (SETH) is false. We show here that nevertheless, when $k>\lfloor Δ/2 \rfloor + 1$, where $Δ$ is the maximum degree in the graph $G$, there is a better algorithm, at least when there are few colorings. We present a Monte Carlo algorithm that given a graph $G$ along with a path decomposition of $G$ with pathwidth $\operatorname{pw}(G)$ runs in $(\lfloor Δ/2 \rfloor + 1)^{\operatorname{pw}(G)}\operatorname{poly}(n)s$ time, that distinguishes between $k$-colorable graphs having at most $s$ proper $k$-colorings and non-$k$-colorable graphs. We also show how to obtain a $k$-coloring in the same asymptotic running time. Our algorithm avoids violating SETH for one since high degree vertices still cost too much and the mentioned hardness construction uses a lot of them. We exploit a new variation of the famous Alon--Tarsi theorem that has an algorithmic advantage over the original form. The original theorem shows a graph has an orientation with outdegree less than $k$ at every vertex, with a different number of odd and even Eulerian subgraphs only if the graph is $k$-colorable, but there is no known way of efficiently finding such an orientation. Our new form shows that if we instead count another difference of even and odd subgraphs meeting modular degree constraints at every vertex picked uniformly at random, we have a fair chance of getting a non-zero value if the graph has few $k$-colorings. Yet every non-$k$-colorable graph gives a zero difference, so a random set of constraints stands a good chance of being useful for separating the two cases.
Multi-Sequential Word Relations
Venue: arXiv cs.FL 2015
Year: 2015

Rational relations are binary relations of finite words that are realised by non-deterministic finite state transducers (NFT). A particular kind of rational relations is the sequential functions. Sequential functions are the functions that can be realised by input-deterministic transducers. Some rational functions are not sequential. However, based on a property on transducers called the twinning property, it is decidable in PTime whether a rational function given by an NFT is sequential. In this paper, we investigate the generalisation of this result to multi-sequential relations, i.e. relations that are equal to a finite union of sequential functions. We show that given an NFT, it is decidable in PTime whether the relation it defines is multi-sequential, based on a property called the weak twinning property. If the weak twinning property is satisfied, we give a procedure that effectively constructs a finite set of input-deterministic transducers whose union defines the relation. This procedure generalises to arbitrary NFT the determinisation procedure of functional NFT.
Promote the Industry Standard of Smart Home in China by Intelligent Router Technology
Venue: arXiv cs.NI 2015
Year: 2015

The reason why smart home remains not popularized lies in bad product user experience, purchasing cost, and compatibility, and a lack of industry standard[1]. Echoing problems above, and having relentless devoted to software and hardware innovation and practice, we have independently developed a set of solution which is based on innovation and integration of router technology, mobile Internet technology,Internet of things technology,communication technology, digital-to-analog conversion and codec technology, and P2P technology among others. We have also established relevant protocols (without the application of protocols abroad). By doing this, we managed to establish a system with low and moderate price, superior performance, all-inclusive functions, easy installation, convenient portability, real-time reliability, security encryption, and the capability to manage home furnitures in an intelligent way. Only a new smart home system like this can inject new idea and energy into smart home industry and thus vigorously promote the establishment of smart home industry standard.
Nash Equilibria And Partition Functions Of Games With Many Dependent Players
Venue: arXiv cs.GT 2015
Year: 2015

We discuss and solve a model for a game with many players, where a subset of truely deciding players is embedded into a hierarchy of dependent agents. These interdependencies modify the game matrix and the Nash equilibria for the deciding players. In a concrete example, we recognize the partition function of the Ising model and for high dependency we observe a phase transition to a new Nash equilibrium, which is the Pareto-efficient outcome. An example we have in mind is the game theory for major shareholders in a stock market, where intermediate companies decide according to a majority vote of their owners and compete for the final profit. In our model, these interdependency eventually forces cooperation.
Self-similar Magneto-electric Nanocircuit Technology for Probabilistic Inference Engines
Venue: arXiv cs.ET 2015
Year: 2015

Probabilistic graphical models are powerful mathematical formalisms for machine learning and reasoning under uncertainty that are widely used for cognitive computing. However they cannot be employed efficiently for large problems (with variables in the order of 100K or larger) on conventional systems, due to inefficiencies resulting from layers of abstraction and separation of logic and memory in CMOS implementations. In this paper, we present a magneto-electric probabilistic technology framework for implementing probabilistic reasoning functions. The technology leverages Straintronic Magneto-Tunneling Junction (S-MTJ) devices in a novel mixed-signal circuit framework for direct computations on probabilities while enabling in-memory computations with persistence. Initial evaluations of the Bayesian likelihood estimation operation occurring during Bayesian Network inference indicate up to 127x lower area, 214x lower active power, and 70x lower latency compared to an equivalent 45nm CMOS Boolean implementation.
Synchronization over $Z_2$ and community detection in multiplex signed networks with constraints
Venue: arXiv cs.SI 2015
Year: 2015

Finding group elements from noisy measurements of their pairwise ratios is also known as the group synchronization problem, first introduced in the context of the group SO(2) of planar rotations, whose usefulness has been demonstrated recently in engineering and structural biology. Here, we focus on synchronization over $\mathbb{Z}_2$, and consider the problem of identifying communities in a multiplex network when the interaction between the nodes is described by a signed (possibly weighted) measure of similarity, and when the multiplex network has a natural partition into two communities. When one has the additional information that certain subsets of nodes represent the same unknown group element, we consider and compare several algorithms based on spectral, semidefinite programming (SDP) and message passing algorithms. In other words, all nodes within such a subset represent the same unknown group element, and one has available noisy pairwise measurements between pairs of nodes that belong to different non-overlapping subsets. Following a recent analysis of the eigenvector method for synchronization over SO(2), we analyze the robustness to noise of the eigenvector method for synchronization over $\mathbb{Z}_2$, when the underlying graph of pairwise measurements is the Erdős-Rényi random graph, using results from the random matrix theory literature. We also propose a message passing synchronization algorithm that outperforms the existing eigenvector synchronization algorithm only for certain classes of graphs and noise models, and enjoys the flexibility of incorporating constraints that may not be easily accommodated by other spectral or SDP-based methods. We apply our methods both to several synthetic models and a real data set of roll call voting patterns in the U.S. Congress across time, to identify the two existing communities, i.e., the Democratic and Republican parties.
Power Aware Wireless File Downloading: A Lyapunov Indexing Approach to A Constrained Restless Bandit Problem
Venue: arXiv cs.PF 2015
Year: 2015

This paper treats power-aware throughput maxi-mization in a multi-user file downloading system. Each user can receive a new file only after its previous file is finished. The file state processes for each user act as coupled Markov chains that form a generalized restless bandit system. First, an optimal algorithm is derived for the case of one user. The algorithm maximizes throughput subject to an average power constraint. Next, the one-user algorithm is extended to a low complexity heuristic for the multi-user problem. The heuristic uses a simple online index policy. In a special case with no power-constraint, the multi-user heuristic is shown to be throughput optimal. Simulations are used to demonstrate effectiveness of the heuristic in the general case. For simple cases where the optimal solution can be computed offline, the heuristic is shown to be near-optimal for a wide range of parameters.
Switching Control for Parameter Identifiability of Uncertain Systems
Venue: arXiv cs.SY 2015
Year: 2015

This paper considers the problem of identifying the parameters of an uncertain linear system by means of feedback control. The problem is approached by considering time-varying controllers. It is shown that even when the uncertainty set is not finite, parameter identifiability can be generically ensured by switching among a finite number of linear time-invariant controllers. The results are shown to have several implications, ranging from fault detection and isolation to adaptive and supervisory control. Practical aspects of the problem are also discussed in details.
Full-Duplex MIMO Small-Cell Networks: Performance Analysis
Venue: arXiv cs.IT 2015
Year: 2015

Full-duplex small-cell relays with multiple antennas constitute a core element of the envisioned 5G network architecture. In this paper, we use stochastic geometry to analyze the performance of wireless networks with full-duplex multiple-antenna small cells, with particular emphasis on the probability of successful transmission. To achieve this goal, we additionally characterize the distribution of the self-interference power of the full-duplex nodes. The proposed framework reveals useful insights on the benefits of full-duplex with respect to half-duplex in terms of network throughput.