OpenRaiser/Intern-Atlas huggingface dataset:
Nearness to Local Subspace Algorithm for Subspace and Motion Segmentation
Venue: arXiv cs.IT 2012
Year: 2012

There is a growing interest in computer science, engineering, and mathematics for modeling signals in terms of union of subspaces and manifolds. Subspace segmentation and clustering of high dimensional data drawn from a union of subspaces are especially important with many practical applications in computer vision, image and signal processing, communications, and information theory. This paper presents a clustering algorithm for high dimensional data that comes from a union of lower dimensional subspaces of equal and known dimensions. Such cases occur in many data clustering problems, such as motion segmentation and face recognition. The algorithm is reliable in the presence of noise, and applied to the Hopkins 155 Dataset, it generates the best results to date for motion segmentation. The two motion, three motion, and overall segmentation rates for the video sequences are 99.43%, 98.69%, and 99.24%, respectively.
MIMO APP Receiver Processing with Performance-Determined Complexity
Venue: arXiv cs.IT 2012
Year: 2012

Typical receiver processing, targeting always the best achievable bit error rate performance, can result in a waste of resources, especially, when the transmission conditions are such that the best performance is orders of magnitude better than the required. In this work, a processing framework is proposed which allows adjusting the processing requirements to the transmission conditions and the required bit error rate. It applies a-posteriori probability receivers operating over multiple-input multiple-output channels. It is demonstrated that significant complexity savings can be achieved both at the soft, sphere-decoder based detector and the channel decoder with only minor modifications.
Analysis and Design of Tuned Turbo Codes
Venue: arXiv cs.IT 2012
Year: 2012

It has been widely observed that there exists a fundamental trade-off between the minimum (Hamming) distance properties and the iterative decoding convergence behavior of turbo-like codes. While capacity achieving code ensembles typically are asymptotically bad in the sense that their minimum distance does not grow linearly with block length, and they therefore exhibit an error floor at moderate-to-high signal to noise ratios, asymptotically good codes usually converge further away from channel capacity. In this paper, we introduce the concept of tuned turbo codes, a family of asymptotically good hybrid concatenated code ensembles, where asymptotic minimum distance growth rates, convergence thresholds, and code rates can be traded-off using two tuning parameters, λ and μ. By decreasing λ, the asymptotic minimum distance growth rate is reduced in exchange for improved iterative decoding convergence behavior, while increasing λ raises the asymptotic minimum distance growth rate at the expense of worse convergence behavior, and thus the code performance can be tuned to fit the desired application. By decreasing μ, a similar tuning behavior can be achieved for higher rate code ensembles.
A non-expert view on Turing machines, Proof Verifiers, and Mental reasoning
Venue: arXiv cs.CC 2012
Year: 2012

The paper explores known results related to the problem of identifying if a given program terminates on all inputs -- this is a simple generalization of the halting problem. We will see how this problem is related and the notion of proof verifiers. We also see how verifying if a program is terminating involves reasoning through a tower of axiomatic theories -- such a tower of theories is known as Turing progressions and was first studied by Alan Turing in the 1930's. We will see that this process has a natural connection to ordinal numbers. The paper is presented from the perspective of a non-expert in the field of logic and proof theory.
To Feed or Not to Feed Back
Venue: arXiv cs.IT 2012
Year: 2012

We study the communication over Finite State Channels (FSCs), where the encoder and the decoder can control the availability or the quality of the noise-free feedback. Specifically, the instantaneous feedback is a function of an action taken by the encoder, an action taken by the decoder, and the channel output. Encoder and decoder actions take values in finite alphabets, and may be subject to average cost constraints. We prove capacity results for such a setting by constructing a sequence of achievable rates, using a simple scheme based on 'code tree' generation, that generates channel input symbols along with encoder and decoder actions. We prove that the limit of this sequence exists. For a given block length and probability of error, we give an upper bound on the maximum achievable rate. Our upper and lower bounds coincide and hence yield the capacity for the case where the probability of initial state is positive for all states. Further, for stationary indecomposable channels without intersymbol interference (ISI), the capacity is given as the limit of normalized directed information between the input and output sequence, maximized over an appropriate set of causally conditioned distributions. As an important special case, we consider the framework of 'to feed or not to feed back' where either the encoder or the decoder takes binary actions, which determine whether current channel output will be fed back to the encoder, with a constraint on the fraction of channel outputs that are fed back. As another special case of our framework, we characterize the capacity of 'coding on the backward link' in FSCs, i.e. when the decoder sends limited-rate instantaneous coded noise-free feedback on the backward link. Finally, we propose an extension of the Blahut-Arimoto algorithm for evaluating the capacity when actions can be cost constrained, and demonstrate its application on a few examples.
Volume-Enclosing Surface Extraction
Venue: arXiv cs.CG 2012
Year: 2012

