OpenRaiser/Intern-Atlas huggingface dataset:
Multiuser Broadcast Erasure Channel with Feedback and Side Information, and Related Index Coding Results
Venue: arXiv cs.IT 2014
Year: 2014

We consider the N-user broadcast erasure channel with public feedback and side information. Before the beginning of transmission, each receiver knows a function of the messages of some of the other receivers. This situation arises naturally in wireless and in particular cognitive networks where a node may overhear transmitted messages destined to other nodes before transmission over a given broadcast channel begins. We provide an upper bound to the capacity region of this system. Furthermore, when the side information is linear, we show that the bound is tight for the case of two-user broadcast channels. The special case where each user knows the whole or nothing of the message of each other node, constitutes a generalization of the index coding problem. For this instance, and when there are no channel errors, we show that the bound reduces to the known Maximum Weighted Acyclic Induced Subgraph bound. We also show how to convert the capacity upper bound to transmission completion rate (broadcast rate) lower bound and provide examples of codes for certain information graphs for which the bound is either achieved of closely approximated
Algorithmic Identification of Probabilities
Venue: arXiv cs.LG 2014
Year: 2014

TThe problem is to identify a probability associated with a set of natural numbers, given an infinite data sequence of elements from the set. If the given sequence is drawn i.i.d. and the probability mass function involved (the target) belongs to a computably enumerable (c.e.) or co-computably enumerable (co-c.e.) set of computable probability mass functions, then there is an algorithm to almost surely identify the target in the limit. The technical tool is the strong law of large numbers. If the set is finite and the elements of the sequence are dependent while the sequence is typical in the sense of Martin-Löf for at least one measure belonging to a c.e. or co-c.e. set of computable measures, then there is an algorithm to identify in the limit a computable measure for which the sequence is typical (there may be more than one such measure). The technical tool is the theory of Kolmogorov complexity. We give the algorithms and consider the associated predictions.
Optimal Stochastic Coordinated Beamforming for Wireless Cooperative Networks with CSI Uncertainty
Venue: arXiv cs.IT 2014
Year: 2014

Transmit optimization and resource allocation for wireless cooperative networks with channel state information (CSI) uncertainty are important but challenging problems in terms of both the uncertainty modeling and performance op- timization. In this paper, we establish a generic stochastic coordinated beamforming (SCB) framework that provides flex- ibility in the channel uncertainty modeling, while guaranteeing optimality in the transmission strategies. We adopt a general stochastic model for the CSI uncertainty, which is applicable for various practical scenarios. The SCB problem turns out to be a joint chance constrained program (JCCP) and is known to be highly intractable. In contrast to all the previous algo- rithms for JCCP that can only find feasible but sub-optimal solutions, we propose a novel stochastic DC (difference-of-convex) programming algorithm with optimality guarantee, which can serve as the benchmark for evaluating heuristic and sub-optimal algorithms. The key observation is that the highly intractable probability constraint can be equivalently reformulated as a DC constraint. This further enables efficient algorithms to achieve optimality. Simulation results will illustrate the convergence, conservativeness, stability and performance gains of the proposed algorithm.
Verifying whether One-Tape Non-Deterministic Turing Machines Run in Time $Cn+D$
Venue: arXiv cs.CC 2014
Year: 2014

We discuss the following family of problems, parameterized by integers $C\geq 2$ and $D\geq 1$: Does a given one-tape non-deterministic $q$-state Turing machine make at most $Cn+D$ steps on all computations on all inputs of length $n$, for all $n$? Assuming a fixed tape and input alphabet, we show that these problems are co-NP-complete and we provide good non-deterministic and co-non-deterministic lower bounds. Specifically, these problems can not be solved in $o(q^{(C-1)/4})$ non-deterministic time by multi-tape Turing machines. We also show that the complements of these problems can be solved in $O(q^{C+2})$ non-deterministic time and not in $o(q^{(C-1)/2})$ non-deterministic time by multi-tape Turing machines.
A compact formula for the derivative of a 3-D rotation in exponential coordinates
Venue: arXiv cs.CV 2014
Year: 2014

We present a compact formula for the derivative of a 3-D rotation matrix with respect to its exponential coordinates. A geometric interpretation of the resulting expression is provided, as well as its agreement with other less-compact but better-known formulas. To the best of our knowledge, this simpler formula does not appear anywhere in the literature. We hope by providing this more compact expression to alleviate the common pressure to reluctantly resort to alternative representations in various computational applications simply as a means to avoid the complexity of differential analysis in exponential coordinates.
Understanding Alternating Minimization for Matrix Completion
Venue: arXiv cs.LG 2014
Year: 2014

