OpenRaiser/Intern-Atlas huggingface dataset:
Transceiver Design for Clustered Wireless Sensor Networks --- Towards SNR Maximization
Venue: arXiv cs.IT 2015
Year: 2015

This paper investigates the transceiver design problem in a noisy-sensing noisy-transmission multi-input multi-output (MIMO) wireless sensor network. Consider a cluster-based network, where multiple sensors scattering across several clusters will first send their noisy observations to their respective cluster-heads (CH), who will then forward the data to one common fusion center (FC). The cluster-heads and the fusion center collectively form a coherent-sum multiple access channel (MAC) that is affected by fading and additive noise. Our goal is to jointly design the linear transceivers at the CHs and the FC to maximize the signal-to-noise ratio (SNR) of the recovered signal. We develop three iterative block coordinated ascent (BCA) algorithms: 2-block BCA based on semidefinite relaxation (SDR) and rank reduction via randomization or solving linear equations, 2-block BCA based on iterative second-order cone programming (SOCP), and multi-block BCA that lends itself to efficient closed-form solutions in specific but important scenarios. We show that all of these methods optimize SNR very well but each has different efficiency characteristics that are tailored for different network setups. Convergence analysis is carried out and extensive numerical results are presented to confirm our findings.
Big Data Small Data, In Domain Out-of Domain, Known Word Unknown Word: The Impact of Word Representation on Sequence Labelling Tasks
Venue: arXiv cs.CL 2015
Year: 2015

Word embeddings -- distributed word representations that can be learned from unlabelled data -- have been shown to have high utility in many natural language processing applications. In this paper, we perform an extrinsic evaluation of five popular word embedding methods in the context of four sequence labelling tasks: POS-tagging, syntactic chunking, NER and MWE identification. A particular focus of the paper is analysing the effects of task-based updating of word representations. We show that when using word embeddings as features, as few as several hundred training instances are sufficient to achieve competitive results, and that word embeddings lead to improvements over OOV words and out of domain. Perhaps more surprisingly, our results indicate there is little difference between the different word embedding methods, and that simple Brown clusters are often competitive with word embeddings across all tasks we consider.
k-anonymous Microdata Release via Post Randomisation Method
Venue: arXiv cs.CR 2015
Year: 2015

The problem of the release of anonymized microdata is an important topic in the fields of statistical disclosure control (SDC) and privacy preserving data publishing (PPDP), and yet it remains sufficiently unsolved. In these research fields, k-anonymity has been widely studied as an anonymity notion for mainly deterministic anonymization algorithms, and some probabilistic relaxations have been developed. However, they are not sufficient due to their limitations, i.e., being weaker than the original k-anonymity or requiring strong parametric assumptions. First we propose Pk-anonymity, a new probabilistic k-anonymity, and prove that Pk-anonymity is a mathematical extension of k-anonymity rather than a relaxation. Furthermore, Pk-anonymity requires no parametric assumptions. This property has a significant meaning in the viewpoint that it enables us to compare privacy levels of probabilistic microdata release algorithms with deterministic ones. Second, we apply Pk-anonymity to the post randomization method (PRAM), which is an SDC algorithm based on randomization. PRAM is proven to satisfy Pk-anonymity in a controlled way, i.e, one can control PRAM's parameter so that Pk-anonymity is satisfied. On the other hand, PRAM is also known to satisfy ${\varepsilon}$-differential privacy, a recent popular and strong privacy notion. This fact means that our results significantly enhance PRAM since it implies the satisfaction of both important notions: k-anonymity and ${\varepsilon}$-differential privacy.
Adaptive Compressive Tracking via Online Vector Boosting Feature Selection
Venue: arXiv cs.CV 2015
Year: 2015

Recently, the compressive tracking (CT) method has attracted much attention due to its high efficiency, but it cannot well deal with the large scale target appearance variations due to its data-independent random projection matrix that results in less discriminative features. To address this issue, in this paper we propose an adaptive CT approach, which selects the most discriminative features to design an effective appearance model. Our method significantly improves CT in three aspects: Firstly, the most discriminative features are selected via an online vector boosting method. Secondly, the object representation is updated in an effective online manner, which preserves the stable features while filtering out the noisy ones. Finally, a simple and effective trajectory rectification approach is adopted that can make the estimated location more accurate. Extensive experiments on the CVPR2013 tracking benchmark demonstrate the superior performance of our algorithm compared over state-of-the-art tracking algorithms.
An information diffusion Fano inequality
Venue: arXiv cs.IT 2015
Year: 2015

