OpenRaiser/Intern-Atlas huggingface dataset:
Socially Optimal Coexistence of Wireless Body Area Networks Enabled by a Non-Cooperative Game
Venue: arXiv cs.NI 2015
Year: 2015

In this paper, we enable the coexistence of multiple wireless body area networks (BANs) using a finite repeated non-cooperative game for transmit power control. With no coordination amongst these personal sensor networks, the proposed game maximizes each network's packet delivery ratio (PDR) at low transmit power. In this context we provide a novel utility function, which gives reduced benefit to players with higher transmission power, and a subsequent reduction in radio interference to other coexisting BANs. Considering the purpose of inter-BAN interference mitigation, PDR is expressed as a compressed exponential function of inverse signal-to-interference-and-noise ratio (SINR), so it is essentially a function of transmit powers of all coexisting BANs. It is shown that a unique Nash Equilibrium (NE) exists, and hence there is a subgame-perfect equilibrium, considering best-response at each stage independent of history. In addition, the NE is proven to be the socially optimal solution across all action profiles. Realistic and extensive on- and inter-body channel models are employed. Results confirm the effectiveness of the proposed scheme in better interference management, greater reliability and reduced transmit power, when compared with other schemes that can be applied in BANs.
Improved Eigenvalue-based Spectrum Sensing via Sensor Signal Overlapping
Venue: arXiv cs.IT 2015
Year: 2015

Eigenvalue-based detectors are considered as an important method of spectrum sensing since they do not require the information about the primary user (PU) signal. In this paper we propose a method to improve the performance of the eigenvalue-based detector. The proposed method introduces a new test statistic based on combinatorial matrix with components which are overlapping subgroups extracted from the array of received signals. As a result, its covariance matrix has a larger maximum eigenvalue and trace value than the one without overlapping. Simulation results show that our proposed method can further improve the detection performance of the optimal eigenvalue-based detector. The paper also shows the effect of different overlapping methods on the receiver operating characteristic curve.
Probabilistic Depth Image Registration incorporating Nonvisual Information
Venue: arXiv cs.RO 2015
Year: 2015

In this paper, we derive a probabilistic registration algorithm for object modeling and tracking. In many robotics applications, such as manipulation tasks, nonvisual information about the movement of the object is available, which we will combine with the visual information. Furthermore we do not only consider observations of the object, but we also take space into account which has been observed to not be part of the object. Furthermore we are computing a posterior distribution over the relative alignment and not a point estimate as typically done in for example Iterative Closest Point (ICP). To our knowledge no existing algorithm meets these three conditions and we thus derive a novel registration algorithm in a Bayesian framework. Experimental results suggest that the proposed methods perform favorably in comparison to PCL implementations of feature mapping and ICP, especially if nonvisual information is available.
Intelligent Health Recommendation System for Computer Users
Venue: arXiv cs.CV 2015
Year: 2015

The time people spend in front of computers has been increasing steadily due to the role computers play in modern society. Individuals who sit in front of computers for an extended period of time, specifically with improper postures may incur various health issues. In this work, individuals' behaviors in front of computers are studied using web cameras. By means of non-rigid face tracking system, data are analyzed to determine the 3D head pose, blink rate and yawn frequency of computer users. When combining these visual cues, a system of intelligent personal assistants for computer users is proposed.
Visual Information Retrieval in Endoscopic Video Archives
Venue: arXiv cs.IR 2015
Year: 2015

In endoscopic procedures, surgeons work with live video streams from the inside of their subjects. A main source for documentation of procedures are still frames from the video, identified and taken during the surgery. However, with growing demands and technical means, the streams are saved to storage servers and the surgeons need to retrieve parts of the videos on demand. In this submission we present a demo application allowing for video retrieval based on visual features and late fusion, which allows surgeons to re-find shots taken during the procedure.
An Optimal Algorithm for Tiling the Plane with a Translated Polyomino
Venue: arXiv cs.CG 2015
Year: 2015

