OpenRaiser/Intern-Atlas huggingface dataset:
Spectral and Energy Efficiency Trade-Offs in Cellular Networks
Venue: arXiv cs.IT 2015
Year: 2015

This paper presents a simple and effective method to study the spectral and energy efficiency (SE-EE) trade-off in cellular networks, an issue that has attracted significant recent interest in the wireless community. The proposed theoretical framework is based on an optimal radio resource allocation of transmit power and bandwidth for the downlink direction, applicable for an orthogonal cellular network. The analysis is initially focused on a single cell scenario, for which in addition to the solution of the main SE-EE optimization problem, it is proved that a traffic repartition scheme can also be adopted as a way to simplify this approach. By exploiting this interesting result along with properties of stochastic geometry, this work is extended to a more challenging multi-cell environment, where interference is shown to play an essential role and for this reason several interference reduction techniques are investigated. Special attention is also given to the case of low signal to noise ratio (SNR) and a way to evaluate the upper bound on EE in this regime is provided. This methodology leads to tractable analytical results under certain common channel properties, and thus allows the study of various models without the need for demanding system-level simulations.
Observability, Identifiability and Sensitivity of Vision-Aided Navigation
Venue: arXiv cs.RO 2015
Year: 2015

We analyze the observability of motion estimates from the fusion of visual and inertial sensors. Because the model contains unknown parameters, such as sensor biases, the problem is usually cast as a mixed identification/filtering, and the resulting observability analysis provides a necessary condition for any algorithm to converge to a unique point estimate. Unfortunately, most models treat sensor bias rates as noise, independent of other states including biases themselves, an assumption that is patently violated in practice. When this assumption is lifted, the resulting model is not observable, and therefore past analyses cannot be used to conclude that the set of states that are indistinguishable from the measurements is a singleton. In other words, the resulting model is not observable. We therefore re-cast the analysis as one of sensitivity: Rather than attempting to prove that the indistinguishable set is a singleton, which is not the case, we derive bounds on its volume, as a function of characteristics of the input and its sufficient excitation. This provides an explicit characterization of the indistinguishable set that can be used for analysis and validation purposes.
On Optimal Disc Covers and a New Characterization of the Steiner Center
Venue: arXiv cs.CG 2015
Year: 2015

Given N points in the plane $P_1 P_2...P_N$ and a location $Ω$, the union of discs with diameters $[ΩP_i], i = 1, 2,...N$ covers the convex hull of the points. The location $Ω_s$ minimizing the area covered by the union of discs, is shown to be the Steiner center of the convex hull of the points. Similar results for $d$-dimensional Euclidean space are conjectured.
Approximating the Stationary Probability of a Single State in a Markov chain
Venue: arXiv cs.DS 2015
Year: 2015

In this paper, we present a novel iterative Monte Carlo method for approximating the stationary probability of a single state of a positive recurrent Markov chain. We utilize the characterization that the stationary probability of a state $i$ is inversely proportional to the expected return time of a random walk beginning at $i$. Our method obtains an $ε$-multiplicative close estimate with probability greater than $1 - α$ using at most $\tilde{O}\left(t_{\text{mix}} \ln(1/α) / π_i ε^2 \right)$ simulated random walk steps on the Markov chain across all iterations, where $t_{\text{mix}}$ is the standard mixing time and $π_i$ is the stationary probability. In addition, the estimate at each iteration is guaranteed to be an upper bound with high probability, and is decreasing in expectation with the iteration count, allowing us to monitor the progress of the algorithm and design effective termination criteria. We propose a termination criteria which guarantees a $ε(1 + 4 \ln(2) t_{\text{mix}})$ multiplicative error performance for states with stationary probability larger than $Δ$, while providing an additive error for states with stationary probability less than $Δ\in (0,1)$. The algorithm along with this termination criteria uses at most $\tilde{O}\left(\frac{\ln(1/α)}{ε^2} \min\left(\frac{t_{\text{mix}}}{π_i}, \frac{1}{εΔ}\right)\right)$ simulated random walk steps, which is bounded by a constant with respect to the Markov Chain. We provide a tight analysis of our algorithm based on a locally weighted variant of the mixing time. Our results naturally extend for countably infinite state space Markov chains via Lyapunov function analysis.
Tight Bounds for the Price of Anarchy of Simultaneous First Price Auctions
Venue: arXiv cs.GT 2015
Year: 2015

