OpenRaiser/Intern-Atlas huggingface dataset:
Memory effects can make the transmission capability of a communication channel uncomputable
Venue: arXiv cs.IT 2018
Year: 2018

Most communication channels are subjected to noise. One of the goals of Information Theory is to add redundancy in the transmission of information so that the information is transmitted reliably and the amount of information transmitted through the channel is as large as possible. The maximum rate at which reliable transmission is possible is called the capacity. If the channel does not keep memory of its past, the capacity is given by a simple optimization problem and can be efficiently computed. The situation of channels with memory is less clear. Here we show that for channels with memory the capacity cannot be computed to within precision 1/5. Our result holds even if we consider one of the simplest families of such channels -information-stable finite state machine channels-, restrict the input and output of the channel to 4 and 1 bit respectively and allow 6 bits of memory.
Rectified Gaussian Scale Mixtures and the Sparse Non-Negative Least Squares Problem
Venue: arXiv cs.LG 2018
Year: 2018

In this paper, we develop a Bayesian evidence maximization framework to solve the sparse non-negative least squares (S-NNLS) problem. We introduce a family of probability densities referred to as the Rectified Gaussian Scale Mixture (R- GSM) to model the sparsity enforcing prior distribution for the solution. The R-GSM prior encompasses a variety of heavy-tailed densities such as the rectified Laplacian and rectified Student- t distributions with a proper choice of the mixing density. We utilize the hierarchical representation induced by the R-GSM prior and develop an evidence maximization framework based on the Expectation-Maximization (EM) algorithm. Using the EM based method, we estimate the hyper-parameters and obtain a point estimate for the solution. We refer to the proposed method as rectified sparse Bayesian learning (R-SBL). We provide four R- SBL variants that offer a range of options for computational complexity and the quality of the E-step computation. These methods include the Markov chain Monte Carlo EM, linear minimum mean-square-error estimation, approximate message passing and a diagonal approximation. Using numerical experiments, we show that the proposed R-SBL method outperforms existing S-NNLS solvers in terms of both signal and support recovery performance, and is also very robust against the structure of the design matrix.
Randomness Extraction in AC0 and with Small Locality
Venue: arXiv cs.CC 2018
Year: 2018

Randomness extractors, which extract high quality (almost-uniform) random bits from biased random sources, are important objects both in theory and in practice. While there have been significant progress in obtaining near optimal constructions of randomness extractors in various settings, the computational complexity of randomness extractors is still much less studied. In particular, it is not clear whether randomness extractors with good parameters can be computed in several interesting complexity classes that are much weaker than P. In this paper we study randomness extractors in the following two models of computation: (1) constant-depth circuits (AC0), and (2) the local computation model. Previous work in these models, such as [Vio05a], [GVW15] and [BG13], only achieve constructions with weak parameters. In this work we give explicit constructions of randomness extractors with much better parameters. As an application, we use our AC0 extractors to study pseudorandom generators in AC0, and show that we can construct both cryptographic pseudorandom generators (under reasonable computational assumptions) and unconditional pseudorandom generators for space bounded computation with very good parameters. Our constructions combine several previous techniques in randomness extractors, as well as introduce new techniques to reduce or preserve the complexity of extractors, which may be of independent interest. These include (1) a general way to reduce the error of strong seeded extractors while preserving the AC0 property and small locality, and (2) a seeded randomness condenser with small locality.
Performance guarantees for model-based Approximate Dynamic Programming in continuous spaces
Venue: arXiv cs.SY 2018
Year: 2018

We study both the value function and Q-function formulation of the Linear Programming approach to Approximate Dynamic Programming. The approach is model-based and optimizes over a restricted function space to approximate the value function or Q-function. Working in the discrete time, continuous space setting, we provide guarantees for the fitting error and online performance of the policy. In particular, the online performance guarantee is obtained by analyzing an iterated version of the greedy policy, and the fitting error guarantee by analyzing an iterated version of the Bellman inequality. These guarantees complement the existing bounds that appear in the literature. The Q-function formulation offers benefits, for example, in decentralized controller design, however it can lead to computationally demanding optimization problems. To alleviate this drawback, we provide a condition that simplifies the formulation, resulting in improved computational times.
Enhancing Genetic Algorithms using Multi Mutations
Venue: arXiv cs.AI 2018
Year: 2018

