OpenRaiser/Intern-Atlas huggingface dataset:
Estimating the Trace of the Matrix Inverse by Interpolating from the Diagonal of an Approximate Inverse
Venue: arXiv cs.NA 2016
Year: 2016

A number of applications require the computation of the trace of a matrix that is implicitly available through a function. A common example of a function is the inverse of a large, sparse matrix, which is the focus of this paper. When the evaluation of the function is expensive, the task is computationally challenging because the standard approach is based on a Monte Carlo method which converges slowly. We present a different approach that exploits the pattern correlation, if present, between the diagonal of the inverse of the matrix and the diagonal of some approximate inverse that can be computed inexpensively. We leverage various sampling and fitting techniques to fit the diagonal of the approximation to the diagonal of the inverse. Depending on the quality of the approximate inverse, our method may serve as a standalone kernel for providing a fast trace estimate with a small number of samples. Furthermore, the method can be used as a variance reduction method for Monte Carlo in some cases. This is decided dynamically by our algorithm. An extensive set of experiments with various technique combinations on several matrices from some real applications demonstrate the potential of our method.
GHOST: Building blocks for high performance sparse linear algebra on heterogeneous systems
Venue: arXiv cs.DC 2016
Year: 2016

While many of the architectural details of future exascale-class high performance computer systems are still a matter of intense research, there appears to be a general consensus that they will be strongly heterogeneous, featuring "standard" as well as "accelerated" resources. Today, such resources are available as multicore processors, graphics processing units (GPUs), and other accelerators such as the Intel Xeon Phi. Any software infrastructure that claims usefulness for such environments must be able to meet their inherent challenges: massive multi-level parallelism, topology, asynchronicity, and abstraction. The "General, Hybrid, and Optimized Sparse Toolkit" (GHOST) is a collection of building blocks that targets algorithms dealing with sparse matrix representations on current and future large-scale systems. It implements the "MPI+X" paradigm, has a pure C interface, and provides hybrid-parallel numerical kernels, intelligent resource management, and truly heterogeneous parallelism for multicore CPUs, Nvidia GPUs, and the Intel Xeon Phi. We describe the details of its design with respect to the challenges posed by modern heterogeneous supercomputers and recent algorithmic developments. Implementation details which are indispensable for achieving high efficiency are pointed out and their necessity is justified by performance measurements or predictions based on performance models. The library code and several applications are available as open source. We also provide instructions on how to make use of GHOST in existing software packages, together with a case study which demonstrates the applicability and performance of GHOST as a component within a larger software stack.
HCMapper: An interactive visualization tool to compare partition-based flat clustering extracted from pairs of dendrograms
Venue: arXiv cs.HC 2016
Year: 2016

We describe a new visualization tool, dubbed HCMapper, that visually helps to compare a pair of dendrograms computed on the same dataset by displaying multiscale partition-based layered structures. The dendrograms are obtained by hierarchical clustering techniques whose output reflects some hypothesis on the data and HCMapper is specifically designed to grasp at first glance both whether the two compared hypotheses broadly agree and the data points on which they do not concur. Leveraging juxtaposition and explicit encodings, HCMapper focus on two selected partitions while displaying coarser ones in context areas for understanding multiscale structure and eventually switching the selected partitions. HCMapper utility is shown through the example of testing whether the prices of credit default swap financial time series only undergo correlation. This use case is detailed in the supplementary material as well as experiments with code on toy-datasets for reproducible research. HCMapper is currently released as a visualization tool on the DataGrapple time series and clustering analysis platorm at www.datagrapple.com.
Response-Time-Optimised Service Deployment: MILP Formulations of Piece-wise Linear Functions Approximating Non-linear Bivariate Mixed-integer Functions
Venue: arXiv cs.NI 2016
Year: 2016

