OpenRaiser/Intern-Atlas huggingface dataset:
Managing Deadline-constrained Bag-of-Tasks Jobs on Hybrid Clouds
Venue: arXiv cs.DC 2016
Year: 2016

Outsourcing jobs to a public cloud is a cost-effective way to address the problem of satisfying the peak resource demand when the local cloud has insufficient resources. In this paper, we study on managing deadline-constrained bag-of-tasks jobs on hybrid clouds. We present a binary nonlinear programming (BNP) problem to model the hybrid cloud management where the utilization of physical machines (PMs) in the local cloud/cluster is maximized when the local resources are enough to satisfy the deadline constraints of jobs, while when not, the rent cost from the public cloud is minimized. To solve this BNP problem in polynomial time, we proposed a heuristic algorithm. Its main idea is assigning the task closest to its deadline to current core until the core cannot finish any task within its deadline. When there is no available core, the algorithm adds an available PM with most capacity or rents a new VM with highest cost-performance ratio. Extensive experimental results show that our heuristic algorithm saves 16.2%-76% rent cost and improves 47.3%-182.8% resource utilizations satisfying deadline constraints, compared with first fit decreasing algorithm.
GNU Radio Signal Processing Models for Dynamic Multi-User Burst Modems
Venue: arXiv cs.NI 2016
Year: 2016

This paper presents a modern method for implementing burst modems in GNU Radio. Since burst modems are widely used for multi-user channel access and sharing in non-broadcast radio systems, this capability is critical to the development of numerous waveforms in GNU Radio. We focus on making such systems easy to develop and adapt to wide classes of modems and computationally efficient at runtime. We use the GNU Radio Event Stream scheduler to demonstrate concise implementations of burst PSK and FSK modems in GNU Radio and compare this with alternate approaches which have been attempted in GNU Radio.
Architectural Impact on Performance of In-memory Data Analytics: Apache Spark Case Study
Venue: arXiv cs.DC 2016
Year: 2016

While cluster computing frameworks are continuously evolving to provide real-time data analysis capabilities, Apache Spark has managed to be at the forefront of big data analytics for being a unified framework for both, batch and stream data processing. However, recent studies on micro-architectural characterization of in-memory data analytics are limited to only batch processing workloads. We compare micro-architectural performance of batch processing and stream processing workloads in Apache Spark using hardware performance counters on a dual socket server. In our evaluation experiments, we have found that batch processing are stream processing workloads have similar micro-architectural characteristics and are bounded by the latency of frequent data access to DRAM. For data accesses we have found that simultaneous multi-threading is effective in hiding the data latencies. We have also observed that (i) data locality on NUMA nodes can improve the performance by 10% on average and(ii) disabling next-line L1-D prefetchers can reduce the execution time by up-to 14\% and (iii) multiple small executors can provide up-to 36\% speedup over single large executor.
Handover Management in Dense Cellular Networks: A Stochastic Geometry Approach
Venue: arXiv cs.NI 2016
Year: 2016

Cellular operators are continuously densifying their networks to cope with the ever-increasing capacity demand. Furthermore, an extreme densification phase for cellular networks is foreseen to fulfill the ambitious fifth generation (5G) performance requirements. Network densification improves spectrum utilization and network capacity by shrinking base stations' (BSs) footprints and reusing the same spectrum more frequently over the spatial domain. However, network densification also increases the handover (HO) rate, which may diminish the capacity gains for mobile users due to HO delays. In highly dense 5G cellular networks, HO delays may neutralize or even negate the gains offered by network densification. In this paper, we present an analytical paradigm, based on stochastic geometry, to quantify the effect of HO delay on the average user rate in cellular networks. To this end, we propose a flexible handover scheme to reduce HO delay in case of highly dense cellular networks. This scheme allows skipping the HO procedure with some BSs along users' trajectories. The performance evaluation and testing of this scheme for only single HO skipping shows considerable gains in many practical scenarios.
Caching and Delivery via Interference Elimination
Venue: arXiv cs.IT 2016
Year: 2016