Mutation is one of the most important stages of the genetic algorithm because of its impact on the exploration of global optima, and to overcome premature convergence. There are many types of mutation, and the problem lies in selection of the appropriate type, where the decision becomes more difficult and needs more trial and error. This paper investigates the use of more than one mutation operator to enhance the performance of genetic algorithms. Novel mutation operators are proposed, in addition to two selection strategies for the mutation operators, one of which is based on selecting the best mutation operator and the other randomly selects any operator. Several experiments on some Travelling Salesman Problems (TSP) were conducted to evaluate the proposed methods, and these were compared to the well-known exchange mutation and rearrangement mutation. The results show the importance of some of the proposed methods, in addition to the significant enhancement of the genetic algorithm's performance, particularly when using more than one mutation operator.
Modular Tracking Framework: A Unified Approach to Registration based Tracking
Venue: arXiv cs.CV 2018
Year: 2018

This paper presents a modular, extensible and highly efficient open source framework for registration based tracking called Modular Tracking Framework (MTF). Targeted at robotics applications, it is implemented entirely in C++ and designed from the ground up to easily integrate with systems that support any of several major vision and robotics libraries including OpenCV, ROS, ViSP and Eigen. It implements more methods, is faster, and more precise than other existing systems. Further, the theoretical basis for its design is a new way to conceptualize registration based trackers that decomposes them into three constituent sub modules - Search Method (SM), Appearance Model (AM) and State Space Model (SSM). In the process, we integrate many important advances published after Baker \& Matthews' landmark work in 2004. In addition to being a practical solution for fast and high precision tracking, MTF can also serve as a useful research tool by allowing existing and new methods for any of the sub modules to be studied better. When a new method is introduced for one of these, the breakdown can help to experimentally find the combination of methods for the others that is optimum for it. By extensive use of generic programming, MTF makes it easy to plug in a new method for any of the sub modules so that it can not only be tested comprehensively with existing methods but also become immediately available for deployment in any project that uses the framework. With 16 AMs, 11 SMs and 13 SSMs implemented already, MTF provides over 2000 distinct single layer trackers. It also allows two or more of these to be combined together in several ways to create a practically unlimited variety of novel multi layer trackers.
Distributed $(Δ+1)$-Coloring in Sublogarithmic Rounds
Venue: arXiv cs.DS 2018
Year: 2018

