OpenRaiser/Intern-Atlas huggingface dataset:
Weakly Submodular Functions
Venue: arXiv cs.DM 2014
Year: 2014

Submodular functions are well-studied in combinatorial optimization, game theory and economics. The natural diminishing returns property makes them suitable for many applications. We study an extension of monotone submodular functions, which we call {\em weakly submodular functions}. Our extension includes some (mildly) supermodular functions. We show that several natural functions belong to this class and relate our class to some other recent submodular function extensions. We consider the optimization problem of maximizing a weakly submodular function subject to uniform and general matroid constraints. For a uniform matroid constraint, the "standard greedy algorithm" achieves a constant approximation ratio where the constant (experimentally) converges to 5.95 as the cardinality constraint increases. For a general matroid constraint, a simple local search algorithm achieves a constant approximation ratio where the constant (analytically) converges to 10.22 as the rank of the matroid increases.
Dynamic Hybrid Traffic Flow Modeling
Venue: arXiv cs.MA 2014
Year: 2014

A flow of moving agents can be observed at different scales. Thus, in traffic modeling, three levels are generally considered: the micro, meso and macro levels, representing respectively the interactions between vehicles, groups of vehicles sharing common properties (such as a common destination or a common localization) and flows of vehicles. Each approach is useful in a given context: micro and meso models allow to simulate road networks with complex topologies such as urban area, while macro models allow to develop control strategies to prevent congestion in highways. However, to simulate large-scale road networks, it can be interesting to integrate different representations, e.g., micro and macro, in a single model. Existing models share the same limitation: connections between levels are fixed a priori and cannot be changed at runtime. Therefore, to be able to observe some emerging phenomena such as congestion formation or to find the exact location of a jam in a large macro section, a dynamic hybrid modeling approach is needed. In 2013 we started the development of a multi-level agent-based simulator called JAM-FREE within the ISART project. It allows to simulate large road networks efficiently using a dynamic level of detail. This simulator relies on a multi-level agent-based modeling framework called SIMILAR.
On the capacity of the dither-quantized Gaussian channel
Venue: arXiv cs.IT 2014
Year: 2014

This paper studies the capacity of the peak-and-average-power-limited Gaussian channel when its output is quantized using a dithered, infinite-level, uniform quantizer of step size $Δ$. It is shown that the capacity of this channel tends to that of the unquantized Gaussian channel when $Δ$ tends to zero, and it tends to zero when $Δ$ tends to infinity. In the low signal-to-noise ratio (SNR) regime, it is shown that, when the peak-power constraint is absent, the low-SNR asymptotic capacity is equal to that of the unquantized channel irrespective of $Δ$. Furthermore, an expression for the low-SNR asymptotic capacity for finite peak-to-average-power ratios is given and evaluated in the low- and high-resolution limit. It is demonstrated that, in this case, the low-SNR asymptotic capacity converges to that of the unquantized channel when $Δ$ tends to zero, and it tends to zero when $Δ$ tends to infinity. Comparing these results with achievability results for (undithered) 1-bit quantization, it is observed that the dither reduces capacity in the low-precision limit, and it reduces the low-SNR asymptotic capacity unless the peak-to-average-power ratio is unbounded.
Slotted Aloha for Networked Base Stations
Venue: arXiv cs.IT 2014
Year: 2014

We study multiple base station, multi-access systems in which the user-base station adjacency is induced by geographical proximity. At each slot, each user transmits (is active) with a certain probability, independently of other users, and is heard by all base stations within the distance $r$. Both the users and base stations are placed uniformly at random over the (unit) area. We first consider a non-cooperative decoding where base stations work in isolation, but a user is decoded as soon as one of its nearby base stations reads a clean signal from it. We find the decoding probability and quantify the gains introduced by multiple base stations. Specifically, the peak throughput increases linearly with the number of base stations $m$ and is roughly $m/4$ larger than the throughput of a single-base station that uses standard slotted Aloha. Next, we propose a cooperative decoding, where the mutually close base stations inform each other whenever they decode a user inside their coverage overlap. At each base station, the messages received from the nearby stations help resolve collisions by the interference cancellation mechanism. Building from our exact formulas for the non-cooperative case, we provide a heuristic formula for the cooperative decoding probability that reflects well the actual performance. Finally, we demonstrate by simulation significant gains of cooperation with respect to the non-cooperative decoding.
On Efficiency and Validity of Previous Homeplug MAC Performance Analysis
Venue: arXiv cs.NI 2014
Year: 2014