In this note, we present an information diffusion inequality derived from an elementary argument, which gives rise to a very general Fano-type inequality. The latter unifies and generalizes the distance-based Fano inequality and the continuous Fano inequality established in [Corollary 1, Propositions 1 and 2, arXiv:1311.2669v2], as well as the generalized Fano inequality in [Equation following (10); T. S. Han and S. Verdú. Generalizing the Fano inequality. IEEE Transactions on Information Theory, 40(4):1247-1251, July 1994].
DoF-Delay Trade-Off for the $K$-user MIMO Interference Channel With Delayed CSIT
Venue: arXiv cs.IT 2015
Year: 2015

The degrees of freedom (DoF) of the $K$-user multiple-input multiple-output (MIMO) interference channel are studied when perfect, but delayed channel state information is available at the transmitter side (delayed CSIT). Recent works have proposed schemes that achieve increasing DoF values, but at the cost of long communication delays. This work proposes three linear precoding strategies, formulated in such a way that the achievable DoF can be derived as a function of the transmission delay, thus elucidating its achievable DoF-delay trade-off. All strategies are based on the concept of interference alignment, and built upon three main ingredients: delayed CSIT precoding, user scheduling, and redundancy transmission. In this respect, the interference alignment is realized by exploiting delayed CSIT in order to align the interference at the non-intended receivers along the space-time domain. Finally, the latter part of this work settles that all the proposed strategies work also for constant channels, except for SISO. In such a case, the schemes can be made feasible by resorting to asymmetric complex signaling concepts. This conclusion removes the time-varying channels assumption unnecessarily common along all the literature on delayed CSIT.
Online Learning Algorithm for Time Series Forecasting Suitable for Low Cost Wireless Sensor Networks Nodes
Venue: arXiv cs.NI 2015
Year: 2015

Time series forecasting is an important predictive methodology which can be applied to a wide range of problems. Particularly, forecasting the indoor temperature permits an improved utilization of the HVAC (Heating, Ventilating and Air Conditioning) systems in a home and thus a better energy efficiency. With such purpose the paper describes how to implement an Artificial Neural Network (ANN) algorithm in a low cost system-on-chip to develop an autonomous intelligent wireless sensor network. The present paper uses a Wireless Sensor Networks (WSN) to monitor and forecast the indoor temperature in a smart home, based on low resources and cost microcontroller technology as the 8051MCU. An on-line learning approach, based on Back-Propagation (BP) algorithm for ANNs, has been developed for real-time time series learning. It performs the model training with every new data that arrive to the system, without saving enormous quantities of data to create a historical database as usual, i.e., without previous knowledge. Consequently to validate the approach a simulation study through a Bayesian baseline model have been tested in order to compare with a database of a real application aiming to see the performance and accuracy. The core of the paper is a new algorithm, based on the BP one, which has been described in detail, and the challenge was how to implement a computational demanding algorithm in a simple architecture with very few hardware resources.
Tree compression using string grammars
Venue: arXiv cs.FL 2015
Year: 2015

We study the compressed representation of a ranked tree by a (string) straight-line program (SLP) for its preorder traversal, and compare it with the well-studied representation by straight-line context free tree grammars (which are also known as tree straight-line programs or TSLPs). Although SLPs turn out to be exponentially more succinct than TSLPs, we show that many simple tree queries can still be performed efficiently on SLPs, such as computing the height and Horton-Strahler number of a tree, tree navigation, or evaluation of Boolean expressions. Other problems on tree traversals turn out to be intractable, e.g. pattern matching and evaluation of tree automata.
Learning Opposites with Evolving Rules
Venue: arXiv cs.NE 2015
Year: 2015

The idea of opposition-based learning was introduced 10 years ago. Since then a noteworthy group of researchers has used some notions of oppositeness to improve existing optimization and learning algorithms. Among others, evolutionary algorithms, reinforcement agents, and neural networks have been reportedly extended into their opposition-based version to become faster and/or more accurate. However, most works still use a simple notion of opposites, namely linear (or type- I) opposition, that for each $x\in[a,b]$ assigns its opposite as $\breve{x}_I=a+b-x$. This, of course, is a very naive estimate of the actual or true (non-linear) opposite $\breve{x}_{II}$, which has been called type-II opposite in literature. In absence of any knowledge about a function $y=f(\mathbf{x})$ that we need to approximate, there seems to be no alternative to the naivety of type-I opposition if one intents to utilize oppositional concepts. But the question is if we can receive some level of accuracy increase and time savings by using the naive opposite estimate $\breve{x}_I$ according to all reports in literature, what would we be able to gain, in terms of even higher accuracies and more reduction in computational complexity, if we would generate and employ true opposites? This work introduces an approach to approximate type-II opposites using evolving fuzzy rules when we first perform opposition mining. We show with multiple examples that learning true opposites is possible when we mine the opposites from the training data to subsequently approximate $\breve{x}_{II}=f(\mathbf{x},y)$.
High rate locally-correctable and locally-testable codes with sub-polynomial query complexity
Venue: arXiv cs.CC 2015
Year: 2015