We propose a new caching scheme where linear combinations of the file segments are cached at the users, for the cases where the number of files is no greater than the number of users. When a user requests a certain file in the delivery phase, the other file segments in the cached linear combinations can be viewed as interferences. The proposed scheme combines rank metric codes and maximum distance separable codes to facilitate the decoding and elimination of these interferences, and also to simultaneously deliver useful contents to the intended users. The performance of the proposed scheme can be explicitly evaluated, and we show that the tradeoff points achieved by this scheme can strictly improve known tradeoff inner bounds in the literature; for certain special cases, the new tradeoff points can be shown to be optimal.
A movie genre prediction based on Multivariate Bernoulli model and genre correlations
Venue: arXiv cs.IR 2016
Year: 2016

Movie ratings play an important role both in determining the likelihood of a potential viewer to watch the movie and in reflecting the current viewer satisfaction with the movie. They are available in several sources like the television guide, best-selling reference books, newspaper columns, and television programs. Furthermore, movie ratings are crucial for recommendation engines that track the behavior of all users and utilize the information to suggest items they might like. Movie ratings in most cases, thus, provide information that might be more important than movie feature-based data. It is intuitively appealing that information about the viewing preferences in movie genres is sufficient for predicting a genre of an unlabeled movie. In order to predict movie genres, we treat ratings as a feature vector, apply the Bernoulli event model to estimate the likelihood of a movies given genre, and evaluate the posterior probability of the genre of a given movie using the Bayes rule. The goal of the proposed technique is to efficiently use the movie ratings for the task of predicting movie genres. In our approach we attempted to answer the question: "Given the set of users who watched a movie, is it possible to predict the genre of a movie based on its ratings?" Our simulation results with MovieLens 100k data demonstrated the efficiency and accuracy of our proposed technique, achieving 59% prediction rate for exact prediction and 69% when including correlated genres.
Licensed-Assisted Access to Unlicensed Spectrum in LTE Release 13
Venue: arXiv cs.NI 2016
Year: 2016

Exploiting the unlicensed spectrum is considered by 3GPP as one promising solution to meet the ever-increasing traffic growth. As a result, one major enhancement for LTE in Release 13 has been to enable its operation in the unlicensed spectrum via Licensed-Assisted Access (LAA). In this article, we provide an overview of the Release 13 LAA technology including motivation, use cases, LTE enhancements for enabling the unlicensed band operation, and the coexistence evaluation results contributed by 3GPP participants.
Infinite Horizon Optimal Transmission Power Control for Remote State Estimation over Fading Channels
Venue: arXiv cs.SY 2016
Year: 2016

Jointly optimal transmission power control and remote estimation over an infinite horizon is studied. A sensor observes a dynamic process and sends its observations to a remote estimator over a wireless fading channel characterized by a time-homogeneous Markov chain. The successful transmission probability depends on both the channel gains and the transmission power used by the sensor. The transmission power control rule and the remote estimator should be jointly designed, aiming to minimize an infinite-horizon cost consisting of the power usage and the remote estimation error. A first question one may ask is: Does this joint optimization problem have a solution? We formulate the joint optimization problem as an average cost belief-state Markov decision process and answer the question by proving that there exists an optimal deterministic and stationary policy. We then show that when the monitored dynamic process is scalar, the optimal remote estimates depend only on the most recently received sensor observation, and the optimal transmission power is symmetric and monotonically increasing with respect to the innovation error.
"Knowing value" logic as a normal modal logic
Venue: arXiv cs.AI 2016
Year: 2016