The Medium Access Control protocol of Power Line Communication networks (defined in Homeplug and IEEE 1901 standards) has received relatively modest attention from the research community. As a consequence, there is only one analytic model that complies with the standardised MAC procedures and considers unsaturated conditions. We identify two important limitations of the existing analytic model: high computational expense and predicted results just prior to the predicted saturation point do not correspond to long-term network performance. In this work, we present a simplification of the previously defined analytic model of Homeplug MAC able to substantially reduce its complexity and demonstrate that the previous performance results just before predicted saturation correspond to a transitory phase. We determine that the causes of previous misprediction are common analytical assumptions and the potential occurrence of a transitory phase, that we show to be of extremely long duration under certain circumstances. We also provide techniques, both analytical and experimental, to correctly predict long-term behaviour and analyse the effect of specific Homeplug/IEEE 1901 features on the magnitude of misprediction errors.
Delayed Channel State Information: Incremental Redundancy with Backtrack Retransmission
Venue: arXiv cs.IT 2014
Year: 2014

In many practical wireless systems, the Signal-to-Interference-and-Noise Ratio (SINR) that is applicable to a certain transmission, referred to as Channel State Information (CSI), can only be learned after the transmission has taken place and is thereby outdated (delayed). For example, this occurs under intermittent interference. We devise the backward retransmission (BRQ) scheme, which uses the delayed CSIT to send the optimal amount of incremental redundancy (IR). BRQ uses fixed-length packets, fixed-rate R transmission codebook, and operates as Markov block coding, where the correlation between the adjacent packets depends on the amount of IR parity bits. When the delayed CSIT is full and R grows asymptotically, the average throughput of BRQ becomes equal to the value achieved with prior CSIT and a fixed-power transmitter; however, at the expense of increased delay. The second contribution is a method for employing BRQ when a limited number of feedback bits is available to report the delayed CSIT. The main novelty is the idea to assemble multiple feedback opportunities and report multiple SINRs through vector quantization. This challenges the conventional wisdom in ARQ protocols where feedback bits are used to only quantize the CSIT of the immediate previous transmission.
Computing the Kullback-Leibler Divergence between two Generalized Gamma Distributions
Venue: arXiv cs.IT 2014
Year: 2014

We derive a closed form solution for the Kullback-Leibler divergence between two generalized gamma distributions. These notes are meant as a reference and provide a guided tour towards a result of practical interest that is rarely explicated in the literature.
Internet of Things: Concept, Building blocks, Applications and Challenges
Venue: arXiv cs.CY 2014
Year: 2014

Internet of things (IoT) constitutes one of the most important technology that has the potential to affect deeply our way of life, after mobile phones and Internet. The basic idea is that every objet that is around us will be part of the network (Internet), interacting to reach a common goal. In another word, the Internet of Things concept aims to link the physical world to the digital one. Technology advances along with popular demand will foster the wide spread deployement of IoT's services, it would radically transform our corporations, communities, and personal spheres. In this survey, we aim to provide the reader with a broad overview of the Internet of things concept, its building blocks, its applications along with its challenges.
Compressive Classification of a Mixture of Gaussians: Analysis, Designs and Geometrical Interpretation
Venue: arXiv cs.IT 2014
Year: 2014

This paper derives fundamental limits on the performance of compressive classification when the source is a mixture of Gaussians. It provides an asymptotic analysis of a Bhattacharya based upper bound on the misclassification probability for the optimal Maximum-A-Posteriori (MAP) classifier that depends on quantities that are dual to the concepts of diversity-order and coding gain in multi-antenna communications. The diversity-order of the measurement system determines the rate at which the probability of misclassification decays with signal-to-noise ratio (SNR) in the low-noise regime. The counterpart of coding gain is the measurement gain which determines the power offset of the probability of misclassification in the low-noise regime. These two quantities make it possible to quantify differences in misclassification probability between random measurement and (diversity-order) optimized measurement. Results are presented for two-class classification problems first with zero-mean Gaussians then with nonzero-mean Gaussians, and finally for multiple-class Gaussian classification problems. The behavior of misclassification probability is revealed to be intimately related to certain fundamental geometric quantities determined by the measurement system, the source and their interplay. Numerical results, representative of compressive classification of a mixture of Gaussians, demonstrate alignment of the actual misclassification probability with the Bhattacharya based upper bound. The connection between the misclassification performance and the alignment between source and measurement geometry may be used to guide the design of dictionaries for compressive classification.
Polar Codes for Some Multi-terminal Communications Problems
Venue: arXiv cs.IT 2014
Year: 2014

It is shown that polar coding schemes achieve the known achievable rate regions for several multi-terminal communications problems including lossy distributed source coding, multiple access channels and multiple descriptions coding. The results are valid for arbitrary alphabet sizes (binary or nonbinary) and arbitrary distributions (symmetric or asymmetric).
Phase Precoded Compute-and-Forward with Partial Feedback
Venue: arXiv cs.IT 2014
Year: 2014

