OpenRaiser/Intern-Atlas huggingface dataset:
Improved Multiple Feedback Successive Interference Cancellation Algorithm for Near-Optimal MIMO Detection
Venue: arXiv cs.IT 2015
Year: 2015

In this article, we propose an improved multiple feedback successive interference cancellation (IMF-SIC) algorithm for symbol vector detection in multiple-input multiple-output (MIMO) spatial multiplexing systems. The multiple feedback (MF) strategy in successive interference cancellation (SIC) is based on the concept of shadow area constraint (SAC) where, if the decision falls in the shadow region multiple neighboring constellation points will be used in the decision feedback loop followed by the conventional SIC. The best candidate symbol from multiple neighboring symbols is selected using the maximum likelihood (ML) criteria. However, while deciding the best symbol from multiple neighboring symbols, the SAC condition may occur in subsequent layers which results in inaccurate decision. In order to overcome this limitation, in the proposed algorithm, SAC criteria is checked recursively for each layer. This results in successful mitigation of error propagation thus significantly improving the bit error rate (BER) performance. Further, we also propose an ordered IMF-SIC (OIMF-SIC) where we use log likelihood ratio (LLR) based dynamic ordering of the detection sequence. In OIMF-SIC, we use the term dynamic ordering in the sense that the detection order is updated after every successful decision. Simulation results show that the proposed algorithms outperform the existing detectors such as conventional SIC and MF-SIC in terms of BER, and achieves a near ML performance.
Variants of Plane Diameter Completion
Venue: arXiv cs.DS 2015
Year: 2015

The {\sc Plane Diameter Completion} problem asks, given a plane graph $G$ and a positive integer $d$, if it is a spanning subgraph of a plane graph $H$ that has diameter at most $d$. We examine two variants of this problem where the input comes with another parameter $k$. In the first variant, called BPDC, $k$ upper bounds the total number of edges to be added and in the second, called BFPDC, $k$ upper bounds the number of additional edges per face. We prove that both problems are {\sf NP}-complete, the first even for 3-connected graphs of face-degree at most 4 and the second even when $k=1$ on 3-connected graphs of face-degree at most 5. In this paper we give parameterized algorithms for both problems that run in $O(n^{3})+2^{2^{O((kd)^2\log d)}}\cdot n$ steps.
Depth Fields: Extending Light Field Techniques to Time-of-Flight Imaging
Venue: arXiv cs.CV 2015
Year: 2015

A variety of techniques such as light field, structured illumination, and time-of-flight (TOF) are commonly used for depth acquisition in consumer imaging, robotics and many other applications. Unfortunately, each technique suffers from its individual limitations preventing robust depth sensing. In this paper, we explore the strengths and weaknesses of combining light field and time-of-flight imaging, particularly the feasibility of an on-chip implementation as a single hybrid depth sensor. We refer to this combination as depth field imaging. Depth fields combine light field advantages such as synthetic aperture refocusing with TOF imaging advantages such as high depth resolution and coded signal processing to resolve multipath interference. We show applications including synthesizing virtual apertures for TOF imaging, improved depth mapping through partial and scattering occluders, and single frequency TOF phase unwrapping. Utilizing space, angle, and temporal coding, depth fields can improve depth sensing in the wild and generate new insights into the dimensions of light's plenoptic function.
Confluent Orthogonal Drawings of Syntax Diagrams
Venue: arXiv cs.OH 2015
Year: 2015

We provide a pipeline for generating syntax diagrams (also called railroad diagrams) from context free grammars. Syntax diagrams are a graphical representation of a context free language, which we formalize abstractly as a set of mutually recursive nondeterministic finite automata and draw by combining elements from the confluent drawing, layered drawing, and smooth orthogonal drawing styles. Within our pipeline we introduce several heuristics that modify the grammar but preserve the language, improving the aesthetics of the final drawing.
A DEEP analysis of the META-DES framework for dynamic selection of ensemble of classifiers
Venue: arXiv cs.LG 2015
Year: 2015

