OpenRaiser/Intern-Atlas huggingface dataset:
Blind system identification using kernel-based methods
Venue: arXiv cs.SY 2016
Year: 2016

We propose a new method for blind system identification. Resorting to a Gaussian regression framework, we model the impulse response of the unknown linear system as a realization of a Gaussian process. The structure of the covariance matrix (or kernel) of such a process is given by the stable spline kernel, which has been recently introduced for system identification purposes and depends on an unknown hyperparameter. We assume that the input can be linearly described by few parameters. We estimate these parameters, together with the kernel hyperparameter and the noise variance, using an empirical Bayes approach. The related optimization problem is efficiently solved with a novel iterative scheme based on the Expectation-Maximization method. In particular, we show that each iteration consists of a set of simple update rules. We show, through some numerical experiments, very promising performance of the proposed method.
Learning Precise Spike Train to Spike Train Transformations in Multilayer Feedforward Neuronal Networks
Venue: arXiv cs.NE 2016
Year: 2016

We derive a synaptic weight update rule for learning temporally precise spike train to spike train transformations in multilayer feedforward networks of spiking neurons. The framework, aimed at seamlessly generalizing error backpropagation to the deterministic spiking neuron setting, is based strictly on spike timing and avoids invoking concepts pertaining to spike rates or probabilistic models of spiking. The derivation is founded on two innovations. First, an error functional is proposed that compares the spike train emitted by the output neuron of the network to the desired spike train by way of their putative impact on a virtual postsynaptic neuron. This formulation sidesteps the need for spike alignment and leads to closed form solutions for all quantities of interest. Second, virtual assignment of weights to spikes rather than synapses enables a perturbation analysis of individual spike times and synaptic weights of the output as well as all intermediate neurons in the network, which yields the gradients of the error functional with respect to the said entities. Learning proceeds via a gradient descent mechanism that leverages these quantities. Simulation experiments demonstrate the efficacy of the proposed learning framework. The experiments also highlight asymmetries between synapses on excitatory and inhibitory neurons.
Query Complexity of Approximate Equilibria in Anonymous Games
Venue: arXiv cs.GT 2016
Year: 2016

We study the computation of equilibria of anonymous games, via algorithms that may proceed via a sequence of adaptive queries to the game's payoff function, assumed to be unknown initially. The general topic we consider is \emph{query complexity}, that is, how many queries are necessary or sufficient to compute an exact or approximate Nash equilibrium. We show that exact equilibria cannot be found via query-efficient algorithms. We also give an example of a 2-strategy, 3-player anonymous game that does not have any exact Nash equilibrium in rational numbers. However, more positive query-complexity bounds are attainable if either further symmetries of the utility functions are assumed or we focus on approximate equilibria. We investigate four sub-classes of anonymous games previously considered by \cite{bfh09, dp14}. Our main result is a new randomized query-efficient algorithm that finds a $O(n^{-1/4})$-approximate Nash equilibrium querying $\tilde{O}(n^{3/2})$ payoffs and runs in time $\tilde{O}(n^{3/2})$. This improves on the running time of pre-existing algorithms for approximate equilibria of anonymous games, and is the first one to obtain an inverse polynomial approximation in poly-time. We also show how this can be utilized as an efficient polynomial-time approximation scheme (PTAS). Furthermore, we prove that $Ω(n \log{n})$ payoffs must be queried in order to find any $ε$-well-supported Nash equilibrium, even by randomized algorithms.
Swarm Aggregation under Fading Attractions
Venue: arXiv cs.SY 2016
Year: 2016