We study the Price of Anarchy of simultaneous first-price auctions for buyers with submodular and subadditive valuations. The current best upper bounds for the Bayesian Price of Anarchy of these auctions are e/(e-1) [Syrgkanis and Tardos 2013] and 2 [Feldman et al. 2013], respectively. We provide matching lower bounds for both cases even for the case of full information and for mixed Nash equilibria via an explicit construction. We present an alternative proof of the upper bound of e/(e-1) for first-price auctions with fractionally subadditive valuations which reveals the worst-case price distribution, that is used as a building block for the matching lower bound construction. We generalize our results to a general class of item bidding auctions that we call bid-dependent auctions (including first-price auctions and all-pay auctions) where the winner is always the highest bidder and each bidder's payment depends only on his own bid. Finally, we apply our techniques to discriminatory price multi-unit auctions. We complement the results of [de Keijzer et al. 2013] for the case of subadditive valuations, by providing a matching lower bound of 2. For the case of submodular valuations, we provide a lower bound of 1.109. For the same class of valuations, we were able to reproduce the upper bound of e/(e-1) using our non-smooth approach.
Distributed Function Computation Over a Rooted Directed Tree
Venue: arXiv cs.IT 2015
Year: 2015

This paper establishes the rate region for a class of source coding function computation setups where sources of information are available at the nodes of a tree and where a function of these sources must be computed at the root. The rate region holds for any function as long as the sources' joint distribution satisfies a certain Markov criterion. This criterion is met, in particular, when the sources are independent. This result recovers the rate regions of several function computation setups. These include the point-to-point communication setting with arbitrary sources, the noiseless multiple access network with "conditionally independent sources," and the cascade network with Markovian sources.
Dependence space of matroids and its application to attribute reduction
Venue: arXiv cs.AI 2015
Year: 2015

Attribute reduction is a basic issue in knowledge representation and data mining. Rough sets provide a theoretical foundation for the issue. Matroids generalized from matrices have been widely used in many fields, particularly greedy algorithm design, which plays an important role in attribute reduction. Therefore, it is meaningful to combine matroids with rough sets to solve the optimization problems. In this paper, we introduce an existing algebraic structure called dependence space to study the reduction problem in terms of matroids. First, a dependence space of matroids is constructed. Second, the characterizations for the space such as consistent sets and reducts are studied through matroids. Finally, we investigate matroids by the means of the space and present two expressions for their bases. In a word, this paper provides new approaches to study attribute reduction.
A Computational Trichotomy for Connectivity of Boolean Satisfiability
Venue: arXiv cs.CC 2015
Year: 2015

For Boolean satisfiability problems, the structure of the solution space is characterized by the solution graph, where the vertices are the solutions, and two solutions are connected iff they differ in exactly one variable. In 2006, Gopalan et al. studied connectivity properties of the solution graph and related complexity issues for CSPs, motivated mainly by research on satisfiability algorithms and the satisfiability threshold. They proved dichotomies for the diameter of connected components and for the complexity of the st-connectivity question, and conjectured a trichotomy for the connectivity question. Building on this work, we here prove the trichotomy: Connectivity is either in P, coNP-complete, or PSPACE-complete. Also, we correct a minor mistake of Gopalan et al., which leads to a slight shift of the boundaries towards the hard side.
Measurement Analysis and Channel Modeling for TOA-Based Ranging in Tunnels
Venue: arXiv cs.IT 2015
Year: 2015