We give a new randomized distributed algorithm for $(Δ+1)$-coloring in the LOCAL model, running in $O(\sqrt{\log Δ})+ 2^{O(\sqrt{\log \log n})}$ rounds in a graph of maximum degree~$Δ$. This implies that the $(Δ+1)$-coloring problem is easier than the maximal independent set problem and the maximal matching problem, due to their lower bounds of $Ω\left( \min \left( \sqrt{\frac{\log n}{\log \log n}}, \frac{\log Δ}{\log \log Δ} \right) \right)$ by Kuhn, Moscibroda, and Wattenhofer [PODC'04]. Our algorithm also extends to list-coloring where the palette of each node contains $Δ+1$ colors. We extend the set of distributed symmetry-breaking techniques by performing a decomposition of graphs into dense and sparse parts.
A New Numerical Method for Solving the Acoustic Radiation Problem
Venue: arXiv cs.NA 2018
Year: 2018

A numerical method of solving the problem of acoustic wave radiation in the presence of a rigid scatterer is described. It combines the finite element method and the boundary algebraic equations. In the proposed method, the exterior domain around the scatterer is discretized, so that there appear an infinite domain with regular discretization and a relatively small layer with irregular mesh. For the infinite regular mesh, the boundary algebraic equation method is used with spurious resonance suppression according to Burton and Miller. In the thin layer with irregular mesh, the finite element method is used. The proposed method is characterized by simple implementation, fair accuracy, and absence of spurious resonances.
On the limitations of analysing worst-case dynamic energy of processing
Venue: arXiv cs.CC 2018
Year: 2018

This paper examines dynamic energy consumption caused by data during software execution on deeply embedded microprocessors, which can be significant on some devices. In worst-case energy consumption analysis, energy models are used to find the most costly execution path. Taking each instruction's worst case energy produces a safe but overly pessimistic upper bound. Algorithms for safe and tight bounds would be desirable. We show that finding exact worst-case energy is NP-hard, and that tight bounds cannot be approximated with guaranteed safety. We conclude that any energy model targeting tightness must either sacrifice safety or accept overapproximation proportional to data-dependent energy.
Linear and Nonlinear Frequency-Division Multiplexing
Venue: arXiv cs.IT 2018
Year: 2018

Two signal multiplexing schemes for optical fiber communication are considered: Wavelength-division multiplexing (WDM) and nonlinear frequency-division multiplexing (NFDM), based on the nonlinear Fourier transform (NFT). Achievable information rates (AIRs) of NFDM and WDM are compared in a network scenario with an ideal lossless model of the optical fiber in the defocusing regime. It is shown that the NFDM AIR is greater than the WDM AIR subject to a bandwidth and average power constraint, in a representative system with one symbol per user. The improvement results from nonlinear signal multiplexing.
Many-to-many Correspondences between Partitions: Introducing a Cut-based Approach
Venue: arXiv cs.DM 2018
Year: 2018

Let $\mathcal{P}$ and $\mathcal{P}'$ be finite partitions of the set $V$. Finding good correspondences between the parts of $\mathcal{P}$ and those of $\mathcal{P}'$ is helpful in classification, pattern recognition, and network analysis. Unlike common similarity measures for partitions that yield only a single value, we provide specifics on how $\mathcal{P}$ and $\mathcal{P'}$ correspond to each other. To this end, we first define natural collections of best correspondences under three constraints \cone, \ctwo, and \cthree. In case of \cone, the best correspondences form a minimum cut basis of a certain bipartite graph, whereas the other two lead to minimum cut bases of $\mathcal{P}$ \wrt $\mathcal{P}'$. We also introduce a constraint, \cfour, which tightens \cthree; both are useful for finding consensus partitions. We then develop branch-and-bound algorithms for finding minimum $P_s$-$P_t$ cuts of $\mathcal{P}$ and thus $\vert \mathcal{P} \vert -1$ best correspondences under \ctwo, \cthree, and \cfour, respectively. In a case study, we use the correspondences to gain insight into a community detection algorithm. The results suggest, among others, that only very minor losses in the quality of the correspondences occur if the branch-and-bound algorithm is restricted to its greedy core. Thus, even for graphs with more than half a million nodes and hundreds of communities, we can find hundreds of best or almost best correspondences in less than a minute.
Joint Stochastic Approximation learning of Helmholtz Machines
Venue: arXiv cs.LG 2018
Year: 2018

Though with progress, model learning and performing posterior inference still remains a common challenge for using deep generative models, especially for handling discrete hidden variables. This paper is mainly concerned with algorithms for learning Helmholz machines, which is characterized by pairing the generative model with an auxiliary inference model. A common drawback of previous learning algorithms is that they indirectly optimize some bounds of the targeted marginal log-likelihood. In contrast, we successfully develop a new class of algorithms, based on stochastic approximation (SA) theory of the Robbins-Monro type, to directly optimize the marginal log-likelihood and simultaneously minimize the inclusive KL-divergence. The resulting learning algorithm is thus called joint SA (JSA). Moreover, we construct an effective MCMC operator for JSA. Our results on the MNIST datasets demonstrate that the JSA's performance is consistently superior to that of competing algorithms like RWS, for learning a range of difficult models.
Dataflow Matrix Machines as a Generalization of Recurrent Neural Networks
Venue: arXiv cs.NE 2018
Year: 2018

Dataflow matrix machines are a powerful generalization of recurrent neural networks. They work with multiple types of arbitrary linear streams, multiple types of powerful neurons, and allow to incorporate higher-order constructions. We expect them to be useful in machine learning and probabilistic programming, and in the synthesis of dynamic systems and of deterministic and probabilistic programs.
Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
Venue: arXiv cs.DS 2018
Year: 2018

We present a new approach for the approximate K-nearest neighbor search based on navigable small world graphs with controllable hierarchy (Hierarchical NSW, HNSW). The proposed solution is fully graph-based, without any need for additional search structures, which are typically used at the coarse search stage of the most proximity graph techniques. Hierarchical NSW incrementally builds a multi-layer structure consisting from hierarchical set of proximity graphs (layers) for nested subsets of the stored elements. The maximum layer in which an element is present is selected randomly with an exponentially decaying probability distribution. This allows producing graphs similar to the previously studied Navigable Small World (NSW) structures while additionally having the links separated by their characteristic distance scales. Starting search from the upper layer together with utilizing the scale separation boosts the performance compared to NSW and allows a logarithmic complexity scaling. Additional employment of a heuristic for selecting proximity graph neighbors significantly increases performance at high recall and in case of highly clustered data. Performance evaluation has demonstrated that the proposed general metric space search index is able to strongly outperform previous opensource state-of-the-art vector-only approaches. Similarity of the algorithm to the skip list structure allows straightforward balanced distributed implementation.
Second-Order Extended Kalman Filter for Extended Object and Group Tracking
Venue: arXiv cs.SY 2018
Year: 2018

In this paper, we propose a novel method for estimating an elliptic shape approximation of a moving extended object that gives rise to multiple scattered measurements per frame. For this purpose, we parameterize the elliptic shape with its orientation and the lengths of the semi-axes. We relate an individual measurement with the ellipse parameters by means of a multiplicative noise model and derive a second-order extended Kalman filter for a closed-form recursive measurement update. The benefits of the new method are discussed by means of Monte Carlo simulations for both static and dynamic scenarios.
Computable dyadic subbases and $\mathbf{T}^ω$-representations of compact sets
Venue: arXiv cs.LO 2018
Year: 2018

We explore representing the compact subsets of a given represented space by infinite sequences over Plotkin's $\mathbb{T}$. We show that computably compact computable metric spaces admit representations of their compact subsets in such a way that compact sets are essentially underspecified points. We can even ensure that a name of an $n$-element compact set contains $n$ occurrences of $\bot$. We undergo this study effectively and show that such a $\mathbb{T}^ω$-representation is effectively obtained from structures of computably compact computable metric spaces. As an application, we prove some statements about the Weihrauch degree of closed choice for finite subsets of computably compact computable metric spaces. Along the way, we introduce the notion of a computable dyadic subbase, and prove that every computably compact computable metric space admits a proper computable dyadic subbase.
Counting Blanks in Polygonal Arrangements
Venue: arXiv cs.CG 2018
Year: 2018

Inside a two dimensional region ("cake"), there are $m$ non-overlapping tiles of a certain kind ("toppings"). We want to expand the toppings while keeping them non-overlapping, and possibly add some blank pieces of the same "certain kind", such that the entire cake is covered. How many blanks must we add? We study this question in several cases: (1) The cake and toppings are general polygons. (2) The cake and toppings are convex figures. (3) The cake and toppings are axes-parallel rectangles. (4) The cake is an axes-parallel rectilinear polygon and the toppings are axes-parallel rectangles. In all four cases, we provide tight bounds on the number of blanks.
Computable performance guarantees for compressed sensing matrices
Venue: arXiv cs.IT 2018
Year: 2018

The null space condition for $\ell_1$ minimization in compressed sensing is a necessary and sufficient condition on the sensing matrices under which a sparse signal can be uniquely recovered from the observation data via $\ell_1$ minimization. However, verifying the null space condition is known to be computationally challenging. Most of the existing methods can provide only upper and lower bounds on the proportion parameter that characterizes the null space condition. In this paper, we propose new polynomial-time algorithms to establish upper bounds of the proportion parameter. We leverage on these techniques to find upper bounds and further develop a new procedure - tree search algorithm - that is able to precisely and quickly verify the null space condition. Numerical experiments show that the execution speed and accuracy of the results obtained from our methods far exceed those of the previous methods which rely on Linear Programming (LP) relaxation and Semidefinite Programming (SDP).
Voynich Manuscript or Book of Dunstan coding and decoding methods
Venue: arXiv cs.CR 2018
Year: 2018

The Voynich manuscript is the book initially dated as fifteenth century book. It written using specific and smart coding methods. This article describes the methods how it was analyzed and how coding keys were found. The last manuscript page decoding. Correlation of the last VMS page content with John Dee notes dedicated to 12th of December 1587. The proof that the Voynich manuscript and the "Book of Dunstan" - the same manuscripts. This article contains Engish version(pages 1-86) and equal Russian (pages 87 - 192) version. The new chapter (#13) is dedicated to Christian symbolics in VMS as well as for the solution of the riddle of 3 queens in astrological part and the riddle of diagram with 2 cancers (red and white) as additional proof of John Dee authorship of manuscript.
Online Dominating Set
Venue: arXiv cs.DS 2018
Year: 2018

This paper is devoted to the online dominating set problem and its variants. We believe the paper represents the first systematic study of the effect of two limitations of online algorithms: making irrevocable decisions while not knowing the future, and being incremental, i.e., having to maintain solutions to all prefixes of the input. This is quantified through competitive analyses of online algorithms against two optimal algorithms, both knowing the entire input, but only one having to be incremental. We also consider the competitive ratio of the weaker of the two optimal algorithms against the other. We consider important graph classes, distinguishing between connected and not necessarily connected graphs. For the classic graph classes of trees, bipartite, planar, and general graphs, we obtain tight results in almost all cases. We also derive upper and lower bounds for the class of bounded-degree graphs. From these analyses, we get detailed information regarding the significance of the necessary requirement that online algorithms be incremental. In some cases, having to be incremental fully accounts for the online algorithm's disadvantage.
Cascading Denial of Service Attacks on Wi-Fi Networks
Venue: arXiv cs.NI 2018
Year: 2018

We unveil the existence of a vulnerability in Wi-Fi, which allows an adversary to remotely launch a Denial-of-Service (DoS) attack that propagates both in time and space. This vulnerability stems from a coupling effect induced by hidden nodes. Cascading DoS attacks can congest an entire network and do not require the adversary to violate any protocol. We demonstrate the feasibility of such attacks through experiments with real Wi-Fi cards, extensive ns-3 simulations, and theoretical analysis. The simulations show that the attack is effective both in networks operating under fixed and varying bit rates, as well as ad hoc and infrastructure modes. To gain insight into the root-causes of the attack, we model the network as a dynamical system and analyze its limiting behavior. The model predicts that a phase transition (and hence a cascading attack) is possible when the retry limit parameter of Wi-Fi is greater or equal to 7, and explicitly characterizes the phase transition region in terms of the system parameters.
Deep CNNs for HEp-2 Cells Classification : A Cross-specimen Analysis
Venue: arXiv cs.CV 2018
Year: 2018

Automatic classification of Human Epithelial Type-2 (HEp-2) cells staining patterns is an important and yet a challenging problem. Although both shallow and deep methods have been applied, the study of deep convolutional networks (CNNs) on this topic is shallow to date, thus failed to claim its top position for this problem. In this paper, we propose a novel study of using CNNs for HEp-2 cells classification focusing on cross-specimen analysis, a key evaluation for generalization. For the first time, our study reveals several key factors of using CNNs for HEp-2 cells classification. Our proposed system achieves state-of-the-art classification accuracy on public benchmark dataset. Comparative experiments on different training data reveals that adding different specimens,rather than increasing in numbers by affine transformations, helps to train a good deep model. This opens a new avenue for adopting deep CNNs to HEp-2 cells classification.