OpenRaiser/Intern-Atlas huggingface dataset:
Universal Communication over Arbitrarily Varying Channels
Venue: arXiv cs.IT 2012
Year: 2012

We consider the problem of universally communicating over an unknown and arbitrarily varying channel, using feedback. The focus of this paper is on determining the input behavior, and specifically, a prior distribution which is used to randomly generate the codebook. We pose the problem of setting the prior as a sequential universal prediction problem, that attempts to approach a given target rate, which depends on the unknown channel sequence. The main result is that, for a channel comprised of an unknown, arbitrary sequence of memoryless channels, there is a system using feedback and common randomness that asymptotically attains, with high probability, the capacity of the time-averaged channel, universally for every sequence of channels. While no prior knowledge of the channel sequence is assumed, the rate achieved meets or exceeds the traditional arbitrarily varying channel (AVC) capacity for every memoryless AVC defined over the same alphabets, and therefore the system universally attains the random code AVC capacity, without knowledge of the AVC parameters. The system we present combines rateless coding with a universal prediction scheme for the prior. We present rough upper bounds on the rates that can be achieved in this setting and lower bounds for the redundancies.
Axiomatizing Resource Bounds for Measure
Venue: arXiv cs.CC 2012
Year: 2012

Resource-bounded measure is a generalization of classical Lebesgue measure that is useful in computational complexity. The central parameter of resource-bounded measure is the {\it resource bound} $Δ$, which is a class of functions. When $Δ$ is unrestricted, i.e., contains all functions with the specified domains and codomains, resource-bounded measure coincides with classical Lebesgue measure. On the other hand, when $Δ$ contains functions satisfying some complexity constraint, resource-bounded measure imposes internal measure structure on a corresponding complexity class. Most applications of resource-bounded measure use only the "measure-zero/measure-one fragment" of the theory. For this fragment, $Δ$ can be taken to be a class of type-one functions (e.g., from strings to rationals). However, in the full theory of resource-bounded measurability and measure, the resource bound $Δ$ also contains type-two functionals. To date, both the full theory and its zero-one fragment have been developed in terms of a list of example resource bounds chosen for their apparent utility. This paper replaces this list-of-examples approach with a careful investigation of the conditions that suffice for a class $Δ$ to be a resource bound. Our main theorem says that every class $Δ$ that has the closure properties of Mehlhorn's basic feasible functionals is a resource bound for measure. We also prove that the type-2 versions of the time and space hierarchies that have been extensively used in resource-bounded measure have these closure properties. In the course of doing this, we prove theorems establishing that these time and space resource bounds are all robust.
Transductive Ordinal Regression
Venue: arXiv cs.LG 2012
Year: 2012

Ordinal regression is commonly formulated as a multi-class problem with ordinal constraints. The challenge of designing accurate classifiers for ordinal regression generally increases with the number of classes involved, due to the large number of labeled patterns that are needed. The availability of ordinal class labels, however, is often costly to calibrate or difficult to obtain. Unlabeled patterns, on the other hand, often exist in much greater abundance and are freely available. To take benefits from the abundance of unlabeled patterns, we present a novel transductive learning paradigm for ordinal regression in this paper, namely Transductive Ordinal Regression (TOR). The key challenge of the present study lies in the precise estimation of both the ordinal class label of the unlabeled data and the decision functions of the ordinal classes, simultaneously. The core elements of the proposed TOR include an objective function that caters to several commonly used loss functions casted in transductive settings, for general ordinal regression. A label swapping scheme that facilitates a strictly monotonic decrease in the objective function value is also introduced. Extensive numerical studies on commonly used benchmark datasets including the real world sentiment prediction problem are then presented to showcase the characteristics and efficacies of the proposed transductive ordinal regression. Further, comparisons to recent state-of-the-art ordinal regression methods demonstrate the introduced transductive learning paradigm for ordinal regression led to the robust and improved performance.
Diversity and Multiplexing Tradeoff in the Uplink of Cellular Systems with Linear MMSE Receiver
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we extend the diversity and multiplexing tradeoff (DMT) analysis from point-to-point channels to cellular systems to evaluate the impact of inter-cell interference on the system reliability and efficiency. Fundamental tradeoff among diversity order, multiplexing gain and inter-cell interference intensity is characterized to reveal the capability of multiple antennas in cellular systems. And the detrimental effects of the inter-cell interference on the system performance of diversity and multiplexing is presented and analyzed.
Schroedinger Eigenmaps for the Analysis of Bio-Medical Data
Venue: arXiv cs.CE 2012
Year: 2012

