OpenRaiser/Intern-Atlas huggingface dataset:
An Optimal Resource Allocation with Joint Carrier Aggregation in 4G-LTE
Venue: arXiv cs.NI 2015
Year: 2015

In this paper, we introduce a novel approach for optimal resource allocation from multiple carriers for users with elastic and inelastic traffic in fourth generation long term evolution (4G-LTE) system. In our model, we use logarithmic and sigmoidal-like utility functions to represent the user applications running on different user equipments (UE)s. We use utility proportional fairness policy, where the fairness among users is in utility percentage of the application running on the mobile station. Our objective is to allocate the resources to the users optimally from multiple carriers. In addition, every user subscribing for the mobile service is guaranteed to have a minimum quality-of-service (QoS) with a priority criterion. Our rate allocation algorithm selects the carrier or multiple carriers that provide the minimum price for the needed resources. We prove that the novel resource allocation optimization problem with joint carrier aggregation is convex and therefore the optimal solution is tractable. We present a distributed algorithm to allocate the resources optimally from multiple evolved NodeBs (eNodeB)s. Finally, we present simulation results for the performance of our rate allocation algorithm.
Artificial Wrestling: A Dynamical Formulation of Autonomous Agents Fighting in a Coupled Inverted Pendula Framework
Venue: arXiv cs.RO 2015
Year: 2015

We develop autonomous agents fighting with each other, inspired by human wrestling. For this purpose, we propose a coupled inverted pendula (CIP) framework in which: 1) tips of two inverted pendulums are linked by a connection rod, 2) each pendulum is primarily stabilized by a PD-controller, 3) and is additionally equipped with an intelligent controller. Based on this framework, we dynamically formulate an intelligent controller designed to store dynamical correspondence from initial states to final states of the CIP model, to receive state vectors of the model, and to output impulsive control forces to produce desired final states of the model. Developing a quantized and reduced order design of this controller, we have a practical control procedure based on an off-line learning method. We then conduct numerical simulations to investigate individual performance of the intelligent controller, showing that the performance can be improved by adding a delay element into the intelligent controller. The result shows that the performance depends not only on quantization resolutions of learning data but also on delay time of the delay element. Finally, we install the intelligent controllers into both pendulums in the proposed framework to demonstrate autonomous competitive behavior between inverted pendulums.
Towards Quality of Experience Determination for Video in Augmented Binocular Vision Scenarios
Venue: arXiv cs.MM 2015
Year: 2015

With the continuous growth in the consumer markets of mobile smartphones and increasingly in augmented reality wearable devices, several avenues of research investigate the relationships between the quality perceived by mobile users and the delivery mechanisms at play to support a high quality of experience for mobile users. In this paper, we present the first study that evaluates the relationships of mobile movie quality and the viewer-perceived quality thereof in an augmented reality setting with see-through devices. We find that participants tend to overestimate the video quality and exhibit a significant variation of accuracy that leans onto the movie content and its dynamics. Our findings, thus, can broadly impact future media adaptation and delivery mechanisms for this new display format of mobile multimedia.
Fast Matlab compatible sparse assembly on multicore computers
Venue: arXiv cs.DC 2015
Year: 2015

We develop and implement in this paper a fast sparse assembly algorithm, the fundamental operation which creates a compressed matrix from raw index data. Since it is often a quite demanding and sometimes critical operation, it is of interest to design a highly efficient implementation. We show how to do this, and moreover, we show how our implementation can be parallelized to utilize the power of modern multicore computers. Our freely available code, fully Matlab compatible, achieves about a factor of 5 times in speedup on a typical 6-core machine and 10 times on a dual-socket 16 core machine compared to the built-in serial implementation.
Probabilistic bounded reachability for hybrid systems with continuous nondeterministic and probabilistic parameters
Venue: arXiv cs.LO 2015
Year: 2015

