OpenRaiser/Intern-Atlas huggingface dataset:
Finite-Length Analysis of BATS Codes
Venue: arXiv cs.IT 2016
Year: 2016

BATS codes were proposed for communication through networks with packet loss. A BATS code consists of an outer code and an inner code. The outer code is a matrix generation of a fountain code, which works with the inner code that comprises random linear coding at the intermediate network nodes. In this paper, the performance of finite-length BATS codes is analyzed with respect to both belief propagation (BP) decoding and inactivation decoding. Our results enable us to evaluate efficiently the finite-length performance in terms of the number of batches used for decoding ranging from 1 to a given maximum number, and provide new insights on the decoding performance. Specifically, for a fixed number of input symbols and a range of the number of batches used for decoding, we obtain recursive formulae to calculate respectively the stopping time distribution of BP decoding and the inactivation probability in inactivation decoding. We also find that both the failure probability of BP decoding and the expected number of inactivations in inactivation decoding can be expressed in a power-sum form where the number of batches appears only as the exponent. This power-sum expression reveals clearly how the decoding failure probability and the expected number of inactivation decrease with the number of batches. When the number of batches used for decoding follows a Poisson distribution, we further derive recursive formulae with potentially lower computational complexity for both decoding algorithms. For the BP decoder that consumes batches one by one, three formulae are provided to characterize the expected number of consumed batches until all the input symbols are decoded.
List-coloring apex-minor-free graphs
Venue: arXiv cs.DM 2016
Year: 2016

A graph H is t-apex if H-X is planar for some subset X of V(H) of size t. For any integer t>=0 and a fixed t-apex graph H, we give a polynomial-time algorithm to decide whether a (t+3)-connected H-minor-free graph is colorable from a given assignment of lists of size t+4. The connectivity requirement is the best possible in the sense that for every t>=1, there exists a t-apex graph H such that testing (t+4)-colorability of (t+2)-connected H-minor-free graphs is NP-complete. Similarly, the size of the lists cannot be decreased (unless P=NP), since for every t>=1, testing (t+3)-list-colorability of (t+3)-connected K_{t+4}-minor-free graphs is NP-complete.
Circular Sphere Decoding: A Low Complexity Detection for MIMO Systems with General Two-dimensional Signal Constellations
Venue: arXiv cs.IT 2016
Year: 2016

We propose a low complexity complex valued Sphere Decoding (CV-SD) algorithm, referred to as Circular Sphere Decoding (CSD) which is applicable to multiple-input multiple-output (MIMO) systems with arbitrary two dimensional (2D) constellations. CSD provides a new constraint test. This constraint test is carefully designed so that the element-wise dependency is removed in the metric computation for the test. As a result, the constraint test becomes simple to perform without restriction on its constellation structure. By additionally employing this simple test as a prescreening test, CSD reduces the complexity of the CV-SD search. We show that the complexity reduction is significant while its maximum-likelihood (ML) performance is not compromised. We also provide a powerful tool to estimate the pruning capacity of any particular search tree. Using this tool, we propose the Predict-And-Change strategy which leads to a further complexity reduction in CSD. Extension of the proposed methods to soft output SD is also presented.
On the Evaluation of the Polyanskiy-Poor-Verdu Converse Bound for Finite Blocklength Coding in AWGN
Venue: arXiv cs.IT 2016
Year: 2016

A tight converse bound to channel coding rate in the finite block-length regime and under AWGN conditions was recently proposed by Polyanskiy, Poor, and Verdu (PPV). The bound is a generalization of a number of other classical results, and it was also claimed to be equivalent to Shannon's 1959 cone packing bound. Unfortunately, its numerical evaluation is troublesome even for not too large values of the block-length n. In this paper we tackle the numerical evaluation by compactly expressing the PPV converse bound in terms of non-central chi-squared distributions, and by evaluating those through a an integral expression and a corresponding series expansion which exploit a method proposed by Temme. As a result, a robust evaluation method and new insights on the bound's asymptotics, as well as new approximate expressions, are given.
Exploiting Causality for Selective Belief Filtering in Dynamic Bayesian Networks
Venue: arXiv cs.AI 2016
Year: 2016

