OpenRaiser/Intern-Atlas huggingface dataset:
An Online Learning Algorithm for Neuromorphic Hardware Implementation
Venue: arXiv cs.NE 2017
Year: 2017

We propose a sign-based online learning (SOL) algorithm for a neuromorphic hardware framework called Trainable Analogue Block (TAB). The TAB framework utilises the principles of neural population coding, implying that it encodes the input stimulus using a large pool of nonlinear neurons. The SOL algorithm is a simple weight update rule that employs the sign of the hidden layer activation and the sign of the output error, which is the difference between the target output and the predicted output. The SOL algorithm is easily implementable in hardware, and can be used in any artificial neural network framework that learns weights by minimising a convex cost function. We show that the TAB framework can be trained for various regression tasks using the SOL algorithm.
Faulty Successive Cancellation Decoding of Polar Codes for the Binary Erasure Channel
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, faulty successive cancellation decoding of polar codes for the binary erasure channel is studied. To this end, a simple erasure-based fault model is introduced to represent errors in the decoder and it is shown that, under this model, polarization does not happen, meaning that fully reliable communication is not possible at any rate. Furthermore, a lower bound on the frame error rate of polar codes under faulty SC decoding is provided, which is then used, along with a well-known upper bound, in order to choose a blocklength that minimizes the erasure probability under faulty decoding. Finally, an unequal error protection scheme that can re-enable asymptotically erasure-free transmission at a small rate loss and by protecting only a constant fraction of the decoder is proposed. The same scheme is also shown to significantly improve the finite-length performance of the faulty successive cancellation decoder by protecting as little as 1.5% of the decoder.
Robust Rotation Synchronization via Low-rank and Sparse Matrix Decomposition
Venue: arXiv cs.CV 2017
Year: 2017

This paper deals with the rotation synchronization problem, which arises in global registration of 3D point-sets and in structure from motion. The problem is formulated in an unprecedented way as a "low-rank and sparse" matrix decomposition that handles both outliers and missing data. A minimization strategy, dubbed R-GoDec, is also proposed and evaluated experimentally against state-of-the-art algorithms on simulated and real data. The results show that R-GoDec is the fastest among the robust algorithms.
GWAT: The Geneva Affective Picture Database WordNet Annotation Tool
Venue: arXiv cs.HC 2017
Year: 2017

The Geneva Affective Picture Database WordNet Annotation Tool (GWAT) is a user-friendly web application for manual annotation of pictures in Geneva Affective Picture Database (GAPED) with WordNet. The annotation tool has an intuitive interface which can be efficiently used with very little technical training. A single picture may be labeled with many synsets allowing experts to describe semantics with different levels of detail. Noun, verb, adjective and adverb synsets can be keyword-searched and attached to a specific GAPED picture with their unique identification numbers. Changes are saved automatically in the tool's relational database. The attached synsets can be reviewed, changed or deleted later. Additionally, GAPED pictures may be browsed in the tool's user interface using simple commands where previously attached WordNet synsets are displayed alongside the pictures. Stored annotations can be exported from the tool's database to different data formats and used in 3rd party applications if needed. Since GAPED does not define keywords of individual pictures but only a general category of picture groups, GWAT represents a significant improvement towards development of comprehensive picture semantics. The tool was developed with open technologies WordNet API, Apache, PHP5 and MySQL. It is freely available for scientific and non-commercial use.
Enumeration Reducibility in Closure Spaces with Applications to Logic and Algebra
Venue: arXiv cs.DM 2017
Year: 2017

In many instances in first order logic or computable algebra, classical theorems show that many problems are undecidable for general structures, but become decidable if some rigidity is imposed on the structure. For example, the set of theorems in many finitely axiomatisable theories is nonrecursive, but the set of theorems for any finitely axiomatisable complete theory is recursive. Finitely presented groups might have an nonrecursive word problem, but finitely presented simple groups have a recursive word problem. In this article we introduce a topological framework based on closure spaces to show that many of these proofs can be obtained in a similar setting. We will show in particular that these statements can be generalized to cover arbitrary structures, with no finite or recursive presentation/axiomatization. This generalizes in particular work by Kuznetsov and others. Examples from first order logic and symbolic dynamics will be discussed at length.
Visual Search at Pinterest
Venue: arXiv cs.CV 2017
Year: 2017