We develop an algorithm for computing bounded reachability probability for hybrid systems, i.e., the probability that the system reaches an unsafe region within a finite number of discrete transitions. In particular, we focus on hybrid systems with continuous dynamics given by solutions of nonlinear ordinary differential equations (with possibly nondeterministic initial conditions and parameters), and probabilistic behaviour given by initial parameters distributed as continuous (with possibly infinite support) and discrete random variables. Our approach is to define an appropriate relaxation of the (undecidable) reachability problem, so that it can be solved by $δ$-complete decision procedures. In particular, for systems with continuous random parameters only, we develop a validated integration procedure which computes an arbitrarily small interval that is guaranteed to contain the reachability probability. In the more general case of systems with both nondeterministic and probabilistic parameters, our procedure computes a guaranteed enclosure for the range of reachability probabilities. We have applied our approach to a number of nonlinear hybrid models and validated the results by comparison with Monte Carlo simulation.
Identification of Patient Zero in Static and Temporal Networks - Robustness and Limitations
Venue: arXiv cs.SI 2015
Year: 2015

Detection of patient-zero can give new insights to the epidemiologists about the nature of first transmissions into a population. In this paper, we study the statistical inference problem of detecting the source of epidemics from a snapshot of spreading on an arbitrary network structure. By using exact analytic calculations and Monte Carlo estimators, we demonstrate the detectability limits for the SIR model, which primarily depend on the spreading process characteristics. Finally, we demonstrate the applicability of the approach in a case of a simulated sexually transmitted infection spreading over an empirical temporal network of sexual interactions.
A Clustering Analysis of Tweet Length and its Relation to Sentiment
Venue: arXiv cs.CL 2015
Year: 2015

Sentiment analysis of Twitter data is performed. The researcher has made the following contributions via this paper: (1) an innovative method for deriving sentiment score dictionaries using an existing sentiment dictionary as seed words is explored, and (2) an analysis of clustered tweet sentiment scores based on tweet length is performed.
Entropy compression method applied to graph colorings
Venue: arXiv cs.DM 2015
Year: 2015

Based on the algorithmic proof of Lovász local lemma due to Moser and Tardos, the works of Grytczuk et al. on words, and Dujmović et al. on colorings, Esperet and Parreau developed a framework to prove upper bounds for several chromatic numbers (in particular acyclic chromatic index, star chromatic number and Thue chromatic number) using the so-called \emph{entropy compression method}. Inspired by this work, we propose a more general framework and a better analysis. This leads to improved upper bounds on chromatic numbers and indices. In particular, every graph with maximum degree $Δ$ has an acyclic chromatic number at most $\frac{3}{2}Δ^{\frac43} + O(Δ)$. Also every planar graph with maximum degree $Δ$ has a facial Thue choice number at most $Δ+ O(Δ^\frac 12)$ and facial Thue choice index at most $10$.
Modeling and Control of High-Voltage Direct-Current Transmission Systems: From Theory to Practice and Back
Venue: arXiv cs.SY 2015
Year: 2015

The problem of modeling and control of multi-terminal high-voltage direct-current transmission systems is addressed in this paper, which contains five main contributions. First, to propose a unified, physically motivated, modeling framework - based on port-Hamiltonian representations - of the various network topologies used in this application. Second, to prove that the system can be globally asymptotically stabilized with a decentralized PI control, that exploits its passivity properties. Close connections between the proposed PI and the popular Akagi's PQ instantaneous power method are also established. Third, to reveal the transient performance limitations of the proposed controller that, interestingly, is shown to be intrinsic to PI passivity-based control. Fourth, motivated by the latter, an outer-loop that overcomes the aforementioned limitations is proposed. The performance limitation of the PI, and its drastic improvement using outer-loop controls, are verified via simulations on a three-terminals benchmark example. A final contribution is a novel formulation of the power flow equations for the centralized references calculation.
3DTouch: A wearable 3D input device with an optical sensor and a 9-DOF inertial measurement unit
Venue: arXiv cs.HC 2015
Year: 2015