Dynamic Bayesian networks (DBNs) are a general model for stochastic processes with partially observed states. Belief filtering in DBNs is the task of inferring the belief state (i.e. the probability distribution over process states) based on incomplete and noisy observations. This can be a hard problem in complex processes with large state spaces. In this article, we explore the idea of accelerating the filtering task by automatically exploiting causality in the process. We consider a specific type of causal relation, called passivity, which pertains to how state variables cause changes in other variables. We present the Passivity-based Selective Belief Filtering (PSBF) method, which maintains a factored belief representation and exploits passivity to perform selective updates over the belief factors. PSBF produces exact belief states under certain assumptions and approximate belief states otherwise, where the approximation error is bounded by the degree of uncertainty in the process. We show empirically, in synthetic processes with varying sizes and degrees of passivity, that PSBF is faster than several alternative methods while achieving competitive accuracy. Furthermore, we demonstrate how passivity occurs naturally in a complex system such as a multi-robot warehouse, and how PSBF can exploit this to accelerate the filtering task.
UNLocBoX: A MATLAB convex optimization toolbox for proximal-splitting methods
Venue: arXiv cs.LG 2016
Year: 2016

Convex optimization is an essential tool for machine learning, as many of its problems can be formulated as minimization problems of specific objective functions. While there is a large variety of algorithms available to solve convex problems, we can argue that it becomes more and more important to focus on efficient, scalable methods that can deal with big data. When the objective function can be written as a sum of "simple" terms, proximal splitting methods are a good choice. UNLocBoX is a MATLAB library that implements many of these methods, designed to solve convex optimization problems of the form $\min_{x \in \mathbb{R}^N} \sum_{n=1}^K f_n(x).$ It contains the most recent solvers such as FISTA, Douglas-Rachford, SDMM as well a primal dual techniques such as Chambolle-Pock and forward-backward-forward. It also includes an extensive list of common proximal operators that can be combined, allowing for a quick implementation of a large variety of convex problems.
Phase transitions and sample complexity in Bayes-optimal matrix factorization
Venue: arXiv cs.NA 2016
Year: 2016

We analyse the matrix factorization problem. Given a noisy measurement of a product of two matrices, the problem is to estimate back the original matrices. It arises in many applications such as dictionary learning, blind matrix calibration, sparse principal component analysis, blind source separation, low rank matrix completion, robust principal component analysis or factor analysis. It is also important in machine learning: unsupervised representation learning can often be studied through matrix factorization. We use the tools of statistical mechanics - the cavity and replica methods - to analyze the achievability and computational tractability of the inference problems in the setting of Bayes-optimal inference, which amounts to assuming that the two matrices have random independent elements generated from some known distribution, and this information is available to the inference algorithm. In this setting, we compute the minimal mean-squared-error achievable in principle in any computational time, and the error that can be achieved by an efficient approximate message passing algorithm. The computation is based on the asymptotic state-evolution analysis of the algorithm. The performance that our analysis predicts, both in terms of the achieved mean-squared-error, and in terms of sample complexity, is extremely promising and motivating for a further development of the algorithm.
A Duality Transform for Constructing Small Grid Embeddings of 3d Polytopes
Venue: arXiv cs.CG 2016
Year: 2016

We study the problem of how to obtain an integer realization of a 3d polytope when an integer realization of its dual polytope is given. We focus on grid embeddings with small coordinates and develop novel techniques based on Colin de Verdière matrices and the Maxwell-Cremona lifting method. We show that every truncated 3d polytope with n vertices can be realized on a grid of size O(n^{9log(6)+1}). Moreover, for every simplicial 3d polytope with n vertices with maximal vertex degree Δ and vertices placed on an L x L x L grid, a dual polytope can be realized on an integer grid of size O(n L^{3Δ+ 9}). This implies that for a class C of simplicial 3d polytopes with bounded vertex degree and polynomial size grid embedding, the dual polytopes of C can be realized on a polynomial size grid as well.
Hybridization Number on Three Rooted Binary Trees is EPT
Venue: arXiv cs.DS 2016
Year: 2016

