OpenRaiser/Intern-Atlas huggingface dataset:
Price of Competition and Dueling Games
Venue: arXiv cs.GT 2016
Year: 2016

We study competition in a general framework introduced by Immorlica et al. and answer their main open question. Immorlica et al. considered classic optimization problems in terms of competition and introduced a general class of games called dueling games. They model this competition as a zero-sum game, where two players are competing for a user's satisfaction. In their main and most natural game, the ranking duel, a user requests a webpage by submitting a query and players output an ordering over all possible webpages based on the submitted query. The user tends to choose the ordering which displays her requested webpage in a higher rank. The goal of both players is to maximize the probability that her ordering beats that of her opponent and gets the user's attention. Immorlica et al. show this game directs both players to provide suboptimal search results. However, they leave the following as their main open question: "does competition between algorithms improve or degrade expected performance?" In this paper, we resolve this question for the ranking duel and a more general class of dueling games. More precisely, we study the quality of orderings in a competition between two players. This game is a zero-sum game, and thus any Nash equilibrium of the game can be described by minimax strategies. Let the value of the user for an ordering be a function of the position of her requested item in the corresponding ordering, and the social welfare for an ordering be the expected value of the corresponding ordering for the user. We propose the price of competition which is the ratio of the social welfare for the worst minimax strategy to the social welfare obtained by a social planner. We use this criterion for analyzing the quality of orderings in the ranking duel. We prove the quality of minimax results is surprisingly close to that of the optimum solution.
A Gaussian Mixture MRF for Model-Based Iterative Reconstruction with Applications to Low-Dose X-ray CT
Venue: arXiv cs.CV 2016
Year: 2016

Markov random fields (MRFs) have been widely used as prior models in various inverse problems such as tomographic reconstruction. While MRFs provide a simple and often effective way to model the spatial dependencies in images, they suffer from the fact that parameter estimation is difficult. In practice, this means that MRFs typically have very simple structure that cannot completely capture the subtle characteristics of complex images. In this paper, we present a novel Gaussian mixture Markov random field model (GM-MRF) that can be used as a very expressive prior model for inverse problems such as denoising and reconstruction. The GM-MRF forms a global image model by merging together individual Gaussian-mixture models (GMMs) for image patches. In addition, we present a novel analytical framework for computing MAP estimates using the GM-MRF prior model through the construction of surrogate functions that result in a sequence of quadratic optimizations. We also introduce a simple but effective method to adjust the GM-MRF so as to control the sharpness in low- and high-contrast regions of the reconstruction separately. We demonstrate the value of the model with experiments including image denoising and low-dose CT reconstruction.
Cross-Domain Visual Matching via Generalized Similarity Measure and Feature Learning
Venue: arXiv cs.CV 2016
Year: 2016

Cross-domain visual data matching is one of the fundamental problems in many real-world vision tasks, e.g., matching persons across ID photos and surveillance videos. Conventional approaches to this problem usually involves two steps: i) projecting samples from different domains into a common space, and ii) computing (dis-)similarity in this space based on a certain distance. In this paper, we present a novel pairwise similarity measure that advances existing models by i) expanding traditional linear projections into affine transformations and ii) fusing affine Mahalanobis distance and Cosine similarity by a data-driven combination. Moreover, we unify our similarity measure with feature representation learning via deep convolutional neural networks. Specifically, we incorporate the similarity measure matrix into the deep architecture, enabling an end-to-end way of model optimization. We extensively evaluate our generalized similarity model in several challenging cross-domain matching tasks: person re-identification under different views and face verification over different modalities (i.e., faces from still images and videos, older and younger faces, and sketch and photo portraits). The experimental results demonstrate superior performance of our model over other state-of-the-art methods.
Lightweight LCP Construction for Very Large Collections of Strings
Venue: arXiv cs.DS 2016
Year: 2016