Dynamic ensemble selection (DES) techniques work by estimating the level of competence of each classifier from a pool of classifiers. Only the most competent ones are selected to classify a given test sample. Hence, the key issue in DES is the criterion used to estimate the level of competence of the classifiers in predicting the label of a given test sample. In order to perform a more robust ensemble selection, we proposed the META-DES framework using meta-learning, where multiple criteria are encoded as meta-features and are passed down to a meta-classifier that is trained to estimate the competence level of a given classifier. In this technical report, we present a step-by-step analysis of each phase of the framework during training and test. We show how each set of meta-features is extracted as well as their impact on the estimation of the competence level of the base classifier. Moreover, an analysis of the impact of several factors in the system performance, such as the number of classifiers in the pool, the use of different linear base classifiers, as well as the size of the validation data. We show that using the dynamic selection of linear classifiers through the META-DES framework, we can solve complex non-linear classification problems where other combination techniques such as AdaBoost cannot.
Multimedia Transmission over Cognitive Radio Channels under Sensing Uncertainty
Venue: arXiv cs.IT 2015
Year: 2015

This paper studies the performance of hierarchical modulation-based multimedia transmission in cognitive radio (CR) systems with imperfect channel sensing results under constraints on both transmit and interference power levels. Unequal error protection (UEP) of data transmission using hierarchical quadrature amplitude modulation (HQAM) is considered in which high priority (HP) data is protected more than low priority (LP) data. In this setting, closed-form bit error rate (BER) expressions for HP data and LP data are derived in Nakagami-$m$ fading channels in the presence of sensing errors. Subsequently, the optimal power control that minimizes weighted sum of average BERs of HP bits and LP bits or its upper bound subject to peak/average transmit power and average interference power constraints is derived and a low-complexity power control algorithm is proposed. Power levels are determined in three different scenarios, depending on the availability of perfect channel side information (CSI) of the transmission and interference links, statistical CSI of both links, or perfect CSI of the transmission link and imperfect CSI of the interference link. The impact of imperfect channel sensing decisions on the error rate performance of cognitive transmissions is also evaluated. In addition, tradeoffs between the number of retransmissions, the severity of fading, and peak signal-to-noise ratio (PSNR) quality are analyzed numerically. Moreover, performance comparisons of multimedia transmission with conventional quadrature amplitude modulation (QAM) and HQAM, and the proposed power control strategies are carried out in terms of the received data quality and number of retransmissions.
On TimeML-Compliant Temporal Expression Extraction in Turkish
Venue: arXiv cs.CL 2015
Year: 2015

It is commonly acknowledged that temporal expression extractors are important components of larger natural language processing systems like information retrieval and question answering systems. Extraction and normalization of temporal expressions in Turkish has not been given attention so far except the extraction of some date and time expressions within the course of named entity recognition. As TimeML is the current standard of temporal expression and event annotation in natural language texts, in this paper, we present an analysis of temporal expressions in Turkish based on the related TimeML classification (i.e., date, time, duration, and set expressions). We have created a lexicon for Turkish temporal expressions and devised considerably wide-coverage patterns using the lexical classes as the building blocks. We believe that the proposed patterns, together with convenient normalization rules, can be readily used by prospective temporal expression extraction tools for Turkish.
A Reconfigurable Mixed-signal Implementation of a Neuromorphic ADC
Venue: arXiv cs.NE 2015
Year: 2015

We present a neuromorphic Analogue-to-Digital Converter (ADC), which uses integrate-and-fire (I&F) neurons as the encoders of the analogue signal, with modulated inhibitions to decohere the neuronal spikes trains. The architecture consists of an analogue chip and a control module. The analogue chip comprises two scan chains and a twodimensional integrate-and-fire neuronal array. Individual neurons are accessed via the chains one by one without any encoder decoder or arbiter. The control module is implemented on an FPGA (Field Programmable Gate Array), which sends scan enable signals to the scan chains and controls the inhibition for individual neurons. Since the control module is implemented on an FPGA, it can be easily reconfigured. Additionally, we propose a pulse width modulation methodology for the lateral inhibition, which makes use of different pulse widths indicating different strengths of inhibition for each individual neuron to decohere neuronal spikes. Software simulations in this paper tested the robustness of the proposed ADC architecture to fixed random noise. A circuit simulation using ten neurons shows the performance and the feasibility of the architecture.
Security Analysis of Secure Force Algorithm for Wireless Sensor Networks
Venue: arXiv cs.CR 2015
Year: 2015