We introduce Schroedinger Eigenmaps, a new semi-supervised manifold learning and recovery technique. This method is based on an implementation of graph Schroedinger operators with appropriately constructed barrier potentials as carriers of labeled information. We use our approach for the analysis of standard bio-medical datasets and new multispectral retinal images.
Let Us Dance Just a Little Bit More --- On the Information Capacity of the Human Motor System
Venue: arXiv cs.IT 2012
Year: 2012

Fitts' law is a fundamental tool in measuring the capacity of the human motor system. However, it is, by definition, limited to aimed movements toward spatially expanded targets. We revisit its information-theoretic basis with the goal of generalizing it into unconstrained trained movement such as dance and sports. The proposed new measure is based on a subject's ability to accurately reproduce a complex movement pattern. We demonstrate our framework using motion-capture data from professional dance performances.
Bounds for identifying codes in terms of degree parameters
Venue: arXiv cs.DM 2012
Year: 2012

An identifying code is a subset of vertices of a graph such that each vertex is uniquely determined by its neighbourhood within the identifying code. If $\M(G)$ denotes the minimum size of an identifying code of a graph $G$, it was conjectured by F. Foucaud, R. Klasing, A. Kosowski and A. Raspaud that there exists a constant $c$ such that if a connected graph $G$ with $n$ vertices and maximum degree $d$ admits an identifying code, then $\M(G)\leq n-\tfrac{n}{d}+c$. We use probabilistic tools to show that for any $d\geq 3$, $\M(G)\leq n-\tfrac{n}{Θ(d)}$ holds for a large class of graphs containing, among others, all regular graphs and all graphs of bounded clique number. This settles the conjecture (up to constants) for these classes of graphs. In the general case, we prove $\M(G)\leq n-\tfrac{n}{Θ(d^{3})}$. In a second part, we prove that in any graph $G$ of minimum degree $δ$ and girth at least 5, $\M(G)\leq(1+o_δ(1))\tfrac{3\logδ}{2δ}n$. Using the former result, we give sharp estimates for the size of the minimum identifying code of random $d$-regular graphs, which is about $\tfrac{\log d}{d}n$.
On the Capacity of the K-User Cyclic Gaussian Interference Channel
Venue: arXiv cs.IT 2012
Year: 2012

This paper studies the capacity region of a $K$-user cyclic Gaussian interference channel, where the $k$th user interferes with only the $(k-1)$th user (mod $K$) in the network. Inspired by the work of Etkin, Tse and Wang, which derived a capacity region outer bound for the two-user Gaussian interference channel and proved that a simple Han-Kobayashi power splitting scheme can achieve to within one bit of the capacity region for all values of channel parameters, this paper shows that a similar strategy also achieves the capacity region for the $K$-user cyclic interference channel to within a constant gap in the weak interference regime. Specifically, a compact representation of the Han-Kobayashi achievable rate region using Fourier-Motzkin elimination is first derived, a capacity region outer bound is then established. It is shown that the Etkin-Tse-Wang power splitting strategy gives a constant gap of at most two bits (or one bit per dimension) in the weak interference regime. Finally, the capacity result of the $K$-user cyclic Gaussian interference channel in the strong interference regime is also given.
Two Birds and One Stone: Gaussian Interference Channel with a Shared Out-of-Band Relay of Limited Rate
Venue: arXiv cs.IT 2012
Year: 2012