In this work, we construct the first locally-correctable codes (LCCs), and locally-testable codes (LTCs) with constant rate, constant relative distance, and sub-polynomial query complexity. Specifically, we show that there exist binary LCCs and LTCs with block length $n$, constant rate (which can even be taken arbitrarily close to 1), constant relative distance, and query complexity $\exp(\tilde{O}(\sqrt{\log n}))$. Previously such codes were known to exist only with $Ω(n^β)$ query complexity (for constant $β> 0$), and there were several, quite different, constructions known. Our codes are based on a general distance-amplification method of Alon and Luby~\cite{AL96_codes}. We show that this method interacts well with local correctors and testers, and obtain our main results by applying it to suitably constructed LCCs and LTCs in the non-standard regime of \emph{sub-constant relative distance}. Along the way, we also construct LCCs and LTCs over large alphabets, with the same query complexity $\exp(\tilde{O}(\sqrt{\log n}))$, which additionally have the property of approaching the Singleton bound: they have almost the best-possible relationship between their rate and distance. This has the surprising consequence that asking for a large alphabet error-correcting code to further be an LCC or LTC with $\exp(\tilde{O}(\sqrt{\log n}))$ query complexity does not require any sacrifice in terms of rate and distance! Such a result was previously not known for any $o(n)$ query complexity. Our results on LCCs also immediately give locally-decodable codes (LDCs) with the same parameters.
Low-Complexity CFO Estimation for Multi-User Massive MIMO Systems
Venue: arXiv cs.IT 2015
Year: 2015

Low-complexity carrier frequency offset (CFO) estimation and compensation in multi-user massive multiple-input multiple-output (MIMO) systems is a challenging problem. The existing CFO estimation algorithms incur tremendous increase in complexity with increasing number of base station (BS) antennas, $M$ and number of user terminals (UTs) $K$ (i.e. massive MIMO regime). In this paper, we address this problem by proposing a novel low-complexity algorithm for CFO estimation which uses the pilot signal received at the BS during special uplink slots. The total per-channel use complexity of the proposed algorithm increases only linearly with increasing $M$ and is independent of $K$. Analysis reveals that the CFO estimation accuracy can be considerably improved by increasing $M$ and $K$ (i.e. massive MIMO regime). For example, for a fixed $K$ and a fixed training length, the required per-user radiated power during uplink training decreases as $\frac{1}{\sqrt{M}}$ with increasing $M$.
When Do WOM Codes Improve the Erasure Factor in Flash Memories?
Venue: arXiv cs.IT 2015
Year: 2015

Flash memory is a write-once medium in which reprogramming cells requires first erasing the block that contains them. The lifetime of the flash is a function of the number of block erasures and can be as small as several thousands. To reduce the number of block erasures, pages, which are the smallest write unit, are rewritten out-of-place in the memory. A Write-once memory (WOM) code is a coding scheme which enables to write multiple times to the block before an erasure. However, these codes come with significant rate loss. For example, the rate for writing twice (with the same rate) is at most 0.77. In this paper, we study WOM codes and their tradeoff between rate loss and reduction in the number of block erasures, when pages are written uniformly at random. First, we introduce a new measure, called erasure factor, that reflects both the number of block erasures and the amount of data that can be written on each block. A key point in our analysis is that this tradeoff depends upon the specific implementation of WOM codes in the memory. We consider two systems that use WOM codes; a conventional scheme that was commonly used, and a new recent design that preserves the overall storage capacity. While the first system can improve the erasure factor only when the storage rate is at most 0.6442, we show that the second scheme always improves this figure of merit.
The $κ$-$μ$ Shadowed Fading Model: Unifying the $κ$-$μ$ and $η$-$μ$ Distributions
Venue: arXiv cs.IT 2015
Year: 2015

This paper shows that the recently proposed $κ$-$μ$ shadowed fading model includes, besides the $κ$-$μ$ model, the $η$-$μ$ fading model as a particular case. This has important relevance in practice, as it allows for the unification of these popular fading distributions through a more general, yet equally tractable, model. The convenience of new underlying physical models is discussed. Then, we derive simple and novel closed-form expressions for the asymptotic ergodic capacity in $κ$-$μ$ shadowed fading channels, which illustrate the effects of the different fading parameters on the system performance. By exploiting the unification here unveiled, the asymptotic capacity expressions for the $κ$-$μ$ and $η$-$μ$ fading models are also obtained in closed-form as special cases.
Distribution Network Topology Detection with Time Series Measurement Data Analysis
Venue: arXiv cs.SY 2015
Year: 2015