A current trend in networking and cloud computing is to provide compute resources at widely dispersed places; this is exemplified by developments such as Network Function Virtualisation. This paves the way for wide-area service deployments with improved service quality: e.g, a nearby server can reduce the user-perceived response times. But always using the nearest server can be a bad decision if that server is already highly utilised. This paper formalises the two related problems of allocating resources at different locations and assigning users to them with the goal of minimising the response times for a given number of resources to use -- a non-linear capacitated facility location problem with integrated queuing systems. To efficiently handle the non-linearity, we introduce five linear problem approximations and adapt the currently best heuristic for a similar problem to our scenario. All six approaches are compared in experiments for solution quality and solving time. Surprisingly, our best optimisation formulation outperforms the heuristic in both time and quality. Additionally, we evaluate the influence ot resource distributions in the network on the response time: Cut by half for some configurations. The presented formulations are applicable to a broader optimisation domain.
$f$-divergence Inequalities
Venue: arXiv cs.IT 2016
Year: 2016

This paper develops systematic approaches to obtain $f$-divergence inequalities, dealing with pairs of probability measures defined on arbitrary alphabets. Functional domination is one such approach, where special emphasis is placed on finding the best possible constant upper bounding a ratio of $f$-divergences. Another approach used for the derivation of bounds among $f$-divergences relies on moment inequalities and the logarithmic-convexity property, which results in tight bounds on the relative entropy and Bhattacharyya distance in terms of $χ^2$ divergences. A rich variety of bounds are shown to hold under boundedness assumptions on the relative information. Special attention is devoted to the total variation distance and its relation to the relative information and relative entropy, including "reverse Pinsker inequalities," as well as on the $E_γ$ divergence, which generalizes the total variation distance. Pinsker's inequality is extended for this type of $f$-divergence, a result which leads to an inequality linking the relative entropy and relative information spectrum. Integral expressions of the Rényi divergence in terms of the relative information spectrum are derived, leading to bounds on the Rényi divergence in terms of either the variational distance or relative entropy.
Coding for interactive communication correcting insertions and deletions
Venue: arXiv cs.DS 2016
Year: 2016

We consider the question of interactive communication, in which two remote parties perform a computation while their communication channel is (adversarially) noisy. We extend here the discussion into a more general and stronger class of noise, namely, we allow the channel to perform insertions and deletions of symbols. These types of errors may bring the parties "out of sync", so that there is no consensus regarding the current round of the protocol. In this more general noise model, we obtain the first interactive coding scheme that has a constant rate and resists noise rates of up to $1/18-\varepsilon$. To this end we develop a novel primitive we name edit distance tree code. The edit distance tree code is designed to replace the Hamming distance constraints in Schulman's tree codes (STOC 93), with a stronger edit distance requirement. However, the straightforward generalization of tree codes to edit distance does not seem to yield a primitive that suffices for communication in the presence of synchronization problems. Giving the "right" definition of edit distance tree codes is a main conceptual contribution of this work.
Non-commutative Edmonds' problem and matrix semi-invariants
Venue: arXiv cs.DS 2016
Year: 2016

In 1967, Edmonds introduced the problem of computing the rank over the rational function field of an $n\times n$ matrix $T$ with integral homogeneous linear polynomials. In this paper, we consider the non-commutative version of Edmonds' problem: compute the rank of $T$ over the free skew field. It is known that this problem relates to the ring of matrix semi-invariants. In particular, if the nullcone of matrix semi-invariants is defined by elements of degree $\leq σ$, then there follows a $\mathrm{poly}(n, σ)$-time randomized algorithm to decide whether the non-commutative rank of $T$ is $<n$. To our knowledge, previously the best bound for $σ$ was $O(n^2\cdot 4^{n^2})$ over algebraically closed fields of characteristic $0$ (Derksen, 2001). In this article we prove the following results: (1) We observe that by using an algorithm of Gurvits, and assuming the above bound $σ$ for $R(n, m)$ over $\mathbb{Q}$, deciding whether $T$ has non-commutative rank $<n$ over $\mathbb{Q}$ can be done deterministically in time polynomial in the input size and $σ$. (2) When $\mathbb{F}$ is large enough, we devise a deterministic algorithm for non-commutative Edmonds' problem in time polynomial in $(n+1)!$, with the following consequences. (2.a) If the commutative rank and the non-commutative rank of $T$ differ by a constant, then there exists a randomized efficient algorithm that computes the non-commutative rank of $T$. (2.b) We prove that $σ\leq (n+1)!$. This not only improves the bound obtained from Derksen's work over algebraically closed field of characteristic $0$ but, more importantly, also provides for the first time an explicit bound on $σ$ for matrix semi-invariants over fields of positive characteristics.
TabletGaze: Unconstrained Appearance-based Gaze Estimation in Mobile Tablets
Venue: arXiv cs.CV 2016
Year: 2016

