OpenRaiser/Intern-Atlas huggingface dataset:
Network Coding as a WiMAX Link Reliability Mechanism
Venue: arXiv cs.NI 2013
Year: 2013

We design and implement a network-coding-enabled reliability architecture for next generation wireless networks. Our network coding (NC) architecture uses a flexible thread-based design, with each encoder-decoder instance applying systematic intra-session random linear network coding as a packet erasure code at the IP layer, to ensure the fast and reliable transfer of information between wireless nodes. Using Global Environment for Network Innovations (GENI) WiMAX platforms, a series of point-to-point transmission experiments were conducted to compare the performance of the NC architecture to that of the Automatic Repeated reQuest (ARQ) and Hybrid ARQ (HARQ) mechanisms. At the application layer, Iperf and UDP-based File Transfer Protocol (UFTP) are used to measure throughput, packet loss and file transfer delay. In our selected scenarios, the proposed architecture is able to decrease packet loss from around 11-32% to nearly 0%; compared to HARQ and joint HARQ/ARQ mechanisms, the NC architecture offers up to 5.9 times gain in throughput and 5.5 times reduction in end-to-end file transfer delay. Our experiments show that network coding as a packet erasure code in the upper layers of the protocol stack has the potential to reduce the need for joint HARQ/ARQ schemes in the PHY/MAC layers, thus offering insights into cross-layer designs of efficient next generation wireless networks.
Worst-Case Expected-Capacity Loss of Slow-Fading Channels
Venue: arXiv cs.IT 2013
Year: 2013

For delay-limited communication over block-fading channels, the difference between the ergodic capacity and the maximum achievable expected rate for coding over a finite number of coherent blocks represents a fundamental measure of the penalty incurred by the delay constraint. This paper introduces a notion of worst-case expected-capacity loss. Focusing on the slow-fading scenario (one-block delay), the worst-case additive and multiplicative expected-capacity losses are precisely characterized for the point-to-point fading channel. Extension to the problem of writing on fading paper is also considered, where both the ergodic capacity and the additive expected-capacity loss over one-block delay are characterized to within one bit per channel use.
The simplex method is strongly polynomial for deterministic Markov decision processes
Venue: arXiv cs.DS 2013
Year: 2013

We prove that the simplex method with the highest gain/most-negative-reduced cost pivoting rule converges in strongly polynomial time for deterministic Markov decision processes (MDPs) regardless of the discount factor. For a deterministic MDP with n states and m actions, we prove the simplex method runs in O(n^3m^2log^2 n) iterations if the discount factor is uniform and O(n^5m^3log^2 n) iterations if each action has a distinct discount factor. Previously the simplex method was known to run in polynomial time only for discounted MDPs where the discount was bounded away from 1 [Ye11]. Unlike in the discounted case, the algorithm does not greedily converge to the optimum, and we require a more complex measure of progress. We identify a set of layers in which the values of primal variables must lie and show that the simplex method always makes progress optimizing one layer, and when the upper layer is updated the algorithm makes a substantial amount of progress. In the case of nonuniform discounts, we define a polynomial number of "milestone" policies and we prove that, while the objective function may not improve substantially overall, the value of at least one dual variable is always making progress towards some milestone, and the algorithm will reach the next milestone in a polynomial number of steps.
On sets of numbers rationally represented in a rational base number system
Venue: arXiv cs.FL 2013
Year: 2013

In this work, it is proved that a set of numbers closed under addition and whose representations in a rational base numeration system is a rational language is not a finitely generated additive monoid. A key to the proof is the definition of a strong combinatorial property on languages : the bounded left iteration property. It is both an unnatural property in usual formal language theory (as it contradicts any kind of pumping lemma) and an ideal fit to the languages defined through rational base number systems.
Near-Optimal Blacklisting
Venue: arXiv cs.CR 2013
Year: 2013

Many applications involve agents sharing a resource, such as networks or services. When agents are honest, the system functions well and there is a net profit. Unfortunately, some agents may be malicious, but it may be hard to detect them. We consider the intrusion response problem of how to permanently blacklist agents, in order to maximise expected profit. This is not trivial, as blacklisting may erroneously expel honest agents. Conversely, while we gain information by allowing an agent to remain, we may incur a cost due to malicious behaviour. We present an efficient algorithm (HIPER) for making near-optimal decisions for this problem. Additionally, we derive three algorithms by reducing the problem to a Markov decision process (MDP). Theoretically, we show that HIPER is near-optimal. Experimentally, its performance is close to that of the full MDP solution, when the (stronger) requirements of the latter are met.
Minimum Complexity Pursuit for Universal Compressed Sensing
Venue: arXiv cs.IT 2013
Year: 2013

