OpenRaiser/Intern-Atlas huggingface dataset:
Simple, compact and robust approximate string dictionary
Venue: arXiv cs.DS 2014
Year: 2014

This paper is concerned with practical implementations of approximate string dictionaries that allow edit errors. In this problem, we have as input a dictionary $D$ of $d$ strings of total length $n$ over an alphabet of size $σ$. Given a bound $k$ and a pattern $x$ of length $m$, a query has to return all the strings of the dictionary which are at edit distance at most $k$ from $x$, where the edit distance between two strings $x$ and $y$ is defined as the minimum-cost sequence of edit operations that transform $x$ into $y$. The cost of a sequence of operations is defined as the sum of the costs of the operations involved in the sequence. In this paper, we assume that each of these operations has unit cost and consider only three operations: deletion of one character, insertion of one character and substitution of a character by another. We present a practical implementation of the data structure we recently proposed and which works only for one error. We extend the scheme to $2\leq k<m$. Our implementation has many desirable properties: it has a very fast and space-efficient building algorithm. The dictionary data structure is compact and has fast and robust query time. Finally our data structure is simple to implement as it only uses basic techniques from the literature, mainly hashing (linear probing and hash signatures) and succinct data structures (bitvectors supporting rank queries).
Sparse, complex-valued representations of natural sounds learned with phase and amplitude continuity priors
Venue: arXiv cs.LG 2014
Year: 2014

Complex-valued sparse coding is a data representation which employs a dictionary of two-dimensional subspaces, while imposing a sparse, factorial prior on complex amplitudes. When trained on a dataset of natural image patches, it learns phase invariant features which closely resemble receptive fields of complex cells in the visual cortex. Features trained on natural sounds however, rarely reveal phase invariance and capture other aspects of the data. This observation is a starting point of the present work. As its first contribution, it provides an analysis of natural sound statistics by means of learning sparse, complex representations of short speech intervals. Secondly, it proposes priors over the basis function set, which bias them towards phase-invariant solutions. In this way, a dictionary of complex basis functions can be learned from the data statistics, while preserving the phase invariance property. Finally, representations trained on speech sounds with and without priors are compared. Prior-based basis functions reveal performance comparable to unconstrained sparse coding, while explicitely representing phase as a temporal shift. Such representations can find applications in many perceptual and machine learning tasks.
An exercise on streams: convergence acceleration
Venue: arXiv cs.NA 2014
Year: 2014

This paper presents convergence acceleration, a method for computing efficiently the limit of numerical sequences as a typical application of streams and higher-order functions.
Millimeter Wave Channel Modeling and Cellular Capacity Evaluation
Venue: arXiv cs.NI 2014
Year: 2014

With the severe spectrum shortage in conventional cellular bands, millimeter wave (mmW) frequencies between 30 and 300 GHz have been attracting growing attention as a possible candidate for next-generation micro- and picocellular wireless networks. The mmW bands offer orders of magnitude greater spectrum than current cellular allocations and enable very high-dimensional antenna arrays for further gains via beamforming and spatial multiplexing. This paper uses recent real-world measurements at 28 and 73 GHz in New York City to derive detailed spatial statistical models of the channels and uses these models to provide a realistic assessment of mmW micro- and picocellular networks in a dense urban deployment. Statistical models are derived for key channel parameters including the path loss, number of spatial clusters, angular dispersion and outage. It is found that, even in highly non-line-of-sight environments, strong signals can be detected 100 m to 200 m from potential cell sites, potentially with multiple clusters to support spatial multiplexing. Moreover, a system simulation based on the models predicts that mmW systems can offer an order of magnitude increase in capacity over current state-of-the-art 4G cellular networks with no increase in cell density from current urban deployments.
Asynchronous Adaptation and Learning over Networks - Part II: Performance Analysis
Venue: arXiv cs.SY 2014
Year: 2014