A robust and accurate positioning solution is required to increase the safety in GPS-denied environments. Although there is a lot of available research in this area, little has been done for confined environments such as tunnels. Therefore, we organized a measurement campaign in a basement tunnel of Linköping university, in which we obtained ultra-wideband (UWB) complex impulse responses for line-of-sight (LOS), and three non-LOS (NLOS) scenarios. This paper is focused on time-of-arrival (TOA) ranging since this technique can provide the most accurate range estimates, which are required for range-based positioning. We describe the measurement setup and procedure, select the threshold for TOA estimation, analyze the channel propagation parameters obtained from the power delay profile (PDP), and provide statistical model for ranging. According to our results, the rise-time should be used for NLOS identification, and the maximum excess delay should be used for NLOS error mitigation. However, the NLOS condition cannot be perfectly determined, so the distance likelihood has to be represented in a Gaussian mixture form. We also compared these results with measurements from a mine tunnel, and found a similar behavior.
Fair assignment of indivisible objects under ordinal preferences
Venue: arXiv cs.GT 2015
Year: 2015

We consider the discrete assignment problem in which agents express ordinal preferences over objects and these objects are allocated to the agents in a fair manner. We use the stochastic dominance relation between fractional or randomized allocations to systematically define varying notions of proportionality and envy-freeness for discrete assignments. The computational complexity of checking whether a fair assignment exists is studied for these fairness notions. We also characterize the conditions under which a fair assignment is guaranteed to exist. For a number of fairness concepts, polynomial-time algorithms are presented to check whether a fair assignment exists. Our algorithmic results also extend to the case of unequal entitlements of agents. Our NP-hardness result, which holds for several variants of envy-freeness, answers an open question posed by Bouveret, Endriss, and Lang (ECAI 2010). We also propose fairness concepts that always suggest a non-empty set of assignments with meaningful fairness properties. Among these concepts, optimal proportionality and optimal weak proportionality appear to be desirable fairness concepts.
On the Learning Behavior of Adaptive Networks - Part II: Performance Analysis
Venue: arXiv cs.MA 2015
Year: 2015

Part I of this work examined the mean-square stability and convergence of the learning process of distributed strategies over graphs. The results identified conditions on the network topology, utilities, and data in order to ensure stability; the results also identified three distinct stages in the learning behavior of multi-agent networks related to transient phases I and II and the steady-state phase. This Part II examines the steady-state phase of distributed learning by networked agents. Apart from characterizing the performance of the individual agents, it is shown that the network induces a useful equalization effect across all agents. In this way, the performance of noisier agents is enhanced to the same level as the performance of agents with less noisy data. It is further shown that in the small step-size regime, each agent in the network is able to achieve the same performance level as that of a centralized strategy corresponding to a fully connected network. The results in this part reveal explicitly which aspects of the network topology and operation influence performance and provide important insights into the design of effective mechanisms for the processing and diffusion of information over networks.
Internalization of extensional equality
Venue: arXiv cs.LO 2015
Year: 2015

We give a type system in which the universe of types is closed by reflection into it of the logical relation defined externally by induction on the structure of types. This contribution is placed in the context of the search for a natural, syntactic construction of the extensional equality type (Tait [1995], Altenkirch [1999], Coquand [2011], Licata and Harper [2012], Martin-Lof [2013]). The system is presented as an extension of lambda-*, the terminal pure type system in which the universe of all types is a type. The universe inconsistency is then removed by the usual method of stratification into levels. We give a set-theoretic model for the stratified system. We conjecture that Strong Normalization holds as well.
On the Complexity of Randomly Weighted Voronoi Diagrams
Venue: arXiv cs.CG 2015
Year: 2015

