OpenRaiser/Intern-Atlas huggingface dataset:
Multiple Access Gaussian Channels with Arbitrary Inputs: Optimal Precoding and Power Allocation
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we derive new closed-form expressions for the gradient of the mutual information with respect to arbitrary parameters of the two-user multiple access channel (MAC). The derived relations generalize the fundamental relation between the derivative of the mutual information and the minimum mean squared error (MMSE) to multiuser setups. We prove that the derivative of the mutual information with respect to the signal to noise ratio (SNR) is equal to the MMSE plus a covariance induced due to the interference, quantified by a term with respect to the cross correlation of the multiuser input estimates, the channels and the precoding matrices. We also derive new relations for the gradient of the conditional and non-conditional mutual information with respect to the MMSE. Capitalizing on the new fundamental relations, we investigate the linear precoding and power allocation policies that maximize the mutual information for the two-user MAC Gaussian channels with arbitrary input distributions. We show that the optimal design of linear precoders may satisfy a fixed-point equation as a function of the channel and the input constellation under specific setups. We show also that the non-mutual interference in a multiuser setup introduces a term to the gradient of the mutual information which plays a fundamental role in the design of optimal transmission strategies, particularly the optimal precoding and power allocation, and explains the losses in the data rates. Therefore, we provide a novel interpretation of the interference with respect to the channel, power, and input estimates of the main user and the interferer.
Two-Variable Ehrenfeucht-Fraisse Games over Omega-Terms
Venue: arXiv cs.LO 2014
Year: 2014

Fragments of first-order logic over words can often be characterized in terms of finite monoids, and identities of omega-terms are an effective mechanism for specifying classes of monoids. Huschenbett and the first author have shown how to use infinite Ehrenfeucht-Fraisse games on linear orders for showing that some given fragment satisfies an identity of omega-terms (STACS 2014). After revisiting this result, we show that for two-variable logic one can use simpler linear orders.
Factorbird - a Parameter Server Approach to Distributed Matrix Factorization
Venue: arXiv cs.LG 2014
Year: 2014

We present Factorbird, a prototype of a parameter server approach for factorizing large matrices with Stochastic Gradient Descent-based algorithms. We designed Factorbird to meet the following desiderata: (a) scalability to tall and wide matrices with dozens of billions of non-zeros, (b) extensibility to different kinds of models and loss functions as long as they can be optimized using Stochastic Gradient Descent (SGD), and (c) adaptability to both batch and streaming scenarios. Factorbird uses a parameter server in order to scale to models that exceed the memory of an individual machine, and employs lock-free Hogwild!-style learning with a special partitioning scheme to drastically reduce conflicting updates. We also discuss other aspects of the design of our system such as how to efficiently grid search for hyperparameters at scale. We present experiments of Factorbird on a matrix built from a subset of Twitter's interaction graph, consisting of more than 38 billion non-zeros and about 200 million rows and columns, which is to the best of our knowledge the largest matrix on which factorization results have been reported in the literature.
Towards Tight Lower Bounds for Range Reporting on the RAM
Venue: arXiv cs.DS 2014
Year: 2014

In the orthogonal range reporting problem, we are to preprocess a set of $n$ points with integer coordinates on a $U \times U$ grid. The goal is to support reporting all $k$ points inside an axis-aligned query rectangle. This is one of the most fundamental data structure problems in databases and computational geometry. Despite the importance of the problem its complexity remains unresolved in the word-RAM. On the upper bound side, three best tradeoffs exists: (1.) Query time $O(\lg \lg n + k)$ with $O(nlg^{\varepsilon}n)$ words of space for any constant $\varepsilon>0$. (2.) Query time $O((1 + k) \lg \lg n)$ with $O(n \lg \lg n)$ words of space. (3.) Query time $O((1+k)\lg^{\varepsilon} n)$ with optimal $O(n)$ words of space. However, the only known query time lower bound is $Ω(\log \log n +k)$, even for linear space data structures. All three current best upper bound tradeoffs are derived by reducing range reporting to a ball-inheritance problem. Ball-inheritance is a problem that essentially encapsulates all previous attempts at solving range reporting in the word-RAM. In this paper we make progress towards closing the gap between the upper and lower bounds for range reporting by proving cell probe lower bounds for ball-inheritance. Our lower bounds are tight for a large range of parameters, excluding any further progress for range reporting using the ball-inheritance reduction.
Simultaneous Localization, Mapping, and Manipulation for Unsupervised Object Discovery
Venue: arXiv cs.RO 2014
Year: 2014