Gradient descent methods have been widely used for organizing multi-agent systems, in which they can provide decentralized control laws with provable convergence. Often, the control laws are designed so that two neighboring agents repel/attract each other at a short/long distance of separation. When the interactions between neighboring agents are moreover nonfading, the potential function from which they are derived is radially unbounded. Hence, the LaSalle's principle is sufficient to establish the system convergence. This paper investigates, in contrast, a more realistic scenario where interactions between neighboring agents have fading attractions. In such setting, the LaSalle type arguments may not be sufficient. To tackle the problem, we introduce a class of partitions, termed dilute partitions, of formations which cluster agents according to the inter- and intra-cluster interaction strengths. We then apply dilute partitions to trajectories of formations generated by the multi-agent system, and show that each of the trajectories remains bounded along the evolution, and converges to the set of equilibria.
Massive MIMO and Waveform Design for 5th Generation Wireless Communication Systems
Venue: arXiv cs.IT 2016
Year: 2016

This article reviews existing related work and identifies the main challenges in the key 5G area at the intersection of waveform design and large-scale multiple antenna systems, also known as Massive MIMO. The property of self-equalization is introduced for Filter Bank Multicarrier (FBMC)-based Massive MIMO, which can reduce the number of subcarriers required by the system. It is also shown that the blind channel tracking property of FBMC can be used to address pilot contamination -- one of the main limiting factors of Massive MIMO systems. Our findings shed light into and motivate for an entirely new research line towards a better understanding of waveform design with emphasis on FBMC-based Massive MIMO networks.
Mechanics-based solution verification for porous media models
Venue: arXiv cs.NA 2016
Year: 2016

This paper presents a new approach to verify accuracy of computational simulations. We develop mathematical theorems which can serve as robust a posteriori error estimation techniques to identify numerical pollution, check the performance of adaptive meshes, and verify numerical solutions. We demonstrate performance of this methodology on problems from flow thorough porous media. However, one can extend it to other models. We construct mathematical properties such that the solutions to Darcy and Darcy-Brinkman equations satisfy them. The mathematical properties include the total minimum mechanical power, minimum dissipation theorem, reciprocal relation, and maximum principle for the vorticity. All the developed theorems have firm mechanical bases and are independent of numerical methods. So, these can be utilized for solution verification of finite element, finite volume, finite difference, lattice Boltzmann methods and so forth. In particular, we show that, for a given set of boundary conditions, Darcy velocity has the minimum total mechanical power of all the kinematically admissible vector fields. We also show that a similar result holds for Darcy-Brinkman velocity. We then show for a conservative body force, the Darcy and Darcy-Brinkman velocities have the minimum total dissipation among their respective kinematically admissible vector fields. Using numerical examples, we show that the minimum dissipation and total mechanical power theorems can be utilized to identify pollution errors in numerical solutions. The solutions to Darcy and Darcy-Brinkman equations are shown to satisfy a reciprocal relation, which has the potential to identify errors in the numerical implementation of boundary conditions.
On robust width property for Lasso and Dantzig selector
Venue: arXiv cs.IT 2016
Year: 2016

Recently, Cahill and Mixon completely characterized the sensing operators in many compressed sensing instances with a robust width property. The proposed property allows uniformly stable and robust reconstruction of certain solutions from an underdetermined linear system via convex optimization. However, their theory does not cover the Lasso and Dantzig selector models, both of which are popular alternatives in the statistics community. In this letter, we show that the robust width property can be perfectly applied to these two models as well. Our results solve an open problem left by Cahill and Mixon.
Does $\ell_p$-minimization outperform $\ell_1$-minimization?
Venue: arXiv cs.IT 2016
Year: 2016