The two-user Gaussian interference channel with a shared out-of-band relay is considered. The relay observes a linear combination of the source signals and broadcasts a common message to the two destinations, through a perfect link of fixed limited rate $R_0$ bits per channel use. The out-of-band nature of the relay is reflected by the fact that the common relay message does not interfere with the received signal at the two destinations. A general achievable rate is established, along with upper bounds on the capacity region for the Gaussian case. For $R_0$ values below a certain threshold, which depends on channel parameters, the capacity region of this channel is determined in this paper to within a constant gap of $Δ=1.95$ bits. We identify interference regimes where a two-for-one gain in achievable rates is possible for every bit relayed, up to a constant approximation error. Instrumental to these results is a carefully-designed quantize-and-forward type of relay strategy along with a joint decoding scheme employed at destination ends. Further, we also study successive decoding strategies with optimal decoding order (corresponding to the order at which common, private, and relay messages are decoded), and show that successive decoding also achieves two-for-one gains asymptotically in regimes where a two-for-one gain is achievable by joint decoding; yet, successive decoding produces unbounded loss asymptotically when compared to joint decoding, in general.
Locating a service facility and a rapid transit line
Venue: arXiv cs.CG 2012
Year: 2012

In this paper we study a facility location problem in the plane in which a single point (facility) and a rapid transit line (highway) are simultaneously located in order to minimize the total travel time of the clients to the facility, using the $L_1$ or Manhattan metric. The rapid transit line is represented by a line segment with fixed length and arbitrary orientation. The highway is an alternative transportation system that can be used by the clients to reduce their travel time to the facility. This problem was introduced by Espejo and Chía in [7]. They gave both a characterization of the optimal solutions and an algorithm running in $O(n^3\log n)$ time, where $n$ represents the number of clients. In this paper we show that the Espejo and Chía's algorithm does not always work correctly. At the same time, we provide a proper characterization of the solutions with a simpler proof and give an algorithm solving the problem in $O(n^3)$ time.
A Proposed Decision Support System/Expert System for Guiding Fresh Students in Selecting a Faculty in Gomal University, Pakistan
Venue: arXiv cs.AI 2012
Year: 2012

This paper presents the design and development of a proposed rule based Decision Support System that will help students in selecting the best suitable faculty/major decision while taking admission in Gomal University, Dera Ismail Khan, Pakistan. The basic idea of our approach is to design a model for testing and measuring the student capabilities like intelligence, understanding, comprehension, mathematical concepts plus his/her past academic record plus his/her intelligence level, and applying the module results to a rule-based decision support system to determine the compatibility of those capabilities with the available faculties/majors in Gomal University. The result is shown as a list of suggested faculties/majors with the student capabilities and abilities.
Optimal Column-Based Low-Rank Matrix Reconstruction
Venue: arXiv cs.DS 2012
Year: 2012

We prove that for any real-valued matrix $X \in \R^{m \times n}$, and positive integers $r \ge k$, there is a subset of $r$ columns of $X$ such that projecting $X$ onto their span gives a $\sqrt{\frac{r+1}{r-k+1}}$-approximation to best rank-$k$ approximation of $X$ in Frobenius norm. We show that the trade-off we achieve between the number of columns and the approximation ratio is optimal up to lower order terms. Furthermore, there is a deterministic algorithm to find such a subset of columns that runs in $O(r n m^ω \log m)$ arithmetic operations where $ω$ is the exponent of matrix multiplication. We also give a faster randomized algorithm that runs in $O(r n m^2)$ arithmetic operations.
Structural Analysis of Network Traffic Matrix via Relaxed Principal Component Pursuit
Venue: arXiv cs.NI 2012
Year: 2012