In Wireless Sensor Networks, the sensor nodes are battery powered small devices designed for long battery life. These devices also lack in terms of processing capability and memory. In order to provide high confidentiality to these resource constrained network nodes, a suitable security algorithm is needed to be deployed that can establish a balance between security level and processing overhead. The objective of this research work is to perform a security analysis and performance evaluation of recently proposed Secure Force algorithm. This paper shows the comparison of Secure Force 64, 128, and 192 bit architecture on the basis of avalanche effect (key sensitivity), entropy change analysis, image histogram, and computational time. Moreover, based on the evaluation results, the paper also suggests the possible solutions for the weaknesses of the SF algorithm.
Introduction to Mathematical Programming-Based Error-Correction Decoding
Venue: arXiv cs.IT 2015
Year: 2015

Decoding error-correctiong codes by methods of mathematical optimization, most importantly linear programming, has become an important alternative approach to both algebraic and iterative decoding methods since its introduction by Feldman et al. At first celebrated mainly for its analytical powers, real-world applications of LP decoding are now within reach thanks to most recent research. This document gives an elaborate introduction into both mathematical optimization and coding theory as well as a review of the contributions by which these two areas have found common ground.
Model Predictive Path Integral Control using Covariance Variable Importance Sampling
Venue: arXiv cs.SY 2015
Year: 2015

In this paper we develop a Model Predictive Path Integral (MPPI) control algorithm based on a generalized importance sampling scheme and perform parallel optimization via sampling using a Graphics Processing Unit (GPU). The proposed generalized importance sampling scheme allows for changes in the drift and diffusion terms of stochastic diffusion processes and plays a significant role in the performance of the model predictive control algorithm. We compare the proposed algorithm in simulation with a model predictive control version of differential dynamic programming.
Parallel Knowledge Embedding with MapReduce on a Multi-core Processor
Venue: arXiv cs.DC 2015
Year: 2015

This article firstly attempts to explore parallel algorithms of learning distributed representations for both entities and relations in large-scale knowledge repositories with {\it MapReduce} programming model on a multi-core processor. We accelerate the training progress of a canonical knowledge embedding method, i.e. {\it translating embedding} ({\bf TransE}) model, by dividing a whole knowledge repository into several balanced subsets, and feeding each subset into an individual core where local embeddings can concurrently run updating during the {\it Map} phase. However, it usually suffers from inconsistent low-dimensional vector representations of the same key, which are collected from different {\it Map} workers, and further leads to conflicts when conducting {\it Reduce} to merge the various vectors associated with the same key. Therefore, we try several strategies to acquire the merged embeddings which may not only retain the performance of {\it entity inference}, {\it relation prediction}, and even {\it triplet classification} evaluated by the single-thread {\bf TransE} on several well-known knowledge bases such as Freebase and NELL, but also scale up the learning speed along with the number of cores within a processor. So far, the empirical studies show that we could achieve comparable results as the single-thread {\bf TransE} performs by the {\it stochastic gradient descend} (SGD) algorithm, as well as increase the training speed multiple times via adapting the {\it batch gradient descend} (BGD) algorithm for {\it MapReduce} paradigm.
Optimal searching of gapped repeats in a word
Venue: arXiv cs.FL 2015
Year: 2015