We give a $O(n)$-time algorithm for determining whether translations of a polyomino with $n$ edges can tile the plane. The algorithm is also a $O(n)$-time algorithm for enumerating all such tilings that are also regular, and we prove that at most $Θ(n)$ such tilings exist.
Large-scale linear regression: Development of high-performance routines
Venue: arXiv cs.CE 2015
Year: 2015

In statistics, series of ordinary least squares problems (OLS) are used to study the linear correlation among sets of variables of interest; in many studies, the number of such variables is at least in the millions, and the corresponding datasets occupy terabytes of disk space. As the availability of large-scale datasets increases regularly, so does the challenge in dealing with them. Indeed, traditional solvers---which rely on the use of black-box" routines optimized for one single OLS---are highly inefficient and fail to provide a viable solution for big-data analyses. As a case study, in this paper we consider a linear regression consisting of two-dimensional grids of related OLS problems that arise in the context of genome-wide association analyses, and give a careful walkthrough for the development of {\sc ols-grid}, a high-performance routine for shared-memory architectures; analogous steps are relevant for tailoring OLS solvers to other applications. In particular, we first illustrate the design of efficient algorithms that exploit the structure of the OLS problems and eliminate redundant computations; then, we show how to effectively deal with datasets that do not fit in main memory; finally, we discuss how to cast the computation in terms of efficient kernels and how to achieve scalability. Importantly, each design decision along the way is justified by simple performance models. {\sc ols-grid} enables the solution of $10^{11}$ correlated OLS problems operating on terabytes of data in a matter of hours.
A Deep Learning Model for Structured Outputs with High-order Interaction
Venue: arXiv cs.LG 2015
Year: 2015

Many real-world applications are associated with structured data, where not only input but also output has interplay. However, typical classification and regression models often lack the ability of simultaneously exploring high-order interaction within input and that within output. In this paper, we present a deep learning model aiming to generate a powerful nonlinear functional mapping from structured input to structured output. More specifically, we propose to integrate high-order hidden units, guided discriminative pretraining, and high-order auto-encoders for this purpose. We evaluate the model with three datasets, and obtain state-of-the-art performances among competitive methods. Our current work focuses on structured output regression, which is a less explored area, although the model can be extended to handle structured label classification.
Automating Abstract Interpretation of Abstract Machines
Venue: arXiv cs.PL 2015
Year: 2015

Static program analysis is a valuable tool for any programming language that people write programs in. The prevalence of scripting languages in the world suggests programming language interpreters are relatively easy to write. Users of these languages lament their inability to analyze their code, therefore programming language analyzers are not easy to write. This thesis investigates a systematic method of creating abstract interpreters from traditional interpreters, called Abstracting Abstract Machines. Abstract interpreters are difficult to develop due to technical, theoretical, and pragmatic problems. Technical problems include engineering data structures and algorithms. I show that modest and simple changes to the mathematical presentation of abstract machines result in 1000 times better running time - just seconds for moderately sized programs. In the theoretical realm, abstraction can make correctness difficult to ascertain. I provide proof techniques for proving the correctness of regular, pushdown, and stack-inspecting pushdown models of abstract computation by leaving computational power to an external factor: allocation. Even if we don't trust the proof, we can run models concretely against test suites to better trust them. In the pragmatic realm, I show that the systematic process of abstracting abstract machines is automatable. I develop a meta-language for expressing abstract machines similar to other semantics engineering languages. The language's special feature is that it provides an interface to abstract allocation. The semantics guarantees that if allocation is finite, then the semantics is a sound and computable approximation of the concrete semantics.
Universal Compression of Power-Law Distributions
Venue: arXiv cs.IT 2015
Year: 2015