The network traffic matrix is widely used in network operation and management. It is therefore of crucial importance to analyze the components and the structure of the network traffic matrix, for which several mathematical approaches such as Principal Component Analysis (PCA) were proposed. In this paper, we first argue that PCA performs poorly for analyzing traffic matrix that is polluted by large volume anomalies, and then propose a new decomposition model for the network traffic matrix. According to this model, we carry out the structural analysis by decomposing the network traffic matrix into three sub-matrices, namely, the deterministic traffic, the anomaly traffic and the noise traffic matrix, which is similar to the Robust Principal Component Analysis (RPCA) problem previously studied in [13]. Based on the Relaxed Principal Component Pursuit (Relaxed PCP) method and the Accelerated Proximal Gradient (APG) algorithm, we present an iterative approach for decomposing a traffic matrix, and demonstrate its efficiency and flexibility by experimental results. Finally, we further discuss several features of the deterministic and noise traffic. Our study develops a novel method for the problem of structural analysis of the traffic matrix, which is robust against pollution of large volume anomalies.
Streaming Tree Transducers
Venue: arXiv cs.FL 2012
Year: 2012

Theory of tree transducers provides a foundation for understanding expressiveness and complexity of analysis problems for specification languages for transforming hierarchically structured data such as XML documents. We introduce streaming tree transducers as an analyzable, executable, and expressive model for transforming unranked ordered trees in a single pass. Given a linear encoding of the input tree, the transducer makes a single left-to-right pass through the input, and computes the output in linear time using a finite-state control, a visibly pushdown stack, and a finite number of variables that store output chunks that can be combined using the operations of string-concatenation and tree-insertion. We prove that the expressiveness of the model coincides with transductions definable using monadic second-order logic (MSO). Existing models of tree transducers either cannot implement all MSO-definable transformations, or require regular look ahead that prohibits single-pass implementation. We show a variety of analysis problems such as type-checking and checking functional equivalence are solvable for our model.
Improved Approximation Guarantees for Lower-Bounded Facility Location
Venue: arXiv cs.DS 2012
Year: 2012

We consider the {\em lower-bounded facility location} (\lbfl) problem (also sometimes called {\em load-balanced facility location}), which is a generalization of {\em uncapacitated facility location} (\ufl), where each open facility is required to serve a certain {\em minimum} amount of demand. More formally, an instance $\I$ of \lbfl is specified by a set $\F$ of facilities with facility-opening costs $\{f_i\}$, a set $\D$ of clients, and connection costs $\{c_{ij}\}$ specifying the cost of assigning a client $j$ to a facility $i$, where the $c_{ij}$s form a metric. A feasible solution specifies a subset $F$ of facilities to open, and assigns each client $j$ to an open facility $i(j)\in F$ so that each open facility serves {\em at least $M$ clients}, where $M$ is an input parameter. The cost of such a solution is $\sum_{i\in F}f_i+\sum_j c_{i(j)j}$, and the goal is to find a feasible solution of minimum cost. The current best approximation ratio for \lbfl is 448 \cite{Svitkina08}. We substantially advance the state-of-the-art for \lbfl by devising an approximation algorithm for \lbfl that achieves a significantly-improved approximation guarantee of 82.6. Our improvement comes from a variety of ideas in algorithm design and analysis, which also yield new insights into \lbfl.
The Pros and Cons of Compressive Sensing for Wideband Signal Acquisition: Noise Folding vs. Dynamic Range
Venue: arXiv cs.IT 2012
Year: 2012