The longest common prefix array is a very advantageous data structure that, combined with the suffix array and the Burrows-Wheeler transform, allows to efficiently compute some combinatorial properties of a string useful in several applications, especially in biological contexts. Nowadays, the input data for many problems are big collections of strings, for instance the data coming from "next-generation" DNA sequencing (NGS) technologies. In this paper we present the first lightweight algorithm (called extLCP) for the simultaneous computation of the longest common prefix array and the Burrows-Wheeler transform of a very large collection of strings having any length. The computation is realized by performing disk data accesses only via sequential scans, and the total disk space usage never needs more than twice the output size, excluding the disk space required for the input. Moreover, extLCP allows to compute also the suffix array of the strings of the collection, without any other further data structure is needed. Finally, we test our algorithm on real data and compare our results with another tool capable to work in external memory on large collections of strings.
The Largest Respectful Function
Venue: arXiv cs.LO 2016
Year: 2016

Respectful functions were introduced by Sangiorgi as a compositional tool to formulate short and clear bisimulation proofs. Usually, the larger the respectful function, the easier the bisimulation proof. In particular the largest respectful function, defined as the pointwise union of all respectful functions, has been shown to be very useful. We here provide an explicit and constructive characterization of it.
Knowledge-Enabled Robotic Agents for Shelf Replenishment in Cluttered Retail Environments
Venue: arXiv cs.RO 2016
Year: 2016

Autonomous robots in unstructured and dynamically changing retail environments have to master complex perception, knowledgeprocessing, and manipulation tasks. To enable them to act competently, we propose a framework based on three core components: (o) a knowledge-enabled perception system, capable of combining diverse information sources to cope with occlusions and stacked objects with a variety of textures and shapes, (o) knowledge processing methods produce strategies for tidying up supermarket racks, and (o) the necessary manipulation skills in confined spaces to arrange objects in semi-accessible rack shelves. We demonstrate our framework in an simulated environment as well as on a real shopping rack using a PR2 robot. Typical supermarket products are detected and rearranged in the retail rack, tidying up what was found to be misplaced items.
Review of state-of-the-arts in artificial intelligence with application to AI safety problem
Venue: arXiv cs.AI 2016
Year: 2016

Here, I review current state-of-the-arts in many areas of AI to estimate when it's reasonable to expect human level AI development. Predictions of prominent AI researchers vary broadly from very pessimistic predictions of Andrew Ng to much more moderate predictions of Geoffrey Hinton and optimistic predictions of Shane Legg, DeepMind cofounder. Given huge rate of progress in recent years and this broad range of predictions of AI experts, AI safety questions are also discussed.
Multi-Phase Smart Relaying and Cooperative Jamming in Secure Cognitive Radio Networks
Venue: arXiv cs.IT 2016
Year: 2016

In this paper we investigate cooperative secure communications in a four-node cognitive radio network where the secondary receiver is treated as a potential eavesdropper with respect to the primary transmission. The secondary user is allowed to transmit his own signals under the condition that the primary user's secrecy rate and transmission scheme are intact. Under this setting we derive the secondary user's achievable rates and the related constraints to guarantee the primary user's weak secrecy rate, when Gelfand-Pinsker coding is used at the secondary transmitter. In addition, we propose a multi-phase transmission scheme to include 1) the phases of the clean relaying with cooperative jamming and 2) the latency to successfully decode the primary message at the secondary transmitter. A capacity upper bound for the secondary user is also derived. Numerical results show that: 1) the proposed scheme can outperform the traditional ones by properly selecting the secondary user's parameters of different transmission schemes according to the relative positions of the nodes; 2) the derived capacity upper bound is close to the secondary user's achievable rate within 0.3 bits/channel use, especially when the secondary transmitter/receiver is far/close enough to the primary receiver/transmitter, respectively. Thereby, a smart secondary transmitter is able to adapt its relaying and cooperative jamming to guarantee primary secrecy rates and to transmit its own data at the same time from relevant geometric positions.
An Algorithmic Framework for Labeling Road Maps
Venue: arXiv cs.CG 2016
Year: 2016

