OpenRaiser/Intern-Atlas huggingface dataset:
On the Monotonicity of the Generalized Marcum and Nuttall Q-Functions
Venue: arXiv cs.IT 2010
Year: 2010

Monotonicity criteria are established for the generalized Marcum Q-function, $\emph{Q}_{M}$, the standard Nuttall Q-function, $\emph{Q}_{M,N}$, and the normalized Nuttall Q-function, $\mathcal{Q}_{M,N}$, with respect to their real order indices M,N. Besides, closed-form expressions are derived for the computation of the standard and normalized Nuttall Q-functions for the case when M,N are odd multiples of 0.5 and $M\geq N$. By exploiting these results, novel upper and lower bounds for $\emph{Q}_{M,N}$ and $\mathcal{Q}_{M,N}$ are proposed. Furthermore, specific tight upper and lower bounds for $\emph{Q}_{M}$, previously reported in the literature, are extended for real values of M. The offered theoretical results can be efficiently applied in the study of digital communications over fading channels, in the information-theoretic analysis of multiple-input multiple-output systems and in the description of stochastic processes in probability theory, among others.
Safety alternating automata on data words
Venue: arXiv cs.LO 2010
Year: 2010

A data word is a sequence of pairs of a letter from a finite alphabet and an element from an infinite set, where the latter can only be compared for equality. Safety one-way alternating automata with one register on infinite data words are considered, their nonemptiness is shown EXPSPACE-complete, and their inclusion decidable but not primitive recursive. The same complexity bounds are obtained for satisfiability and refinement, respectively, for the safety fragment of linear temporal logic with freeze quantification. Dropping the safety restriction, adding past temporal operators, or adding one more register, each causes undecidability.
Stream sampling for variance-optimal estimation of subset sums
Venue: arXiv cs.DS 2010
Year: 2010

From a high volume stream of weighted items, we want to maintain a generic sample of a certain limited size $k$ that we can later use to estimate the total weight of arbitrary subsets. This is the classic context of on-line reservoir sampling, thinking of the generic sample as a reservoir. We present an efficient reservoir sampling scheme, $\varoptk$, that dominates all previous schemes in terms of estimation quality. $\varoptk$ provides {\em variance optimal unbiased estimation of subset sums}. More precisely, if we have seen $n$ items of the stream, then for {\em any} subset size $m$, our scheme based on $k$ samples minimizes the average variance over all subsets of size $m$. In fact, the optimality is against any off-line scheme with $k$ samples tailored for the concrete set of items seen. In addition to optimal average variance, our scheme provides tighter worst-case bounds on the variance of {\em particular} subsets than previously possible. It is efficient, handling each new item of the stream in $O(\log k)$ time. Finally, it is particularly well suited for combination of samples from different streams in a distributed setting.
Grammatical Evolution with Restarts for Fast Fractal Generation
Venue: arXiv cs.NE 2010
Year: 2010

In a previous work, the authors proposed a Grammatical Evolution algorithm to automatically generate Lindenmayer Systems which represent fractal curves with a pre-determined fractal dimension. This paper gives strong statistical evidence that the probability distributions of the execution time of that algorithm exhibits a heavy tail with an hyperbolic probability decay for long executions, which explains the erratic performance of different executions of the algorithm. Three different restart strategies have been incorporated in the algorithm to mitigate the problems associated to heavy tail distributions: the first assumes full knowledge of the execution time probability distribution, the second and third assume no knowledge. These strategies exploit the fact that the probability of finding a solution in short executions is non-negligible and yield a severe reduction, both in the expected execution time (up to one order of magnitude) and in its variance, which is reduced from an infinite to a finite value.
A Random Search Framework for Convergence Analysis of Distributed Beamforming with Feedback
Venue: arXiv cs.DC 2010
Year: 2010

The focus of this work is on the analysis of transmit beamforming schemes with a low-rate feedback link in wireless sensor/relay networks, where nodes in the network need to implement beamforming in a distributed manner. Specifically, the problem of distributed phase alignment is considered, where neither the transmitters nor the receiver has perfect channel state information, but there is a low-rate feedback link from the receiver to the transmitters. In this setting, a framework is proposed for systematically analyzing the performance of distributed beamforming schemes. To illustrate the advantage of this framework, a simple adaptive distributed beamforming scheme that was recently proposed by Mudambai et al. is studied. Two important properties for the received signal magnitude function are derived. Using these properties and the systematic framework, it is shown that the adaptive distributed beamforming scheme converges both in probability and in mean. Furthermore, it is established that the time required for the adaptive scheme to converge in mean scales linearly with respect to the number of sensor/relay nodes.
Concept-Oriented Programming
Venue: arXiv cs.PL 2010
Year: 2010

