OpenRaiser/Intern-Atlas huggingface dataset:
An improved FPT algorithm for Independent Feedback Vertex Set
Venue: arXiv cs.DS 2020
Year: 2020

We study the Independent Feedback Vertex Set problem - a variant of the classic Feedback Vertex Set problem where, given a graph $G$ and an integer $k$, the problem is to decide whether there exists a vertex set $S\subseteq V(G)$ such that $G\setminus S$ is a forest and $S$ is an independent set of size at most $k$. We present an $O^\ast((1+φ^{2})^{k})$-time FPT algorithm for this problem, where $φ<1.619$ is the golden ratio, improving the previous fastest $O^\ast(4.1481^{k})$-time algorithm given by Agrawal et al [IPEC 2016]. The exponential factor in our time complexity bound matches the fastest deterministic FPT algorithm for the classic Feedback Vertex Set problem. On the technical side, the main novelty is a refined measure of an input instance in a branching process, that allows for a simpler and more concise description and analysis of the algorithm.
Event-based Moving Object Detection and Tracking
Venue: arXiv cs.CV 2020
Year: 2020

Event-based vision sensors, such as the Dynamic Vision Sensor (DVS), are ideally suited for real-time motion analysis. The unique properties encompassed in the readings of such sensors provide high temporal resolution, superior sensitivity to light and low latency. These properties provide the grounds to estimate motion extremely reliably in the most sophisticated scenarios but they come at a price - modern event-based vision sensors have extremely low resolution and produce a lot of noise. Moreover, the asynchronous nature of the event stream calls for novel algorithms. This paper presents a new, efficient approach to object tracking with asynchronous cameras. We present a novel event stream representation which enables us to utilize information about the dynamic (temporal) component of the event stream, and not only the spatial component, at every moment of time. This is done by approximating the 3D geometry of the event stream with a parametric model; as a result, the algorithm is capable of producing the motion-compensated event stream (effectively approximating egomotion), and without using any form of external sensors in extremely low-light and noisy conditions without any form of feature tracking or explicit optical flow computation. We demonstrate our framework on the task of independent motion detection and tracking, where we use the temporal model inconsistencies to locate differently moving objects in challenging situations of very fast motion.
Deletion in abstract Voronoi diagrams in expected linear time and related problems
Venue: arXiv cs.CG 2020
Year: 2020

Updating an abstract Voronoi diagram after deletion of one site in linear time has been a well-known open problem; similarly, for concrete Voronoi diagrams of non-point sites. In this paper, we present an expected linear-time algorithm to update an abstract Voronoi diagram after deletion of one site. We introduce the concept of a Voronoi-like diagram, a relaxed version of an abstract Voronoi construct that has a structure similar to an ordinary Voronoi diagram, without, however, being one. We formalize the concept, and prove that it is robust under insertion, therefore, enabling its use in incremental constructions. The time-complexity analysis of the resulting simple randomized incremental construction is non-standard, and interesting in its own right, because the intermediate Voronoi-like structures are order-dependent. We further extend the approach to compute the following structures in expected linear time: the order-(k+1) subdivision within an order-k Voronoi region, and the farthest abstract Voronoi diagram after the order of its regions at infinity is known.
On the stability of persistent entropy and new summary functions for TDA
Venue: arXiv cs.IT 2020
Year: 2020

Persistent homology and persistent entropy have recently become useful tools for patter recognition. In this paper, we find requirements under which persistent entropy is stable to small perturbations in the input data and scale invariant. In addition, we describe two new stable summary functions combining persistent entropy and the Betti curve. Finally, we use the previously defined summary functions in a material classification task to show their usefulness in machine learning and pattern recognition.
Contextual Salience for Fast and Accurate Sentence Vectors
Venue: arXiv cs.CL 2020
Year: 2020