We present 3DTouch, a novel 3D wearable input device worn on the fingertip for 3D manipulation tasks. 3DTouch is designed to fill the missing gap of a 3D input device that is self-contained, mobile, and universally working across various 3D platforms. This paper presents a low-cost solution to designing and implementing such a device. Our approach relies on relative positioning technique using an optical laser sensor and a 9-DOF inertial measurement unit. 3DTouch is self-contained, and designed to universally work on various 3D platforms. The device employs touch input for the benefits of passive haptic feedback, and movement stability. On the other hand, with touch interaction, 3DTouch is conceptually less fatiguing to use over many hours than 3D spatial input devices. We propose a set of 3D interaction techniques including selection, translation, and rotation using 3DTouch. An evaluation also demonstrates the device's tracking accuracy of 1.10 mm and 2.33 degrees for subtle touch interaction in 3D space. Modular solutions like 3DTouch opens up a whole new design space for interaction techniques to further develop on.
Frame Based Precoding in Satellite Communications: A Multicast Approach
Venue: arXiv cs.IT 2015
Year: 2015

In the present work, a multibeam satellite that employs aggressive frequency reuse towards increasing the offered throughput is considered. Focusing on the forward link, the goal is to employ multi-antenna signal processing techniques, namely linear precoding, to manage the inter-beam interferences. In this context, fundamental practical limitations, namely the rigid framing structure of satellite communication standards and the on-board per-antenna power constraints, are herein considered. Therefore, the concept of optimal frame based precoding under per-antenna constraints, is discussed. This consists in precoding the transmit signals without changing the underlying framing structure of the communication standard. In the present work, the connection of the frame based precoding problem with the generic signal processing problem of conveying independent sets of common data to distinct groups of users is established. This model is known as physical layer multicasting to multiple co-channel groups. Building on recent results, the weighted fair per-antenna power constrained multigroup multicast precoders are employed for frame based precoding. The throughput performance of these solutions is compared to multicast aware heuristic precoding methods over a realistic multibeam satellite scenario. Consequently, the gains of the proposed approach are quantified via extensive numerical results.
Multicast Multigroup Precoding and User Scheduling for Frame-Based Satellite Communications
Venue: arXiv cs.IT 2015
Year: 2015

The present work focuses on the forward link of a broadband multibeam satellite system that aggressively reuses the user link frequency resources. Two fundamental practical challenges, namely the need to frame multiple users per transmission and the per-antenna transmit power limitations, are addressed. To this end, the so-called frame-based precoding problem is optimally solved using the principles of physical layer multicasting to multiple co-channel groups under per-antenna constraints. In this context, a novel optimization problem that aims at maximizing the system sum rate under individual power constraints is proposed. Added to that, the formulation is further extended to include availability constraints. As a result, the high gains of the sum rate optimal design are traded off to satisfy the stringent availability requirements of satellite systems. Moreover, the throughput maximization with a granular spectral efficiency versus SINR function, is formulated and solved. Finally, a multicast-aware user scheduling policy, based on the channel state information, is developed. Thus, substantial multiuser diversity gains are gleaned. Numerical results over a realistic simulation environment exhibit as much as 30% gains over conventional systems, even for 7 users per frame, without modifying the framing structure of legacy communication standards.
A Data-Driven Approach for Tag Refinement and Localization in Web Videos
Venue: arXiv cs.CV 2015
Year: 2015

Tagging of visual content is becoming more and more widespread as web-based services and social networks have popularized tagging functionalities among their users. These user-generated tags are used to ease browsing and exploration of media collections, e.g. using tag clouds, or to retrieve multimedia content. However, not all media are equally tagged by users. Using the current systems is easy to tag a single photo, and even tagging a part of a photo, like a face, has become common in sites like Flickr and Facebook. On the other hand, tagging a video sequence is more complicated and time consuming, so that users just tag the overall content of a video. In this paper we present a method for automatic video annotation that increases the number of tags originally provided by users, and localizes them temporally, associating tags to keyframes. Our approach exploits collective knowledge embedded in user-generated tags and web sources, and visual similarity of keyframes and images uploaded to social sites like YouTube and Flickr, as well as web sources like Google and Bing. Given a keyframe, our method is able to select on the fly from these visual sources the training exemplars that should be the most relevant for this test sample, and proceeds to transfer labels across similar images. Compared to existing video tagging approaches that require training classifiers for each tag, our system has few parameters, is easy to implement and can deal with an open vocabulary scenario. We demonstrate the approach on tag refinement and localization on DUT-WEBV, a large dataset of web videos, and show state-of-the-art results.
The Complexity of Reasoning with FODD and GFODD
Venue: arXiv cs.AI 2015
Year: 2015