In many application areas we are faced with the following question: Can we recover a sparse vector $x_o \in \mathbb{R}^N$ from its undersampled set of noisy observations $y \in \mathbb{R}^n$, $y=A x_o+w$. The last decade has witnessed a surge of algorithms and theoretical results addressing this question. One of the most popular algorithms is the $\ell_p$-regularized least squares (LPLS) given by the following formulation: \[ \hat{x}(γ,p )\in \arg\min_x \frac{1}{2}\|y - Ax\|_2^2+γ\|x\|_p^p, \] where $p \in [0,1]$. Despite the non-convexity of these problems for $p<1$, they are still appealing because of the following folklores in compressed sensing: (i) $\hat{x}(γ,p )$ is closer to $x_o$ than $\hat{x}(γ,1)$. (ii) If we employ iterative methods that aim to converge to a local minima of LPLS, then under good initialization these algorithms converge to a solution that is closer to $x_o$ than $\hat{x}(γ,1)$. In spite of the existence of plenty of empirical results that support these folklore theorems, the theoretical progress to establish them has been very limited. This paper aims to study the above folklore theorems and establish their scope of validity. Starting with approximate message passing algorithm as a heuristic method for solving LPLS, we study the impact of initialization on the performance of AMP. Then, we employ the replica analysis to show the connection between the solution of AMP and $\hat{x}(γ, p)$ in the asymptotic settings. This enables us to compare the accuracy of $\hat{x}(γ,p)$ for $p \in [0,1]$. In particular, we will characterize the phase transition and noise sensitivity of LPLS for every $0\leq p\leq 1$ accurately. Our results in the noiseless setting confirm that LPLS exhibits the same phase transition for every $0\leq p <1$ and this phase transition is much higher than that of LASSO.
Varentropy Decreases Under the Polar Transform
Venue: arXiv cs.IT 2016
Year: 2016

We consider the evolution of variance of entropy (varentropy) in the course of a polar transform operation on binary data elements (BDEs). A BDE is a pair $(X,Y)$ consisting of a binary random variable $X$ and an arbitrary side information random variable $Y$. The varentropy of $(X,Y)$ is defined as the variance of the random variable $-\log p_{X|Y}(X|Y)$. A polar transform of order two is a certain mapping that takes two independent BDEs and produces two new BDEs that are correlated with each other. It is shown that the sum of the varentropies at the output of the polar transform is less than or equal to the sum of the varentropies at the input, with equality if and only if at least one of the inputs has zero varentropy. This result is extended to polar transforms of higher orders and it is shown that the varentropy decreases to zero asymptotically when the BDEs at the input are independent and identially distributed.
Detecting Overlapping Link Communities by Finding Local Minima of a Cost Function with a Memetic Algorithm. Part 1: Problem and Method
Venue: arXiv cs.SI 2016
Year: 2016

We propose an algorithm for detecting communities of links in networks which uses local information, is based on a new evaluation function, and allows for pervasive overlaps of communities. The complexity of the clustering task requires the application of a memetic algorithm that combines probabilistic evolutionary strategies with deterministic local searches. In Part 2 we will present results of experiments with with citation networks.
On Optimal Family of Codes for Archival DNA Storage
Venue: arXiv cs.IT 2016
Year: 2016

DNA based storage systems received attention by many researchers. This includes archival and re-writable random access DNA based storage systems. In this work, we have developed an efficient technique to encode the data into DNA sequence by using non-linear families of ternary codes. In particular, we proposes an algorithm to encode data into DNA with high information storage density and better error correction using a sub code of Golay code. Theoretically, 115 exabytes (EB) data can be stored in one gram of DNA by our method.
Adaptive Compute-and-Forward with Lattice Codes Over Algebraic Integers
Venue: arXiv cs.IT 2016
Year: 2016

We consider the compute-and-forward paradigm with limited feedback. Without feedback, compute-and-forward is typically realized with lattice codes over the ring of integers, the ring of Gaussian integers, or the ring of Eisenstein integers, which are all principal ideal domains (PID). A novel scheme called adaptive compute-and-forward is proposed to exploit the limited feedback about the channel state by working with the best ring of imaginary quadratic integers. This is enabled by generalizing the famous Construction A from PID to other rings of imaginary quadratic integers which may not form PID and by showing such the construction can produce good lattices for coding in the sense of Poltyrev and for MSE quantization. Simulation results show that by adaptively choosing the best ring among the considered ones according to the limited feedback, the proposed adaptive compute-and-forward provides a better performance than that provided by the conventional compute-and-forward scheme which works over Gaussian or Eisenstein integers solely.
Locality-aware parallel block-sparse matrix-matrix multiplication using the Chunks and Tasks programming model
Venue: arXiv cs.DC 2016
Year: 2016