The nascent field of compressed sensing is founded on the fact that high-dimensional signals with "simple structure" can be recovered accurately from just a small number of randomized samples. Several specific kinds of structures have been explored in the literature, from sparsity and group sparsity to low-rankness. However, two fundamental questions have been left unanswered, namely: What are the general abstract meanings of "structure" and "simplicity"? And do there exist universal algorithms for recovering such simple structured objects from fewer samples than their ambient dimension? In this paper, we address these two questions. Using algorithmic information theory tools such as the Kolmogorov complexity, we provide a unified definition of structure and simplicity. Leveraging this new definition, we develop and analyze an abstract algorithm for signal recovery motivated by Occam's Razor.Minimum complexity pursuit (MCP) requires just O(3κ) randomized samples to recover a signal of complexity κand ambient dimension n. We also discuss the performance of MCP in the presence of measurement noise and with approximately simple signals.
Authorship Identification in Bengali Literature: a Comparative Analysis
Venue: arXiv cs.CL 2013
Year: 2013

Stylometry is the study of the unique linguistic styles and writing behaviors of individuals. It belongs to the core task of text categorization like authorship identification, plagiarism detection etc. Though reasonable number of studies have been conducted in English language, no major work has been done so far in Bengali. In this work, We will present a demonstration of authorship identification of the documents written in Bengali. We adopt a set of fine-grained stylistic features for the analysis of the text and use them to develop two different models: statistical similarity model consisting of three measures and their combination, and machine learning model with Decision Tree, Neural Network and SVM. Experimental results show that SVM outperforms other state-of-the-art methods after 10-fold cross validations. We also validate the relative importance of each stylistic feature to show that some of them remain consistently significant in every model used in this experiment.
The finiteness of a group generated by a 2-letter invertible-reversible Mealy automaton is decidable
Venue: arXiv cs.FL 2013
Year: 2013

We prove that a semigroup generated by a reversible two-state Mealy automaton is either finite or free of rank 2. This fact leads to the decidability of finiteness for groups generated by two-state or two-letter invertible-reversible Mealy automata and to the decidability of freeness for semigroups generated by two-state invertible-reversible Mealy automata.
Adaptive Smolyak Pseudospectral Approximations
Venue: arXiv cs.NA 2013
Year: 2013

Polynomial approximations of computationally intensive models are central to uncertainty quantification. This paper describes an adaptive method for non-intrusive pseudospectral approximation, based on Smolyak's algorithm with generalized sparse grids. We rigorously analyze and extend the non-adaptive method proposed in [6], and compare it to a common alternative approach for using sparse grids to construct polynomial approximations, direct quadrature. Analysis of direct quadrature shows that O(1) errors are an intrinsic property of some configurations of the method, as a consequence of internal aliasing. We provide precise conditions, based on the chosen polynomial basis and quadrature rules, under which this aliasing error occurs. We then establish theoretical results on the accuracy of Smolyak pseudospectral approximation, and show that the Smolyak approximation avoids internal aliasing and makes far more effective use of sparse function evaluations. These results are applicable to broad choices of quadrature rule and generalized sparse grids. Exploiting this flexibility, we introduce a greedy heuristic for adaptive refinement of the pseudospectral approximation. We numerically demonstrate convergence of the algorithm on the Genz test functions, and illustrate the accuracy and efficiency of the adaptive approach on a realistic chemical kinetics problem.
On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization
Venue: arXiv cs.LG 2013
Year: 2013

The problem of stochastic convex optimization with bandit feedback (in the learning community) or without knowledge of gradients (in the optimization community) has received much attention in recent years, in the form of algorithms and performance upper bounds. However, much less is known about the inherent complexity of these problems, and there are few lower bounds in the literature, especially for nonlinear functions. In this paper, we investigate the attainable error/regret in the bandit and derivative-free settings, as a function of the dimension d and the available number of queries T. We provide a precise characterization of the attainable performance for strongly-convex and smooth functions, which also imply a non-trivial lower bound for more general problems. Moreover, we prove that in both the bandit and derivative-free setting, the required number of queries must scale at least quadratically with the dimension. Finally, we show that on the natural class of quadratic functions, it is possible to obtain a "fast" O(1/T) error rate in terms of T, under mild assumptions, even without having access to gradients. To the best of our knowledge, this is the first such rate in a derivative-free stochastic setting, and holds despite previous results which seem to imply the contrary.
Stable Manifold Embeddings with Structured Random Matrices
Venue: arXiv cs.IT 2013
Year: 2013