Unsupervised vector representations of sentences or documents are a major building block for many language tasks such as sentiment classification. However, current methods are uninterpretable and slow or require large training datasets. Recent word vector-based proposals implicitly assume that distances in a word embedding space are equally important, regardless of context. We introduce contextual salience (CoSal), a measure of word importance that uses the distribution of context vectors to normalize distances and weights. CoSal relies on the insight that unusual word vectors disproportionately affect phrase vectors. A bag-of-words model with CoSal-based weights produces accurate unsupervised sentence or document representations for classification, requiring little computation to evaluate and only a single covariance calculation to ``train." CoSal supports small contexts, out-of context words and outperforms SkipThought on most benchmarks, beats tf-idf on all benchmarks, and is competitive with the unsupervised state-of-the-art.
On the Importance of Stereo for Accurate Depth Estimation: An Efficient Semi-Supervised Deep Neural Network Approach
Venue: arXiv cs.CV 2020
Year: 2020

We revisit the problem of visual depth estimation in the context of autonomous vehicles. Despite the progress on monocular depth estimation in recent years, we show that the gap between monocular and stereo depth accuracy remains large$-$a particularly relevant result due to the prevalent reliance upon monocular cameras by vehicles that are expected to be self-driving. We argue that the challenges of removing this gap are significant, owing to fundamental limitations of monocular vision. As a result, we focus our efforts on depth estimation by stereo. We propose a novel semi-supervised learning approach to training a deep stereo neural network, along with a novel architecture containing a machine-learned argmax layer and a custom runtime (that will be shared publicly) that enables a smaller version of our stereo DNN to run on an embedded GPU. Competitive results are shown on the KITTI 2015 stereo dataset. We also evaluate the recent progress of stereo algorithms by measuring the impact upon accuracy of various design criteria.
Tight Revenue Gaps among Simple Mechanisms
Venue: arXiv cs.GT 2020
Year: 2020

We consider a fundamental problem in microeconomics: selling a single item to a number of potential buyers, whose values are drawn from known independent and regular (not necessarily identical) distributions. There are four widely-used and widely-studied mechanisms in the literature: {\sf Myerson Auction}~({\sf OPT}), {\sf Sequential Posted-Pricing}~({\sf SPM}), {\sf Second-Price Auction with Anonymous Reserve}~({\sf AR}), and {\sf Anonymous Pricing}~({\sf AP}). {\sf OPT} is revenue-optimal but complicated, which also experiences several issues in practice such as fairness; {\sf AP} is the simplest mechanism, but also generates the lowest revenue among these four mechanisms; {\sf SPM} and {\sf AR} are of intermediate complexity and revenue. We explore revenue gaps among these mechanisms, each of which is defined as the largest ratio between revenues from a pair of mechanisms. We establish two tight bounds and one improved bound: 1. {\sf SPM} vs.\ {\sf AP}: this ratio studies the power of discrimination in pricing schemes. We obtain the tight ratio of $\mathcal{C^*} \approx 2.62$, closing the gap between $\big[\frac{e}{e - 1}, e\big]$ left before. 2. {\sf AR} vs.\ {\sf AP}: this ratio measures the relative power of auction scheme vs.\ pricing scheme, when no discrimination is allowed. We attain the tight ratio of $\frac{π^2}{6} \approx 1.64$, closing the previously known bounds $\big[\frac{e}{e - 1}, e\big]$. 3. {\sf OPT} vs.\ {\sf AR}: this ratio quantifies the power of discrimination in auction schemes, and is previously known to be somewhere between $\big[2, e\big]$. The lower-bound of $2$ was conjectured to be tight by Hartline and Roughgarden (2009) and Alaei et al.\ (2015). We acquire a better lower-bound of $2.15$, and thus disprove this conjecture.
Universal and Succinct Source Coding of Deep Neural Networks
Venue: arXiv cs.IT 2020
Year: 2020