Phylogenetic networks are leaf-labelled directed acyclic graphs that are used to describe non-treelike evolutionary histories and are thus a generalization of phylogenetic trees. The hybridization number of a phylogenetic network is the sum of all indegrees minus the number of nodes plus one. The Hybridization Number problem takes as input a collection of phylogenetic trees and asks to construct a phylogenetic network that contains an embedding of each of the input trees and has a smallest possible hybridization number. We present an algorithm for the Hybridization Number problem on three binary trees on $n$ leaves, which runs in time $O(c^k poly(n))$, with $k$ the hybridization number of an optimal network and $c$ a constant. For two trees, an algorithm with running time $O(3.18^k n)$ was proposed before whereas an algorithm with running time $O(c^k poly(n))$ had prior to this article remained elusive for more than two trees. The algorithm for two trees uses the close connection to acyclic agreement forests to achieve a linear exponent in the running time, while previous algorithms for more than two trees (explicitly or implicitly) relied on a brute force search through all possible underlying network topologies, leading to running times that are not $O(c^k poly(n))$ for any $c$. The connection to acyclic agreement forests is much weaker for more than two trees, so even given the right agreement forest, reconstructing the network poses major challenges. We prove novel structural results that allow us to reconstruct a network without having to guess the underlying topology. Our techniques generalize to more than three input trees with the exception of one key lemma that maps nodes in the network to tree nodes and, thus, minimizes the amount of guessing involved in constructing the network. The main open problem therefore is to establish a similar mapping for more than three trees.
Threshold and Symmetric Functions over Bitmaps
Venue: arXiv cs.DB 2016
Year: 2016

Bitmap indexes are routinely used to speed up simple aggregate queries in databases. Set operations such as intersections, unions and complements can be represented as logical operations (AND, OR, NOT). However, less is known about the application of bitmap indexes to more advanced queries. We want to extend the applicability of bitmap indexes. As a starting point, we consider symmetric Boolean queries (e.g., threshold functions). For example, we might consider stores as sets of products, and ask for products that are on sale in 2 to 10 stores. Such symmetric Boolean queries generalize intersection, union, and T-occurrence queries. It may not be immediately obvious to an engineer how to use bitmap indexes for symmetric Boolean queries. Yet, maybe surprisingly, we find that the best of our bitmap-based algorithms are competitive with the state-of-the-art algorithms for important special cases (e.g., MergeOpt, MergeSkip, DivideSkip, ScanCount). Moreover, unlike the competing algorithms, the result of our computation is again a bitmap which can be further processed within a bitmap index. We review algorithmic design issues such as the aggregation of many compressed bitmaps. We conclude with a discussion on other advanced queries that bitmap indexes might be able to support efficiently.
A Multiplierless Pruned DCT-like Transformation for Image and Video Compression that Requires 10 Additions Only
Venue: arXiv cs.MM 2016
Year: 2016

A multiplierless pruned approximate 8-point discrete cosine transform (DCT) requiring only 10 additions is introduced. The proposed algorithm was assessed in image and video compression, showing competitive performance with state-of-the-art methods. Digital implementation in 45 nm CMOS technology up to place-and-route level indicates clock speed of 288 MHz at a 1.1 V supply. The 8x8 block rate is 36 MHz.The DCT approximation was embedded into HEVC reference software; resulting video frames, at up to 327 Hz for 8-bit RGB HEVC, presented negligible image degradation.
Average Case Performance of Replicator Dynamics in Potential Games via Computing Regions of Attraction
Venue: arXiv cs.GT 2016
Year: 2016