Given an unlabeled road map, we consider, from an algorithmic perspective, the cartographic problem to place non-overlapping road labels embedded in their roads. We first decompose the road network into logically coherent road sections, e.g., parts of roads between two junctions. Based on this decomposition, we present and implement a new and versatile framework for placing labels in road maps such that the number of labeled road sections is maximized. In an experimental evaluation with road maps of 11 major cities we show that our proposed labeling algorithm is both fast in practice and that it reaches near-optimal solution quality, where optimal solutions are obtained by mixed-integer linear programming. In comparison to the standard OpenStreetMap renderer Mapnik, our algorithm labels 31% more road sections in average.
A First Look at Quality of Mobile Live Streaming Experience: the Case of Periscope
Venue: arXiv cs.MM 2016
Year: 2016

Live multimedia streaming from mobile devices is rapidly gaining popularity but little is known about the QoE they provide. In this paper, we examine the Periscope service. We first crawl the service in order to understand its usage patterns. Then, we study the protocols used, the typical quality of experience indicators, such as playback smoothness and latency, video quality, and the energy consumption of the Android application.
Guard Region Model for Pilot Reuse Analysis in Uplink Massive MIMO Systems
Venue: arXiv cs.IT 2016
Year: 2016

Massive multiple-input multiple-output (MIMO) are expected to significantly enhance the spectrum efficiency (SE) and energy efficiency (EE) of future cellular systems. Since the performance gain of massive MIMO is fundamentally limited by pilot contamination, pilot reuse design is crucial to achieve reasonable cell throughput and user rate. In this paper, we leverage stochastic geometry to model pilot reuse in massive MIMO systems by introducing a guard region model to match realistic pilot allocation strategies. The uplink signal-to-interference-plus-noise ratio (SINR) distribution is analytically derived, based on which the benefits of pilot reuse on cell-throughput and user-rate are investigated. The optimal pilot reuse factor for uplink transmission is obtained. We also find through simulations that increasing the pilot reuse factor beyond a certain value would not improve user-rate, and could even lead to a significant loss of the cell throughput.
Frequency Assignment Problem with Net Filter Discrimination Constraints
Venue: arXiv cs.NI 2016
Year: 2016

Managing radio spectrum resources is a crucial issue. The frequency assignment problem (FAP) basically aims to allocate, in an efficient manner, limited number of frequencies to communication links. Geographically close links, however, cause interference, which complicates the assignment, imposing frequency separation constraints. The FAP is closely related to the graph-coloring problem and it is an NP-hard problem. In this paper, we propose to incorporate the randomization into greedy and fast heuristics. As far as being implemented, the proposed algorithms are very straight forward and are without system parameters that need tuned. The proposed algorithms significantly improve, quickly and effectively, the solutions obtained by greedy algorithms in terms of the number of assigned frequencies and the range. The enhanced versions of proposed algorithms perform close to the lower bounds while running for a reasonable duration. Another novelty of our study is its consideration of the net filter discrimination effects in the communication model. Performance analysis is done by synthetic and measured data, where the measurement data includes the effect of the real 3-dimensional (3D) geographical features in the Daejeon region in Korea. In both cases, we observe a significant improvement by employing randomized heuristics.
Precoding design for single-RF massive MIMO systems: A large system analysis
Venue: arXiv cs.IT 2016
Year: 2016

This work revisits a recently proposed precoding design for massive multiple-input multiple output (MIMO) systems that is based on the use of an instantaneous total power constraint. The main advantages of this technique lie in its suitability to single RF MIMO systems coupled with a very-high power efficiency. Such features have been proven using simulations for uncorrelated channels. Based on tools from random matrix theory, we propose in this work to analyze the performance of this precoder for more involved channels accounting for spatial correlation. The obtained expressions are then optimized in order to maximize the signal-to-interference-plus-noise ratio (SINR). Simulation results are provided in order to illustrate the performance of the optimized precoder in terms of peak-to-average power ratio (PAPR) and signal-to-interference-plus-noise ratio (SINR).
Advantages of EEG phase patterns for the detection of gait intention in healthy and stroke subjects
Venue: arXiv cs.HC 2016
Year: 2016