Recent work introduced Generalized First Order Decision Diagrams (GFODD) as a knowledge representation that is useful in mechanizing decision theoretic planning in relational domains. GFODDs generalize function-free first order logic and include numerical values and numerical generalizations of existential and universal quantification. Previous work presented heuristic inference algorithms for GFODDs and implemented these heuristics in systems for decision theoretic planning. In this paper, we study the complexity of the computational problems addressed by such implementations. In particular, we study the evaluation problem, the satisfiability problem, and the equivalence problem for GFODDs under the assumption that the size of the intended model is given with the problem, a restriction that guarantees decidability. Our results provide a complete characterization placing these problems within the polynomial hierarchy. The same characterization applies to the corresponding restriction of problems in first order logic, giving an interesting new avenue for efficient inference when the number of objects is bounded. Our results show that for $Σ_k$ formulas, and for corresponding GFODDs, evaluation and satisfiability are $Σ_k^p$ complete, and equivalence is $Π_{k+1}^p$ complete. For $Π_k$ formulas evaluation is $Π_k^p$ complete, satisfiability is one level higher and is $Σ_{k+1}^p$ complete, and equivalence is $Π_{k+1}^p$ complete.
Approximation and Streaming Algorithms for Projective Clustering via Random Projections
Venue: arXiv cs.CG 2015
Year: 2015

Let $P$ be a set of $n$ points in $\mathbb{R}^d$. In the projective clustering problem, given $k, q$ and norm $ρ\in [1,\infty]$, we have to compute a set $\mathcal{F}$ of $k$ $q$-dimensional flats such that $(\sum_{p\in P}d(p, \mathcal{F})^ρ)^{1/ρ}$ is minimized; here $d(p, \mathcal{F})$ represents the (Euclidean) distance of $p$ to the closest flat in $\mathcal{F}$. We let $f_k^q(P,ρ)$ denote the minimal value and interpret $f_k^q(P,\infty)$ to be $\max_{r\in P}d(r, \mathcal{F})$. When $ρ=1,2$ and $\infty$ and $q=0$, the problem corresponds to the $k$-median, $k$-mean and the $k$-center clustering problems respectively. For every $0 < ε< 1$, $S\subset P$ and $ρ\ge 1$, we show that the orthogonal projection of $P$ onto a randomly chosen flat of dimension $O(((q+1)^2\log(1/ε)/ε^3) \log n)$ will $ε$-approximate $f_1^q(S,ρ)$. This result combines the concepts of geometric coresets and subspace embeddings based on the Johnson-Lindenstrauss Lemma. As a consequence, an orthogonal projection of $P$ to an $O(((q+1)^2 \log ((q+1)/ε)/ε^3) \log n)$ dimensional randomly chosen subspace $ε$-approximates projective clusterings for every $k$ and $ρ$ simultaneously. Note that the dimension of this subspace is independent of the number of clusters~$k$. Using this dimension reduction result, we obtain new approximation and streaming algorithms for projective clustering problems. For example, given a stream of $n$ points, we show how to compute an $ε$-approximate projective clustering for every $k$ and $ρ$ simultaneously using only $O((n+d)((q+1)^2\log ((q+1)/ε))/ε^3 \log n)$ space. Compared to standard streaming algorithms with $Ω(kd)$ space requirement, our approach is a significant improvement when the number of input points and their dimensions are of the same order of magnitude.
Mobility-Aware Uplink Interference Model for 5G Heterogeneous Networks
Venue: arXiv cs.IT 2015
Year: 2015