Object-oriented programming (OOP) is aimed at describing the structure and behaviour of objects by hiding the mechanism of their representation and access in primitive references. In this article we describe an approach, called concept-oriented programming (COP), which focuses on modelling references assuming that they also possess application-specific structure and behaviour accounting for a great deal or even most of the overall program complexity. References in COP are completely legalized and get the same status as objects while the functions are distributed among both objects and references. In order to support this design we introduce a new programming construct, called concept, which generalizes conventional classes and concept inclusion relation generalizing class inheritance. The main advantage of COP is that it allows programmers to describe two sides of any program: explicitly used functions of objects and intermediate functionality of references having cross-cutting nature and executed implicitly behind the scenes during object access.
Channel Coding and Decoding in a Relay System Operated with Physical layer Network Coding
Venue: arXiv cs.NI 2010
Year: 2010

Physical-layer Network Coding (PNC) can significantly improve the throughput of wireless two way relay channel (TWRC) by allowing the two end nodes to transmit messages to the relay simultaneously. To achieve reliable communication, channel coding could be applied on top of PNC. This paper investigates link-by-link channel-coded PNC, in which a critical process at the relay is to transform the superimposed channel-coded packets received from the two end nodes plus noise, Y3=X1+X2+W3, to the network-coded combination of the source packets, S1 XOR S2 . This is in distinct to the traditional multiple-access problem, in which the goal is to obtain S1 and S2 separately. The transformation from Y3 to (S1 XOR S2) is referred to as the Channel-decoding-Network-Coding process (CNC) in that it involves both channel decoding and network coding operations. A contribution of this paper is the insight that in designing CNC, we should first (i) channel-decode Y3 to the superimposed source symbols S1+S2 before (ii) transforming S1+S2 to the network-coded packets (S1 XOR S2) . Compared with previously proposed strategies for CNC, this strategy reduces the channel-coding network-coding mismatch. It is not obvious, however, that an efficient decoder for step (i) exists. A second contribution of this paper is to provide an explicit construction of such a decoder based on the use of the Repeat Accumulate (RA) code. Specifically, we redesign the belief propagation algorithm of the RA code for traditional point-to-point channel to suit the need of the PNC multiple-access channel. Simulation results show that our new scheme outperforms the previously proposed schemes significantly in terms of BER without added complexity.
Efficient tests for equivalence of hidden Markov processes and quantum random walks
Venue: arXiv cs.IT 2010
Year: 2010

While two hidden Markov process (HMP) resp. quantum random walk (QRW) parametrizations can differ from one another, the stochastic processes arising from them can be equivalent. Here a polynomial-time algorithm is presented which can determine equivalence of two HMP parametrizations $\cM_1,\cM_2$ resp. two QRW parametrizations $\cQ_1,\cQ_2$ in time $O(|§|\max(N_1,N_2)^{4})$, where $N_1,N_2$ are the number of hidden states in $\cM_1,\cM_2$ resp. the dimension of the state spaces associated with $\cQ_1,\cQ_2$, and $§$ is the set of output symbols. Previously available algorithms for testing equivalence of HMPs were exponential in the number of hidden states. In case of QRWs, algorithms for testing equivalence had not yet been presented. The core subroutines of this algorithm can also be used to efficiently test hidden Markov processes and quantum random walks for ergodicity.
Bounded Underapproximations
Venue: arXiv cs.LO 2010
Year: 2010

We show a new and constructive proof of the following language-theoretic result: for every context-free language L, there is a bounded context-free language L' included in L which has the same Parikh (commutative) image as L. Bounded languages, introduced by Ginsburg and Spanier, are subsets of regular languages of the form w1*w2*...wk* for some finite words w1,...,wk. In particular bounded subsets of context-free languages have nice structural and decidability properties. Our proof proceeds in two parts. First, using Newton's iterations on the language semiring, we construct a context-free subset Ls of L that can be represented as a sequence of substitutions on a linear language and has the same Parikh image as L. Second, we inductively construct a Parikh-equivalent bounded context-free subset of Ls. We show two applications of this result in model checking: to underapproximate the reachable state space of multithreaded procedural programs and to underapproximate the reachable state space of recursive counter programs. The bounded language constructed above provides a decidable underapproximation for the original problems. By iterating the construction, we get a semi-algorithm for the original problems that constructs a sequence of underapproximations such that no two underapproximations of the sequence can be compared. This provides a progress guarantee: every word w in L is in some underapproximation of the sequence. In addition, we show that our approach subsumes context-bounded reachability for multithreaded programs.
Modeling Social Annotation: a Bayesian Approach
Venue: arXiv cs.AI 2010
Year: 2010