What does it mean to fully understand the behavior of a network of adaptive agents? The golden standard typically is the behavior of learning dynamics in potential games, where many evolutionary dynamics, e.g., replicator, are known to converge to sets of equilibria. Even in such classic settings many critical questions remain unanswered. We examine issues such as: Point-wise convergence: Does the system actually equilibrate even in the presence of continuums of equilibria? Computing regions of attraction: Given point-wise convergence can we compute the region of asymptotic stability of each equilibrium (e.g., estimate its volume, geometry)? System invariants: Invariant functions remain constant along every system trajectory. This notion is orthogonal to the game theoretic concept of a potential function, which always strictly increases/decreases along system trajectories. Do dynamics in potential games exhibit invariant functions? If so, how many? How do these functions look like? Based on these geometric characterizations, we propose a novel quantitative framework for analyzing the efficiency of potential games with many equilibria. The predictions of different equilibria are weighted by their probability to arise under evolutionary dynamics given uniformly random initial conditions. This average case analysis is shown to offer novel insights in classic game theoretic challenges, including quantifying the risk dominance in stag-hunt games and allowing for more nuanced performance analysis in networked coordination and congestion games with large gaps between price of stability and price of anarchy.
Updating Formulas and Algorithms for Computing Entropy and Gini Index from Time-Changing Data Streams
Venue: arXiv cs.AI 2016
Year: 2016

Despite growing interest in data stream mining the most successful incremental learners, such as VFDT, still use periodic recomputation to update attribute information gains and Gini indices. This note provides simple incremental formulas and algorithms for computing entropy and Gini index from time-changing data streams.
On the allocation of multiple divisible assets to players with different utilities
Venue: arXiv cs.GT 2016
Year: 2016

When there is a dispute between players on how to divide multiple divisible assets, how should it be resolved? In this paper we introduce a multi-asset game model that enables cooperation between multiple agents who bargain on sharing K assets, when each player has a different value for each asset. It thus extends the sequential discrete Raiffa solution and the Talmud rule solution to multi-asset cases. keyword: resource allocation, game theory, Raiffa Bargaining Solution, Aumann Bankruptcy, non-transferable commodities
Comments on "IEEE 1588 Clock Synchronization using Dual Slave Clocks in a Slave"
Venue: arXiv cs.AR 2016
Year: 2016

In the above letter, Chin and Chen proposed an IEEE 1588 clock synchronization method based on dual slave clocks, where they claim that multiple unknown parameters --- i.e., clock offset, clock skew, and master-to-slave delay --- can be estimated with only one-way time transfers using more equations than usual. This comment investigates Chin and Chen's dual clock scheme with detailed models for a master and dual slave clocks and shows that the formulation of multi-parameter estimation is invalid, which affirms that it is impossible to distinguish the effect of delay from that of clock offset at a slave even with dual slave clocks.
From Proximity to Utility: A Voronoi Partition of Pareto Optima
Venue: arXiv cs.CG 2016
Year: 2016

We present an extension of Voronoi diagrams where when considering which site a client is going to use, in addition to the site distances, other site attributes are also considered (for example, prices or weights). A cell in this diagram is then the locus of all clients that consider the same set of sites to be relevant. In particular, the precise site a client might use from this candidate set depends on parameters that might change between usages, and the candidate set lists all of the relevant sites. The resulting diagram is significantly more expressive than Voronoi diagrams, but naturally has the drawback that its complexity, even in the plane, might be quite high. Nevertheless, we show that if the attributes of the sites are drawn from the same distribution (note that the locations are fixed), then the expected complexity of the candidate diagram is near linear. To this end, we derive several new technical results, which are of independent interest. In particular, we provide a high-probability, asymptotically optimal bound on the number of Pareto optima points in a point set uniformly sampled from the $d$-dimensional hypercube. To do so we revisit the classical backward analysis technique, both simplifying and improving relevant results in order to achieve the high-probability bounds.
On the MacWilliams Identity for Classical and Quantum Convolutional Codes
Venue: arXiv cs.IT 2016
Year: 2016