English words and the outputs of many other natural processes are well-known to follow a Zipf distribution. Yet this thoroughly-established property has never been shown to help compress or predict these important processes. We show that the expected redundancy of Zipf distributions of order $α>1$ is roughly the $1/α$ power of the expected redundancy of unrestricted distributions. Hence for these orders, Zipf distributions can be better compressed and predicted than was previously known. Unlike the expected case, we show that worst-case redundancy is roughly the same for Zipf and for unrestricted distributions. Hence Zipf distributions have significantly different worst-case and expected redundancies, making them the first natural distribution class shown to have such a difference.
Cooperative Interference Mitigation and Handover Management for Heterogeneous Cloud Small Cell Networks
Venue: arXiv cs.IT 2015
Year: 2015

Heterogeneous small cell network has attracted much attention to satisfy users' explosive data traffic requirements. Heterogeneous cloud small cell network (HCSNet), which combines cloud computing and heterogeneous small cell network, will likely play an important role in 5G mobile communication networks. However, with massive deployment of small cells, co-channel interference and handover management are two important problems in HCSNet, especially for cell edge users. In this article, we examine the problems of cooperative interference mitigation and handover management in HCSNet. A network architecture is described to combine cloud radio access network with small cells. An effective coordinated multi-point (CoMP) clustering scheme using affinity propagation is adopted to mitigate cell edge users' interference. A low complexity handover management scheme is presented, and its signaling procedure is analyzed in HCSNet. Numerical results show that the proposed network architecture, CoMP clustering scheme and handover management scheme can significantly increase the capacity of HCSNet while maintaining users' quality of service.
On Some Classes of $\mathbb{Z}_{2}\mathbb{Z}_{4}-$Linear Codes and their Covering Radius
Venue: arXiv cs.IT 2015
Year: 2015

In this paper we define $\mathbb{Z}_{2}\mathbb{Z}_{4}-$Simplex and MacDonald Codes of type $α$ and $β$ and we give the covering radius of these codes.
Detecting and ordering adjectival scalemates
Venue: arXiv cs.CL 2015
Year: 2015

This paper presents a pattern-based method that can be used to infer adjectival scales, such as <lukewarm, warm, hot>, from a corpus. Specifically, the proposed method uses lexical patterns to automatically identify and order pairs of scalemates, followed by a filtering phase in which unrelated pairs are discarded. For the filtering phase, several different similarity measures are implemented and compared. The model presented in this paper is evaluated using the current standard, along with a novel evaluation set, and shown to be at least as good as the current state-of-the-art.
Manipulation is Harder with Incomplete Votes
Venue: arXiv cs.AI 2015
Year: 2015

The Coalitional Manipulation (CM) problem has been studied extensively in the literature for many voting rules. The CM problem, however, has been studied only in the complete information setting, that is, when the manipulators know the votes of the non-manipulators. A more realistic scenario is an incomplete information setting where the manipulators do not know the exact votes of the non- manipulators but may have some partial knowledge of the votes. In this paper, we study a setting where the manipulators know a partial order for each voter that is consistent with the vote of that voter. In this setting, we introduce and study two natural computational problems - (1) Weak Manipulation (WM) problem where the manipulators wish to vote in a way that makes their preferred candidate win in at least one extension of the partial votes of the non-manipulators; (2) Strong Manipulation (SM) problem where the manipulators wish to vote in a way that makes their preferred candidate win in all possible extensions of the partial votes of the non-manipulators. We study the computational complexity of the WM and the SM problems for commonly used voting rules such as plurality, veto, k-approval, k-veto, maximin, Copeland, and Bucklin. Our key finding is that, barring a few exceptions, manipulation becomes a significantly harder problem in the setting of incomplete votes.
Refining Existential Properties in Separation Logic Analyses
Venue: arXiv cs.LO 2015
Year: 2015