The fields of compressed sensing (CS) and matrix completion have shown that high-dimensional signals with sparse or low-rank structure can be effectively projected into a low-dimensional space (for efficient acquisition or processing) when the projection operator achieves a stable embedding of the data by satisfying the Restricted Isometry Property (RIP). It has also been shown that such stable embeddings can be achieved for general Riemannian submanifolds when random orthoprojectors are used for dimensionality reduction. Due to computational costs and system constraints, the CS community has recently explored the RIP for structured random matrices (e.g., random convolutions, localized measurements, deterministic constructions). The main contribution of this paper is to show that any matrix satisfying the RIP (i.e., providing a stable embedding for sparse signals) can be used to construct a stable embedding for manifold-modeled signals by randomizing the column signs and paying reasonable additional factors in the number of measurements. We demonstrate this result with several new constructions for stable manifold embeddings using structured matrices. This result allows advances in efficient projection schemes for sparse signals to be immediately applied to manifold signal models.
Low-Complexity Quantized Switching Controllers using Approximate Bisimulation
Venue: arXiv cs.SY 2013
Year: 2013

In this paper, we consider the problem of synthesizing low-complexity controllers for incrementally stable switched systems. For that purpose, we establish a new approximation result for the computation of symbolic models that are approximately bisimilar to a given switched system. The main advantage over existing results is that it allows us to design naturally quantized switching controllers for safety or reachability specifications; these can be pre-computed offline and therefore the online execution time is reduced. Then, we present a technique to reduce the memory needed to store the control law by borrowing ideas from algebraic decision diagrams for compact function representation and by exploiting the non-determinism of the synthesized controllers. We show the merits of our approach by applying it to a simple model of temperature regulation in a building.
History-Preserving Bisimilarity for Higher-Dimensional Automata via Open Maps
Venue: arXiv cs.LO 2013
Year: 2013

We show that history-preserving bisimilarity for higher-dimensional automata has a simple characterization directly in terms of higher-dimensional transitions. This implies that it is decidable for finite higher-dimensional automata. To arrive at our characterization, we apply the open-maps framework of Joyal, Nielsen and Winskel in the category of unfoldings of precubical sets.
Structure theorem of square complex orthogonal design
Venue: arXiv cs.IT 2013
Year: 2013

Square COD (complex orthogonal design) with size $[n, n, k]$ is an $n \times n$ matrix $\mathcal{O}_z$, where each entry is a complex linear combination of $z_i$ and their conjugations $z_i^*$, $i=1,\ldots, k$, such that $\mathcal{O}_z^H \mathcal{O}_z = (|z_1|^2 + \ldots + |z_k|^2)I_n$. Closely following the work of Hottinen and Tirkkonen, which proved an upper bound of $k/n$ by making a crucial observation between square COD and group representation, we prove the structure theorem of square COD.
Decentralized Routing on Spatial Networks with Stochastic Edge Weights
Venue: arXiv cs.SI 2013
Year: 2013

We investigate algorithms to find short paths in spatial networks with stochastic edge weights. Our formulation of the problem of finding short paths differs from traditional formulations because we specifically do not make two of the usual simplifying assumptions: (1) we allow edge weights to be stochastic rather than deterministic; and (2) we do not assume that global knowledge of a network is available. We develop a decentralized routing algorithm that provides en route guidance for travelers on a spatial network with stochastic edge weights without the need to rely on global knowledge about the network. To guide a traveler, our algorithm uses an estimation function that evaluates cumulative arrival probability distributions based on distances between pairs of nodes. The estimation function carries a notion of proximity between nodes and thereby enables routing without global knowledge. In testing our decentralized algorithm, we define a criterion that allows one to discriminate among arrival probability distributions, and we test our algorithm and this criterion using both synthetic and real networks.
Leapfrog Triejoin: a worst-case optimal join algorithm
Venue: arXiv cs.DB 2013
Year: 2013

Recent years have seen exciting developments in join algorithms. In 2008, Atserias, Grohe and Marx (henceforth AGM) proved a tight bound on the maximum result size of a full conjunctive query, given constraints on the input relation sizes. In 2012, Ngo, Porat, R{é} and Rudra (henceforth NPRR) devised a join algorithm with worst-case running time proportional to the AGM bound. Our commercial Datalog system LogicBlox employs a novel join algorithm, \emph{leapfrog triejoin}, which compared conspicuously well to the NPRR algorithm in preliminary benchmarks. This spurred us to analyze the complexity of leapfrog triejoin. In this paper we establish that leapfrog triejoin is also worst-case optimal, up to a log factor, in the sense of NPRR. We improve on the results of NPRR by proving that leapfrog triejoin achieves worst-case optimality for finer-grained classes of database instances, such as those defined by constraints on projection cardinalities. We show that NPRR is \emph{not} worst-case optimal for such classes, giving a counterexample where leapfrog triejoin runs in $O(n \log n)$ time, compared to $Θ(n^{1.375})$ time for NPRR. On a practical note, leapfrog triejoin can be implemented using conventional data structures such as B-trees, and extends naturally to $\exists_1$ queries. We believe our algorithm offers a useful addition to the existing toolbox of join algorithms, being easy to absorb, simple to implement, and having a concise optimality proof.
Two-step greedy algorithm for reduced order quadratures
Venue: arXiv cs.NA 2013
Year: 2013