We demonstrate that, with the availability of distributed computation platforms such as Amazon Web Services and open-source tools, it is possible for a small engineering team to build, launch and maintain a cost-effective, large-scale visual search system with widely available tools. We also demonstrate, through a comprehensive set of live experiments at Pinterest, that content recommendation powered by visual search improve user engagement. By sharing our implementation details and the experiences learned from launching a commercial visual search engines from scratch, we hope visual search are more widely incorporated into today's commercial applications.
Robust $H_\infty$ Estimation of Uncertain Linear Quantum Systems
Venue: arXiv cs.SY 2017
Year: 2017

We consider classical estimators for a class of physically realizable linear quantum systems. Optimal estimation using a complex Kalman filter for this problem has been previously explored. Here, we study robust $H_\infty$ estimation for uncertain linear quantum systems. The estimation problem is solved by converting it to a suitably scaled $H_\infty$ control problem. The solution is obtained in the form of two algebraic Riccati equations. Relevant examples involving dynamic squeezers are presented to illustrate the efficacy of our method.
Improved Utility-based Congestion Control for Delay-Constrained Communication
Venue: arXiv cs.NI 2017
Year: 2017

Due to the presence of buffers in the inner network nodes, each congestion event leads to buffer queueing and thus to an increasing end-to-end delay. In the case of delay sensitive applications, a large delay might not be acceptable and a solution to properly manage congestion events while maintaining a low end-to-end delay is required. Delay-based congestion algorithms are a viable solution as they target to limit the experienced end-to-end delay. Unfortunately, they do not perform well when sharing the bandwidth with congestion control algorithms not regulated by delay constraints (e.g., loss-based algorithms). Our target is to fill this gap, proposing a novel congestion control algorithm for delay-constrained communication over best effort packet switched networks. The proposed algorithm is able to maintain a bounded queueing delay when competing with other delay-based flows, and avoid starvation when competing with loss-based flows. We adopt the well-known price-based distributed mechanism as congestion control, but: 1) we introduce a novel non-linear mapping between the experienced delay and the price function and 2) we combine both delay and loss information into a single price term based on packet interarrival measurements. We then provide a stability analysis for our novel algorithm and we show its performance in the simulation results carried out in the NS3 framework. Simulation results demonstrate that the proposed algorithm is able to: achieve good intra-protocol fairness properties, control efficiently the end-to-end delay, and finally, protect the flow from starvation when other flows cause the queuing delay to grow excessively.
Towards an Algebra for Cascade Effects
Venue: arXiv cs.DM 2017
Year: 2017

We introduce a new class of (dynamical) systems that inherently capture cascading effects (viewed as consequential effects) and are naturally amenable to combinations. We develop an axiomatic general theory around those systems, and guide the endeavor towards an understanding of cascading failure. The theory evolves as an interplay of lattices and fixed points, and its results may be instantiated to commonly studied models of cascade effects. We characterize the systems through their fixed points, and equip them with two operators. We uncover properties of the operators, and express global systems through combinations of local systems. We enhance the theory with a notion of failure, and understand the class of shocks inducing a system to failure. We develop a notion of mu-rank to capture the energy of a system, and understand the minimal amount of effort required to fail a system, termed resilience. We deduce a dual notion of fragility and show that the combination of systems sets a limit on the amount of fragility inherited.
Coexistence Analysis between Radar and Cellular System in LoS Channel
Venue: arXiv cs.NI 2017
Year: 2017