In separation logic program analyses, tractability is generally achieved by restricting invariants to a finite abstract domain. As this domain cannot vary, loss of information can cause failure even when verification is possible in the underlying logic. In this paper, we propose a CEGAR-like method for detecting spurious failures and avoiding them by refining the abstract domain. Our approach is geared towards discovering existential properties, e.g. "list contains value x". To diagnose failures, we use abduction, a technique for inferring command preconditions. Our method works backwards from an error, identifying necessary information lost by abstraction, and refining the forward analysis to avoid the error. We define domains for several classes of existential properties, and show their effectiveness on case studies adapted from Redis, Azureus and FreeRTOS.
Revenue-Maximizing Mechanism Design for Quasi-Proportional Auctions
Venue: arXiv cs.GT 2015
Year: 2015

In quasi-proportional auctions, each bidder receives a fraction of the allocation equal to the weight of their bid divided by the sum of weights of all bids, where each bid's weight is determined by a weight function. We study the relationship between the weight function, bidders' private values, number of bidders, and the seller's revenue in equilibrium. It has been shown that if one bidder has a much higher private value than the others, then a nearly flat weight function maximizes revenue. Essentially, threatening the bidder who has the highest valuation with having to share the allocation maximizes the revenue. We show that as bidder private values approach parity, steeper weight functions maximize revenue by making the quasi-proportional auction more like a winner-take-all auction. We also show that steeper weight functions maximize revenue as the number of bidders increases. For flatter weight functions, there is known to be a unique pure-strategy Nash equilibrium. We show that a pure-strategy Nash equilibrium also exists for steeper weight functions, and we give lower bounds for bids at an equilibrium. For a special case that includes the two-bidder auction, we show that the pure-strategy Nash equilibrium is unique, and we show how to compute the revenue at equilibrium. We also show that selecting a weight function based on private value ratios and number of bidders is necessary for a quasi-proportional auction to produce more revenue than a second-price auction.
On the Structure, Covering, and Learning of Poisson Multinomial Distributions
Venue: arXiv cs.DS 2015
Year: 2015

An $(n,k)$-Poisson Multinomial Distribution (PMD) is the distribution of the sum of $n$ independent random vectors supported on the set ${\cal B}_k=\{e_1,\ldots,e_k\}$ of standard basis vectors in $\mathbb{R}^k$. We prove a structural characterization of these distributions, showing that, for all $\varepsilon >0$, any $(n, k)$-Poisson multinomial random vector is $\varepsilon$-close, in total variation distance, to the sum of a discretized multidimensional Gaussian and an independent $(\text{poly}(k/\varepsilon), k)$-Poisson multinomial random vector. Our structural characterization extends the multi-dimensional CLT of Valiant and Valiant, by simultaneously applying to all approximation requirements $\varepsilon$. In particular, it overcomes factors depending on $\log n$ and, importantly, the minimum eigenvalue of the PMD's covariance matrix from the distance to a multidimensional Gaussian random variable. We use our structural characterization to obtain an $\varepsilon$-cover, in total variation distance, of the set of all $(n, k)$-PMDs, significantly improving the cover size of Daskalakis and Papadimitriou, and obtaining the same qualitative dependence of the cover size on $n$ and $\varepsilon$ as the $k=2$ cover of Daskalakis and Papadimitriou. We further exploit this structure to show that $(n,k)$-PMDs can be learned to within $\varepsilon$ in total variation distance from $\tilde{O}_k(1/\varepsilon^2)$ samples, which is near-optimal in terms of dependence on $\varepsilon$ and independent of $n$. In particular, our result generalizes the single-dimensional result of Daskalakis, Diakonikolas, and Servedio for Poisson Binomials to arbitrary dimension.
Rule based lexicographical permutation sequences
Venue: arXiv cs.DS 2015
Year: 2015

In a permutation sequence built by means of sub permutations the transition between successive permutations are subject to a set of n(n - 1)/2 rules that group into n - 1 matrices with a high degree of regularity. By means of these rules the sequence can be produced in O(3n!) time and O(n^3) space.
FIFTH system for general-purpose connectionist computation
Venue: arXiv cs.AI 2015
Year: 2015