In this paper, we provide an $O(n \mathrm{polylog} n)$ bound on the expected complexity of the randomly weighted Voronoi diagram of a set of $n$ sites in the plane, where the sites can be either points, interior-disjoint convex sets, or other more general objects. Here the randomness is on the weight of the sites, not their location. This compares favorably with the worst case complexity of these diagrams, which is quadratic. As a consequence we get an alternative proof to that of Agarwal etal [AHKS13] of the near linear complexity of the union of randomly expanded disjoint segments or convex sets (with an improved bound on the latter). The technique we develop is elegant and should be applicable to other problems.
An efficient way to assemble finite element matrices in vector languages
Venue: arXiv cs.MS 2015
Year: 2015

Efficient Matlab codes in 2D and 3D have been proposed recently to assemble finite element matrices. In this paper we present simple, compact and efficient vectorized algorithms, which are variants of these codes, in arbitrary dimension, without the use of any lower level language. They can be easily implemented in many vector languages (e.g. Matlab, Octave, Python, Scilab, R, Julia, C++ with STL,...). The principle of these techniques is general, we present it for the assembly of several finite element matrices in arbitrary dimension, in the P1 finite element case. We also provide an extension of the algorithms to the case of a system of PDE's. Then we give an extension to piecewise polynomials of higher order. We compare numerically the performance of these algorithms in Matlab, Octave and Python, with that in FreeFEM++ and in a compiled language such as C. Examples show that, unlike what is commonly believed, the performance is not radically worse than that of C : in the best/worst cases, selected vector languages are respectively 2.3/3.5 and 2.9/4.1 times slower than C in the scalar and vector cases. We also present numerical results which illustrate the computational costs of these algorithms compared to standard algorithms and to other recent ones.
Studying the SINR process of the typical user in Poisson networks by using its factorial moment measures
Venue: arXiv cs.NI 2015
Year: 2015

Based on a stationary Poisson point process, a wireless network model with random propagation effects (shadowing and/or fading) is considered in order to examine the process formed by the signal-to-interference-plus-noise ratio (SINR) values experienced by a typical user with respect to all base stations in the down-link channel. This SINR process is completely characterized by deriving its factorial moment measures, which involve numerically tractable, explicit integral expressions. This novel framework naturally leads to expressions for the k-coverage probability, including the case of random SINR threshold values considered in multi-tier network models. While the k-coverage probabilities correspond to the marginal distributions of the order statistics of the SINR process, a more general relation is presented connecting the factorial moment measures of the SINR process to the joint densities of these order statistics. This gives a way for calculating exact values of the coverage probabilities arising in a general scenario of signal combination and interference cancellation between base stations. The presented framework consisting of mathematical representations of SINR characteristics with respect to the factorial moment measures holds for the whole domain of SINR and is amenable to considerable model extension.
A domination algorithm for $\{0,1\}$-instances of the travelling salesman problem
Venue: arXiv cs.DS 2015
Year: 2015

We present an approximation algorithm for $\{0,1\}$-instances of the travelling salesman problem which performs well with respect to combinatorial dominance. More precisely, we give a polynomial-time algorithm which has domination ratio $1-n^{-1/29}$. In other words, given a $\{0,1\}$-edge-weighting of the complete graph $K_n$ on $n$ vertices, our algorithm outputs a Hamilton cycle $H^*$ of $K_n$ with the following property: the proportion of Hamilton cycles of $K_n$ whose weight is smaller than that of $H^*$ is at most $n^{-1/29}$. Our analysis is based on a martingale approach. Previously, the best result in this direction was a polynomial-time algorithm with domination ratio $1/2-o(1)$ for arbitrary edge-weights. We also prove a hardness result showing that, if the Exponential Time Hypothesis holds, there exists a constant $C$ such that $n^{-1/29}$ cannot be replaced by $\exp(-(\log n)^C)$ in the result above.
Solving the Pricing Problem in a Branch-and-Price Algorithm for Graph Coloring using Zero-Suppressed Binary Decision Diagrams
Venue: arXiv cs.DS 2015
Year: 2015