Deep neural networks have shown incredible performance for inference tasks in a variety of domains. Unfortunately, most current deep networks are enormous cloud-based structures that require significant storage space, which limits scaling of deep learning as a service (DLaaS) and use for on-device intelligence. This paper is concerned with finding universal lossless compressed representations of deep feedforward networks with synaptic weights drawn from discrete sets, and directly performing inference without full decompression. The basic insight that allows less rate than naive approaches is recognizing that the bipartite graph layers of feedforward networks have a kind of permutation invariance to the labeling of nodes, in terms of inferential operation. We provide efficient algorithms to dissipate this irrelevant uncertainty and then use arithmetic coding to nearly achieve the entropy bound in a universal manner. We also provide experimental results of our approach on several standard datasets.
Higher Order and Long-Range Synchronization Effects for Classification and Computing in Oscillator-Based Spiking Neural Networks
Venue: arXiv cs.NE 2020
Year: 2020

In the circuit of two thermally coupled VO2 oscillators, we studied a higher order synchronization effect, which can be used in object classification techniques to increase the number of possible synchronous states of the oscillator system. We developed the phase-locking estimation method to determine the values of subharmonic ratio and synchronization effectiveness. In our experiment, the number of possible synchronous states of the oscillator system was twelve, and subharmonic ratio distributions were shaped as Arnold's tongues. In the model, the number of states may reach the maximum value of 150 at certain levels of coupling strength and noise. The long-range synchronization effect in a one-dimensional chain of oscillators occurs even at low values of synchronization effectiveness for intermediate links. We demonstrate a technique for storing and recognizing vector images, which can used for reservoir computing. In addition, we present the implementation of analog operation of multiplication, the synchronization based logic for binary computations, and the possibility to develop the interface between spike neural network and a computer. Based on the universal physical effects, the high order synchronization can be applied to any spiking oscillators with any coupling type, enhancing the practical value of the presented results to expand spike neural network capabilities.
A Neural Markovian Multiresolution Image Labeling Algorithm
Venue: arXiv cs.CV 2020
Year: 2020

This paper describes the results of formally evaluating the MCV (Markov concurrent vision) image labeling algorithm which is a (semi-) hierarchical algorithm commencing with a partition made up of single pixel regions and merging regions or subsets of regions using a Markov random field (MRF) image model. It is an example of a general approach to computer vision called concurrent vision in which the operations of image segmentation and image classification are carried out concurrently. While many image labeling algorithms output a single partition, or segmentation, the MCV algorithm outputs a sequence of partitions and this more elaborate structure may provide information that is valuable for higher level vision systems. With certain types of MRF the component of the system for image evaluation can be implemented as a hardwired feed forward neural network. While being applicable to images (i.e. 2D signals), the algorithm is equally applicable to 1D signals (e.g. speech) or 3D signals (e.g. video sequences) (though its performance in such domains remains to be tested). The algorithm is assessed using subjective and objective criteria with very good results.
Connectivity in Random Annulus Graphs and the Geometric Block Model
Venue: arXiv cs.DM 2020
Year: 2020

We provide new connectivity results for {\em vertex-random graphs} or {\em random annulus graphs} which are significant generalizations of random geometric graphs. Random geometric graphs (RGG) are one of the most basic models of random graphs for spatial networks proposed by Gilbert in 1961, shortly after the introduction of the Erdős-R\'{en}yi random graphs. They resemble social networks in many ways (e.g. by spontaneously creating cluster of nodes with high modularity). The connectivity properties of RGG have been studied since its introduction, and analyzing them has been significantly harder than their Erdős-R\'{en}yi counterparts due to correlated edge formation. Our next contribution is in using the connectivity of random annulus graphs to provide necessary and sufficient conditions for efficient recovery of communities for {\em the geometric block model} (GBM). The GBM is a probabilistic model for community detection defined over an RGG in a similar spirit as the popular {\em stochastic block model}, which is defined over an Erdős-R\'{en}yi random graph. The geometric block model inherits the transitivity properties of RGGs and thus models communities better than a stochastic block model. However, analyzing them requires fresh perspectives as all prior tools fail due to correlation in edge formation. We provide a simple and efficient algorithm that can recover communities in GBM exactly with high probability in the regime of connectivity.
Multi-Sound-Source Localization Using Machine Learning for Small Autonomous Unmanned Vehicles with a Self-Rotating Bi-Microphone Array
Venue: arXiv cs.SD 2020
Year: 2020