Compressive sensing (CS) exploits the sparsity present in many signals to reduce the number of measurements needed for digital acquisition. With this reduction would come, in theory, commensurate reductions in the size, weight, power consumption, and/or monetary cost of both signal sensors and any associated communication links. This paper examines the use of CS in the design of a wideband radio receiver in a noisy environment. We formulate the problem statement for such a receiver and establish a reasonable set of requirements that a receiver should meet to be practically useful. We then evaluate the performance of a CS-based receiver in two ways: via a theoretical analysis of its expected performance, with a particular emphasis on noise and dynamic range, and via simulations that compare the CS receiver against the performance expected from a conventional implementation. On the one hand, we show that CS-based systems that aim to reduce the number of acquired measurements are somewhat sensitive to signal noise, exhibiting a 3dB SNR loss per octave of subsampling, which parallels the classic noise-folding phenomenon. On the other hand, we demonstrate that since they sample at a lower rate, CS-based systems can potentially attain a significantly larger dynamic range. Hence, we conclude that while a CS-based system has inherent limitations that do impose some restrictions on its potential applications, it also has attributes that make it highly desirable in a number of important practical settings.
A Novel Power Allocation Scheme for Two-User GMAC with Finite Input Constellations
Venue: arXiv cs.IT 2012
Year: 2012

Constellation Constrained (CC) capacity regions of two-user Gaussian Multiple Access Channels (GMAC) have been recently reported, wherein an appropriate angle of rotation between the constellations of the two users is shown to enlarge the CC capacity region. We refer to such a scheme as the Constellation Rotation (CR) scheme. In this paper, we propose a novel scheme called the Constellation Power Allocation (CPA) scheme, wherein the instantaneous transmit power of the two users are varied by maintaining their average power constraints. We show that the CPA scheme offers CC sum capacities equal (at low SNR values) or close (at high SNR values) to those offered by the CR scheme with reduced decoding complexity for QAM constellations. We study the robustness of the CPA scheme for random phase offsets in the channel and unequal average power constraints for the two users. With random phase offsets in the channel, we show that the CC sum capacity offered by the CPA scheme is more than the CR scheme at high SNR values. With unequal average power constraints, we show that the CPA scheme provides maximum gain when the power levels are close, and the advantage diminishes with the increase in the power difference.
Signal Processing in Large Systems: a New Paradigm
Venue: arXiv cs.IT 2012
Year: 2012

For a long time, detection and parameter estimation methods for signal processing have relied on asymptotic statistics as the number $n$ of observations of a population grows large comparatively to the population size $N$, i.e. $n/N\to \infty$. Modern technological and societal advances now demand the study of sometimes extremely large populations and simultaneously require fast signal processing due to accelerated system dynamics. This results in not-so-large practical ratios $n/N$, sometimes even smaller than one. A disruptive change in classical signal processing methods has therefore been initiated in the past ten years, mostly spurred by the field of large dimensional random matrix theory. The early works in random matrix theory for signal processing applications are however scarce and highly technical. This tutorial provides an accessible methodological introduction to the modern tools of random matrix theory and to the signal processing methods derived from them, with an emphasis on simple illustrative examples.
Generalized Boosting Algorithms for Convex Optimization
Venue: arXiv cs.LG 2012
Year: 2012

Boosting is a popular way to derive powerful learners from simpler hypothesis classes. Following previous work (Mason et al., 1999; Friedman, 2000) on general boosting frameworks, we analyze gradient-based descent algorithms for boosting with respect to any convex objective and introduce a new measure of weak learner performance into this setting which generalizes existing work. We present the weak to strong learning guarantees for the existing gradient boosting work for strongly-smooth, strongly-convex objectives under this new measure of performance, and also demonstrate that this work fails for non-smooth objectives. To address this issue, we present new algorithms which extend this boosting approach to arbitrary convex loss functions and give corresponding weak to strong convergence results. In addition, we demonstrate experimental results that support our analysis and demonstrate the need for the new algorithms we present.
Decoding q-ary lattices in the Lee metric
Venue: arXiv cs.IT 2012
Year: 2012

q-ary lattices can be obtained from q-ary codes using the so-called Construction A. We investigate these lattices in the Lee metric and show how their decoding process can be related to the associated codes. For prime q we derive a Lee sphere decoding algorithm for q-ary lattices, present a brief discussion on its complexity and some comparisons with the classic sphere decoding.