We present an unsupervised framework for simultaneous appearance-based object discovery, detection, tracking and reconstruction using RGBD cameras and a robot manipulator. The system performs dense 3D simultaneous localization and mapping concurrently with unsupervised object discovery. Putative objects that are spatially and visually coherent are manipulated by the robot to gain additional motion-cues. The robot uses appearance alone, followed by structure and motion cues, to jointly discover, verify, learn and improve models of objects. Induced motion segmentation reinforces learned models which are represented implicitly as 2D and 3D level sets to capture both shape and appearance. We compare three different approaches for appearance-based object discovery and find that a novel form of spatio-temporal super-pixels gives the highest quality candidate object models in terms of precision and recall. Live experiments with a Baxter robot demonstrate a holistic pipeline capable of automatic discovery, verification, detection, tracking and reconstruction of unknown objects.
Inner Loop Optimizations in Mapping Single Threaded Programs to Hardware
Venue: arXiv cs.AR 2014
Year: 2014

In the context of mapping high-level algorithms to hardware, we consider the basic problem of generating an efficient hardware implementation of a single threaded program, in particular, that of an inner loop. We describe a control-flow mechanism which provides dynamic loop-pipelining capability in hardware, so that multiple iterations of an arbitrary inner loop can be made simultaneously active in the generated hardware, We study the impact of this loop-pipelining scheme in conjunction with source-level loop-unrolling. In particular, we apply this technique to some common loop kernels: regular kernels such as the fast-fourier transform and matrix multiplication, as well as an example of an inner loop whose body has branching. The resulting resulting hardware descriptions are synthesized to an FPGA target, and then characterized for performance and resource utilization. We observe that the use of dynamic loop-pipelining mechanism alone typically results in a significant improvements in the performance of the hardware. If the loop is statically unrolled and if loop-pipelining is applied to the unrolled program, then the performance improvement is still substantial. When dynamic loop pipelining is used in conjunction with static loop unrolling, the improvement in performance ranges from 6X to 20X (in terms of number of clock cycles needed for the computation) across the loop kernels that we have studied. These optimizations do have a hardware overhead, but, in spite of this, we observe that the joint use of these loop optimizations not only improves performance, but also the performance/cost ratio of the resulting hardware.
Power-law distributions, the h-index, and Google Scholar (GS) citations: a test of their relationship with economics Nobelists
Venue: arXiv cs.DL 2014
Year: 2014

This paper presents proof that Google Scholar (GS) can construct documentary sets relevant for evaluating researchers' works. Nobelists in economics were the researchers under analysis, and two types of tests of the GS cites to their works were performed: distributional and semantic. Distributional tests found that the GS cites to the laureates' works conformed to the power-law model with an asymptote or "tail" conterminous with their h-index demarcating their core oeuvre, validating both GS and the h-index. Semantic tests revealed that their works highest in GS cites were on topics for which they were awarded the prize.
The cost of getting local monotonicity
Venue: arXiv cs.GT 2014
Year: 2014

Manfred Holler introduced the Public Good index as a proposal to divide a public good among players. In its unnormalized version, i.e., the raw measure, it counts the number of times that a player belongs to a minimal winning coalition. Unlike the Banzhaf index, it does not count the remaining winning coalitions in which the player is crucial. Holler noticed that his index does not satisfy local monotonicity, a fact that can be seen either as a major drawback or as an advantage.
A Heuristic Method for Solving the Problem of Partitioning Graphs with Supply and Demand
Venue: arXiv cs.AI 2014
Year: 2014