We present an algorithm to generate application-specific, global reduced order quadratures (ROQ) for multiple fast evaluations of weighted inner products between parameterized functions. If a reduced basis (RB) or any other projection-based model reduction technique is applied, the dimensionality of integrands is reduced dramatically; however, the cost of approximating the integrands by projection still scales as the size of the original problem. In contrast, using discrete empirical interpolation (DEIM) points as ROQ nodes leads to a computational cost which depends linearly on the dimension of the reduced space. Generation of a reduced basis via a greedy procedure requires a training set, which for products of functions can be very large. Since this direct approach can be impractical in many applications, we propose instead a two-step greedy targeted towards approximation of such products. We present numerical experiments demonstrating the accuracy and the efficiency of the two-step approach. The presented ROQ are expected to display very fast convergence whenever there is regularity with respect to parameter variation. We find that for the particular application here considered, one driven by gravitational wave physics, the two-step approach speeds up the offline computations to build the ROQ by more than two orders of magnitude. Furthermore, the resulting ROQ rule is found to converge exponentially with the number of nodes, and a factor of ~50 savings, without loss of accuracy, is observed in evaluations of inner products when ROQ are used as a downsampling strategy for equidistant samples using the trapezoidal rule. While the primary focus of this paper is on quadrature rules for inner products of parameterized functions, our method can be easily adapted to integrations of single parameterized functions, and some examples of this type are considered.
Nonparametric Unsupervised Classification
Venue: arXiv cs.LG 2013
Year: 2013

Unsupervised classification methods learn a discriminative classifier from unlabeled data, which has been proven to be an effective way of simultaneously clustering the data and training a classifier from the data. Various unsupervised classification methods obtain appealing results by the classifiers learned in an unsupervised manner. However, existing methods do not consider the misclassification error of the unsupervised classifiers except unsupervised SVM, so the performance of the unsupervised classifiers is not fully evaluated. In this work, we study the misclassification error of two popular classifiers, i.e. the nearest neighbor classifier (NN) and the plug-in classifier, in the setting of unsupervised classification.
Cross-Layer Scheduling in Multi-user System with Delay and Secrecy Constraints
Venue: arXiv cs.IT 2013
Year: 2013

Recently, physical layer security based approaches have drawn considerable attentions and are envisaged to provide secure communications in the wireless networks. However, most existing literatures only focus on the physical layer. Thus, how to design an effective transmission scheme which also considers the requirements from the upper layers is still an unsolved problem. We consider such cross-layer resource allocation problem in the multi-user downlink environment for both having instantaneous and partial eavesdropping channel information scenarios. The problem is first formulated in a new security framework. Then, the control scheme is designed to maximize the average admission rate of the data, incorporating delay, power, and secrecy as constraints, for both non-colluding and colluding eavesdropping cases in each scenario. Performance analysis is given based on the stochastic optimization theory and the simulations are carried out to validate the effectiveness of our scheme.
Community Structure Detection in Complex Networks with Partial Background Information
Venue: arXiv cs.SI 2013
Year: 2013

Constrained clustering has been well-studied in the unsupervised learning society. However, how to encode constraints into community structure detection, within complex networks, remains a challenging problem. In this paper, we propose a semi-supervised learning framework for community structure detection. This framework implicitly encodes the must-link and cannot-link constraints by modifying the adjacency matrix of network, which can also be regarded as de-noising the consensus matrix of community structures. Our proposed method gives consideration to both the topology and the functions (background information) of complex network, which enhances the interpretability of the results. The comparisons performed on both the synthetic benchmarks and the real-world networks show that the proposed framework can significantly improve the community detection performance with few constraints, which makes it an attractive methodology in the analysis of complex networks.
On Optimal TCM Encoders
Venue: arXiv cs.IT 2013
Year: 2013

An asymptotically optimal trellis-coded modulation (TCM) encoder requires the joint design of the encoder and the binary labeling of the constellation. Since analytical approaches are unknown, the only available solution is to perform an exhaustive search over the encoder and the labeling. For large constellation sizes and/or many encoder states, however, an exhaustive search is unfeasible. Traditional TCM designs overcome this problem by using a labeling that follows the set-partitioning principle and by performing an exhaustive search over the encoders. In this paper we study binary labelings for TCM and show how they can be grouped into classes, which considerably reduces the search space in a joint design. For 8-ary constellations, the number of different binary labelings that must be tested is reduced from 8!=40320 to 240. For the particular case of an 8-ary pulse amplitude modulation constellation, this number is further reduced to 120 and for 8-ary phase shift keying to only 30. An algorithm to generate one labeling in each class is also introduced. Asymptotically optimal TCM encoders are tabulated which are up to 0.3 dB better than the previously best known encoders.