To date, work on formalizing connectionist computation in a way that is at least Turing-complete has focused on recurrent architectures and developed equivalences to Turing machines or similar super-Turing models, which are of more theoretical than practical significance. We instead develop connectionist computation within the framework of information propagation networks extended with unbounded recursion, which is related to constraint logic programming and is more declarative than the semantics typically used in practical programming, but is still formally known to be Turing-complete. This approach yields contributions to the theory and practice of both connectionist computation and programming languages. Connectionist computations are carried out in a way that lets them communicate with, and be understood and interrogated directly in terms of the high-level semantics of a general-purpose programming language. Meanwhile, difficult (unbounded-dimension, NP-hard) search problems in programming that have previously been left to the programmer to solve in a heuristic, domain-specific way are solved uniformly a priori in a way that approximately achieves information-theoretic limits on performance.
A Case Study on Quality Attribute Measurement using MARF and GIPSY
Venue: arXiv cs.SE 2015
Year: 2015

This literature focuses on doing a comparative analysis between Modular Audio Recognition Framework (MARF) and the General Intentional Programming System (GIPSY) with the help of different software metrics. At first, we understand the general principles, architecture and working of MARF and GIPSY by looking at their frameworks and running them in the Eclipse environment. Then, we study some of the important metrics including a few state of the art metrics and rank them in terms of their usefulness and their influence on the different quality attributes of a software. The quality attributes are viewed and computed with the help of the Logiscope and McCabe IQ tools. These tools perform a comprehensive analysis on the case studies and generate a quality report at the factor level, criteria level and metrics level. In next step, we identify the worst code at each of these levels, extract the worst code and provide recommendations to improve the quality. We implement and test some of the metrics which are ranked as the most useful metrics with a set of test cases in JDeodorant. Finally, we perform an analysis on both MARF and GIPSY by doing a fuzzy code scan using MARFCAT to find the list of weak and vulnerable classes.
Image Denoising using Optimally Weighted Bilateral Filters: A Sure and Fast Approach
Venue: arXiv cs.CV 2015
Year: 2015

The bilateral filter is known to be quite effective in denoising images corrupted with small dosages of additive Gaussian noise. The denoising performance of the filter, however, is known to degrade quickly with the increase in noise level. Several adaptations of the filter have been proposed in the literature to address this shortcoming, but often at a substantial computational overhead. In this paper, we report a simple pre-processing step that can substantially improve the denoising performance of the bilateral filter, at almost no additional cost. The modified filter is designed to be robust at large noise levels, and often tends to perform poorly below a certain noise threshold. To get the best of the original and the modified filter, we propose to combine them in a weighted fashion, where the weights are chosen to minimize (a surrogate of) the oracle mean-squared-error (MSE). The optimally-weighted filter is thus guaranteed to perform better than either of the component filters in terms of the MSE, at all noise levels. We also provide a fast algorithm for the weighted filtering. Visual and quantitative denoising results on standard test images are reported which demonstrate that the improvement over the original filter is significant both visually and in terms of PSNR. Moreover, the denoising performance of the optimally-weighted bilateral filter is competitive with the computation-intensive non-local means filter.
Finding the Median (Obliviously) with Bounded Space
Venue: arXiv cs.CC 2015
Year: 2015

We prove that any oblivious algorithm using space $S$ to find the median of a list of $n$ integers from $\{1,...,2n\}$ requires time $Ω(n \log\log_S n)$. This bound also applies to the problem of determining whether the median is odd or even. It is nearly optimal since Chan, following Munro and Raman, has shown that there is a (randomized) selection algorithm using only $s$ registers, each of which can store an input value or $O(\log n)$-bit counter, that makes only $O(\log\log_s n)$ passes over the input. The bound also implies a size lower bound for read-once branching programs computing the low order bit of the median and implies the analog of $P \ne NP \cap coNP$ for length $o(n \log\log n)$ oblivious branching programs.