OpenRaiser/Intern-Atlas huggingface dataset:
Stochastic Ordering of Fading Channels Through the Shannon Transform
Venue: arXiv cs.IT 2014
Year: 2014

A new stochastic order between two fading distributions is introduced. A fading channel dominates another in the ergodic capacity ordering sense, if the Shannon transform of the first is greater than that of the second at all values of average signal to noise ratio. It is shown that some parametric fading models such as the Nakagami-m, Rician, and Hoyt are distributions that are monotonic in their line of sight parameters with respect to the ergodic capacity order. Some operations under which the ergodic capacity order is preserved are also discussed. Through these properties of the ergodic capacity order, it is possible to compare under two different fading scenarios, the ergodic capacity of a composite system involving multiple fading links with coding/decoding capabilities only at the transmitter/receiver. Such comparisons can be made even in cases when a closed form expression for the ergodic capacity of the composite system is not analytically tractable. Applications to multiple access channels, and extensions to multiple-input multiple-output (MIMO) systems are also discussed.
Exploiting Independent Subformulas: A Faster Approximation Scheme for #k-SAT
Venue: arXiv cs.DS 2014
Year: 2014

We present an improvement on Thurley's recent randomized approximation scheme for #k-SAT where the task is to count the number of satisfying truth assignments of a Boolean function Φ given as an n-variable k-CNF. We introduce a novel way to identify independent substructures of Φ and can therefore reduce the size of the search space considerably. Our randomized algorithm works for any k. For #3-SAT, it runs in time O(ε^{-2}*1.51426^n), for #4-SAT, it runs in time O(ε^{-2}*1.60816^n), with error bound ε.
A polynomial-time approximation scheme for Euclidean Steiner forest
Venue: arXiv cs.CG 2014
Year: 2014

We give a randomized O(n polylog n)-time approximation scheme for the Steiner forest problem in the Euclidean plane. For every fixed eps > 0 and given n terminals in the plane with connection requests between some pairs of terminals, our scheme finds a (1 + eps)-approximation to the minimum-length forest that connects every requested pair of terminals.
Homology-based Distributed Coverage Hole Detection in Wireless Sensor Networks
Venue: arXiv cs.NI 2014
Year: 2014

Homology theory provides new and powerful solutions to address the coverage problems in wireless sensor networks (WSNs). They are based on algebraic objects, such as Cech complex and Rips complex. Cech complex gives accurate information about coverage quality but requires a precise knowledge of the relative locations of nodes. This assumption is rather strong and hard to implement in practical deployments. Rips complex provides an approximation of Cech complex. It is easier to build and does not require any knowledge of nodes location. This simplicity is at the expense of accuracy. Rips complex can not always detect all coverage holes. It is then necessary to evaluate its accuracy. This work proposes to use the proportion of the area of undiscovered coverage holes as performance criteria. Investigations show that it depends on the ratio between communication and sensing radii of a sensor. Closed-form expressions for lower and upper bounds of the accuracy are also derived. For those coverage holes which can be discovered by Rips complex, a homology-based distributed algorithm is proposed to detect them. Simulation results are consistent with the proposed analytical lower bound, with a maximum difference of 0.5%. Upper bound performance depends on the ratio of communication and sensing radii. Simulations also show that the algorithm can localize about 99% coverage holes in about 99% cases.
Situation-Aware Approach to Improve Context-based Recommender System
Venue: arXiv cs.IR 2014
Year: 2014

In this paper, we introduce a novel situation aware approach to improve a context based recommender system. To build situation aware user profiles, we rely on evidence issued from retrieval situations. A retrieval situation refers to the social spatio temporal context of the user when he interacts with the recommender system. A situation is represented as a combination of social spatio temporal concepts inferred from ontological knowledge given social group, location and time information. User's interests are inferred from past user's interaction with the recommender system related to the identified situations. They are represented using concepts issued from a domain ontology. We also propose a method to dynamically adapt the system to the user's interest's evolution.
Optimizing an Utility Function for Exploration / Exploitation Trade-off in Context-Aware Recommender System
Venue: arXiv cs.IR 2014
Year: 2014