We study gaze estimation on tablets, our key design goal is uncalibrated gaze estimation using the front-facing camera during natural use of tablets, where the posture and method of holding the tablet is not constrained. We collected the first large unconstrained gaze dataset of tablet users, labeled Rice TabletGaze dataset. The dataset consists of 51 subjects, each with 4 different postures and 35 gaze locations. Subjects vary in race, gender and in their need for prescription glasses, all of which might impact gaze estimation accuracy. Driven by our observations on the collected data, we present a TabletGaze algorithm for automatic gaze estimation using multi-level HoG feature and Random Forests regressor. The TabletGaze algorithm achieves a mean error of 3.17 cm. We perform extensive evaluation on the impact of various factors such as dataset size, race, wearing glasses and user posture on the gaze estimation accuracy and make important observations about the impact of these factors.
Finding Function in Form: Compositional Character Models for Open Vocabulary Word Representation
Venue: arXiv cs.CL 2016
Year: 2016

We introduce a model for constructing vector representations of words by composing characters using bidirectional LSTMs. Relative to traditional word representation models that have independent vectors for each word type, our model requires only a single vector per character type and a fixed set of parameters for the compositional model. Despite the compactness of this model and, more importantly, the arbitrary nature of the form-function relationship in language, our "composed" word representations yield state-of-the-art results in language modeling and part-of-speech tagging. Benefits over traditional baselines are particularly pronounced in morphologically rich languages (e.g., Turkish).
Maximum Entropy Vector Kernels for MIMO system identification
Venue: arXiv cs.SY 2016
Year: 2016

Recent contributions have framed linear system identification as a nonparametric regularized inverse problem. Relying on $\ell_2$-type regularization which accounts for the stability and smoothness of the impulse response to be estimated, these approaches have been shown to be competitive w.r.t classical parametric methods. In this paper, adopting Maximum Entropy arguments, we derive a new $\ell_2$ penalty deriving from a vector-valued kernel; to do so we exploit the structure of the Hankel matrix, thus controlling at the same time complexity, measured by the McMillan degree, stability and smoothness of the identified models. As a special case we recover the nuclear norm penalty on the squared block Hankel matrix. In contrast with previous literature on reweighted nuclear norm penalties, our kernel is described by a small number of hyper-parameters, which are iteratively updated through marginal likelihood maximization; constraining the structure of the kernel acts as a (hyper)regularizer which helps controlling the effective degrees of freedom of our estimator. To optimize the marginal likelihood we adapt a Scaled Gradient Projection (SGP) algorithm which is proved to be significantly computationally cheaper than other first and second order off-the-shelf optimization methods. The paper also contains an extensive comparison with many state-of-the-art methods on several Monte-Carlo studies, which confirms the effectiveness of our procedure.
Algorithmic Aspects of Optimal Channel Coding
Venue: arXiv cs.IT 2016
Year: 2016