One use of EEG-based brain-computer interfaces (BCIs) in rehabilitation is the detection of movement intention. In this paper we investigate for the first time the instantaneous phase of movement related cortical potential (MRCP) and its application to the detection of gait intention. We demonstrate the utility of MRCP phase in two independent datasets, in which 10 healthy subjects and 9 chronic stroke patients executed a self-initiated gait task in three sessions. Phase features were compared to more conventional amplitude and power features. The neurophysiology analysis showed that phase features have higher signal-to-noise ratio than the other features. Also, BCI detectors of gait intention based on phase, amplitude, and their combination were evaluated under three conditions: session specific calibration, intersession transfer, and intersubject transfer. Results show that the phase based detector is the most accurate for session specific calibration (movement intention was correctly detected in 66.5% of trials in healthy subjects, and in 63.3% in stroke patients). However, in intersession and intersubject transfer, the detector that combines amplitude and phase features is the most accurate one and the only that retains its accuracy (62.5% in healthy subjects and 59% in stroke patients) w.r.t. session specific calibration. Thus, MRCP phase features improve the detection of gait intention and could be used in practice to remove time-consuming BCI recalibration.
Fluctuations of the SNR at the output of the MVDR with Regularized Tyler Estimators
Venue: arXiv cs.IT 2016
Year: 2016

This paper analyzes the statistical properties of the signal-to-noise ratio (SNR) at the output of the Capon's minimum variance distortionless response (MVDR) beamformers when operating over impulsive noises. Particularly, we consider the supervised case in which the receiver employs the regularized Tyler estimator in order to estimate the covariance matrix of the interference-plus-noise process using $n$ observations of size $N\times 1$. The choice for the regularized Tylor estimator (RTE) is motivated by its resilience to the presence of outliers and its regularization parameter that guarantees a good conditioning of the covariance estimate. Of particular interest in this paper is the derivation of the second order statistics of the SINR. To achieve this goal, we consider two different approaches. The first one is based on considering the classical regime, referred to as the $n$-large regime, in which $N$ is assumed to be fixed while $n$ grows to infinity. The second approach is built upon recent results developed within the framework of random matrix theory and assumes that $N$ and $n$ grow large together. Numerical results are provided in order to compare between the accuracies of each regime under different settings.
TwinCG: Dual Thread Redundancy with Forward Recovery for Conjugate Gradient Methods
Venue: arXiv cs.DC 2016
Year: 2016

Even though iterative solvers like the Conjugate Gradients method (CG) have been studied for over fifty years, fault tolerance for such solvers has seen much attention in recent years. For iterative solvers, two major reliable strategies of recovery exist: checkpoint-restart for backward recovery, or some type of redundancy technique for forward recovery. Important redundancy techniques like ABFT techniques for sparse matrix-vector products (SpMxV) have recently been proposed, which increase the resilience of CG methods. These techniques offer limited recovery options, and introduce a tolerable overhead. In this work, we study a more powerful resilience concept, which is redundant multithreading. It offers more generic and stronger recovery guarantees, including any soft faults in CG iterations (among others covering ABFT SpMxV), but also requires more resources. We carefully study this redundancy/efficiency conflict. We propose a fault tolerant CG method, called TwinCG, which introduces minimal wallclock time overhead, and significant advantages in detection and correction strategies. Our method uses Dual Modular Redundancy instead of the more expensive Triple Modular Redundancy; still, it retains the TMR advantages of fault correction. We describe, implement, and benchmark our iterative solver, and compare it in terms of efficiency and fault tolerance capabilities to state-of-the-art techniques. We find that before parallelization, TwinCG introduces around 5-6% runtime overhead compared to standard CG, and after parallelization efficiently uses BLAS. In the presence of faults, it reliably performs forward recovery for a range of problems, outperforming SpMxV ABFT solutions.
A Foray into Efficient Mapping of Algorithms to Hardware Platforms on Heterogeneous Systems
Venue: arXiv cs.AR 2016
Year: 2016