In this paper we present a new method, which allows for the construction of triangular isosurfaces from three-dimensional data sets, such as 3D image data and/or numerical simulation data that are based on regularly shaped, cubic lattices. This novel volume-enclosing surface extraction technique, which has been named VESTA, can produce up to six different results due to the nature of the discretized 3D space under consideration. VESTA is neither template-based nor it is necessarily required to operate on 2x2x2 voxel cell neighborhoods only. The surface tiles are determined with a very fast and robust construction technique while potential ambiguities are detected and resolved. Here, we provide an in-depth comparison between VESTA and various versions of the well-known and very popular Marching Cubes algorithm for the very first time. In an application section, we demonstrate the extraction of VESTA isosurfaces for various data sets ranging from computer tomographic scan data to simulation data of relativistic hydrodynamic fireball expansions.
Design and Analysis of LT Codes with Decreasing Ripple Size
Venue: arXiv cs.IT 2012
Year: 2012

In this paper we propose a new design of LT codes, which decreases the amount of necessary overhead in comparison to existing designs. The design focuses on a parameter of the LT decoding process called the ripple size. This parameter was also a key element in the design proposed in the original work by Luby. Specifically, Luby argued that an LT code should provide a constant ripple size during decoding. In this work we show that the ripple size should decrease during decoding, in order to reduce the necessary overhead. Initially we motivate this claim by analytical results related to the redundancy within an LT code. We then propose a new design procedure, which can provide any desired achievable decreasing ripple size. The new design procedure is evaluated and compared to the current state of the art through simulations. This reveals a significant increase in performance with respect to both average overhead and error probability at any fixed overhead.
Multiscale Gossip for Efficient Decentralized Averaging in Wireless Packet Networks
Venue: arXiv cs.DC 2012
Year: 2012

This paper describes and analyzes a hierarchical gossip algorithm for solving the distributed average consensus problem in wireless sensor networks. The network is recursively partitioned into subnetworks. Initially, nodes at the finest scale gossip to compute local averages. Then, using geographic routing to enable gossip between nodes that are not directly connected, these local averages are progressively fused up the hierarchy until the global average is computed. We show that the proposed hierarchical scheme with $k$ levels of hierarchy is competitive with state-of-the-art randomized gossip algorithms, in terms of message complexity, achieving $ε$-accuracy with high probability after $O\big(n \log \log n \log \frac{kn}ε \big)$ messages. Key to our analysis is the way in which the network is recursively partitioned. We find that the optimal scaling law is achieved when subnetworks at scale $j$ contain $O(n^{(2/3)^j})$ nodes; then the message complexity at any individual scale is $O(n \log \frac{kn}ε)$, and the total number of scales in the hierarchy grows slowly, as $Θ(\log \log n)$. Another important consequence of hierarchical construction is that the longest distance over which messages are exchanged is $O(n^{1/3})$ hops (at the highest scale), and most messages (at lower scales) travel shorter distances. In networks that use link-level acknowledgements, this results in less congestion and resource usage by reducing message retransmissions. Simulations illustrate that the proposed scheme is more message-efficient than existing state-of-the-art randomized gossip algorithms based on averaging along paths.
Reducing Higher Order Pi-Calculus to Spatial Logics
Venue: arXiv cs.LO 2012
Year: 2012

In this paper, we show that theory of processes can be reduced to the theory of spatial logic. Firstly, we propose a spatial logic SL for higher order pi-calculus, and give an inference system of SL. The soundness and incompleteness of SL are proved. Furthermore, we show that the structure congruence relation and one-step transition relation can be described as the logical relation of SL formulae. We also extend bisimulations for processes to that for SL formulae. Then we extend all definitions and results of SL to a weak semantics version of SL, called WL. At last, we add mu-operator to SL. This new logic is named muSL. We show that WL is a sublogic of muSL and replication operator can be expressed in muSL.
On the approximation ability of evolutionary optimization with application to minimum set cover
Venue: arXiv cs.NE 2012
Year: 2012

Evolutionary algorithms (EAs) are heuristic algorithms inspired by natural evolution. They are often used to obtain satisficing solutions in practice. In this paper, we investigate a largely underexplored issue: the approximation performance of EAs in terms of how close the solution obtained is to an optimal solution. We study an EA framework named simple EA with isolated population (SEIP) that can be implemented as a single- or multi-objective EA. We analyze the approximation performance of SEIP using the partial ratio, which characterizes the approximation ratio that can be guaranteed. Specifically, we analyze SEIP using a set cover problem that is NP-hard. We find that in a simple configuration, SEIP efficiently achieves an $H_n$-approximation ratio, the asymptotic lower bound, for the unbounded set cover problem. We also find that SEIP efficiently achieves an $(H_k-\frac{k-1}/{8k^9})$-approximation ratio, the currently best-achievable result, for the k-set cover problem. Moreover, for an instance class of the k-set cover problem, we disclose how SEIP, using either one-bit or bit-wise mutation, can overcome the difficulty that limits the greedy algorithm.
Jamming Games in the MIMO Wiretap Channel With an Active Eavesdropper
Venue: arXiv cs.IT 2012
Year: 2012