Alternating Minimization is a widely used and empirically successful heuristic for matrix completion and related low-rank optimization problems. Theoretical guarantees for Alternating Minimization have been hard to come by and are still poorly understood. This is in part because the heuristic is iterative and non-convex in nature. We give a new algorithm based on Alternating Minimization that provably recovers an unknown low-rank matrix from a random subsample of its entries under a standard incoherence assumption. Our results reduce the sample size requirements of the Alternating Minimization approach by at least a quartic factor in the rank and the condition number of the unknown matrix. These improvements apply even if the matrix is only close to low-rank in the Frobenius norm. Our algorithm runs in nearly linear time in the dimension of the matrix and, in a broad range of parameters, gives the strongest sample bounds among all subquadratic time algorithms that we are aware of. Underlying our work is a new robust convergence analysis of the well-known Power Method for computing the dominant singular vectors of a matrix. This viewpoint leads to a conceptually simple understanding of Alternating Minimization. In addition, we contribute a new technique for controlling the coherence of intermediate solutions arising in iterative algorithms based on a smoothed analysis of the QR factorization. These techniques may be of interest beyond their application here.
Rank-Modulation Rewrite Coding for Flash Memories
Venue: arXiv cs.IT 2014
Year: 2014

The current flash memory technology focuses on the cost minimization of its static storage capacity. However, the resulting approach supports a relatively small number of program-erase cycles. This technology is effective for consumer devices (e.g., smartphones and cameras) where the number of program-erase cycles is small. However, it is not economical for enterprise storage systems that require a large number of lifetime writes. The proposed approach in this paper for alleviating this problem consists of the efficient integration of two key ideas: (i) improving reliability and endurance by representing the information using relative values via the rank modulation scheme and (ii) increasing the overall (lifetime) capacity of the flash device via rewriting codes, namely, performing multiple writes per cell before erasure. This paper presents a new coding scheme that combines rank modulation with rewriting. The key benefits of the new scheme include: (i) the ability to store close to 2 bits per cell on each write with minimal impact on the lifetime of the memory, and (ii) efficient encoding and decoding algorithms that make use of capacity-achieving write-once-memory (WOM) codes that were proposed recently.
An algebraic study of linkages with helical joints
Venue: arXiv cs.RO 2014
Year: 2014

Methods from algebra and algebraic geometry have been used in various ways to study linkages in kinematics. These methods have failed so far for the study of linkages with helical joints (joints with screw motion), because of the presence of some non-algebraic relations. In this article, we explore a delicate reduction of some analytic equations in kinematics to algebraic questions via a theorem of Ax. As an application, we give a classification of mobile closed 5-linkages with revolute, prismatic, and helical joints.
Programming Protocol-Independent Packet Processors
Venue: arXiv cs.NI 2014
Year: 2014

P4 is a high-level language for programming protocol-independent packet processors. P4 works in conjunction with SDN control protocols like OpenFlow. In its current form, OpenFlow explicitly specifies protocol headers on which it operates. This set has grown from 12 to 41 fields in a few years, increasing the complexity of the specification while still not providing the flexibility to add new headers. In this paper we propose P4 as a strawman proposal for how OpenFlow should evolve in the future. We have three goals: (1) Reconfigurability in the field: Programmers should be able to change the way switches process packets once they are deployed. (2) Protocol independence: Switches should not be tied to any specific network protocols. (3) Target independence: Programmers should be able to describe packet-processing functionality independently of the specifics of the underlying hardware. As an example, we describe how to use P4 to configure a switch to add a new hierarchical label.
Space-Time Polar Coded Modulation
Venue: arXiv cs.IT 2014
Year: 2014

The polar codes are proven to be capacity-achieving and are shown to have equivalent or even better finite-length performance than the turbo/LDPC codes under some improved decoding algorithms over the additive white Gaussian noise (AWGN) channels. Polar coding is based on the so-called channel polarization phenomenon induced by a transform over the underlying binary-input channel. The channel polarization is found to be universal in many signal processing problems and has been applied to the coded modulation schemes. In this paper, the channel polarization is further extended to the multiple antenna transmission following a multilevel coding principle. The multiple-input multile-output (MIMO) channel under quadrature amplitude modulation (QAM) are transformed into a series of synthesized binary-input channels under a three-stage channel transform. Based on this generalized channel polarization, the proposed space-time polar coded modulation (STPCM) scheme allows a joint optimization of the binary polar coding, modulation and MIMO transmission. In addition, a practical solution of polar code construction over the fading channels is also provided, where the fading channels are approximated by an AWGN channel which shares the same capacity with the original. The simulations over the MIMO channel with uncorrelated Rayleigh fast fading show that the proposed STPCM scheme can outperform the bit-interleaved turbo coded scheme in all the simulated cases, where the latter is adopted in many existing communication systems.
Automatic recognition and tagging of topologically different regimes in dynamical systems
Venue: arXiv cs.CG 2014
Year: 2014