Abstract While vision-based localization techniques have been widely studied for small autonomous unmanned vehicles (SAUVs), sound-source localization capabilities have not been fully enabled for SAUVs. This paper presents two novel approaches for SAUVs to perform three-dimensional (3D) multi-sound-sources localization (MSSL) using only the inter-channel time difference (ICTD) signal generated by a self-rotating bi-microphone array. The proposed two approaches are based on two machine learning techniques viz., Density-Based Spatial Clustering of Applications with Noise (DBSCAN) and Random Sample Consensus (RANSAC) algorithms, respectively, whose performances are tested and compared in both simulations and experiments. The results show that both approaches are capable of correctly identifying the number of sound sources along with their 3D orientations in a reverberant environment.
Efficient Solvers for Sparse Subspace Clustering
Venue: arXiv cs.CV 2020
Year: 2020

Sparse subspace clustering (SSC) clusters $n$ points that lie near a union of low-dimensional subspaces. The SSC model expresses each point as a linear or affine combination of the other points, using either $\ell_1$ or $\ell_0$ regularization. Using $\ell_1$ regularization results in a convex problem but requires $O(n^2)$ storage, and is typically solved by the alternating direction method of multipliers which takes $O(n^3)$ flops. The $\ell_0$ model is non-convex but only needs memory linear in $n$, and is solved via orthogonal matching pursuit and cannot handle the case of affine subspaces. This paper shows that a proximal gradient framework can solve SSC, covering both $\ell_1$ and $\ell_0$ models, and both linear and affine constraints. For both $\ell_1$ and $\ell_0$, algorithms to compute the proximity operator in the presence of affine constraints have not been presented in the SSC literature, so we derive an exact and efficient algorithm that solves the $\ell_1$ case with just $O(n^2)$ flops. In the $\ell_0$ case, our algorithm retains the low-memory overhead, and is the first algorithm to solve the SSC-$\ell_0$ model with affine constraints. Experiments show our algorithms do not rely on sensitive regularization parameters, and they are less sensitive to sparsity misspecification and high noise.
A time- and space-optimal algorithm for the many-visits TSP
Venue: arXiv cs.DS 2020
Year: 2020

The many-visits traveling salesperson problem (MV-TSP) asks for an optimal tour of $n$ cities that visits each city $c$ a prescribed number $k_c$ of times. Travel costs may be asymmetric, and visiting a city twice in a row may incur a non-zero cost. The MV-TSP problem finds applications in scheduling, geometric approximation, and Hamiltonicity of certain graph families. The fastest known algorithm for MV-TSP is due to Cosmadakis and Papadimitriou (SICOMP, 1984). It runs in time $n^{O(n)} + O(n^3 \log \sum_c k_c )$ and requires $n^{Θ(n)}$ space. An interesting feature of the Cosmadakis-Papadimitriou algorithm is its \emph{logarithmic} dependence on the total length $\sum_c k_c$ of the tour, allowing the algorithm to handle instances with very long tours. The \emph{superexponential} dependence on the number of cities in both the time and space complexity, however, renders the algorithm impractical for all but the narrowest range of this parameter. In this paper we improve upon the Cosmadakis-Papadimitriou algorithm, giving an MV-TSP algorithm that runs in time $2^{O(n)}$, i.e.\ \emph{single-exponential} in the number of cities, using \emph{polynomial} space. Our algorithm is deterministic, and arguably both simpler and easier to analyse than the original approach of Cosmadakis and Papadimitriou. It involves an optimization over directed spanning trees and a recursive, centroid-based decomposition of trees.
Effect of Spatial and Temporal Traffic Statistics on the Performance of Wireless Networks
Venue: arXiv cs.NI 2020
Year: 2020