In this paper, we develop a dynamic exploration/ exploitation (exr/exp) strategy for contextual recommender systems (CRS). Specifically, our methods can adaptively balance the two aspects of exr/exp by automatically learning the optimal tradeoff. This consists of optimizing a utility function represented by a linearized form of the probability distributions of the rewards of the clicked and the non-clicked documents already recommended. Within an offline simulation framework we apply our algorithms to a CRS and conduct an evaluation with real event log data. The experimental results and detailed analysis demonstrate that our algorithms outperform existing algorithms in terms of click-through-rate (CTR).
An Equivalence between the Lasso and Support Vector Machines
Venue: arXiv cs.LG 2014
Year: 2014

We investigate the relation of two fundamental tools in machine learning and signal processing, that is the support vector machine (SVM) for classification, and the Lasso technique used in regression. We show that the resulting optimization problems are equivalent, in the following sense. Given any instance of an $\ell_2$-loss soft-margin (or hard-margin) SVM, we construct a Lasso instance having the same optimal solutions, and vice versa. As a consequence, many existing optimization algorithms for both SVMs and Lasso can also be applied to the respective other problem instances. Also, the equivalence allows for many known theoretical insights for SVM and Lasso to be translated between the two settings. One such implication gives a simple kernelized version of the Lasso, analogous to the kernels used in the SVM setting. Another consequence is that the sparsity of a Lasso solution is equal to the number of support vectors for the corresponding SVM instance, and that one can use screening rules to prune the set of support vectors. Furthermore, we can relate sublinear time algorithms for the two problems, and give a new such algorithm variant for the Lasso. We also study the regularization paths for both methods.
Relay Selection for Simultaneous Information Transmission and Wireless Energy Transfer: A Tradeoff Perspective
Venue: arXiv cs.IT 2014
Year: 2014

In certain applications, relay terminals can be employed to simultaneously deliver information and energy to a designated receiver and a radio frequency (RF) energy harvester, respectively. In such scenarios, the relay that is preferable for information transmission does not necessarily coincide with the relay with the strongest channel to the energy harvester, since the corresponding channels fade independently. Relay selection thus entails a tradeoff between the efficiency of the information transfer to the receiver and the amount of energy transferred to the energy harvester. The study of this tradeoff is the subject on which this work mainly focuses. Specifically, we investigate the behavior of the ergodic capacity and the outage probability of the information transmission to the receiver, for a given amount of energy transferred to the RF energy harvester. We propose two relay selection methods that apply to any number of available relays. Furthermore, for the case of two relays, we develop the optimal relay selection method in a maximum capacity / minimum outage probability sense, for a given energy transfer constraint. A close-to-optimal selection method that is easier to analyze than the optimal one is also examined. Closed-form expressions for the capacity-energy and the outage-energy tradeoffs of the developed schemes are provided and corroborated by simulations. Interesting insights on the aforementioned tradeoffs are obtained.
Rate Gain Region and Design Tradeoffs for Full-Duplex Wireless Communications
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we analytically study the regime in which practical full-duplex systems can achieve larger rates than an equivalent half-duplex systems. The key challenge in practical full-duplex systems is uncancelled self-interference signal, which is caused by a combination of hardware and implementation imperfections. Thus, we first present a signal model which captures the effect of significant impairments such as oscillator phase noise, low-noise amplifier noise figure, mixer noise, and analog-to-digital converter quantization noise. Using the detailed signal model, we study the rate gain region, which is defined as the region of received signal-of-interest strength where full-duplex systems outperform half-duplex systems in terms of achievable rate. The rate gain region is derived as a piece-wise linear approximation in log-domain, and numerical results show that the approximation closely matches the exact region. Our analysis shows that when phase noise dominates mixer and quantization noise, full-duplex systems can use either active analog cancellation or base-band digital cancellation to achieve near-identical rate gain regions. Finally, as a design example, we numerically investigate the full-duplex system performance and rate gain region in typical indoor environments for practical wireless applications.
A Simple Algorithm for Global Value Numbering
Venue: arXiv cs.PL 2014
Year: 2014