In this work, we propose phase precoding for the compute-and-forward (CoF) protocol. We derive the phase precoded computation rate and show that it is greater than the original computation rate of CoF protocol without precoder. To maximize the phase precoded computation rate, we need to 'jointly' find the optimum phase precoding matrix and the corresponding network equation coefficients. This is a mixed integer programming problem where the optimum precoders should be obtained at the transmitters and the network equation coefficients have to be computed at the relays. To solve this problem, we introduce phase precoded CoF with partial feedback. It is a quantized precoding system where the relay jointly computes both a quasi-optimal precoder from a finite codebook and the corresponding network equations. The index of the obtained phase precoder within the codebook will then be fedback to the transmitters. A "deep hole phase precoder" is presented as an example of such a scheme. We further simulate our scheme with a lattice code carved out of the Gosset lattice and show that significant coding gains can be obtained in terms of equation error performance.
Probably Safe or Live
Venue: arXiv cs.LO 2014
Year: 2014

This paper presents a formal characterisation of safety and liveness properties à la Alpern and Schneider for fully probabilistic systems. As for the classical setting, it is established that any (probabilistic tree) property is equivalent to a conjunction of a safety and liveness property. A simple algorithm is provided to obtain such property decomposition for flat probabilistic CTL (PCTL). A safe fragment of PCTL is identified that provides a sound and complete characterisation of safety properties. For liveness properties, we provide two PCTL fragments, a sound and a complete one. We show that safety properties only have finite counterexamples, whereas liveness properties have none. We compare our characterisation for qualitative properties with the one for branching time properties by Manolios and Trefler, and present sound and complete PCTL fragments for characterising the notions of strong safety and absolute liveness coined by Sistla.
Visualizing Cognitive Moves for Assessing Information Perception Biases in Decision Making
Venue: arXiv cs.HC 2014
Year: 2014

In decision making a key source of uncertainty is people's perception of information which is influenced by their attitudes toward risk. Both, perception of information and risk attitude, affect the interpretation of information and hence the choice of suitable courses of action in a variety of contexts ranging from project planning to military operations. Visualization associated with the dynamics of cognitive states of people processing information and making decision is therefore not only important for analysis but has also significant practical applications, in particular in the military command and control domain. In this paper, we focus on a major concept that affect human cognition in this context: reliability of information. We introduce Cognitive Move Diagrams (CMD)---a simple visualization tool---to represent and evaluate the impact of this concept on decision making. We demonstrate through both a hypothetical example and a subject matter expert based experiment that CMD are effective in visualizing, detecting and qualifying human biases.
Two Models of Nonadaptive Group Testing for Designing Screening Experiments
Venue: arXiv cs.IT 2014
Year: 2014

We discuss two non-standard models of nonadaptive combinatorial search which develop the conventional disjunct search model for a small number of defective elements contained in a finite ground set or a population. The first model is called a search of defective supersets. The second model is called a search of defective subsets in the presence of inhibitors. For these models, we study the constructive search methods based on the known constructions for the disjunct model.
Information quantity in a pixel of digital image
Venue: arXiv cs.CV 2014
Year: 2014

The paper is devoted to the problem of integer-valued estimating of information quantity in a pixel of digital image. The definition of an integer estimation of information quantity based on constructing of the certain binary hierarchy of pixel clusters is proposed. The methods for constructing hierarchies of clusters and generating of hierarchical sequences of image approximations that minimally differ from the image by a standard deviation are developed. Experimental results on integer-valued estimation of information quantity are compared with the results obtained by utilizing of the classical formulas.
Excel 2013 Spreadsheet Inquire
Venue: arXiv cs.SE 2014
Year: 2014

Excel 2013 (version 15) includes an add-in "Inquire" for auditing spreadsheets. We describe the evolution of such tools in the third-party marketplace and assess the usefulness of Microsoft's own add-in in this context. We compare in detail the features of Inquire with similar products and make suggestions for how it could be enhanced. We offer a free helper add-in that in our opinion corrects one major shortcoming of Inquire.
Experimental Evaluation of Algorithms for the Food-Selection Problem
Venue: arXiv cs.DS 2014
Year: 2014

In this paper, we describe the result of our experiments on Algorithms for the Food-Selection Problem, which is the fundamental problem first stated and addressed in the seminal paper \cite{pigout}. Because the key aspect of any experimental evaluation is the \textbf{reproducibility}, we detail deeply the setup of all our experiments, thus leaving to the interested eater the opportunity to reproduce all the results described in this paper. More specifically, we describe all the answers we provided to the questions proposed in \cite{pigout}: Where can I have dinner tonight? What is the typical Roman cuisine that I should (not) miss? Where can I find the best coffee or gelato in town?
Mathematical Modelling of Turning Delays in Swarm Robotics
Venue: arXiv cs.RO 2014
Year: 2014