Sharing spectrum with incumbents such as radar systems is an attractive solution for cellular operators in order to meet the ever growing bandwidth requirements and ease the spectrum crunch problem. In order to realize efficient spectrum sharing, interference mitigation techniques are required. In this letter we address techniques to mitigate MIMO radar interference at MIMO cellular base stations (BSs). We specifically look at the amount of power received at BSs when radar uses null space projection (NSP)-based interference mitigation method. NSP reduces the amount of projected power at targets that are in-close vicinity to BSs. We study this issue and show that this can be avoided if radar employs a larger transmit array. In addition, we compute the coherence time of channel between radar and BSs and show that the coherence time of channel is much larger than the pulse repetition interval of radars. Therefore, NSP-based interference mitigation techniques which depends on accurate channel state information (CSI) can be effective as the problem of CSI being outdated does not occur for most practical scenarios.
Camera Calibration from Dynamic Silhouettes Using Motion Barcodes
Venue: arXiv cs.CV 2017
Year: 2017

Computing the epipolar geometry between cameras with very different viewpoints is often problematic as matching points are hard to find. In these cases, it has been proposed to use information from dynamic objects in the scene for suggesting point and line correspondences. We propose a speed up of about two orders of magnitude, as well as an increase in robustness and accuracy, to methods computing epipolar geometry from dynamic silhouettes. This improvement is based on a new temporal signature: motion barcode for lines. Motion barcode is a binary temporal sequence for lines, indicating for each frame the existence of at least one foreground pixel on that line. The motion barcodes of two corresponding epipolar lines are very similar, so the search for corresponding epipolar lines can be limited only to lines having similar barcodes. The use of motion barcodes leads to increased speed, accuracy, and robustness in computing the epipolar geometry.
Construction $π_A$ and $π_D$ Lattices: Construction, Goodness, and Decoding Algorithms
Venue: arXiv cs.IT 2017
Year: 2017

A novel construction of lattices is proposed. This construction can be thought of as a special class of Construction A from codes over finite rings that can be represented as the Cartesian product of $L$ linear codes over $\mathbb{F}_{p_1},\ldots,\mathbb{F}_{p_L}$, respectively, and hence is referred to as Construction $π_A$. The existence of a sequence of such lattices that is good for channel coding (i.e., Poltyrev-limit achieving) under multistage decoding is shown. A new family of multilevel nested lattice codes based on Construction $π_A$ lattices is proposed and its achievable rate for the additive white Gaussian channel is analyzed. A generalization named Construction $π_D$ is also investigated which subsumes Construction A with codes over prime fields, Construction D, and Construction $π_A$ as special cases.
Adding Isolated Vertices Makes some Online Algorithms Optimal
Venue: arXiv cs.DM 2017
Year: 2017

An unexpected difference between online and offline algorithms is observed. The natural greedy algorithms are shown to be worst case online optimal for Online Independent Set and Online Vertex Cover on graphs with 'enough' isolated vertices, Freckle Graphs. For Online Dominating Set, the greedy algorithm is shown to be worst case online optimal on graphs with at least one isolated vertex. These algorithms are not online optimal in general. The online optimality results for these greedy algorithms imply optimality according to various worst case performance measures, such as the competitive ratio. It is also shown that, despite this worst case optimality, there are Freckle graphs where the greedy independent set algorithm is objectively less good than another algorithm. It is shown that it is NP-hard to determine any of the following for a given graph: the online independence number, the online vertex cover number, and the online domination number.
I/O-Efficient Similarity Join
Venue: arXiv cs.DS 2017
Year: 2017

We present an I/O-efficient algorithm for computing similarity joins based on locality-sensitive hashing (LSH). In contrast to the filtering methods commonly suggested our method has provable sub-quadratic dependency on the data size. Further, in contrast to straightforward implementations of known LSH-based algorithms on external memory, our approach is able to take significant advantage of the available internal memory: Whereas the time complexity of classical algorithms includes a factor of $N^ρ$, where $ρ$ is a parameter of the LSH used, the I/O complexity of our algorithm merely includes a factor $(N/M)^ρ$, where $N$ is the data size and $M$ is the size of internal memory. Our algorithm is randomized and outputs the correct result with high probability. It is a simple, recursive, cache-oblivious procedure, and we believe that it will be useful also in other computational settings such as parallel computation.
L infinity Isotonic Regression for Linear, Multidimensional, and Tree Orders
Venue: arXiv cs.DS 2017
Year: 2017