Global Value Numbering(GVN) is a method for detecting redundant computations in programs. Here, we introduce the problem of Global Value Numbering in its original form, as conceived by Kildall(1973), and present an algorithm which is a simpler variant of Kildall's. The algorithm uses the concept of value expression - an abstraction of a set of expressions - enabling a representation of the equivalence information which is compact and simple to manipulate.
A Taxonomy of Hyperlink Hiding Techniques
Venue: arXiv cs.IR 2014
Year: 2014

Hidden links are designed solely for search engines rather than visitors. To get high search engine rankings, link hiding techniques are usually used for the profitability of black industries, such as illicit game servers, false medical services, illegal gambling, and less attractive high-profit industry, etc. This paper investigates hyperlink hiding techniques on the Web, and gives a detailed taxonomy. We believe the taxonomy can help develop appropriate countermeasures. Study on 5,583,451 Chinese sites' home pages indicate that link hidden techniques are very prevalent on the Web. We also tried to explore the attitude of Google towards link hiding spam by analyzing the PageRank values of relative links. The results show that more should be done to punish the hidden link spam.
Hybrid Q-Learning Applied to Ubiquitous recommender system
Venue: arXiv cs.LG 2014
Year: 2014

Ubiquitous information access becomes more and more important nowadays and research is aimed at making it adapted to users. Our work consists in applying machine learning techniques in order to bring a solution to some of the problems concerning the acceptance of the system by users. To achieve this, we propose a fundamental shift in terms of how we model the learning of recommender system: inspired by models of human reasoning developed in robotic, we combine reinforcement learning and case-base reasoning to define a recommendation process that uses these two approaches for generating recommendations on different context dimensions (social, temporal, geographic). We describe an implementation of the recommender system based on this framework. We also present preliminary results from experiments with the system and show how our approach increases the recommendation quality.
Application of Quantum Process Calculus to Higher Dimensional Quantum Protocols
Venue: arXiv cs.LO 2014
Year: 2014

We describe the use of quantum process calculus to describe and analyze quantum communication protocols, following the successful field of formal methods from classical computer science. We have extended the quantum process calculus to describe d-dimensional quantum systems, which has not been done before. We summarise the necessary theory in the generalisation of quantum gates and Bell states and use the theory to apply the quantum process calculus CQP to quantum protocols, namely qudit teleportation and superdense coding.
Separating linear forms for bivariate systems
Venue: arXiv cs.SC 2014
Year: 2014

We present an algorithm for computing a separating linear form of a system of bivariate polynomials with integer coefficients, that is a linear combination of the variables that takes different values when evaluated at distinct (complex) solutions of the system. In other words, a separating linear form defines a shear of the coordinate system that sends the algebraic system in generic position, in the sense that no two distinct solutions are vertically aligned. The computation of such linear forms is at the core of most algorithms that solve algebraic systems by computing rational parameterizations of the solutions and, moreover, the computation a separating linear form is the bottleneck of these algorithms, in terms of worst-case bit complexity. Given two bivariate polynomials of total degree at most $d$ with integer coefficients of bitsize at most~$τ$, our algorithm computes a separating linear form in $\sOB(d^{8}+d^7τ)$ bit operations in the worst case, where the previously known best bit complexity for this problem was $\sOB(d^{10}+d^9τ)$ (where $\sO$ refers to the complexity where polylogarithmic factors are omitted and $O_B$ refers to the bit complexity).
A Derivation of the Source-Channel Error Exponent using Non-identical Product Distributions
Venue: arXiv cs.IT 2014
Year: 2014