In this paper we present a greedy algorithm for solving the problem of the maximum partitioning of graphs with supply and demand (MPGSD). The goal of the method is to solve the MPGSD for large graphs in a reasonable time limit. This is done by using a two stage greedy algorithm, with two corresponding types of heuristics. The solutions acquired in this way are improved by applying a computationally inexpensive, hill climbing like, greedy correction procedure. In our numeric experiments we analyze different heuristic functions for each stage of the greedy algorithm, and show that their performance is highly dependent on the properties of the specific instance. Our tests show that by exploring a relatively small number of solutions generated by combining different heuristic functions, and applying the proposed correction procedure we can find solutions within only a few percent of the optimal ones.
ira_laser_tools: a ROS LaserScan manipulation toolbox
Venue: arXiv cs.RO 2014
Year: 2014

Laser scanners are sensors of widespread use in robotic applications. Under the Robot Operating System (ROS) the information generated by laser scanners can be conveyed by either LaserScan messages or in the form of PointClouds. Many publicly available algorithms (mapping, localization, navigation, etc.) rely on LaserScan messages, yet a tool for handling multiple lasers, merging their measurements, or to generate generic LaserScan messages from PointClouds, is not available. This report describes two tools, in the form of ROS nodes, which we release as open source under the BSD license, which allow to either merge multiple single-plane laser scans or to generate virtual laser scans from a point cloud. A short tutorial, along with the main advantages and limitations of these tools are presented.
On the Subtleties of q-PAM Linear Physical-Layer Network Coding
Venue: arXiv cs.IT 2014
Year: 2014

This paper investigates various subtleties of applying linear physical-layer network coding (PNC) with q-level pulse amplitude modulation (q-PAM) in two-way relay channels (TWRC). A critical issue is how the PNC system performs when the received powers from the two users at the relay are imbalanced. In particular, how would the PNC system perform under slight power imbalance that is inevitable in practice, even when power control is applied? To answer these questions, this paper presents a comprehensive analysis of q-PAM PNC. Our contributions are as follows: 1) We give a systematic way to obtain the analytical relationship between the minimum distance of the signal constellation induced by the superimposed signals of the two users (a key performance determining factor) and the channel-gain ratio of the two users, for all q. In particular, we show how the minimum distance changes in a piecewise linear fashion as the channel-gain ratio varies. 2) We show that the performance of q-PAM PNC is highly sensitive to imbalanced received powers from the two users at the relay, even when the power imbalance is slight (e.g., the residual power imbalance in a power-controlled system). This sensitivity problem is exacerbated as q increases, calling into question the robustness of high-order modulated PNC. 3) We propose an asynchronized PNC system in which the symbol arrival times of the two users at the relay are deliberately made to be asynchronous. We show that such asynchronized PNC, when operated with a belief propagation (BP) decoder, can remove the sensitivity problem, allowing a robust high-order modulated PNC system to be built.
How Well Can Graphs Represent Wireless Interference?
Venue: arXiv cs.NI 2014
Year: 2014

Efficient use of a wireless network requires that transmissions be grouped into feasible sets, where feasibility means that each transmission can be successfully decoded in spite of the interference caused by simultaneous transmissions. Feasibility is most closely modeled by a signal-to-interference-plus-noise (SINR) formula, which unfortunately is conceptually complicated, being an asymmetric, cumulative, many-to-one relationship. We re-examine how well graphs can capture wireless receptions as encoded in SINR relationships, placing them in a framework in order to understand the limits of such modelling. We seek for each wireless instance a pair of graphs that provide upper and lower bounds on the feasibility relation, while aiming to minimize the gap between the two graphs. The cost of a graph formulation is the worst gap over all instances, and the price of (graph) abstraction is the smallest cost of a graph formulation. We propose a family of conflict graphs that is parameterized by a non-decreasing sub-linear function, and show that with a judicious choice of functions, the graphs can capture feasibility with a cost of $O(\log^* Δ)$, where $Δ$ is the ratio between the longest and the shortest link length. This holds on the plane and more generally in doubling metrics. We use this to give greatly improved $O(\log^* Δ)$-approximation for fundamental link scheduling problems with arbitrary power control. We explore the limits of graph representations and find that our upper bound is tight: the price of graph abstraction is $Ω(\log^* Δ)$. We also give strong impossibility results for general metrics, and for approximations in terms of the number of links.
Edge Detection based on Kernel Density Estimation
Venue: arXiv cs.CV 2014
Year: 2014