The weight generating functions associated with convolutional codes (CCs) are based on state space realizations or the weight adjacency matrices (WAMs). The MacWilliams identity for CCs on the WAMs was first established by Gluesing- Luerssen and Schneider in the case of minimal encoders, and generalized by Forney. We consider this problem in the viewpoint of constraint codes and obtain a simple and direct proof of this MacWilliams identity in the case of minimal encoders. For our purpose, we choose a different representation for the exact weight generating function (EWGF) of a block code, by defining it as a linear combination of orthonormal vectors in Dirac bra-ket notation. This representation provides great flexibility so that general split weight generating functions and their MacWilliams identities can be easily obtained from the MacWilliams identity for EWGFs. As a result, we also obtain the MacWilliams identity for the input-parity weight adjacency matrices of a systematic convolutional code and its dual. Finally, paralleling the development of the classical case, we establish the MacWilliams identity for quantum convolutional codes.
Multitask Learning for Sequence Labeling Tasks
Venue: arXiv cs.LG 2016
Year: 2016

In this paper, we present a learning method for sequence labeling tasks in which each example sequence has multiple label sequences. Our method learns multiple models, one model for each label sequence. Each model computes the joint probability of all label sequences given the example sequence. Although each model considers all label sequences, its primary focus is only one label sequence, and therefore, each model becomes a task-specific model, for the task belonging to that primary label. Such multiple models are learned {\it simultaneously} by facilitating the learning transfer among models through {\it explicit parameter sharing}. We experiment the proposed method on two applications and show that our method significantly outperforms the state-of-the-art method.
Area Coverage Under Low Sensor Density
Venue: arXiv cs.NI 2016
Year: 2016

This paper presents a solution to the problem of monitoring a region of interest (RoI) using a set of nodes that is not sufficient to achieve the required degree of monitoring coverage. In particular, sensing coverage of wireless sensor networks (WSNs) is a crucial issue in projects due to failure of sensors. The lack of sensor equipment resources hinders the traditional method of using mobile robots to move around the RoI to collect readings. Instead, our solution employs supervised neural networks to produce the values of the uncovered locations by extracting the non-linear relation among randomly deployed sensor nodes throughout the area. Moreover, we apply a hybrid backpropagation method to accelerate the learning convergence speed to a local minimum solution. We use a real-world data set from meteorological deployment for experimental validation and analysis.
Model Checking Markov Chains Against Unambiguous Buchi Automata
Venue: arXiv cs.LO 2016
Year: 2016

We give a polynomial-time algorithm for model checking finite Markov chains against omega-regular specifications given as unambiguous Buchi automata.
Screening Tests for Lasso Problems
Venue: arXiv cs.LG 2016
Year: 2016

This paper is a survey of dictionary screening for the lasso problem. The lasso problem seeks a sparse linear combination of the columns of a dictionary to best match a given target vector. This sparse representation has proven useful in a variety of subsequent processing and decision tasks. For a given target vector, dictionary screening quickly identifies a subset of dictionary columns that will receive zero weight in a solution of the corresponding lasso problem. These columns can be removed from the dictionary prior to solving the lasso problem without impacting the optimality of the solution obtained. This has two potential advantages: it reduces the size of the dictionary, allowing the lasso problem to be solved with less resources, and it may speed up obtaining a solution. Using a geometrically intuitive framework, we provide basic insights for understanding useful lasso screening tests and their limitations. We also provide illustrative numerical studies on several datasets.
Error Reporting in Parsing Expression Grammars
Venue: arXiv cs.PL 2016
Year: 2016

Parsing Expression Grammars (PEGs) describe top-down parsers. Unfortunately, the error-reporting techniques used in conventional top-down parsers do not directly apply to parsers based on Parsing Expression Grammars (PEGs), so they have to be somehow simulated. While the PEG formalism has no account of semantic actions, actual PEG implementations add them, and we show how to simulate an error-reporting heuristic through these semantic actions. We also propose a complementary error reporting strategy that may lead to better error messages: labeled failures. This approach is inspired by exception handling of programming languages, and lets a PEG define different kinds of failure, with each ordered choice operator specifying which kinds it catches. Labeled failures give a way to annotate grammars for better error reporting, to express some of the error reporting strategies used by deterministic parser combinators, and to encode predictive top-down parsing in a PEG.