Heterogeneous computing can potentially offer significant performance and performance per watt improvements over homogeneous computing, but the question "what is the ideal mapping of algorithms to architectures?" remains an open one. In the past couple of years new types of computing devices such as FPGAs have come into general computing use. In this work we attempt to add to the body of scientific knowledge by comparing Kernel performance and performance per watt of seven key algorithms according to Berkley's dwarf taxonomy. We do so using the Rodinia benchmark suite on three different high-end hardware architecture representatives from the CPU, GPU and FPGA families. We find results that support some distinct mappings between the architecture and performance per watt. Perhaps the most interesting finding is that, for our specific hardware representatives, FPGAs should be considered as alternatives to GPUs and CPUs in several key algorithms: N-body simulations, dense linear algebra and structured grid.
Heart Beat Characterization from Ballistocardiogram Signals using Extended Functions of Multiple Instances
Venue: arXiv cs.CV 2016
Year: 2016

A multiple instance learning (MIL) method, extended Function of Multiple Instances ($e$FUMI), is applied to ballistocardiogram (BCG) signals produced by a hydraulic bed sensor. The goal of this approach is to learn a personalized heartbeat "concept" for an individual. This heartbeat concept is a prototype (or "signature") that characterizes the heartbeat pattern for an individual in ballistocardiogram data. The $e$FUMI method models the problem of learning a heartbeat concept from a BCG signal as a MIL problem. This approach elegantly addresses the uncertainty inherent in a BCG signal e. g., misalignment between training data and ground truth, mis-collection of heartbeat by some transducers, etc. Given a BCG training signal coupled with a ground truth signal (e.g., a pulse finger sensor), training "bags" labeled with only binary labels denoting if a training bag contains a heartbeat signal or not can be generated. Then, using these bags, $e$FUMI learns a personalized concept of heartbeat for a subject as well as several non-heartbeat background concepts. After learning the heartbeat concept, heartbeat detection and heart rate estimation can be applied to test data. Experimental results show that the estimated heartbeat concept found by $e$FUMI is more representative and a more discriminative prototype of the heartbeat signals than those found by comparison MIL methods in the literature.
Solve-Select-Scale: A Three Step Process For Sparse Signal Estimation
Venue: arXiv cs.IT 2016
Year: 2016

In the theory of compressed sensing (CS), the sparsity $\|x\|_0$ of the unknown signal $\mathbf{x} \in \mathcal{R}^n$ is of prime importance and the focus of reconstruction algorithms has mainly been either $\|x\|_0$ or its convex relaxation (via $\|x\|_1$). However, it is typically unknown in practice and has remained a challenge when nothing about the size of the support is known. As pointed recently, $\|x\|_0$ might not be the best metric to minimize directly, both due to its inherent complexity as well as its noise performance. Recently a novel stable measure of sparsity $s(\mathbf{x}) := \|\mathbf{x}\|_1^2/\|\mathbf{x}\|_2^2$ has been investigated by Lopes \cite{Lopes2012}, which is a sharp lower bound on $\|\mathbf{x}\|_0$. The estimation procedure for this measure uses only a small number of linear measurements, does not rely on any sparsity assumptions, and requires very little computation. The usage of the quantity $s(\mathbf{x})$ in sparse signal estimation problems has not received much importance yet. We develop the idea of incorporating $s(\mathbf{x})$ into the signal estimation framework. We also provide a three step algorithm to solve problems of the form $\mathbf{Ax=b}$ with no additional assumptions on the original signal $\mathbf{x}$.