We present a method for parallel block-sparse matrix-matrix multiplication on distributed memory clusters. By using a quadtree matrix representation, data locality is exploited without prior information about the matrix sparsity pattern. A distributed quadtree matrix representation is straightforward to implement due to our recent development of the Chunks and Tasks programming model [Parallel Comput. 40, 328 (2014)]. The quadtree representation combined with the Chunks and Tasks model leads to favorable weak and strong scaling of the communication cost with the number of processes, as shown both theoretically and in numerical experiments. Matrices are represented by sparse quadtrees of chunk objects. The leaves in the hierarchy are block-sparse submatrices. Sparsity is dynamically detected by the matrix library and may occur at any level in the hierarchy and/or within the submatrix leaves. In case graphics processing units (GPUs) are available, both CPUs and GPUs are used for leaf-level multiplication work, thus making use of the full computing capacity of each node. The performance is evaluated for matrices with different sparsity structures, including examples from electronic structure calculations. Compared to methods that do not exploit data locality, our locality-aware approach reduces communication significantly, achieving essentially constant communication per node in weak scaling tests.
Bar recursion in classical realisability : dependent choice and continuum hypothesis
Venue: arXiv cs.LO 2016
Year: 2016

This paper is about the bar recursion operator in the context of classical realizability. After the pioneering work of Berardi, Bezem & Coquand [1], T. Streicher has shown [10], by means of their bar recursion operator, that the realizability models of ZF, obtained from usual models of $λ$-calculus (Scott domains, coherent spaces, . . .), satisfy the axiom of dependent choice. We give a proof of this result, using the tools of classical realizability. Moreover, we show that these realizability models satisfy the well ordering of $\mathbb{R}$ and the continuum hypothesis These formulas are therefore realized by closed $λ_c$-terms. This allows to obtain programs from proofs of arithmetical formulas using all these axioms.
Lock in Feedback in Sequential Experiments
Venue: arXiv cs.LG 2016
Year: 2016

We often encounter situations in which an experimenter wants to find, by sequential experimentation, $x_{max} = \arg\max_{x} f(x)$, where $f(x)$ is a (possibly unknown) function of a well controllable variable $x$. Taking inspiration from physics and engineering, we have designed a new method to address this problem. In this paper, we first introduce the method in continuous time, and then present two algorithms for use in sequential experiments. Through a series of simulation studies, we show that the method is effective for finding maxima of unknown functions by experimentation, even when the maximum of the functions drifts or when the signal to noise ratio is low.
The Three-Terminal Interactive Lossy Source Coding Problem
Venue: arXiv cs.IT 2016
Year: 2016

The three-node multiterminal lossy source coding problem is investigated. We derive an inner bound to the general rate-distortion region of this problem which is a natural extension of the seminal work by Kaspi'85 on the interactive two-terminal source coding problem. It is shown that this (rather involved) inner bound contains several rate-distortion regions of some relevant source coding settings. In this way, besides the non-trivial extension of the interactive two terminal problem, our results can be seen as a generalization and hence unification of several previous works in the field. Specializing to particular cases we obtain novel rate-distortion regions for several lossy source coding problems. We finish by describing some of the open problems and challenges. However, the general three-node multiterminal lossy source coding problem seems to offer a formidable mathematical complexity.
A Generalization of the Borkar-Meyn Theorem for Stochastic Recursive Inclusions
Venue: arXiv cs.SY 2016
Year: 2016

In this paper the stability theorem of Borkar and Meyn is extended to include the case when the mean field is a differential inclusion. Two different sets of sufficient conditions are presented that guarantee the stability and convergence of stochastic recursive inclusions. Our work builds on the works of Benaim, Hofbauer and Sorin as well as Borkar and Meyn. As a corollary to one of the main theorems, a natural generalization of the Borkar and Meyn Theorem follows. In addition, the original theorem of Borkar and Meyn is shown to hold under slightly relaxed assumptions. Finally, as an application to one of the main theorems we discuss a solution to the approximate drift problem.
Querying for Paths in Graphs using Context-Free Path Queries
Venue: arXiv cs.DB 2016
Year: 2016