In Part I \cite{Zhao13TSPasync1}, we introduced a fairly general model for asynchronous events over adaptive networks including random topologies, random link failures, random data arrival times, and agents turning on and off randomly. We performed a stability analysis and established the notable fact that the network is still able to converge in the mean-square-error sense to the desired solution. Once stable behavior is guaranteed, it becomes important to evaluate how fast the iterates converge and how close they get to the optimal solution. This is a demanding task due to the various asynchronous events and due to the fact that agents influence each other. In this Part II, we carry out a detailed analysis of the mean-square-error performance of asynchronous strategies for solving distributed optimization and adaptation problems over networks. We derive analytical expressions for the mean-square convergence rate and the steady-state mean-square-deviation. The expressions reveal how the various parameters of the asynchronous behavior influence network performance. In the process, we establish the interesting conclusion that even under the influence of asynchronous events, all agents in the adaptive network can still reach an $O(ν^{1 + γ_o'})$ near-agreement with some $γ_o' > 0$ while approaching the desired solution within $O(ν)$ accuracy, where $ν$ is proportional to the small step-size parameter for adaptation.
Asynchronous Adaptation and Learning over Networks - Part III: Comparison Analysis
Venue: arXiv cs.SY 2014
Year: 2014

In Part II [3] we carried out a detailed mean-square-error analysis of the performance of asynchronous adaptation and learning over networks under a fairly general model for asynchronous events including random topologies, random link failures, random data arrival times, and agents turning on and off randomly. In this Part III, we compare the performance of synchronous and asynchronous networks. We also compare the performance of decentralized adaptation against centralized stochastic-gradient (batch) solutions. Two interesting conclusions stand out. First, the results establish that the performance of adaptive networks is largely immune to the effect of asynchronous events: the mean and mean-square convergence rates and the asymptotic bias values are not degraded relative to synchronous or centralized implementations. Only the steady-state mean-square-deviation suffers a degradation in the order of $ν$, which represents the small step-size parameters used for adaptation. Second, the results show that the adaptive distributed network matches the performance of the centralized solution. These conclusions highlight another critical benefit of cooperation by networked agents: cooperation does not only enhance performance in comparison to stand-alone single-agent processing, but it also endows the network with remarkable resilience to various forms of random failure events and is able to deliver performance that is as powerful as batch solutions.
Optimal Combinatorial Batch Codes based on Block Designs
Venue: arXiv cs.DM 2014
Year: 2014

Batch codes, introduced by Ishai, Kushilevitz, Ostrovsky and Sahai, represent the distributed storage of an $n$-element data set on $m$ servers in such a way that any batch of $k$ data items can be retrieved by reading at most one (or more generally, $t$) items from each server, while keeping the total storage over $m$ servers equal to $N$. This paper considers a class of batch codes (for $t=1$), called combinatorial batch codes (CBC), where each server stores a subset of a database. A CBC is called optimal if the total storage $N$ is minimal for given $n,m$, and $k$. A $c$-uniform CBC is a combinatorial batch code where each item is stored in exactly $c$ servers. A $c$-uniform CBC is called optimal if its parameter $n$ has maximum value for given $m$ and $k$. Optimal $c$-uniform CBCs have been known only for $c\in \{2,k-1,k-2\}$. In this paper we present new constructions of optimal CBCs in both the uniform and general settings, for values of the parameters where tight bounds have not been established previously. In the uniform setting, we provide constructions of two new families of optimal uniform codes with $c\sim \sqrt{k}$. Our constructions are based on affine planes and transversal designs.
Learning Type-Driven Tensor-Based Meaning Representations
Venue: arXiv cs.CL 2014
Year: 2014

This paper investigates the learning of 3rd-order tensors representing the semantics of transitive verbs. The meaning representations are part of a type-driven tensor-based semantic framework, from the newly emerging field of compositional distributional semantics. Standard techniques from the neural networks literature are used to learn the tensors, which are tested on a selectional preference-style task with a simple 2-dimensional sentence space. Promising results are obtained against a competitive corpus-based baseline. We argue that extending this work beyond transitive verbs, and to higher-dimensional sentence spaces, is an interesting and challenging problem for the machine learning community to consider.
A note on the undercut procedure
Venue: arXiv cs.GT 2014
Year: 2014

The undercut procedure was presented by Brams et al. [2] as a procedure for identifying an envy-free allocation when agents have preferences over sets of objects. They assumed that agents have strict preferences over objects and their preferences are extended over to sets of objects via the responsive set extension. We point out some shortcomings of the undercut procedure. We then simplify the undercut procedure of Brams et al. [2] and show that it works under a more general condition where agents may express indifference between objects and they may not necessarily have responsive preferences over sets of objects. Finally, we show that the procedure works even if agents have unequal claims.
Book inequalities
Venue: arXiv cs.IT 2014
Year: 2014

Information theoretical inequalities have strong ties with polymatroids and their representability. A polymatroid is entropic if its rank function is given by the Shannon entropy of the subsets of some discrete random variables. The book is a special iterated adhesive extension of a polymatroid with the property that entropic polymatroids have $n$-page book extensions over an arbitrary spine. We prove that every polymatroid has an $n$-page book extension over a single element and over an all-but-one-element spine. Consequently, for polymatroids on four elements, only book extensions over a two-element spine should be considered. F. Matúš proved that the Zhang-Yeung inequalities characterize polymatroids on four elements which have such a 2-page book extension. The $n$-page book inequalities, defined in this paper, are conjectured to characterize polymatroids on four elements which have $n$-page book extensions over a two-element spine. We prove that the condition is necessary; consequently every book inequality is an information inequality on four random variables. Using computer-aided multiobjective optimization, the sufficiency of the condition is verified up to 9-page book extensions.
Faster all-pairs shortest paths via circuit complexity
Venue: arXiv cs.DS 2014
Year: 2014

We present a new randomized method for computing the min-plus product (a.k.a., tropical product) of two $n \times n$ matrices, yielding a faster algorithm for solving the all-pairs shortest path problem (APSP) in dense $n$-node directed graphs with arbitrary edge weights. On the real RAM, where additions and comparisons of reals are unit cost (but all other operations have typical logarithmic cost), the algorithm runs in time \[\frac{n^3}{2^{Ω(\log n)^{1/2}}}\] and is correct with high probability. On the word RAM, the algorithm runs in $n^3/2^{Ω(\log n)^{1/2}} + n^{2+o(1)}\log M$ time for edge weights in $([0,M] \cap {\mathbb Z})\cup\{\infty\}$. Prior algorithms used either $n^3/(\log^c n)$ time for various $c \leq 2$, or $O(M^αn^β)$ time for various $α> 0$ and $β> 2$. The new algorithm applies a tool from circuit complexity, namely the Razborov-Smolensky polynomials for approximately representing ${\sf AC}^0[p]$ circuits, to efficiently reduce a matrix product over the $(\min,+)$ algebra to a relatively small number of rectangular matrix products over ${\mathbb F}_2$, each of which are computable using a particularly efficient method due to Coppersmith. We also give a deterministic version of the algorithm running in $n^3/2^{\log^δ n}$ time for some $δ> 0$, which utilizes the Yao-Beigel-Tarui translation of ${\sf AC}^0[m]$ circuits into "nice" depth-two circuits.
Joint Transmitter and Receiver Energy Minimization in Multiuser OFDM Systems
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we formulate and solve a weighted-sum transmitter and receiver energy minimization (WSTREMin) problem in the downlink of an orthogonal frequency division multiplexing (OFDM) based multiuser wireless system. The proposed approach offers the flexibility of assigning different levels of importance to base station (BS) and mobile terminal (MT) power consumption, corresponding to the BS being connected to the grid and the MT relying on batteries. To obtain insights into the characteristics of the problem, we first consider two extreme cases separately, i.e., weighted-sum receiver-side energy minimization (WSREMin) for MTs and transmitter-side energy minimization (TEMin) for the BS. It is shown that Dynamic TDMA (D-TDMA), where MTs are scheduled for single-user OFDM transmissions over orthogonal time slots, is the optimal transmission strategy for WSREMin at MTs, while OFDMA is optimal for TEMin at the BS. As a hybrid of the two extreme cases, we further propose a new multiple access scheme, i.e., Time-Slotted OFDMA (TS-OFDMA) scheme, in which MTs are grouped into orthogonal time slots with OFDMA applied to users assigned within the same slot. TS-OFDMA can be shown to include both D-TDMA and OFDMA as special cases. Numerical results confirm that the proposed schemes enable a flexible range of energy consumption tradeoffs between the BS and MTs.
Minimum Dominating Set for a Point Set in $\IR^2$
Venue: arXiv cs.DS 2014
Year: 2014

In this article, we consider the problem of computing minimum dominating set for a given set $S$ of $n$ points in $\IR^2$. Here the objective is to find a minimum cardinality subset $S'$ of $S$ such that the union of the unit radius disks centered at the points in $S'$ covers all the points in $S$. We first propose a simple 4-factor and 3-factor approximation algorithms in $O(n^6 \log n)$ and $O(n^{11} \log n)$ time respectively improving time complexities by a factor of $O(n^2)$ and $O(n^4)$ respectively over the best known result available in the literature [M. De, G.K. Das, P. Carmi and S.C. Nandy, {\it Approximation algorithms for a variant of discrete piercing set problem for unit disk}, Int. J. of Comp. Geom. and Appl., to appear]. Finally, we propose a very important shifting lemma, which is of independent interest and using this lemma we propose a $\frac{5}{2}$-factor approximation algorithm and a PTAS for the minimum dominating set problem.
Model reduction of networked passive systems through clustering
Venue: arXiv cs.SY 2014
Year: 2014

In this paper, a model reduction procedure for a network of interconnected identical passive subsystems is presented. Here, rather than performing model reduction on the subsystems, adjacent subsystems are clustered, leading to a reduced-order networked system that allows for a convenient physical interpretation. The identification of the subsystems to be clustered is performed through controllability and observability analysis of an associated edge system and it is shown that the property of synchronization (i.e., the convergence of trajectories of the subsystems to each other) is preserved during reduction. The results are illustrated by means of an example.
On the Minimum Decoding Delay of Balanced Complex Orthogonal Design
Venue: arXiv cs.IT 2014
Year: 2014

Complex orthogonal design (COD) with parameter $[p, n, k]$ is a combinatorial design used in space-time block codes (STBCs). For STBC, $n$ is the number of antennas, $k/p$ is the rate, and $p$ is the decoding delay. A class of rate $1/2$ COD called balanced complex orthogonal design (BCOD) has been proposed by Adams et al., and they constructed BCODs with rate $k/p = 1/2$ and decoding delay $p = 2^m$ for $n=2m$. Furthermore, they prove that the constructions have optimal decoding delay when $m$ is congruent to $1$, $2$, or $3$ module $4$. They conjecture that for the case $m \equiv 0 \pmod 4$, $2^m$ is also a lower bound of $p$. In this paper, we prove this conjecture.
The H2 Control Problem for Quadratically Invariant Systems with Delays
Venue: arXiv cs.SY 2014
Year: 2014

This paper gives a new solution to the output feedback H2 problem for quadratically invariant communication delay patterns. A characterization of all stabilizing controllers satisfying the delay constraints is given and the decentralized H2 problem is cast as a convex model matching problem. The main result shows that the model matching problem can be reduced to a finite-dimensional quadratic program. A recursive state-space method for computing the optimal controller based on vectorization is given.
On Minimal Trajectories for Mobile Sampling of Bandlimited Fields
Venue: arXiv cs.IT 2014
Year: 2014

We study the design of sampling trajectories for stable sampling and the reconstruction of bandlimited spatial fields using mobile sensors. The spectrum is assumed to be a symmetric convex set. As a performance metric we use the path density of the set of sampling trajectories that is defined as the total distance traveled by the moving sensors per unit spatial volume of the spatial region being monitored. Focussing first on parallel lines, we identify the set of parallel lines with minimal path density that contains a set of stable sampling for fields bandlimited to a known set. We then show that the problem becomes ill-posed when the optimization is performed over all trajectories by demonstrating a feasible trajectory set with arbitrarily low path density. However, the problem becomes well-posed if we explicitly specify the stability margins. We demonstrate this by obtaining a non-trivial lower bound on the path density of an arbitrary set of trajectories that contain a sampling set with explicitly specified stability bounds.
A DDoS-Aware IDS Model Based on Danger Theory and Mobile Agents
Venue: arXiv cs.DC 2014
Year: 2014

We propose an artificial immune model for intrusion detection in distributed systems based on a relatively recent theory in immunology called Danger theory. Based on Danger theory, immune response in natural systems is a result of sensing corruption as well as sensing unknown substances. In contrast, traditional self-nonself discrimination theory states that immune response is only initiated by sensing nonself (unknown) patterns. Danger theory solves many problems that could only be partially explained by the traditional model. Although the traditional model is simpler, such problems result in high false positive rates in immune-inspired intrusion detection systems. We believe using danger theory in a multi-agent environment that computationally emulates the behavior of natural immune systems is effective in reducing false positive rates. We first describe a simplified scenario of immune response in natural systems based on danger theory and then, convert it to a computational model as a network protocol. In our protocol, we define several immune signals and model cell signaling via message passing between agents that emulate cells. Most messages include application-specific patterns that must be meaningfully extracted from various system properties. We show how to model these messages in practice by performing a case study on the problem of detecting distributed denial-of-service attacks in wireless sensor networks. We conduct a set of systematic experiments to find a set of performance metrics that can accurately distinguish malicious patterns. The results indicate that the system can be efficiently used to detect malicious patterns with a high level of accuracy.
On structural properties of trees with minimal atom-bond connectivity index
Venue: arXiv cs.DM 2014
Year: 2014

The {\em atom-bond connectivity (ABC) index} is a degree-based molecular descriptor, that found chemical applications. It is well known that among all connected graphs, the graphs with minimal ABC index are trees. A complete characterization of trees with minimal $ABC$ index is still an open problem. In this paper, we present new structural properties of trees with minimal ABC index. Our main results reveal that trees with minimal ABC index do not contain so-called {\em $B_k$-branches}, with $k \geq 5$, and that they do not have more than four $B_4$-branches.
Generalization Bounds for Representative Domain Adaptation
Venue: arXiv cs.LG 2014
Year: 2014

In this paper, we propose a novel framework to analyze the theoretical properties of the learning process for a representative type of domain adaptation, which combines data from multiple sources and one target (or briefly called representative domain adaptation). In particular, we use the integral probability metric to measure the difference between the distributions of two domains and meanwhile compare it with the H-divergence and the discrepancy distance. We develop the Hoeffding-type, the Bennett-type and the McDiarmid-type deviation inequalities for multiple domains respectively, and then present the symmetrization inequality for representative domain adaptation. Next, we use the derived inequalities to obtain the Hoeffding-type and the Bennett-type generalization bounds respectively, both of which are based on the uniform entropy number. Moreover, we present the generalization bounds based on the Rademacher complexity. Finally, we analyze the asymptotic convergence and the rate of convergence of the learning process for representative domain adaptation. We discuss the factors that affect the asymptotic behavior of the learning process and the numerical experiments support our theoretical findings as well. Meanwhile, we give a comparison with the existing results of domain adaptation and the classical results under the same-distribution assumption.
Faster 3-Periodic Merging Networks
Venue: arXiv cs.DS 2014
Year: 2014

We consider the problem of merging two sorted sequences on a comparator network that is used repeatedly, that is, if the output is not sorted, the network is applied again using the output as input. The challenging task is to construct such networks of small depth. The first constructions of merging networks with a constant period were given by Kutyłowski, Loryś and Oesterdikhoff. They have given $3$-periodic network that merges two sorted sequences of $N$ numbers in time $12\log N$ and a similar network of period $4$ that works in $5.67\log N$. We present a new family of such networks that are based on Canfield and Williamson periodic sorter. Our $3$-periodic merging networks work in time upper-bounded by $6\log N$. The construction can be easily generalized to larger constant periods with decreasing running time, for example, to $4$-periodic ones that work in time upper-bounded by $4\log N$. Moreover, to obtain the facts we have introduced a new proof technique.