Recent years witness a growing interest in nonstandard epistemic logics of "knowing whether", "knowing what", "knowing how", and so on. These logics are usually not normal, i.e., the standard axioms and reasoning rules for modal logic may be invalid. In this paper, we show that the conditional "knowing value" logic proposed by Wang and Fan \cite{WF13} can be viewed as a disguised normal modal logic by treating the negation of the Kv operator as a special diamond. Under this perspective, it turns out that the original first-order Kripke semantics can be greatly simplified by introducing a ternary relation $R_i^c$ in standard Kripke models, which associates one world with two $i$-accessible worlds that do not agree on the value of constant $c$. Under intuitive constraints, the modal logic based on such Kripke models is exactly the one studied by Wang and Fan (2013,2014}. Moreover, there is a very natural binary generalization of the "knowing value" diamond, which, surprisingly, does not increase the expressive power of the logic. The resulting logic with the binary diamond has a transparent normal modal system, which sharpens our understanding of the "knowing value" logic and simplifies some previously hard problems.
Music transcription modelling and composition using deep learning
Venue: arXiv cs.SD 2016
Year: 2016

We apply deep learning methods, specifically long short-term memory (LSTM) networks, to music transcription modelling and composition. We build and train LSTM networks using approximately 23,000 music transcriptions expressed with a high-level vocabulary (ABC notation), and use them to generate new transcriptions. Our practical aim is to create music transcription models useful in particular contexts of music composition. We present results from three perspectives: 1) at the population level, comparing descriptive statistics of the set of training transcriptions and generated transcriptions; 2) at the individual level, examining how a generated transcription reflects the conventions of a music practice in the training transcriptions (Celtic folk); 3) at the application level, using the system for idea generation in music composition. We make our datasets, software and sound examples open and available: \url{https://github.com/IraKorshunova/folk-rnn}.
Exploring Social Networks for Optimized User Association in Wireless Small Cell Networks with Device-to-Device Communications
Venue: arXiv cs.NI 2016
Year: 2016

In this paper, we propose a novel social network aware approach for user association in wireless small cell networks. The proposed approach exploits social relationships between user equipments (UEs) and their physical proximity to optimize the network throughput. We formulate the problem as a matching game between UEs and their serving nodes (SNs). In our proposed game, the serving node can be a small cell base station (SCBS) or an important node with device-to-device capabilities. In this game, the SCBSs and UEs maximize their respective utility functions capturing both the spatial and social structures of the network. We show that the proposed game belongs to the class of matching games with externalities. Subsequently, we propose a distributed algorithm using which the SCBSs and UEs interact and reach a stable matching. We show the convergence of the proposed algorithm and study the properties of the resulting matching. Simulation results show that the proposed socially-aware user association approach can efficiently offload traffic while yielding a significant gain reaching up to 63% in terms of data rates as compared to the classical (social-unaware) approach.
Enabling Relaying Over Heterogeneous Backhauls in the Uplink of Wireless Femtocell Networks
Venue: arXiv cs.NI 2016
Year: 2016

In this paper, we develop novel two-tier interference management strategies that enable macrocell users (MUEs) to improve their performance, with the help of open-access femtocells. To this end, we propose a rate-splitting technique using which the MUEs optimize their uplink transmissions by dividing their signals into two types: a coarse message that is intended for direct transmission to the macrocell base station and a fine message that is decoded by a neighboring femtocell and subsequently relayed over a heterogeneous (wireless/wired) backhaul. For deploying the proposed technique, we formulate a non-cooperative game between the MUEs in which each MUE can decide on its relaying femtocell while maximizing a utility function that captures both the achieved throughput and the expected backhaul delay. Simulation results show that the proposed approach yields up to 125% rate improvement and up to 2 times delay reduction with wired backhaul and, 150% rate improvement and up to 10 times delay reduction with wireless backhaul, relative to classical interference management approaches, with no cross-tier cooperation.
The Z-loss: a shift and scale invariant classification loss belonging to the Spherical Family
Venue: arXiv cs.LG 2016
Year: 2016

Despite being the standard loss function to train multi-class neural networks, the log-softmax has two potential limitations. First, it involves computations that scale linearly with the number of output classes, which can restrict the size of problems we are able to tackle with current hardware. Second, it remains unclear how close it matches the task loss such as the top-k error rate or other non-differentiable evaluation metrics which we aim to optimize ultimately. In this paper, we introduce an alternative classification loss function, the Z-loss, which is designed to address these two issues. Unlike the log-softmax, it has the desirable property of belonging to the spherical loss family (Vincent et al., 2015), a class of loss functions for which training can be performed very efficiently with a complexity independent of the number of output classes. We show experimentally that it significantly outperforms the other spherical loss functions previously investigated. Furthermore, we show on a word language modeling task that it also outperforms the log-softmax with respect to certain ranking scores, such as top-k scores, suggesting that the Z-loss has the flexibility to better match the task loss. These qualities thus makes the Z-loss an appealing candidate to train very efficiently large output networks such as word-language models or other extreme classification problems. On the One Billion Word (Chelba et al., 2014) dataset, we are able to train a model with the Z-loss 40 times faster than the log-softmax and more than 4 times faster than the hierarchical softmax.
Grasping versus Knitting: a Geometric Perspective
Venue: arXiv cs.RO 2016
Year: 2016

Grasping an object is a matter of first moving a prehensile organ at some position in the world, and then managing the contact relationship between the prehensile organ and the object. Once the contact relationship has been established and made stable, the object is part of the body and it can move in the world. As any action, the action of grasping is ontologically anchored in the physical space while the correlative movement originates in the space of the body. Evolution has found amazing solutions that allow organisms to rapidly and efficiently manage the relationship between their body and the world. It is then natural that roboticists consider taking inspiration of these natural solutions, while contributing to better understand their origin.
A Predictor-based Attitude and Position Estimation for Rigid Bodies Moving in Planar Space by using Delayed Landmark Measurements
Venue: arXiv cs.SY 2016
Year: 2016

This paper proposes a globally and exponentially convergent predictive observer for attitude and position estimation based on landmark measurements and velocity (angular and linear) readings. It is assumed that landmark measurements are available with time-delay. The maximum value of the sensor delay under which the estimation error converges to zero is calculated. Synthesis of the observer is based on a representation of rigid-body kinematics and sensor delay, formulated via ordinary and partial differential equations (ODE-PDE). Observability condition specifies necessary and sufficient landmark configuration for convergence of attitude and position estimation error to zero. Finally, for implementation purposes, a PDE-free realization of the predictive observer is proposed. Simulation results are presented to demonstrate performance and convergence properties of the predictive observer in case of a wheeled mobile robot.
On the Complexity of Solving Zero-Dimensional Polynomial Systems via Projection
Venue: arXiv cs.SC 2016
Year: 2016

Given a zero-dimensional polynomial system consisting of n integer polynomials in n variables, we propose a certified and complete method to compute all complex solutions of the system as well as a corresponding separating linear form l with coefficients of small bit size. For computing l, we need to project the solutions into one dimension along O(n) distinct directions but no further algebraic manipulations. The solutions are then directly reconstructed from the considered projections. The first step is deterministic, whereas the second step uses randomization, thus being Las-Vegas. The theoretical analysis of our approach shows that the overall cost for the two problems considered above is dominated by the cost of carrying out the projections. We also give bounds on the bit complexity of our algorithms that are exclusively stated in terms of the number of variables, the total degree and the bitsize of the input polynomials.
Sharp Bounds Between Two Rényi Entropies of Distinct Positive Orders
Venue: arXiv cs.IT 2016
Year: 2016

Many axiomatic definitions of entropy, such as the Rényi entropy, of a random variable are closely related to the $\ell_α$-norm of its probability distribution. This study considers probability distributions on finite sets, and examines the sharp bounds of the $\ell_β$-norm with a fixed $\ell_α$-norm, $α\neq β$, for $n$-dimensional probability vectors with an integer $n \ge 2$. From the results, we derive the sharp bounds of the Rényi entropy of positive order $β$ with a fixed Rényi entropy of another positive order $α$. As applications, we investigate sharp bounds of Ariomoto's mutual information of order $α$ and Gallager's random coding exponents for uniformly focusing channels under the uniform input distribution.
Strongly Refuting Random CSPs Below the Spectral Threshold
Venue: arXiv cs.DS 2016
Year: 2016

Random constraint satisfaction problems (CSPs) are known to exhibit threshold phenomena: given a uniformly random instance of a CSP with $n$ variables and $m$ clauses, there is a value of $m = Ω(n)$ beyond which the CSP will be unsatisfiable with high probability. Strong refutation is the problem of certifying that no variable assignment satisfies more than a constant fraction of clauses; this is the natural algorithmic problem in the unsatisfiable regime (when $m/n = ω(1)$). Intuitively, strong refutation should become easier as the clause density $m/n$ grows, because the contradictions introduced by the random clauses become more locally apparent. For CSPs such as $k$-SAT and $k$-XOR, there is a long-standing gap between the clause density at which efficient strong refutation algorithms are known, $m/n \ge \widetilde O(n^{k/2-1})$, and the clause density at which instances become unsatisfiable with high probability, $m/n = ω(1)$. In this paper, we give spectral and sum-of-squares algorithms for strongly refuting random $k$-XOR instances with clause density $m/n \ge \widetilde O(n^{(k/2-1)(1-δ)})$ in time $\exp(\widetilde O(n^δ))$ or in $\widetilde O(n^δ)$ rounds of the sum-of-squares hierarchy, for any $δ\in [0,1)$ and any integer $k \ge 3$. Our algorithms provide a smooth transition between the clause density at which polynomial-time algorithms are known at $δ= 0$, and brute-force refutation at the satisfiability threshold when $δ= 1$. We also leverage our $k$-XOR results to obtain strong refutation algorithms for SAT (or any other Boolean CSP) at similar clause densities. Our algorithms match the known sum-of-squares lower bounds due to Grigoriev and Schonebeck, up to logarithmic factors. Additionally, we extend our techniques to give new results for certifying upper bounds on the injective tensor norm of random tensors.
Constructive neural network learning
Venue: arXiv cs.LG 2016
Year: 2016

In this paper, we aim at developing scalable neural network-type learning systems. Motivated by the idea of "constructive neural networks" in approximation theory, we focus on "constructing" rather than "training" feed-forward neural networks (FNNs) for learning, and propose a novel FNNs learning system called the constructive feed-forward neural network (CFN). Theoretically, we prove that the proposed method not only overcomes the classical saturation problem for FNN approximation, but also reaches the optimal learning rate when the regression function is smooth, while the state-of-the-art learning rates established for traditional FNNs are only near optimal (up to a logarithmic factor). A series of numerical simulations are provided to show the efficiency and feasibility of CFN via comparing with the well-known regularized least squares (RLS) with Gaussian kernel and extreme learning machine (ELM).
Indoor Massive MIMO: Uplink Pilot Mitigation Using Channel State Information Map
Venue: arXiv cs.NI 2016
Year: 2016

Massive MIMO brings both motivations and challenges to develop the 5th generation Mobile wireless technology. The promising number of users and the high bitrate offered per unit area are challenged by uplink pilot contamination due to pilot reuse and a limited number of orthogonal pilot sequences. This paper proposes a solution to mitigate uplink pilot contamination in an indoor scenario where multi-cell share the same pool of pilot sequences, that are supposed to be less than the number of users. This can be done by reducing uplink pilots using Channel State Information (CSI) prediction. The proposed method is based on machine learning approach, where a quantized version of Channel State Information (QCSI) is learned during estimation session and stored at the Base Station (BS) to be exploited for future CSI prediction. The learned QCSI are represented by a weighted directed graph, which is responsible to monitor and predict the CSI of User Terminals (UTs) in the local cell. We introduce an online learning algorithm to create and update this graph which we call CSI map. Simulation results show an increase in the downlink sum-rate and a significant feedback reduction.