Navigational queries for graph-structured data, such as the regular path queries and the context-free path queries, are usually evaluated to a relation of node-pairs $(m, n)$ such that there is a path from $m$ to $n$ satisfying the conditions of the query. Although this relational query semantics has practical value, we believe that the relational query semantics can only provide limited insight in the structure of the graph data. To address the limits of the relational query semantics, we introduce the all-path query semantics and the single-path query semantics. Under these path-based query semantics, a query is evaluated to all paths satisfying the conditions of the query, or, respectively, to a single such path. While focusing on context-free path queries, we provide a formal framework for evaluating queries on graphs using both path-based query semantics. For the all-path query semantics, we show that the result of a query can be represented by a finite context-free grammar annotated with node-information relevant for deriving each path in the query result. For the single-path query semantics, we propose to search for a path of minimum length. We reduce the problem of finding such a path of minimum length to finding a string of minimum length in a context-free language, and for deriving such a string we propose a novel algorithm. Our initial results show that the path-based query semantics have added practical value and that query evaluation for both path-based query semantics is feasible, even when query results grow very large. For the single-path query semantics, determining strict worst-case upper bounds on the size of the query result remains the focus of future work.
Tractability and Decompositions of Global Cost Functions
Venue: arXiv cs.AI 2016
Year: 2016

Enforcing local consistencies in cost function networks is performed by applying so-called Equivalent Preserving Transformations (EPTs) to the cost functions. As EPTs transform the cost functions, they may break the property that was making local consistency enforcement tractable on a global cost function. A global cost function is called tractable projection-safe when applying an EPT to it is tractable and does not break the tractability property. In this paper, we prove that depending on the size r of the smallest scopes used for performing EPTs, the tractability of global cost functions can be preserved (r = 0) or destroyed (r > 1). When r = 1, the answer is indefinite. We show that on a large family of cost functions, EPTs can be computed via dynamic programming-based algorithms, leading to tractable projection-safety. We also show that when a global cost function can be decomposed into a Berge acyclic network of bounded arity cost functions, soft local consistencies such as soft Directed or Virtual Arc Consistency can directly emulate dynamic programming. These different approaches to decomposable cost functions are then embedded in a solver for extensive experiments that confirm the feasibility and efficiency of our proposal.
An equalised global graphical model-based approach for multi-camera object tracking
Venue: arXiv cs.CV 2016
Year: 2016

Non-overlapping multi-camera visual object tracking typically consists of two steps: single camera object tracking and inter-camera object tracking. Most of tracking methods focus on single camera object tracking, which happens in the same scene, while for real surveillance scenes, inter-camera object tracking is needed and single camera tracking methods can not work effectively. In this paper, we try to improve the overall multi-camera object tracking performance by a global graph model with an improved similarity metric. Our method treats the similarities of single camera tracking and inter-camera tracking differently and obtains the optimization in a global graph model. The results show that our method can work better even in the condition of poor single camera object tracking.
Social Welfare in One-Sided Matching Mechanisms
Venue: arXiv cs.GT 2016
Year: 2016

We study the Price of Anarchy of mechanisms for the well-known problem of one-sided matching, or house allocation, with respect to the social welfare objective. We consider both ordinal mechanisms, where agents submit preference lists over the items, and cardinal mechanisms, where agents may submit numerical values for the items being allocated. We present a general lower bound of $Ω(\sqrt{n})$ on the Price of Anarchy, which applies to all mechanisms. We show that two well-known mechanisms, Probabilistic Serial, and Random Priority, achieve a matching upper bound. We extend our lower bound to the Price of Stability of a large class of mechanisms that satisfy a common proportionality property, and show stronger bounds on the Price of Anarchy of all deterministic mechanisms.