Branch-and-price algorithms combine a branch-and-bound search with an exponentially-sized LP formulation that must be solved via column generation. Unfortunately, the standard branching rules used in branch-and-bound for integer programming interfere with the structure of the column generation routine; therefore, most such algorithms employ alternate branching rules to circumvent this difficulty. This paper shows how a zero-suppressed binary decision diagram (ZDD) can be used to solve the pricing problem in a branch-and-price algorithm for the graph coloring problem, even in the presence of constraints imposed by branching decisions. This approach facilitates a much more direct solution method, and can improve convergence of the column generation subroutine.
Continuous Localization and Mapping of a Pan Tilt Zoom Camera for Wide Area Tracking
Venue: arXiv cs.CV 2015
Year: 2015

Pan-tilt-zoom (PTZ) cameras are powerful to support object identification and recognition in far-field scenes. However, the effective use of PTZ cameras in real contexts is complicated by the fact that a continuous on-line camera calibration is needed and the absolute pan, tilt and zoom positional values provided by the camera actuators cannot be used because are not synchronized with the video stream. So, accurate calibration must be directly extracted from the visual content of the frames. Moreover, the large and abrupt scale changes, the scene background changes due to the camera operation and the need of camera motion compensation make target tracking with these cameras extremely challenging. In this paper, we present a solution that provides continuous on-line calibration of PTZ cameras which is robust to rapid camera motion, changes of the environment due to illumination or moving objects and scales beyond thousands of landmarks. The method directly derives the relationship between the position of a target in the 3D world plane and the corresponding scale and position in the 2D image, and allows real-time tracking of multiple targets with high and stable degree of accuracy even at far distances and any zooming level.
A Rate-Distortion Approach to Index Coding
Venue: arXiv cs.IT 2015
Year: 2015

We approach index coding as a special case of rate-distortion with multiple receivers, each with some side information about the source. Specifically, using techniques developed for the rate-distortion problem, we provide two upper bounds and one lower bound on the optimal index coding rate. The upper bounds involve specific choices of the auxiliary random variables in the best existing scheme for the rate-distortion problem. The lower bound is based on a new lower bound for the general rate-distortion problem. The bounds are shown to coincide for a number of (groupcast) index coding instances, including all instances for which the number of decoders does not exceed three.
Efficient Gradient-Based Inference through Transformations between Bayes Nets and Neural Nets
Venue: arXiv cs.LG 2015
Year: 2015

Hierarchical Bayesian networks and neural networks with stochastic hidden units are commonly perceived as two separate types of models. We show that either of these types of models can often be transformed into an instance of the other, by switching between centered and differentiable non-centered parameterizations of the latent variables. The choice of parameterization greatly influences the efficiency of gradient-based posterior inference; we show that they are often complementary to eachother, we clarify when each parameterization is preferred and show how inference can be made robust. In the non-centered form, a simple Monte Carlo estimator of the marginal likelihood can be used for learning the parameters. Theoretical results are supported by experiments.
Variable-length compression allowing errors
Venue: arXiv cs.IT 2015
Year: 2015

This paper studies the fundamental limits of the minimum average length of lossless and lossy variable-length compression, allowing a nonzero error probability $ε$, for lossless compression. We give non-asymptotic bounds on the minimum average length in terms of Erokhin's rate-distortion function and we use those bounds to obtain a Gaussian approximation on the speed of approach to the limit which is quite accurate for all but small blocklengths: $$(1 - ε) k H(\mathsf S) - \sqrt{\frac{k V(\mathsf S)}{2 π} } e^{- \frac {(Q^{-1}(ε))^2} 2 }$$ where $Q^{-1}(\cdot)$ is the functional inverse of the standard Gaussian complementary cdf, and $V(\mathsf S)$ is the source dispersion. A nonzero error probability thus not only reduces the asymptotically achievable rate by a factor of $1 - ε$, but this asymptotic limit is approached from below, i.e. larger source dispersions and shorter blocklengths are beneficial. Variable-length lossy compression under an excess distortion constraint is shown to exhibit similar properties.