This paper investigates reliable and covert transmission strategies in a multiple-input multiple-output (MIMO) wiretap channel with a transmitter, receiver and an adversarial wiretapper, each equipped with multiple antennas. In a departure from existing work, the wiretapper possesses a novel capability to act either as a passive eavesdropper or as an active jammer, under a half-duplex constraint. The transmitter therefore faces a choice between allocating all of its power for data, or broadcasting artificial interference along with the information signal in an attempt to jam the eavesdropper (assuming its instantaneous channel state is unknown). To examine the resulting trade-offs for the legitimate transmitter and the adversary, we model their interactions as a two-person zero-sum game with the ergodic MIMO secrecy rate as the payoff function. We first examine conditions for the existence of pure-strategy Nash equilibria (NE) and the structure of mixed-strategy NE for the strategic form of the game.We then derive equilibrium strategies for the extensive form of the game where players move sequentially under scenarios of perfect and imperfect information. Finally, numerical simulations are presented to examine the equilibrium outcomes of the various scenarios considered.
The Light of Existence
Venue: arXiv cs.OH 2012
Year: 2012

This chapter derives the properties of light from the properties of processing, including its ability to be both a wave and a particle, to respond to objects it doesn't physically touch, to take all paths to a destination, to choose a route after it arrives, and to spin both ways at once as it moves. Here a photon is an entity program spreading as a processing wave of instances. It becomes a "particle" if any part of it overloads the grid network that runs it, causing the photon program to reboot and restart at a new node. The "collapse of the wave function" is how quantum processing creates what we call a physical photon. This informational approach gives insights into issues like the law of least action, entanglement, superposition, counterfactuals, the holographic principle and the measurement problem. The conceptual cost is that physical reality is a quantum processing output, i.e. virtual.
A Center Transversal Theorem for Hyperplanes and Applications to Graph Drawing
Venue: arXiv cs.CG 2012
Year: 2012

Motivated by an open problem from graph drawing, we study several partitioning problems for line and hyperplane arrangements. We prove a ham-sandwich cut theorem: given two sets of n lines in R^2, there is a line l such that in both line sets, for both halfplanes delimited by l, there are n^{1/2} lines which pairwise intersect in that halfplane, and this bound is tight; a centerpoint theorem: for any set of n lines there is a point such that for any halfplane containing that point there are (n/3)^{1/2} of the lines which pairwise intersect in that halfplane. We generalize those results in higher dimension and obtain a center transversal theorem, a same-type lemma, and a positive portion Erdos-Szekeres theorem for hyperplane arrangements. This is done by formulating a generalization of the center transversal theorem which applies to set functions that are much more general than measures. Back to Graph Drawing (and in the plane), we completely solve the open problem that motivated our search: there is no set of n labelled lines that are universal for all n-vertex labelled planar graphs. As a side note, we prove that every set of n (unlabelled) lines is universal for all n-vertex (unlabelled) planar graphs.
Inverse-Category-Frequency based supervised term weighting scheme for text categorization
Venue: arXiv cs.LG 2012
Year: 2012

Term weighting schemes often dominate the performance of many classifiers, such as kNN, centroid-based classifier and SVMs. The widely used term weighting scheme in text categorization, i.e., tf.idf, is originated from information retrieval (IR) field. The intuition behind idf for text categorization seems less reasonable than IR. In this paper, we introduce inverse category frequency (icf) into term weighting scheme and propose two novel approaches, i.e., tf.icf and icf-based supervised term weighting schemes. The tf.icf adopts icf to substitute idf factor and favors terms occurring in fewer categories, rather than fewer documents. And the icf-based approach combines icf and relevance frequency (rf) to weight terms in a supervised way. Our cross-classifier and cross-corpus experiments have shown that our proposed approaches are superior or comparable to six supervised term weighting schemes and three traditional schemes in terms of macro-F1 and micro-F1.
Extending Büchi Automata with Constraints on Data Values
Venue: arXiv cs.LO 2012
Year: 2012

Recently data trees and data words have received considerable amount of attention in connection with XML reasoning and system verification. These are trees or words that, in addition to labels from a finite alphabet, carry data values from an infinite alphabet (data). In general it is rather hard to obtain logics for data words and trees that are sufficiently expressive, but still have reasonable complexity for the satisfiability problem. In this paper we extend and study the notion of Büchi automata for omega-words with data. We prove that the emptiness problem for such extension is decidable in elementary complexity. We then apply our result to show the decidability of two kinds of logics for omega-words with data: the two-variable fragment of first-order logic and some extensions of classical linear temporal logic for omega-words with data.
On the Capacity of the Discrete Memoryless Broadcast Channel with Feedback
Venue: arXiv cs.IT 2012
Year: 2012