This paper proposes a novel approach for detecting the topology of distribution networks based on the analysis of time series measurements. The time-based analysis approach draws on data from high-precision phasor measurement units (PMUs or synchrophasors) for distribution systems. A key fact is that time-series data taken from a dynamic system show specific patterns regarding state transitions such as opening or closing switches, as a kind of signature from each topology change. The proposed algorithm here is based on the comparison of the actual signature of a recent state transition against a library of signatures derived from topology simulations. The IEEE 33-bus model is used for initial algorithm validation.
Allocating Indivisible Items in Categorized Domains
Venue: arXiv cs.GT 2015
Year: 2015

We formulate a general class of allocation problems called categorized domain allocation problems (CDAPs), where indivisible items from multiple categories are allocated to agents without monetary transfer and each agent gets at least one item per category. We focus on basic CDAPs, where the number of items in each category is equal to the number of agents. We characterize serial dictatorships for basic CDAPs by a minimal set of three axiomatic properties: strategy-proofness, non-bossiness, and category-wise neutrality. Then, we propose a natural extension of serial dictatorships called categorial sequential allocation mechanisms (CSAMs), which allocate the items in multiple rounds: in each round, the active agent chooses an item from a designated category. We fully characterize the worst-case rank efficiency of CSAMs for optimistic and pessimistic agents, and provide a bound for strategic agents. We also conduct experiments to compare expected rank efficiency of various CSAMs w.r.t. random generated data.
Differentially Private $k$-Means Clustering
Venue: arXiv cs.CR 2015
Year: 2015

There are two broad approaches for differentially private data analysis. The interactive approach aims at developing customized differentially private algorithms for various data mining tasks. The non-interactive approach aims at developing differentially private algorithms that can output a synopsis of the input dataset, which can then be used to support various data mining tasks. In this paper we study the tradeoff of interactive vs. non-interactive approaches and propose a hybrid approach that combines interactive and non-interactive, using $k$-means clustering as an example. In the hybrid approach to differentially private $k$-means clustering, one first uses a non-interactive mechanism to publish a synopsis of the input dataset, then applies the standard $k$-means clustering algorithm to learn $k$ cluster centroids, and finally uses an interactive approach to further improve these cluster centroids. We analyze the error behavior of both non-interactive and interactive approaches and use such analysis to decide how to allocate privacy budget between the non-interactive step and the interactive step. Results from extensive experiments support our analysis and demonstrate the effectiveness of our approach.
Blind Index Coding
Venue: arXiv cs.IT 2015
Year: 2015

We introduce the blind index coding (BIC) problem, in which a single sender communicates distinct messages to multiple users over a shared channel. Each user has partial knowledge of each message as side information. However, unlike classic index coding, in BIC, the sender is uncertain of what side information is available to each user. In particular, the sender only knows the amount of bits in each user's side information but not its content. This problem can arise naturally in caching and wireless networks. In order to blindly exploit side information in the BIC problem, we develop a hybrid coding scheme that XORs uncoded bits of a subset of messages with random combinations of bits from other messages. This scheme allows us to strike the right balance between maximizing the transmission rate to each user and minimizing the interference leakage to others. We also develop a general outer bound, which relies on a strong data processing inequality to effectively capture the senders uncertainty about the users' side information. Additionally, we consider the case where communication takes place over a shared wireless medium, modeled by an erasure broadcast channel, and show that surprisingly, combining repetition coding with hybrid coding improves the achievable rate region and outperforms alternative strategies of coping with channel erasure and while blindly exploiting side information.
State of the Art of the Intra-Task Dynamic Voltage and Frequency Scaling Technique
Venue: arXiv cs.OH 2015
Year: 2015

In recent years there has been an increasing use of embedded systems because of advances in technology, the reduction of the costs of electronic equipment and mainly the popularity of mobile devices. Many of these systems implement low power consumption policies to extend their autonomy, usually because they have a reduced amount of resources and the great majority of them use electric power from batteries. One way to minimize the power consumption of these devices is through of the application of low power consumption techniques. From the various techniques presented in the literature - the intra-task Dynamic Voltage and Frequency Scaling (DVFS) has played an important role. The main aim of DVFS is to allow each task to manage the minimum resources necessary for tasks execution, this way reducing the processor power consumption and, at the same time, respecting the task deadlines when considered a real-time system context. Therefore, this paper aims to apply a systematic literature review with the goal of identifying and presenting the main methods using the intra-task DVFS technique, applied in the context of real-time systems to reduce energy consumption on the processor. Finally, this work will show the advantages and disadvantages of each cataloged methodology.