Following (Kolpakov et al., 2013; Gawrychowski and Manea, 2015), we continue the study of {\em $α$-gapped repeats} in strings, defined as factors $uvu$ with $|uv|\leq α|u|$. Our main result is the $O(αn)$ bound on the number of {\em maximal} $α$-gapped repeats in a string of length $n$, previously proved to be $O(α^2 n)$ in (Kolpakov et al., 2013). For a closely related notion of maximal $δ$-subrepetition (maximal factors of exponent between $1+δ$ and $2$), our result implies the $O(n/δ)$ bound on their number, which improves the bound of (Kolpakov et al., 2010) by a $\log n$ factor. We also prove an algorithmic time bound $O(αn+S)$ ($S$ size of the output) for computing all maximal $α$-gapped repeats. Our solution, inspired by (Gawrychowski and Manea, 2015), is different from the recently published proof by (Tanimura et al., 2015) of the same bound. Together with our bound on $S$, this implies an $O(αn)$-time algorithm for computing all maximal $α$-gapped repeats.
Analog Computing Using Graphene-based Metalines
Venue: arXiv cs.ET 2015
Year: 2015

We introduce the new concept of "metalines" for manipulating the amplitude and phase profile of an incident wave locally and independently. Thanks to the highly confined graphene plasmons, a transmit-array of graphene-based metalines is used to realize analog computing on an ultra-compact, integrable and planar platform. By employing the general concepts of spatial Fourier transformation, a well-designed structure of such meta-transmit-array combined with graded index lenses can perform two mathematical operations; i.e. differentiation and integration, with high efficiency. The presented configuration is about 60 times shorter than the recent structure proposed by Silva et al.(Science, 2014, 343, 160-163); moreover, our simulated output responses are in more agreement with the desired analytic results. These findings may lead to remarkable achievements in light-based plasmonic signal processors at nanoscale instead of their bulky conventional dielectric lens-based counterparts.
Incremental Active Opinion Learning Over a Stream of Opinionated Documents
Venue: arXiv cs.IR 2015
Year: 2015

Applications that learn from opinionated documents, like tweets or product reviews, face two challenges. First, the opinionated documents constitute an evolving stream, where both the author's attitude and the vocabulary itself may change. Second, labels of documents are scarce and labels of words are unreliable, because the sentiment of a word depends on the (unknown) context in the author's mind. Most of the research on mining over opinionated streams focuses on the first aspect of the problem, whereas for the second a continuous supply of labels from the stream is assumed. Such an assumption though is utopian as the stream is infinite and the labeling cost is prohibitive. To this end, we investigate the potential of active stream learning algorithms that ask for labels on demand. Our proposed ACOSTREAM 1 approach works with limited labels: it uses an initial seed of labeled documents, occasionally requests additional labels for documents from the human expert and incrementally adapts to the underlying stream while exploiting the available labeled documents. In its core, ACOSTREAM consists of a MNB classifier coupled with "sampling" strategies for requesting class labels for new unlabeled documents. In the experiments, we evaluate the classifier performance over time by varying: (a) the class distribution of the opinionated stream, while assuming that the set of the words in the vocabulary is fixed but their polarities may change with the class distribution; and (b) the number of unknown words arriving at each moment, while the class polarity may also change. Our results show that active learning on a stream of opinionated documents, delivers good performance while requiring a small selection of labels
Diffusion-KLMS Algorithm and its Performance Analysis for Non-Linear Distributed Networks
Venue: arXiv cs.LG 2015
Year: 2015

In a distributed network environment, the diffusion-least mean squares (LMS) algorithm gives faster convergence than the original LMS algorithm. It has also been observed that, the diffusion-LMS generally outperforms other distributed LMS algorithms like spatial LMS and incremental LMS. However, both the original LMS and diffusion-LMS are not applicable in non-linear environments where data may not be linearly separable. A variant of LMS called kernel-LMS (KLMS) has been proposed in the literature for such non-linearities. In this paper, we propose kernelised version of diffusion-LMS for non-linear distributed environments. Simulations show that the proposed approach has superior convergence as compared to algorithms of the same genre. We also introduce a technique to predict the transient and steady-state behaviour of the proposed algorithm. The techniques proposed in this work (or algorithms of same genre) can be easily extended to distributed parameter estimation applications like cooperative spectrum sensing and massive multiple input multiple output (MIMO) receiver design which are potential components for 5G communication systems.
Adaptively Directional Wireless Power Transfer for Large-scale Sensor Networks
Venue: arXiv cs.IT 2015
Year: 2015