To meet the surging demand for throughput, 5G cellular networks need to be more heterogeneous and much denser, by deploying more and more small cells. In particular, the number of users in each small cell can change dramatically due to users' mobility, resulting in random and time varying uplink interference. This paper considers the uplink interference in a 5G heterogeneous network which is jointly covered by one macro cell and several small cells. Based on the Lévy flight moving model, a mobility-aware interference model is proposed to characterize the uplink interference from macro cell users to small cell users. In this model, the total uplink interference is characterized by its moment generating function, for both closed subscriber group (CSG) and open subscriber group (CSG) femto cells. In addition, the proposed interference model is a function of basic step length, which is a key velocity parameter of Lévy flights. It is shown by both theoretical analysis and simulation results that the proposed interference model provides a flexible way of evaluating the system performance in terms of success probability and average rate.
Capacity Approximations for Gaussian Relay Networks
Venue: arXiv cs.IT 2015
Year: 2015

Consider a Gaussian relay network where a source node communicates to a destination node with the help of several layers of relays. Recent work has shown that compress-and-forward based strategies can achieve the capacity of this network within an additive gap. Here, the relays quantize their received signals at the noise level and map them to random Gaussian codebooks. The resultant gap to capacity is independent of the SNRs of the channels in the network and the topology but is linear in the total number of nodes. In this paper, we provide an improved lower bound on the rate achieved by compress-and-forward based strategies (noisy network coding in particular) in arbitrary Gaussian relay networks, whose gap to capacity depends on the network not only through the total number of nodes but also through the degrees of freedom of the min cut of the network. We illustrate that for many networks, this refined lower bound can lead to a better approximation of the capacity. In particular, we demonstrate that it leads to a logarithmic rather than linear capacity gap in the total number of nodes for certain classes of layered networks. The improvement comes from quantizing the received signals of the relays at a resolution decreasing with the total number of nodes in the network. This suggests that the rule-of-thumb in literature of quantizing the received signals at the noise level can be highly suboptimal.
Probabilistic Group Testing under Sum Observations: A Parallelizable 2-Approximation for Entropy Loss
Venue: arXiv cs.IT 2015
Year: 2015

We consider the problem of group testing with sum observations and noiseless answers, in which we aim to locate multiple objects by querying the number of objects in each of a sequence of chosen sets. We study a probabilistic setting with entropy loss, in which we assume a joint Bayesian prior density on the locations of the objects and seek to choose the sets queried to minimize the expected entropy of the Bayesian posterior distribution after a fixed number of questions. We present a new non-adaptive policy, called the dyadic policy, show it is optimal among non-adaptive policies, and is within a factor of two of optimal among adaptive policies. This policy is quick to compute, its nonadaptive nature makes it easy to parallelize, and our bounds show it performs well even when compared with adaptive policies. We also study an adaptive greedy policy, which maximizes the one-step expected reduction in entropy, and show that it performs at least as well as the dyadic policy, offering greater query efficiency but reduced parallelism. Numerical experiments demonstrate that both procedures outperform a divide-and-conquer benchmark policy from the literature, called sequential bifurcation, and show how these procedures may be applied in a stylized computer vision problem.
A new algorithm for solving the rSUM problem
Venue: arXiv cs.DS 2015
Year: 2015

A determined algorithm is presented for solving the rSUM problem for any natural r with a sub-quadratic assessment of time complexity in some cases. In terms of an amount of memory used the obtained algorithm is the nlog^3(n) order. The idea of the obtained algorithm is based not considering integer numbers, but rather k (is a natural) successive bits of these numbers in the binary numeration system. It is shown that if a sum of integer numbers is equal to zero, then the sum of numbers presented by any k successive bits of these numbers must be sufficiently "close" to zero. This makes it possible to discard the numbers, which a fortiori, do not establish the solution.