We investigate the effect of turning delays on the behaviour of groups of differential wheeled robots and show that the group-level behaviour can be described by a transport equation with a suitably incorporated delay. The results of our mathematical analysis are supported by numerical simulations and experiments with e-puck robots. The experimental quantity we compare to our revised model is the mean time for robots to find the target area in an unknown environment. The transport equation with delay better predicts the mean time to find the target than the standard transport equation without delay.
Controlling a Software-Defined Network via Distributed Controllers
Venue: arXiv cs.NI 2014
Year: 2014

In this paper, we propose a distributed OpenFlow controller and an associated coordination framework that achieves scalability and reliability even under heavy data center loads. The proposed framework, which is designed to work with all existing OpenFlow controllers with minimal or no required changes, provides support for dynamic addition and removal of controllers to the cluster without any interruption to the network operation. We demonstrate performance results of the proposed framework implemented over an experimental testbed that uses controllers running Beacon.
A Generalized Probabilistic Framework for Compact Codebook Creation
Venue: arXiv cs.CV 2014
Year: 2014

Compact and discriminative visual codebooks are preferred in many visual recognition tasks. In the literature, a number of works have taken the approach of hierarchically merging visual words of an initial large-sized codebook, but implemented this approach with different merging criteria. In this work, we propose a single probabilistic framework to unify these merging criteria, by identifying two key factors: the function used to model class-conditional distribution and the method used to estimate the distribution parameters. More importantly, by adopting new distribution functions and/or parameter estimation methods, our framework can readily produce a spectrum of novel merging criteria. Three of them are specifically focused in this work. In the first criterion, we adopt the multinomial distribution with Bayesian method; In the second criterion, we integrate Gaussian distribution with maximum likelihood parameter estimation. In the third criterion, which shows the best merging performance, we propose a max-margin-based parameter estimation method and apply it with multinomial distribution. Extensive experimental study is conducted to systematically analyse the performance of the above three criteria and compare them with existing ones. As demonstrated, the best criterion obtained in our framework achieves the overall best merging performance among the comparable merging criteria developed in the literature.
Optimal power control in Cognitive MIMO systems with limited feedback
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, the problem of optimal power allocation in Cognitive Radio (CR) Multiple Input Multiple Output (MIMO) systems is treated. The focus is on providing limited feedback solutions aiming at maximizing the secondary system rate subject to a constraint on the average interference caused to primary communication. The limited feedback solutions are obtained by reducing the information available at secondary transmitter (STx) for the link between STx and the secondary receiver (SRx) as well as by limiting the level of available information at STx that corresponds to the link between the STx and the primary receiver PRx. Monte Carlo simulation results are given that allow to quanitfy the performance achieved by the proposed algorithms.
Loopy annealing belief propagation for vertex cover and matching: convergence, LP relaxation, correctness and Bethe approximation
Venue: arXiv cs.DM 2014
Year: 2014

For the minimum cardinality vertex cover and maximum cardinality matching problems, the max-product form of belief propagation (BP) is known to perform poorly on general graphs. In this paper, we present an iterative loopy annealing BP (LABP) algorithm which is shown to converge and to solve a Linear Programming relaxation of the vertex cover or matching problem on general graphs. LABP finds (asymptotically) a minimum half-integral vertex cover (hence provides a 2-approximation) and a maximum fractional matching on any graph. We also show that LABP finds (asymptotically) a minimum size vertex cover for any bipartite graph and as a consequence compute the matching number of the graph. Our proof relies on some subtle monotonicity arguments for the local iteration. We also show that the Bethe free entropy is concave and that LABP maximizes it. Using loop calculus, we also give an exact (also intractable for general graphs) expression of the partition function for matching in term of the LABP messages which can be used to improve mean-field approximations.
Preserving Lagrangian structure in nonlinear model reduction with application to structural dynamics
Venue: arXiv cs.CE 2014
Year: 2014

This work proposes a model-reduction methodology that preserves Lagrangian structure (equivalently Hamiltonian structure) and achieves computational efficiency in the presence of high-order nonlinearities and arbitrary parameter dependence. As such, the resulting reduced-order model retains key properties such as energy conservation and symplectic time-evolution maps. We focus on parameterized simple mechanical systems subjected to Rayleigh damping and external forces, and consider an application to nonlinear structural dynamics. To preserve structure, the method first approximates the system's `Lagrangian ingredients'---the Riemannian metric, the potential-energy function, the dissipation function, and the external force---and subsequently derives reduced-order equations of motion by applying the (forced) Euler--Lagrange equation with these quantities. From the algebraic perspective, key contributions include two efficient techniques for approximating parameterized reduced matrices while preserving symmetry and positive definiteness: matrix gappy POD and reduced-basis sparsification (RBS). Results for a parameterized truss-structure problem demonstrate the importance of preserving Lagrangian structure and illustrate the proposed method's merits: it reduces computation time while maintaining high accuracy and stability, in contrast to existing nonlinear model-reduction techniques that do not preserve structure.