Wireless power transfer (WPT) prolongs the lifetime of wireless sensor network by providing sustainable power supply to the distributed sensor nodes (SNs) via electromagnetic waves. To improve the energy transfer efficiency in a large WPT system, this paper proposes an adaptively directional WPT (AD-WPT) scheme, where the power beacons (PBs) adapt the energy beamforming strategy to SNs' locations by concentrating the transmit power on the nearby SNs within the efficient charging radius. With the aid of stochastic geometry, we derive the closed-form expressions of the distribution metrics of the aggregate received power at a typical SN and further approximate the complementary cumulative distribution function using Gamma distribution with second-order moment matching. To design the charging radius for the optimal AD-WPT operation, we exploit the tradeoff between the power intensity of the energy beams and the number of SNs to be charged. Depending on different SN task requirements, the optimal AD-WPT can maximize the average received power or the active probability of the SNs, respectively. It is shown that both the maximized average received power and the maximized sensor active probability increase with the increased deployment density and transmit power of the PBs, and decrease with the increased density of the SNs and the energy beamwidth. Finally, we show that the optimal AD-WPT can significantly improve the energy transfer efficiency compared with the traditional omnidirectional WPT.
CNN Based Hashing for Image Retrieval
Venue: arXiv cs.CV 2015
Year: 2015

Along with data on the web increasing dramatically, hashing is becoming more and more popular as a method of approximate nearest neighbor search. Previous supervised hashing methods utilized similarity/dissimilarity matrix to get semantic information. But the matrix is not easy to construct for a new dataset. Rather than to reconstruct the matrix, we proposed a straightforward CNN-based hashing method, i.e. binarilizing the activations of a fully connected layer with threshold 0 and taking the binary result as hash codes. This method achieved the best performance on CIFAR-10 and was comparable with the state-of-the-art on MNIST. And our experiments on CIFAR-10 suggested that the signs of activations may carry more information than the relative values of activations between samples, and that the co-adaption between feature extractor and hash functions is important for hashing.
Quantization based Fast Inner Product Search
Venue: arXiv cs.AI 2015
Year: 2015

We propose a quantization based approach for fast approximate Maximum Inner Product Search (MIPS). Each database vector is quantized in multiple subspaces via a set of codebooks, learned directly by minimizing the inner product quantization error. Then, the inner product of a query to a database vector is approximated as the sum of inner products with the subspace quantizers. Different from recently proposed LSH approaches to MIPS, the database vectors and queries do not need to be augmented in a higher dimensional feature space. We also provide a theoretical analysis of the proposed approach, consisting of the concentration results under mild assumptions. Furthermore, if a small sample of example queries is given at the training time, we propose a modified codebook learning procedure which further improves the accuracy. Experimental results on a variety of datasets including those arising from deep neural networks show that the proposed approach significantly outperforms the existing state-of-the-art.
Analyzing large-scale DNA Sequences on Multi-core Architectures
Venue: arXiv cs.DC 2015
Year: 2015

Rapid analysis of DNA sequences is important in preventing the evolution of different viruses and bacteria during an early phase, early diagnosis of genetic predispositions to certain diseases (cancer, cardiovascular diseases), and in DNA forensics. However, real-world DNA sequences may comprise several Gigabytes and the process of DNA analysis demands adequate computational resources to be completed within a reasonable time. In this paper we present a scalable approach for parallel DNA analysis that is based on Finite Automata, and which is suitable for analyzing very large DNA segments. We evaluate our approach for real-world DNA segments of mouse (2.7GB), cat (2.4GB), dog (2.4GB), chicken (1GB), human (3.2GB) and turkey (0.2GB). Experimental results on a dual-socket shared-memory system with 24 physical cores show speed-ups of up to 17.6x. Our approach is up to 3x faster than a pattern-based parallel approach that uses the RE2 library.