A coding scheme for the discrete memoryless broadcast channel with {noiseless, noisy, generalized} feedback is proposed, and the associated achievable region derived. The scheme is based on a block-Markov strategy combining the Marton scheme and a lossy version of the Gray-Wyner scheme with side-information. In each block the transmitter sends fresh data and update information that allows the receivers to improve the channel outputs observed in the previous block. For a generalization of Dueck's broadcast channel our scheme achieves the noiseless-feedback capacity, which is strictly larger than the no-feedback capacity. For a generalization of Blackwell's channel and when the feedback is noiseless our new scheme achieves rate points that are outside the no-feedback capacity region. It follows by a simple continuity argument that for both these channels and when the feedback noise is sufficiently low, our scheme improves on the no-feedback capacity even when the feedback is noisy.
A comprehensive operational semantics of the SCOOP programming model
Venue: arXiv cs.DC 2012
Year: 2012

Operational semantics has established itself as a flexible but rigorous means to describe the meaning of programming languages. Oftentimes, it is felt necessary to keep a semantics small, for example to facilitate its use for model checking by avoiding state space explosion. However, omitting many details in a semantics typically makes results valid for a limited core language only, leaving a wide gap towards any real implementation. In this paper we present a full-fledged semantics of the concurrent object-oriented programming language SCOOP (Simple Concurrent Object-Oriented Programming). The semantics has been found detailed enough to guide an implementation of the SCOOP compiler and runtime system, and to detect and correct a variety of errors and ambiguities in the original informal specification and prototype implementation. In our formal specification, we use abstract data types with preconditions and axioms to describe the state, and introduce a number of special run-time operations to model the runtime system with our inference rules. This approach allows us to make our large formal specification manageable, providing a first step towards reference documents for specifying object-oriented languages based on operational semantics.
Control of Wireless Networks with Secrecy
Venue: arXiv cs.IT 2012
Year: 2012

We consider the problem of cross-layer resource allocation in time-varying cellular wireless networks, and incorporate information theoretic secrecy as a Quality of Service constraint. Specifically, each node in the network injects two types of traffic, private and open, at rates chosen in order to maximize a global utility function, subject to network stability and secrecy constraints. The secrecy constraint enforces an arbitrarily low mutual information leakage from the source to every node in the network, except for the sink node. We first obtain the achievable rate region for the problem for single and multi-user systems assuming that the nodes have full CSI of their neighbors. Then, we provide a joint flow control, scheduling and private encoding scheme, which does not rely on the knowledge of the prior distribution of the gain of any channel. We prove that our scheme achieves a utility, arbitrarily close to the maximum achievable utility. Numerical experiments are performed to verify the analytical results, and to show the efficacy of the dynamic control algorithm.
Throw One's Cake --- and Have It Too
Venue: arXiv cs.GT 2012
Year: 2012

We consider the problem of fairly dividing a heterogeneous cake between a number of players with different tastes. In this setting, it is known that fairness requirements may result in a suboptimal division from the social welfare standpoint. Here, we show that in some cases, discarding some of the cake and fairly dividing only the remainder may be socially preferable to any fair division of the entire cake. We study this phenomenon, providing asymptotically-tight bounds on the social improvement achievable by such discarding.
Competitive and Deterministic Embeddings of Virtual Networks
Venue: arXiv cs.NI 2012
Year: 2012

Network virtualization is an important concept to overcome the ossification of today's Internet as it facilitates innovation also in the network core and as it promises a more efficient use of the given resources and infrastructure. Virtual networks (VNets) provide an abstraction of the physical network: multiple VNets may cohabit the same physical network, but can be based on completely different protocol stacks (also beyond IP). One of the main challenges in network virtualization is the efficient admission control and embedding of VNets. The demand for virtual networks (e.g., for a video conference) can be hard to predict, and once the request is accepted, the specification / QoS guarantees must be ensured throughout the VNet's lifetime. This requires an admission control algorithm which only selects high-benefit VNets in times of scarce resources, and an embedding algorithm which realizes the VNet in such a way that the likelihood that future requests can be embedded as well is maximized. This article describes a generic algorithm for the online VNet embedding problem which does not rely on any knowledge of the future VNet requests but whose performance is competitive to an optimal offline algorithm that has complete knowledge of the request sequence in advance: the so-called competitive ratio is, loosely speaking, logarithmic in the sum of the resources. Our algorithm is generic in the sense that it supports multiple traffic models, multiple routing models, and even allows for nonuniform benefits and durations of VNet requests.