Collaborative tagging systems, such as Delicious, CiteULike, and others, allow users to annotate resources, e.g., Web pages or scientific papers, with descriptive labels called tags. The social annotations contributed by thousands of users, can potentially be used to infer categorical knowledge, classify documents or recommend new relevant information. Traditional text inference methods do not make best use of social annotation, since they do not take into account variations in individual users' perspectives and vocabulary. In a previous work, we introduced a simple probabilistic model that takes interests of individual annotators into account in order to find hidden topics of annotated resources. Unfortunately, that approach had one major shortcoming: the number of topics and interests must be specified a priori. To address this drawback, we extend the model to a fully Bayesian framework, which offers a way to automatically estimate these numbers. In particular, the model allows the number of interests and topics to change as suggested by the structure of the data. We evaluate the proposed model in detail on the synthetic and real-world data by comparing its performance to Latent Dirichlet Allocation on the topic extraction task. For the latter evaluation, we apply the model to infer topics of Web resources from social annotations obtained from Delicious in order to discover new resources similar to a specified one. Our empirical results demonstrate that the proposed model is a promising method for exploiting social knowledge contained in user-generated annotations.
Packing and Covering Properties of Subspace Codes for Error Control in Random Linear Network Coding
Venue: arXiv cs.IT 2010
Year: 2010

Codes in the projective space and codes in the Grassmannian over a finite field - referred to as subspace codes and constant-dimension codes (CDCs), respectively - have been proposed for error control in random linear network coding. For subspace codes and CDCs, a subspace metric was introduced to correct both errors and erasures, and an injection metric was proposed to correct adversarial errors. In this paper, we investigate the packing and covering properties of subspace codes with both metrics. We first determine some fundamental geometric properties of the projective space with both metrics. Using these properties, we then derive bounds on the cardinalities of packing and covering subspace codes, and determine the asymptotic rates of optimal packing and optimal covering subspace codes with both metrics. Our results not only provide guiding principles for the code design for error control in random linear network coding, but also illustrate the difference between the two metrics from a geometric perspective. In particular, our results show that optimal packing CDCs are optimal packing subspace codes up to a scalar for both metrics if and only if their dimension is half of their length (up to rounding). In this case, CDCs suffer from only limited rate loss as opposed to subspace codes with the same minimum distance. We also show that optimal covering CDCs can be used to construct asymptotically optimal covering subspace codes with the injection metric only.
Omnidirectional Relay in Wireless Networks
Venue: arXiv cs.IT 2010
Year: 2010

For wireless networks with multiple sources, an omnidirectional relay scheme is developed, where each node can simultaneously relay different messages in different directions. This is accomplished by the decode-and-forward relay strategy, with each relay binning the multiple messages to be transmitted, in the same spirit of network coding. Specially for the all-source all-cast problem, where each node is an independent source to be transmitted to all the other nodes, this scheme completely eliminates interference in the whole network, and the signal transmitted by any node can be used by any other node. For networks with some kind of symmetry, assuming no beamforming is to be performed, this omnidirectional relay scheme is capable of achieving the maximum achievable rate.
Approximating the least hypervolume contributor: NP-hard in general, but fast in practice
Venue: arXiv cs.DS 2010
Year: 2010

The hypervolume indicator is an increasingly popular set measure to compare the quality of two Pareto sets. The basic ingredient of most hypervolume indicator based optimization algorithms is the calculation of the hypervolume contribution of single solutions regarding a Pareto set. We show that exact calculation of the hypervolume contribution is #P-hard while its approximation is NP-hard. The same holds for the calculation of the minimal contribution. We also prove that it is NP-hard to decide whether a solution has the least hypervolume contribution. Even deciding whether the contribution of a solution is at most $(1+\eps)$ times the minimal contribution is NP-hard. This implies that it is neither possible to efficiently find the least contributing solution (unless $P = NP$) nor to approximate it (unless $NP = BPP$). Nevertheless, in the second part of the paper we present a fast approximation algorithm for this problem. We prove that for arbitrarily given $\eps,δ>0$ it calculates a solution with contribution at most $(1+\eps)$ times the minimal contribution with probability at least $(1-δ)$. Though it cannot run in polynomial time for all instances, it performs extremely fast on various benchmark datasets. The algorithm solves very large problem instances which are intractable for exact algorithms (e.g., 10000 solutions in 100 dimensions) within a few seconds.
A Pseudopolynomial Algorithm for Alexandrov's Theorem
Venue: arXiv cs.CG 2010
Year: 2010

Alexandrov's Theorem states that every metric with the global topology and local geometry required of a convex polyhedron is in fact the intrinsic metric of a unique convex polyhedron. Recent work by Bobenko and Izmestiev describes a differential equation whose solution leads to the polyhedron corresponding to a given metric. We describe an algorithm based on this differential equation to compute the polyhedron to arbitrary precision given the metric, and prove a pseudopolynomial bound on its running time. Along the way, we develop pseudopolynomial algorithms for computing shortest paths and weighted Delaunay triangulations on a polyhedral surface, even when the surface edges are not shortest paths.
A Novel Clustering Algorithm Based Upon Games on Evolving Network
Venue: arXiv cs.LG 2010
Year: 2010