The traffic in wireless networks has become diverse and fluctuating both spatially and temporally due to the emergence of new wireless applications and the complexity of scenarios. The purpose of this paper is to quantitatively analyze the impact of the wireless traffic, which fluctuates both spatially and temporally, on the performance of the wireless networks. Specially, we propose to combine the tools from stochastic geometry and queueing theory to model the spatial and temporal fluctuation of traffic, which to our best knowledge has seldom been evaluated analytically. We derive the spatial and temporal statistics, the total arrival rate, the stability of queues and the delay of users by considering two different spatial properties of traffic, i.e., the uniformly and non-uniformly distributed cases. The numerical results indicate that although the fluctuation of traffic (reflected by the variance of total arrival rate) when the users are clustered is much fiercer than that when the users are uniformly distributed, the unstable probability is smaller. Our work provides a useful reference for the design of wireless networks when the complex spatio-temporal fluctuation of the traffic is considered.
On the cluster admission problem for cloud computing
Venue: arXiv cs.DC 2020
Year: 2020

Cloud computing providers face the problem of matching heterogeneous customer workloads to resources that will serve them. This is particularly challenging if customers, who are already running a job on a cluster, scale their resource usage up and down over time. The provider therefore has to continuously decide whether she can add additional workloads to a given cluster or if doing so would impact existing workloads' ability to scale. Currently, this is often done using simple threshold policies to reserve large parts of each cluster, which leads to low efficiency (i.e., low average utilization of the cluster). We propose more sophisticated policies for controlling admission to a cluster and demonstrate that they significantly increase cluster utilization. We first introduce the cluster admission problem and formalize it as a constrained Partially Observable Markov Decision Process (POMDP). As it is infeasible to solve the POMDP optimally, we then systematically design admission policies that estimate moments of each workload's distribution of future resource usage. Via extensive simulations grounded in a trace from Microsoft Azure, we show that our admission policies lead to a substantial improvement over the simple threshold policy. We then show that substantial further gains are possible if high-quality information is available about arriving workloads. Based on this, we propose an information elicitation approach to incentivize users to provide this information and simulate its effects.
Learning in Games with Cumulative Prospect Theoretic Preferences
Venue: arXiv cs.GT 2020
Year: 2020

We consider repeated games where the players behave according to cumulative prospect theory (CPT). We show that, when the players have calibrated strategies and behave according to CPT, the natural analog of the notion of correlated equilibrium in the CPT case, as defined by Keskin, is not enough to capture all subsequential limits of the empirical distribution of action play. We define the notion of a mediated CPT correlated equilibrium via an extension of the stage game to a so-called mediated game. We then show, along the lines of the result of Foster and Vohra about convergence to the set of correlated equilibria when the players behave according to expected utility theory that, in the CPT case, under calibrated learning the empirical distribution of action play converges to the set of all mediated CPT correlated equilibria. We also show that, in general, the set of CPT correlated equilibria is not approachable in the Blackwell approachability sense. We observe that a mediated game is a specific type of a game with communication, as introduced by Myerson, and as a consequence we get that the revelation principle does not hold under CPT.
Nearly Linear Time Deterministic Algorithms for Submodular Maximization Under Knapsack Constraint and Beyond
Venue: arXiv cs.DS 2020
Year: 2020

In this work, we study the classic submodular maximization problem under knapsack constraints and beyond. We first present an $(7/16-\varepsilon)$-approximate algorithm for single knapsack constraint, which requires $O(n\cdot\max\{\varepsilon^{-1},\log\log n\})$ queries, and two passes in the streaming setting. This provides improvements in approximation ratio, query complexity and number of passes on the stream. We next show that there exists an $(1/2-\varepsilon)$-approximate deterministic algorithm for constant number of binary packing constraints, which achieves a query complexity of $O_{\varepsilon}(n\cdot\log \log n)$. One salient feature of our deterministic algorithm is, both its approximation ratio and time complexity are independent of the number of constraints. Lastly we present nearly linear time algorithms for the intersection of $p$-system and $d$ knapsack constraint, we achieve approximation ratio of $(1/(p+\frac{7}{4}d+1)-\varepsilon)$ for monotone objective and $(p/(p+1)(2p+\frac{7}{4}d+1)-\varepsilon)$ for non-monotone objective.