A central question in information theory is to determine the maximum success probability that can be achieved in sending a fixed number of messages over a noisy channel. This was first studied in the pioneering work of Shannon who established a simple expression characterizing this quantity in the limit of multiple independent uses of the channel. Here we consider the general setting with only one use of the channel. We observe that the maximum success probability can be expressed as the maximum value of a submodular function. Using this connection, we establish the following results: 1. There is a simple greedy polynomial-time algorithm that computes a code achieving a (1-1/e)-approximation of the maximum success probability. Moreover, for this problem it is NP-hard to obtain an approximation ratio strictly better than (1-1/e). 2. Shared quantum entanglement between the sender and the receiver can increase the success probability by a factor of at most 1/(1-1/e). In addition, this factor is tight if one allows an arbitrary non-signaling box between the sender and the receiver. 3. We give tight bounds on the one-shot performance of the meta-converse of Polyanskiy-Poor-Verdu.
A Discrete and Bounded Envy-free Cake Cutting Protocol for Four Agents
Venue: arXiv cs.DS 2016
Year: 2016

We consider the well-studied cake cutting problem in which the goal is to identify a fair allocation based on a minimal number of queries from the agents. The problem has attracted considerable attention within various branches of computer science, mathematics, and economics. Although, the elegant Selfridge-Conway envy-free protocol for three agents has been known since 1960, it has been a major open problem for the last fifty years to obtain a bounded envy-free protocol for more than three agents. We propose a discrete and bounded envy-free protocol for four agents.
On the Physical Design of Molecular Communication Receiver Based on Nanoscale Biosensors
Venue: arXiv cs.ET 2016
Year: 2016

Molecular communications (MC), where molecules are used to encode, transmit, and receive information, is a promising means of enabling the coordination of nanoscale devices. The paradigm has been extensively studied from various aspects, including channel modeling and noise analysis. Comparatively little attention has been given to the physical design of molecular receiver and transmitter, envisioning biological synthetic cells with intrinsic molecular reception and transmission capabilities as the future nanomachines. However, this assumption leads to a discrepancy between the envisaged applications requiring complex communication interfaces and protocols, and the very limited computational capacities of the envisioned biological nanomachines. In this paper, we examine the feasibility of designing a molecular receiver, in a physical domain other than synthetic biology, meeting the basic requirements of nanonetwork applications. We first review the state-of-the-art biosensing approaches to determine whether they can inspire a receiver design. We reveal that nanoscale field effect transistor based electrical biosensor technology (bioFET) is a particularly useful starting point for designing a molecular receiver. Focusing on bioFET-based molecular receivers with a conceptual approach, we provide a guideline elaborating on their operation principles, performance metrics and design parameters. We then provide a simple model for signal flow in silicon nanowire (SiNW) FET-based molecular receiver. Lastly, we discuss the practical challenges of implementing the receiver and present the future research avenues from a communication theoretical perspective.
Optimal input signal distribution and per-sample mutual information for nondispersive nonlinear optical fiber channel at large SNR
Venue: arXiv cs.IT 2016
Year: 2016

We consider a model nondispersive nonlinear optical fiber channel with additive white Gaussian noise at large $\mathrm{SNR}$ (signal-to-noise ratio) in the intermediate power region. Using Feynman path-integral technique we for the first time find the optimal input signal distribution maximizing the channel's per-sample mutual information. The finding of the optimal input signal distribution allows us to improve previously known estimates for the channel capacity. The output signal entropy, conditional entropy, and per-sample mutual information are calculated for Gaussian, half-Gaussian and modified Gaussian input signal distributions. We explicitly show that in the intermediate power regime the per-sample mutual information for the optimal input signal distribution is greater than the per-sample mutual information for the Gaussian and half-Gaussian input signal distributions.
A note on the complexity of the causal ordering problem
Venue: arXiv cs.AI 2016
Year: 2016

In this note we provide a concise report on the complexity of the causal ordering problem, originally introduced by Simon to reason about causal dependencies implicit in systems of mathematical equations. We show that Simon's classical algorithm to infer causal ordering is NP-Hard---an intractability previously guessed but never proven. We present then a detailed account based on Nayak's suggested algorithmic solution (the best available), which is dominated by computing transitive closure---bounded in time by $O(|\mathcal V|\cdot |\mathcal S|)$, where $\mathcal S(\mathcal E, \mathcal V)$ is the input system structure composed of a set $\mathcal E$ of equations over a set $\mathcal V$ of variables with number of variable appearances (density) $|\mathcal S|$. We also comment on the potential of causal ordering for emerging applications in large-scale hypothesis management and analytics.
Efficient Private Statistics with Succinct Sketches
Venue: arXiv cs.CR 2016
Year: 2016