Edges of an image are considered a crucial type of information. These can be extracted by applying edge detectors with different methodology. Edge detection is a vital step in computer vision tasks, because it is an essential issue for pattern recognition and visual interpretation. In this paper, we propose a new method for edge detection in images, based on the estimation by kernel of the probability density function. In our algorithm, pixels in the image with minimum value of density function are labeled as edges. The boundary between two homogeneous regions is defined in two domains: the spatial/lattice domain and the range/color domain. Extensive experimental evaluations proved that our edge detection method is significantly a competitive algorithm.
Election vs. Selection: Two Ways of Finding the Largest Node in a Graph
Venue: arXiv cs.DC 2014
Year: 2014

Finding the node with the largest label in a network, modeled as an undirected connected graph, is one of the fundamental problems in distributed computing. This is the way in which $\textit{leader election}$ is usually solved. We consider two distinct tasks in which the largest-labeled node is found deterministically. In $\textit{selection}$, this node must output 1 and all other nodes must output 0. In $\textit{election}$, the other nodes must additionally learn the largest label. Our aim is to compare the difficulty of these two tasks executed under stringent running time constraints. The measure of difficulty is the amount of information that nodes of the network must initially possess in order to solve the given task in an imposed amount of time. Following the standard framework of $\textit{algorithms with advice}$, this information (a single binary string) is provided to all nodes at the start by an oracle knowing the entire graph. The length of this string is called the $\textit{size of advice}$. Consider the class of $n$-node graphs with any diameter $diam \leq D$. If time is larger than $diam$, then both tasks can be solved without advice. For the task of $\textit{election}$, we show that if time is smaller than $diam$, then the optimal size of advice is $Θ(\log n)$, and if time is exactly $diam$, then the optimal size of advice is $Θ(\log D)$. For the task of $\textit{selection}$, the situation changes dramatically, even within the class of rings. Indeed, for the class of rings, we show that, if time is $O(diam^ε)$, for any $ε<1$, then the optimal size of advice is $Θ(\log D)$, and, if time is $Θ(diam)$ (and at most $diam$) then this optimal size is $Θ(\log \log D)$.
On Match Lengths, Zero Entropy and Large Deviations - with Application to Sliding Window Lempel-Ziv Algorithm
Venue: arXiv cs.IT 2014
Year: 2014

The Sliding Window Lempel-Ziv (SWLZ) algorithm that makes use of recurrence times and match lengths has been studied from various perspectives in information theory literature. In this paper, we undertake a finer study of these quantities under two different scenarios, i) \emph{zero entropy} sources that are characterized by strong long-term memory, and ii) the processes with weak memory as described through various mixing conditions. For zero entropy sources, a general statement on match length is obtained. It is used in the proof of almost sure optimality of Fixed Shift Variant of Lempel-Ziv (FSLZ) and SWLZ algorithms given in literature. Through an example of stationary and ergodic processes generated by an irrational rotation we establish that for a window of size $n_w$, a compression ratio given by $O(\frac{\log n_w}{{n_w}^a})$ where $a$ depends on $n_w$ and approaches 1 as $n_w \rightarrow \infty$, is obtained under the application of FSLZ and SWLZ algorithms. Also, we give a general expression for the compression ratio for a class of stationary and ergodic processes with zero entropy. Next, we extend the study of Ornstein and Weiss on the asymptotic behavior of the \emph{normalized} version of recurrence times and establish the \emph{large deviation property} (LDP) for a class of mixing processes. Also, an estimator of entropy based on recurrence times is proposed for which large deviation principle is proved for sources satisfying similar mixing conditions.
Efficient Representations for Life-Long Learning and Autoencoding
Venue: arXiv cs.LG 2014
Year: 2014