This paper studies the random-coding exponent of joint source-channel coding for a scheme where source messages are assigned to disjoint subsets (referred to as classes), and codewords are independently generated according to a distribution that depends on the class index of the source message. For discrete memoryless systems, two optimally chosen classes and product distributions are found to be sufficient to attain the sphere-packing exponent in those cases where it is tight.
Hardware Architecture for List SC Decoding of Polar Codes
Venue: arXiv cs.IT 2014
Year: 2014

We present a hardware architecture and algorithmic improvements for list SC decoding of polar codes. More specifically, we show how to completely avoid copying of the likelihoods, which is algorithmically the most cumbersome part of list SC decoding. The hardware architecture was synthesized for a blocklength of N = 1024 bits and list sizes L = 2, 4 using a UMC 90nm VLSI technology. The resulting decoder can achieve a coded throughput of 181 Mbps at a frequency of 459 MHz.
On the Gaussian Interference Channel with Half-Duplex Causal Cognition
Venue: arXiv cs.IT 2014
Year: 2014

This paper studies the two-user Gaussian interference channel with half-duplex causal cognition. This channel model consists of two source-destination pairs sharing a common wireless channel. One of the sources, referred to as the cognitive, overhears the other source, referred to as the primary, through a noisy link and can therefore assist in sending the primary's data. Due to practical constraints, the cognitive source is assumed to work in half-duplex mode, that is, it cannot simultaneously transmit and receive. This model is more relevant for practical cognitive radio systems than the classical information theoretic cognitive channel model, where the cognitive source is assumed to have a non-causal knowledge of the primary's message. Different network topologies are considered, corresponding to different interference scenarios: (i) the interference-symmetric scenario, where both destinations are in the coverage area of the two sources and hence experience interference, and (ii) the interference-asymmetric scenario, where one destination does not suffer from interference. For each topology the sum-rate performance is studied by first deriving the generalized Degrees of Freedom (gDoF), or "sum-capacity pre-log" in the high-SNR regime, and then showing relatively simple coding schemes that achieve a sum-rate upper bound to within a constant number of bits for any SNR. Finally, the gDoF of the channel is compared to that of the non-cooperative interference channel and to that of the non-causal cognitive channel to identify the parameter regimes where half-duplex causal cognition is useless in practice or attains its ideal ultimate limit, respectively.
Analytic Samplers and the Combinatorial Rejection Method
Venue: arXiv cs.DM 2014
Year: 2014

Boltzmann samplers, introduced by Duchon et al. in 2001, make it possible to uniformly draw approximate size objects from any class which can be specified through the symbolic method. This, through by evaluating the associated generating functions to obtain the correct branching probabilities. But these samplers require generating functions, in particular in the neighborhood of their sunglarity, which is a complex problem; they also require picking an appropriate tuning value to best control the size of generated objects. Although Pivoteau~\etal have brought a sweeping question to the first question, with the introduction of their Newton oracle, questions remain. By adapting the rejection method, a classical tool from the random, we show how to obtain a variant of the Boltzmann sampler framework, which is tolerant of approximation, even large ones. Our goal for this is twofold: this allows for exact sampling with approximate values; but this also allows much more flexibility in tuning samplers. For the class of simple trees, we will try to show how this could be used to more easily calibrate samplers.
Variation of "The effect of caching on a model of content and access provider revenues in information-centric networks"
Venue: arXiv cs.NI 2014
Year: 2014

This is a variation of the two-sided market model of [10]: Demand D is concave in \tilde{D} in (16) of [10] So, in (5) of [10] and after Theorem 2, take the parametric case 0 < a <1. Thus, demand D is both decreasing and concave in price p, and so the utilities (U=pD) are also concave in price. Also, herein a simpler illustrative demand-response model is used in Appendix A and B.
A chaotic image encryption scheme owning temp-value feedback
Venue: arXiv cs.CR 2014
Year: 2014