Complex systems are commonly modeled using nonlinear dynamical systems. These models are often high-dimensional and chaotic. An important goal in studying physical systems through the lens of mathematical models is to determine when the system undergoes changes in qualitative behavior. A detailed description of the dynamics can be difficult or impossible to obtain for high-dimensional and chaotic systems. Therefore, a more sensible goal is to recognize and mark transitions of a system between qualitatively different regimes of behavior. In practice, one is interested in developing techniques for detection of such transitions from sparse observations, possibly contaminated by noise. In this paper we develop a framework to accurately tag different regimes of complex systems based on topological features. In particular, our framework works with a high degree of success in picking out a cyclically orbiting regime from a stationary equilibrium regime in high-dimensional stochastic dynamical systems.
Efficient Large-Scale Graph Processing on Hybrid CPU and GPU Systems
Venue: arXiv cs.DC 2014
Year: 2014

The increasing scale and wealth of inter-connected data, such as those accrued by social network applications, demand the design of new techniques and platforms to efficiently derive actionable knowledge from large-scale graphs. However, real-world graphs are famously difficult to process efficiently. Not only they have a large memory footprint, but also most graph algorithms entail memory access patterns with poor locality, data-dependent parallelism and a low compute-to-memory access ratio. Moreover, most real-world graphs have a highly heterogeneous node degree distribution, hence partitioning these graphs for parallel processing and simultaneously achieving access locality and load-balancing is difficult. This work starts from the hypothesis that hybrid platforms (e.g., GPU-accelerated systems) have both the potential to cope with the heterogeneous structure of real graphs and to offer a cost-effective platform for high-performance graph processing. This work assesses this hypothesis and presents an extensive exploration of the opportunity to harness hybrid systems to process large-scale graphs efficiently. In particular, (i) we present a performance model that estimates the achievable performance on hybrid platforms; (ii) informed by the performance model, we design and develop TOTEM - a processing engine that provides a convenient environment to implement graph algorithms on hybrid platforms; (iii) we show that further performance gains can be extracted using partitioning strategies that aim to produce partitions that each matches the strengths of the processing element it is allocated to, finally, (iv) we demonstrate the performance advantages of the hybrid system through a comprehensive evaluation that uses real and synthetic workloads (as large as 16 billion edges), multiple graph algorithms that stress the system in various ways, and a variety of hardware configurations.
On the Complexity of Making a Distinguished Vertex Minimum or Maximum Degree by Vertex Deletion
Venue: arXiv cs.DS 2014
Year: 2014

In this paper, we investigate the approximability of two node deletion problems. Given a vertex weighted graph $G=(V,E)$ and a specified, or "distinguished" vertex $p \in V$, MDD(min) is the problem of finding a minimum weight vertex set $S \subseteq V\setminus \{p\}$ such that $p$ becomes the minimum degree vertex in $G[V \setminus S]$; and MDD(max) is the problem of finding a minimum weight vertex set $S \subseteq V\setminus \{p\}$ such that $p$ becomes the maximum degree vertex in $G[V \setminus S]$. These are known $NP$-complete problems and have been studied from the parameterized complexity point of view in previous work. Here, we prove that for any $ε> 0$, both the problems cannot be approximated within a factor $(1 - ε)\log n$, unless $NP \subseteq DTIME(n^{\log\log n})$. We also show that for any $ε> 0$, MDD(min) cannot be approximated within a factor $(1 -ε)\log n$ on bipartite graphs, unless $NP \subseteq DTIME(n^{\log\log n})$, and that for any $ε> 0$, MDD(max) cannot be approximated within a factor $(1/2 - ε)\log n$ on bipartite graphs, unless $NP \subseteq DTIME(n^{\log\log n})$. We give an $O(\log n)$ factor approximation algorithm for MDD(max) on general graphs, provided the degree of $p$ is $O(\log n)$. We then show that if the degree of $p$ is $n-O(\log n)$, a similar result holds for MDD(min). We prove that MDD(max) is $APX$-complete on 3-regular unweighted graphs and provide an approximation algorithm with ratio $1.583$ when $G$ is a 3-regular unweighted graph. In addition, we show that MDD(min) can be solved in polynomial time when $G$ is a regular graph of constant degree.
Low-rank Similarity Measure for Role Model Extraction
Venue: arXiv cs.SI 2014
Year: 2014

Computing meaningful clusters of nodes is crucial to analyze large networks. In this paper, we present a pairwise node similarity measure that allows to extract roles, i.e. group of nodes sharing similar flow patterns within a network. We propose a low rank iterative scheme to approximate the similarity measure for very large networks. Finally, we show that our low rank similarity score successfully extracts the different roles in random graphs and that its performances are similar to the pairwise similarity measure.
Classification of Human Ventricular Arrhythmia in High Dimensional Representation Spaces
Venue: arXiv cs.CE 2014
Year: 2014