Algorithms are given for determining $L_\infty$ isotonic regression of weighted data. For a linear order, grid in multidimensional space, or tree, of $n$ vertices, optimal algorithms are given, taking $Θ(n)$ time. These improve upon previous algorithms by a factor of $Ω(\log n)$. For vertices at arbitrary positions in $d$-dimensional space a $Θ(n \log^{d-1} n)$ algorithm employs iterative sorting to yield the functionality of a multidimensional structure while using only $Θ(n)$ space. The algorithms utilize a new non-constructive feasibility test on a rendezvous graph, with bounded error envelopes at each vertex.
Sparse Approximation via Generating Point Sets
Venue: arXiv cs.CG 2017
Year: 2017

$ \newcommand{\kalg}{k_{\mathrm{alg}}} \newcommand{\kopt}{k_{\mathrm{opt}}} \newcommand{\algset}{T} \renewcommand{\Re}{\mathbb{R}} \newcommand{\eps}{\varepsilon} \newcommand{\pth}[2][\!]{#1\left({#2}\right)} \newcommand{\npoints}{n} \newcommand{\ballD}{\mathsf{b}} \newcommand{\dataset}{P} $ For a set $\dataset$ of $\npoints$ points in the unit ball $\ballD \subseteq \Re^d$, consider the problem of finding a small subset $\algset \subseteq \dataset$ such that its convex-hull $\eps$-approximates the convex-hull of the original set. We present an efficient algorithm to compute such a $\eps'$-approximation of size $\kalg$, where $\eps'$ is function of $\eps$, and $\kalg$ is a function of the minimum size $\kopt$ of such an $\eps$-approximation. Surprisingly, there is no dependency on the dimension $d$ in both bounds. Furthermore, every point of $\dataset$ can be $\eps$-approximated by a convex-combination of points of $\algset$ that is $O(1/\eps^2)$-sparse. Our result can be viewed as a method for sparse, convex autoencoding: approximately representing the data in a compact way using sparse combinations of a small subset $\algset$ of the original data. The new algorithm can be kernelized, and it preserves sparsity in the original input.
Differential Hybrid Games
Venue: arXiv cs.LO 2017
Year: 2017

This article introduces differential hybrid games, which combine differential games with hybrid games. In both kinds of games, two players interact with continuous dynamics. The difference is that hybrid games also provide all the features of hybrid systems and discrete games, but only deterministic differential equations. Differential games, instead, provide differential equations with continuous-time game input by both players, but not the luxury of hybrid games, such as mode switches and discrete-time or alternating adversarial interaction. This article augments differential game logic with modalities for the combined dynamics of differential hybrid games. It shows how hybrid games subsume differential games and introduces differential game invariants and differential game variants for proving properties of differential games inductively.
Unknown sparsity in compressed sensing: Denoising and inference
Venue: arXiv cs.IT 2017
Year: 2017

The theory of Compressed Sensing (CS) asserts that an unknown signal $x\in\mathbb{R}^p$ can be accurately recovered from an underdetermined set of $n$ linear measurements with $n\ll p$, provided that $x$ is sufficiently sparse. However, in applications, the degree of sparsity $\|x\|_0$ is typically unknown, and the problem of directly estimating $\|x\|_0$ has been a longstanding gap between theory and practice. A closely related issue is that $\|x\|_0$ is a highly idealized measure of sparsity, and for real signals with entries not equal to 0, the value $\|x\|_0=p$ is not a useful description of compressibility. In our previous conference paper [Lop13] that examined these problems, we considered an alternative measure of "soft" sparsity, $\|x\|_1^2/\|x\|_2^2$, and designed a procedure to estimate $\|x\|_1^2/\|x\|_2^2$ that does not rely on sparsity assumptions. The present work offers a new deconvolution-based method for estimating unknown sparsity, which has wider applicability and sharper theoretical guarantees. In particular, we introduce a family of entropy-based sparsity measures $s_q(x):=\big(\frac{\|x\|_q}{\|x\|_1}\big)^{\frac{q}{1-q}}$ parameterized by $q\in[0,\infty]$. This family interpolates between $\|x\|_0=s_0(x)$ and $\|x\|_1^2/\|x\|_2^2=s_2(x)$ as $q$ ranges over $[0,2]$. For any $q\in (0,2]\setminus\{1\}$, we propose an estimator $\hat{s}_q(x)$ whose relative error converges at the dimension-free rate of $1/\sqrt{n}$, even when $p/n\to\infty$. Our main results also describe the limiting distribution of $\hat{s}_q(x)$, as well as some connections to Basis Pursuit Denosing, the Lasso, deterministic measurement matrices, and inference problems in CS.
Setting Lower Bounds on Truthfulness
Venue: arXiv cs.GT 2017
Year: 2017

We present and discuss general techniques for proving inapproximability results for truthful mechanisms. We make use of these techniques to prove lower bounds on the approximability of several non-utilitarian multi-parameter problems. In particular, we demonstrate the strength of our techniques by exhibiting a lower bound of $2-\frac{1}{m}$ for the scheduling problem with unrelated machines (formulated as a mechanism design problem in the seminal paper of Nisan and Ronen on Algorithmic Mechanism Design). Our lower bound applies to truthful randomized mechanisms (disregarding any computational assumptions on the running time of these mechanisms). Moreover, it holds even for the weaker notion of truthfulness for randomized mechanisms -- i.e., truthfulness in expectation. This lower bound nearly matches the known $\frac{7}{4}$ (randomized) truthful upper bound for the case of two machines (a non-truthful FPTAS exists). No lower bound for truthful randomized mechanisms in multi-parameter settings was previously known. We show an application of our techniques to the workload-minimization problem in networks. We prove our lower bounds for this problem in the inter-domain routing setting presented by Feigenbaum, Papadimitriou, Sami, and Shenker. Finally, we discuss several notions of non-utilitarian "fairness" (Max-Min fairness, Min-Max fairness, and envy minimization). We show how our techniques can be used to prove lower bounds for these notions.
Quantization for uniform distributions on equilateral triangles
Venue: arXiv cs.IT 2017
Year: 2017

We approximate the uniform measure on an equilateral triangle by a measure supported on $n$ points. We find the optimal sets of points ($n$-means) and corresponding approximation (quantization) error for $n\leq4$, give numerical optimization results for $n\leq 21$, and a bound on the quantization error for $n\to\infty$. The equilateral triangle has particularly efficient quantizations due to its connection with the triangular lattice. Our methods can be applied to the uniform distributions on general sets with piecewise smooth boundaries.
Relative Suffix Trees
Venue: arXiv cs.DS 2017
Year: 2017

Suffix trees are one of the most versatile data structures in stringology, with many applications in bioinformatics. Their main drawback is their size, which can be tens of times larger than the input sequence. Much effort has been put into reducing the space usage, leading ultimately to compressed suffix trees. These compressed data structures can efficiently simulate the suffix tree, while using space proportional to a compressed representation of the sequence. In this work, we take a new approach to compressed suffix trees for repetitive sequence collections, such as collections of individual genomes. We compress the suffix trees of individual sequences relative to the suffix tree of a reference sequence. These relative data structures provide competitive time/space trade-offs, being almost as small as the smallest compressed suffix trees for repetitive collections, and competitive in time with the largest and fastest compressed suffix trees.
On the structure of (pan, even hole)-free graphs
Venue: arXiv cs.DM 2017
Year: 2017

A hole is a chordless cycle with at least four vertices. A pan is a graph which consists of a hole and a single vertex with precisely one neighbor on the hole. An even hole is a hole with an even number of vertices. We prove that a (pan, even hole)-free graph can be decomposed by clique cutsets into essentially unit circular-arc graphs. This structure theorem is the basis of our $O(nm)$-time certifying algorithm for recognizing (pan, even hole)-free graphs and for our $O(n^{2.5}+nm)$-time algorithm to optimally color them. Using this structure theorem, we show that the tree-width of a (pan, even hole)-free graph is at most 1.5 times the clique number minus 1, and thus the chromatic number is at most 1.5 times the clique number.