This paper presents a novel efficient chaotic image encryption scheme, in which the temp-value feedback mechanism is introduced to the permutation and diffusion procedures. Firstly, a simple trick is played to map the plain-image pixels to the initial condition of the Logistic map. Then, a pseudorandom number sequence (PRNS) is obtained from iterating the map. The permutation procedure is carried out by a permutation sequence which is generated by comparing the PRNS and its sorted version. The diffusion procedure is composed of two reversely executed rounds. During each round, the current plain-image pixel and the last cipher-image pixel are used to produce the current cipher-image pixel with the help of the Logistic map and a pseudorandom number generated by the Chen system. To enhance the efficiency, only expanded XOR operation and modulo 256 addition are employed during diffusion. Experimental results show that the new scheme owns a large key space and can resist the differential attack. It is also efficient.
A Generalized Online Mirror Descent with Applications to Classification and Regression
Venue: arXiv cs.LG 2014
Year: 2014

Online learning algorithms are fast, memory-efficient, easy to implement, and applicable to many prediction problems, including classification, regression, and ranking. Several online algorithms were proposed in the past few decades, some based on additive updates, like the Perceptron, and some on multiplicative updates, like Winnow. A unifying perspective on the design and the analysis of online algorithms is provided by online mirror descent, a general prediction strategy from which most first-order algorithms can be obtained as special cases. We generalize online mirror descent to time-varying regularizers with generic updates. Unlike standard mirror descent, our more general formulation also captures second order algorithms, algorithms for composite losses and algorithms for adaptive filtering. Moreover, we recover, and sometimes improve, known regret bounds as special cases of our analysis using specific regularizers. Finally, we show the power of our approach by deriving a new second order algorithm with a regret bound invariant with respect to arbitrary rescalings of individual features.
Detecting Directionality in Random Fields Using the Monogenic Signal
Venue: arXiv cs.IT 2014
Year: 2014

Detecting and analyzing directional structures in images is important in many applications since one-dimensional patterns often correspond to important features such as object contours or trajectories. Classifying a structure as directional or non-directional requires a measure to quantify the degree of directionality and a threshold, which needs to be chosen based on the statistics of the image. In order to do this, we model the image as a random field. So far, little research has been performed on analyzing directionality in random fields. In this paper, we propose a measure to quantify the degree of directionality based on the random monogenic signal, which enables a unique decomposition of a 2D signal into local amplitude, local orientation, and local phase. We investigate the second-order statistical properties of the monogenic signal for isotropic, anisotropic, and unidirectional random fields. We analyze our measure of directionality for finite-size sample images, and determine a threshold to distinguish between unidirectional and non-unidirectional random fields, which allows the automatic classification of images.
Faster sparse interpolation of straight-line programs
Venue: arXiv cs.SC 2014
Year: 2014

We give a new probabilistic algorithm for interpolating a "sparse" polynomial f given by a straight-line program. Our algorithm constructs an approximation f* of f, such that their difference probably has at most half the number of terms of f, then recurses on their difference. Our approach builds on previous work by Garg and Schost (2009), and Giesbrecht and Roche (2011), and is asymptotically more efficient in terms of the total cost of the probes required than previous methods, in many cases.
On the Reliability Function of the Discrete Memoryless Relay Channel
Venue: arXiv cs.IT 2014
Year: 2014

Bounds on the reliability function for the discrete memoryless relay channel are derived using the method of types. Two achievable error exponents are derived based on partial decode-forward and compress-forward which are well-known superposition block-Markov coding schemes. The derivations require combinations of the techniques involved in the proofs of Csiszár-Körner-Marton's packing lemma for the error exponent of channel coding and Marton's type covering lemma for the error exponent of source coding with a fidelity criterion. The decode-forward error exponent is evaluated on Sato's relay channel. From this example, it is noted that to obtain the fastest possible decay in the error probability for a fixed effective coding rate, one ought to optimize the number of blocks in the block-Markov coding scheme assuming the blocklength within each block is large. An upper bound on the reliability function is also derived using ideas from Haroutunian's lower bound on the error probability for point-to-point channel coding with feedback.