We studied classification of human ECGs labelled as normal sinus rhythm, ventricular fibrillation and ventricular tachycardia by means of support vector machines in different representation spaces, using different observation lengths. ECG waveform segments of duration 0.5-4 s, their Fourier magnitude spectra, and lower dimensional projections of Fourier magnitude spectra were used for classification. All considered representations were of much higher dimension than in published studies. Classification accuracy improved with segment duration up to 2 s, with 4 s providing little improvement. We found that it is possible to discriminate between ventricular tachycardia and ventricular fibrillation by the present approach with much shorter runs of ECG (2 s, minimum 86% sensitivity per class) than previously imagined. Ensembles of classifiers acting on 1 s segments taken over 5 s observation windows gave best results, with sensitivities of detection for all classes exceeding 93%.
Skolemization for Weighted First-Order Model Counting
Venue: arXiv cs.AI 2014
Year: 2014

First-order model counting emerged recently as a novel reasoning task, at the core of efficient algorithms for probabilistic logics. We present a Skolemization algorithm for model counting problems that eliminates existential quantifiers from a first-order logic theory without changing its weighted model count. For certain subsets of first-order logic, lifted model counters were shown to run in time polynomial in the number of objects in the domain of discourse, where propositional model counters require exponential time. However, these guarantees apply only to Skolem normal form theories (i.e., no existential quantifiers) as the presence of existential quantifiers reduces lifted model counters to propositional ones. Since textbook Skolemization is not sound for model counting, these restrictions precluded efficient model counting for directed models, such as probabilistic logic programs, which rely on existential quantification. Our Skolemization procedure extends the applicability of first-order model counters to these representations. Moreover, it simplifies the design of lifted model counting algorithms.
Blind Denoising with Random Greedy Pursuits
Venue: arXiv cs.IT 2014
Year: 2014

Denoising methods require some assumptions about the signal of interest and the noise. While most denoising procedures require some knowledge about the noise level, which may be unknown in practice, here we assume that the signal expansion in a given dictionary has a distribution that is more heavy-tailed than the noise. We show how this hypothesis leads to a stopping criterion for greedy pursuit algorithms which is independent from the noise level. Inspired by the success of ensemble methods in machine learning, we propose a strategy to reduce the variance of greedy estimates by averaging pursuits obtained from randomly subsampled dictionaries. We call this denoising procedure Blind Random Pursuit Denoising (BIRD). We offer a generalization to multidimensional signals, with a structured sparse model (S-BIRD). The relevance of this approach is demonstrated on synthetic and experimental MEG signals where, without any parameter tuning, BIRD outperforms state-of-the-art algorithms even when they are informed by the noise level. Code is available to reproduce all experiments.
On the Joint Impact of Beamwidth and Orientation Error on Throughput in Directional Wireless Poisson Networks
Venue: arXiv cs.IT 2014
Year: 2014

We introduce a model for capturing the effects of beam misdirection on coverage and throughput in a directional wireless network using stochastic geometry. In networks employing ideal sector antennas without sidelobes, we find that concavity of the orientation error distribution is sufficient to prove monotonicity and quasi-concavity (both with respect to antenna beamwidth) of spatial throughput and transmission capacity, respectively. Additionally, we identify network conditions that produce opposite extremal choices in beamwidth (absolutely directed versus omni-directional) that maximize the two related throughput metrics. We conclude our paper with a numerical exploration of the relationship between mean orientation error, throughput-maximizing beamwidths, and maximum throughput, across radiation patterns of varied complexity.
On the number of response regions of deep feed forward networks with piece-wise linear activations
Venue: arXiv cs.LG 2014
Year: 2014

This paper explores the complexity of deep feedforward networks with linear pre-synaptic couplings and rectified linear activations. This is a contribution to the growing body of work contrasting the representational power of deep and shallow network architectures. In particular, we offer a framework for comparing deep and shallow models that belong to the family of piecewise linear functions based on computational geometry. We look at a deep rectifier multi-layer perceptron (MLP) with linear outputs units and compare it with a single layer version of the model. In the asymptotic regime, when the number of inputs stays constant, if the shallow model has $kn$ hidden units and $n_0$ inputs, then the number of linear regions is $O(k^{n_0}n^{n_0})$. For a $k$ layer model with $n$ hidden units on each layer it is $Ω(\left\lfloor {n}/{n_0}\right\rfloor^{k-1}n^{n_0})$. The number $\left\lfloor{n}/{n_0}\right\rfloor^{k-1}$ grows faster than $k^{n_0}$ when $n$ tends to infinity or when $k$ tends to infinity and $n \geq 2n_0$. Additionally, even when $k$ is small, if we restrict $n$ to be $2n_0$, we can show that a deep model has considerably more linear regions that a shallow one. We consider this as a first step towards understanding the complexity of these models and specifically towards providing suitable mathematical tools for future analysis.