This paper introduces a model based upon games on an evolving network, and develops three clustering algorithms according to it. In the clustering algorithms, data points for clustering are regarded as players who can make decisions in games. On the network describing relationships among data points, an edge-removing-and-rewiring (ERR) function is employed to explore in a neighborhood of a data point, which removes edges connecting to neighbors with small payoffs, and creates new edges to neighbors with larger payoffs. As such, the connections among data points vary over time. During the evolution of network, some strategies are spread in the network. As a consequence, clusters are formed automatically, in which data points with the same evolutionarily stable strategy are collected as a cluster, so the number of evolutionarily stable strategies indicates the number of clusters. Moreover, the experimental results have demonstrated that data points in datasets are clustered reasonably and efficiently, and the comparison with other algorithms also provides an indication of the effectiveness of the proposed algorithms.
A parameter-free hedging algorithm
Venue: arXiv cs.LG 2010
Year: 2010

We study the problem of decision-theoretic online learning (DTOL). Motivated by practical applications, we focus on DTOL when the number of actions is very large. Previous algorithms for learning in this framework have a tunable learning rate parameter, and a barrier to using online-learning in practical applications is that it is not understood how to set this parameter optimally, particularly when the number of actions is large. In this paper, we offer a clean solution by proposing a novel and completely parameter-free algorithm for DTOL. We introduce a new notion of regret, which is more natural for applications with a large number of actions. We show that our algorithm achieves good performance with respect to this new notion of regret; in addition, it also achieves performance close to that of the best bounds achieved by previous algorithms with optimally-tuned parameters, according to previous notions of regret.
Tracking using explanation-based modeling
Venue: arXiv cs.LG 2010
Year: 2010

We study the tracking problem, namely, estimating the hidden state of an object over time, from unreliable and noisy measurements. The standard framework for the tracking problem is the generative framework, which is the basis of solutions such as the Bayesian algorithm and its approximation, the particle filters. However, the problem with these solutions is that they are very sensitive to model mismatches. In this paper, motivated by online learning, we introduce a new framework -- an {\em explanatory} framework -- for tracking. We provide an efficient tracking algorithm for this framework. We provide experimental results comparing our algorithm to the Bayesian algorithm on simulated data. Our experiments show that when there are slight model mismatches, our algorithm vastly outperforms the Bayesian algorithm.
Range Quantile Queries: Another Virtue of Wavelet Trees
Venue: arXiv cs.DS 2010
Year: 2010

We show how to use a balanced wavelet tree as a data structure that stores a list of numbers and supports efficient {\em range quantile queries}. A range quantile query takes a rank and the endpoints of a sublist and returns the number with that rank in that sublist. For example, if the rank is half the sublist's length, then the query returns the sublist's median. We also show how these queries can be used to support space-efficient {\em coloured range reporting} and {\em document listing}.
Modified-CS: Modifying Compressive Sensing for Problems with Partially Known Support
Venue: arXiv cs.IT 2010
Year: 2010

We study the problem of reconstructing a sparse signal from a limited number of its linear projections when a part of its support is known, although the known part may contain some errors. The ``known" part of the support, denoted T, may be available from prior knowledge. Alternatively, in a problem of recursively reconstructing time sequences of sparse spatial signals, one may use the support estimate from the previous time instant as the ``known" part. The idea of our proposed solution (modified-CS) is to solve a convex relaxation of the following problem: find the signal that satisfies the data constraint and is sparsest outside of T. We obtain sufficient conditions for exact reconstruction using modified-CS. These are much weaker than those needed for compressive sensing (CS) when the sizes of the unknown part of the support and of errors in the known part are small compared to the support size. An important extension called Regularized Modified-CS (RegModCS) is developed which also uses prior signal estimate knowledge. Simulation comparisons for both sparse and compressible signals are shown.
Coding Versus ARQ in Fading Channels: How reliable should the PHY be?
Venue: arXiv cs.IT 2010
Year: 2010

This paper studies the tradeoff between channel coding and ARQ (automatic repeat request) in Rayleigh block-fading channels. A heavily coded system corresponds to a low transmission rate with few ARQ re-transmissions, whereas lighter coding corresponds to a higher transmitted rate but more re-transmissions. The optimum error probability, where optimum refers to the maximization of the average successful throughput, is derived and is shown to be a decreasing function of the average signal-to-noise ratio and of the channel diversity order. A general conclusion of the work is that the optimum error probability is quite large (e.g., 10% or larger) for reasonable channel parameters, and that operating at a very small error probability can lead to a significantly reduced throughput. This conclusion holds even when a number of practical ARQ considerations, such as delay constraints and acknowledgement feedback errors, are taken into account.