Large-scale collection of contextual information is often essential in order to gather statistics, train machine learning models, and extract knowledge from data. The ability to do so in a {\em privacy-preserving} way -- i.e., without collecting fine-grained user data -- enables a number of additional computational scenarios that would be hard, or outright impossible, to realize without strong privacy guarantees. In this paper, we present the design and implementation of practical techniques for privately gathering statistics from large data streams. We build on efficient cryptographic protocols for private aggregation and on data structures for succinct data representation, namely, Count-Min Sketch and Count Sketch. These allow us to reduce the communication and computation complexity incurred by each data source (e.g., end-users) from linear to logarithmic in the size of their input, while introducing a parametrized upper-bounded error that does not compromise the quality of the statistics. We then show how to use our techniques, efficiently, to instantiate real-world privacy-friendly systems, supporting recommendations for media streaming services, prediction of user locations, and computation of median statistics for Tor hidden services.
Reduced-order Distributed Consensus Controller Design via Edge Dynamics
Venue: arXiv cs.SY 2016
Year: 2016

This paper proposes a novel approach to design reduced-order distributed consensus controllers for multi-agent systems (MASs) with identical linear dynamics of agents. A new model namely edge dynamics representing the differences on agents' states is first presented. Then the distributed consensus controller design is shown to be equivalent to the synthesis of a distributed stabilizing controller for this edge dynamics. Consequently, based on LQR approach, the globally optimal and locally optimal distributed stabilizing controller designs are proposed, of which the locally distributed stabilizing controller for the edge dynamics results in a distributed consensus controller for the MAS with no conservative bound on the coupling strength. This approach is next further developed to obtain reduced-order distributed consensus controllers for linear MASs. Several numerical examples are introduced to illustrate the theoretical results.
The Stable Fixtures Problem with Payments
Venue: arXiv cs.GT 2016
Year: 2016

We generalize two well-known game-theoretic models by introducing multiple partners matching games, defined by a graph $G=(N,E)$, with an integer vertex capacity function $b$ and an edge weighting $w$. The set $N$ consists of a number of players that are to form a set $M\subseteq E$ of 2-player coalitions $ij$ with value $w(ij)$, such that each player $i$ is in at most $b(i)$ coalitions. A payoff vector is a mapping $p: N \times N \rightarrow {\mathbb R}$ with $p(i,j)+p(j,i)=w(ij)$ if $ij\in M$ and $p(i,j)=p(j,i)=0$ if $ij\notin M$. The pair $(M,p)$ is called a solution. A pair of players $i,j$ with $ij\in E\setminus M$ blocks a solution $(M,p)$ if $i,j$ can form, possibly only after withdrawing from one of their existing 2-player coalitions, a new 2-player coalition in which they are mutually better off. A solution is stable if it has no blocking pairs. We give a polynomial-time algorithm that either finds that a given multiple partners matching game has no stable solution, or obtains a stable solution for it. We characterize the set of stable solutions of a multiple partners matching game in two different ways and show how this leads to simple proofs for a number of known results of Sotomayor (1992,1999,2007) for multiple partners ssignment games and to generalizations of some of these results to multiple partners matching games. We also perform a study on the core of the corresponding cooperative game, where coalitions of any size may be formed. In particular we show that the standard relation between the existence of a stable solution and the non-emptiness of the core, which holds in the other models with payments, is no longer valid for our (most general) model. We also prove that the problem of deciding if an allocation belongs to the core jumps from being polynomial-time solvable for $b\leq 2$ to NP-complete for $b\equiv 3$.