It has been a long-standing goal in machine learning, as well as in AI more generally, to develop life-long learning systems that learn many different tasks over time, and reuse insights from tasks learned, "learning to learn" as they do so. In this work we pose and provide efficient algorithms for several natural theoretical formulations of this goal. Specifically, we consider the problem of learning many different target functions over time, that share certain commonalities that are initially unknown to the learning algorithm. Our aim is to learn new internal representations as the algorithm learns new target functions, that capture this commonality and allow subsequent learning tasks to be solved more efficiently and from less data. We develop efficient algorithms for two very different kinds of commonalities that target functions might share: one based on learning common low-dimensional and unions of low-dimensional subspaces and one based on learning nonlinear Boolean combinations of features. Our algorithms for learning Boolean feature combinations additionally have a dual interpretation, and can be viewed as giving an efficient procedure for constructing near-optimal sparse Boolean autoencoders under a natural "anchor-set" assumption.
Device-to-Device Data Storage with Regenerating Codes
Venue: arXiv cs.NI 2014
Year: 2014

Caching data files directly on mobile user devices combined with device-to-device (D2D) communications has recently been suggested to improve the capacity of wireless net6works. We investigate the performance of regenerating codes in terms of the total energy consumption of a cellular network. We show that regenerating codes can offer large performance gains. It turns out that using redundancy against storage node failures is only beneficial if the popularity of the data is between certain thresholds. As our major contribution, we investigate under which circumstances regenerating codes with multiple redundant data fragments outdo uncoded caching.
Metric and non-metric proximity transformations at linear costs
Venue: arXiv cs.DS 2014
Year: 2014

Domain specific (dis-)similarity or proximity measures used e.g. in alignment algorithms of sequence data, are popular to analyze complex data objects and to cover domain specific data properties. Without an underlying vector space these data are given as pairwise (dis-)similarities only. The few available methods for such data focus widely on similarities and do not scale to large data sets. Kernel methods are very effective for metric similarity matrices, also at large scale, but costly transformations are necessary starting with non-metric (dis-) similarities. We propose an integrative combination of Nystroem approximation, potential double centering and eigenvalue correction to obtain valid kernel matrices at linear costs in the number of samples. By the proposed approach effective kernel approaches, become accessible. Experiments with several larger (dis-)similarity data sets show that the proposed method achieves much better runtime performance than the standard strategy while keeping competitive model accuracy. The main contribution is an efficient and accurate technique, to convert (potentially non-metric) large scale dissimilarity matrices into approximated positive semi-definite kernel matrices at linear costs.
On Chord and Sagitta in ${\mathbb Z}^2$: An Analysis towards Fast and Robust Circular Arc Detection
Venue: arXiv cs.CG 2014
Year: 2014

Although chord and sagitta, when considered in tandem, may reflect many underlying geometric properties of circles on the Euclidean plane, their implications on the digital plane are not yet well-understood. In this paper, we explore some of their fundamental properties on the digital plane that have a strong bearing on the unsupervised detection of circles and circular arcs in a digital image. We show that although the chord-and-sagitta properties of a real circle do not readily migrate to the digital plane, they can indeed be used for the analysis in the discrete domain based on certain bounds on their deviations, which are derived from the real domain. In particular, we derive an upper bound on the circumferential angular deviation of a point in the context of chord property, and an upper bound on the relative error in radius estimation with regard to the sagitta property. Using these two bounds, we design a novel algorithm for the detection and parameterization of circles and circular arcs, which does not require any heuristic initialization or manual tuning. The chord property is deployed for the detection of circular arcs, whereas the sagitta property is used to estimate their centers and radii. Finally, to improve the accuracy of estimation, the notion of restricted Hough transform is used. Experimental results demonstrate superior efficiency and robustness of the proposed methodology compared to existing techniques.
State of Charge Evolution Equations for Flywheels
Venue: arXiv cs.SY 2014
Year: 2014

A mathematical state-of-charge evolution equation is present for Flywheel Energy Storage Systems.