OpenRaiser/Intern-Atlas huggingface dataset:
On fixed-parameter tractability of the mixed domination problem for graphs with bounded tree-width
Venue: arXiv cs.DM 2018
Year: 2018

A mixed dominating set for a graph $G = (V,E)$ is a set $S\subseteq V \cup E$ such that every element $x \in (V \cup E) \backslash S$ is either adjacent or incident to an element of $S$. The mixed domination number of a graph $G$, denoted by $γ_m(G)$, is the minimum cardinality of mixed dominating sets of $G$. Any mixed dominating set with the cardinality of $γ_m(G)$ is called a minimum mixed dominating set. The mixed domination set (MDS) problem is to find a minimum mixed dominating set for a graph $G$ and is known to be an NP-complete problem. In this paper, we present a novel approach to find all of the mixed dominating sets, called the AMDS problem, of a graph with bounded tree-width $tw$. Our new technique of assigning power values to edges and vertices, and combining with dynamic programming, leads to a fixed-parameter algorithm of time $O(3^{tw^{2}}\times tw^2 \times |V|)$. This shows that MDS is fixed-parameter tractable with respect to tree-width. In addition, we theoretically improve the proposed algorithm to solve the MDS problem in $O(6^{tw} \times |V|)$ time.
Decentralized RLS with Data-Adaptive Censoring for Regressions over Large-Scale Networks
Venue: arXiv cs.SY 2018
Year: 2018

The deluge of networked data motivates the development of algorithms for computation- and communication-efficient information processing. In this context, three data-adaptive censoring strategies are introduced to considerably reduce the computation and communication overhead of decentralized recursive least-squares (D-RLS) solvers. The first relies on alternating minimization and the stochastic Newton iteration to minimize a network-wide cost, which discards observations with small innovations. In the resultant algorithm, each node performs local data-adaptive censoring to reduce computations, while exchanging its local estimate with neighbors so as to consent on a network-wide solution. The communication cost is further reduced by the second strategy, which prevents a node from transmitting its local estimate to neighbors when the innovation it induces to incoming data is minimal. In the third strategy, not only transmitting, but also receiving estimates from neighbors is prohibited when data-adaptive censoring is in effect. For all strategies, a simple criterion is provided for selecting the threshold of innovation to reach a prescribed average data reduction. The novel censoring-based (C)D-RLS algorithms are proved convergent to the optimal argument in the mean-square deviation sense. Numerical experiments validate the effectiveness of the proposed algorithms in reducing computation and communication overhead.
On the Broadcast Independence Number of Caterpillars
Venue: arXiv cs.DM 2018
Year: 2018

Let $G$ be a simple undirected graph.A broadcast on $G$ isa function $f : V(G)\rightarrow\mathbb{N}$ such that $f(v)\le e\_G(v)$ holds for every vertex $v$ of $G$, where $e\_G(v)$ denotes the eccentricity of $v$ in $G$, that is, the maximum distance from $v$ to any other vertex of $G$.The cost of $f$ is the value ${\rm cost}(f)=\sum\_{v\in V(G)}f(v)$.A broadcast $f$ on $G$ is independent if for every two distinct vertices $u$ and $v$ in $G$, $d\_G(u,v)>\max\{f(u),f(v)\}$,where $d\_G(u,v)$ denotes the distance between $u$ and $v$ in $G$.The broadcast independence number of $G$ is then defined as the maximum cost of an independent broadcast on $G$. In this paper, we study independent broadcasts of caterpillars and give an explicit formula for the broadcast independence number of caterpillars having no pair of adjacent vertices with degree 2.
Extracting Sub-Exposure Images from a Single Capture Through Fourier-based Optical Modulation
Venue: arXiv cs.CV 2018
Year: 2018

Through pixel-wise optical coding of images during exposure time, it is possible to extract sub-exposure images from a single capture. Such a capability can be used for different purposes, including high-speed imaging, high-dynamic-range imaging and compressed sensing. In this paper, we demonstrate a sub-exposure image extraction method, where the exposure coding pattern is inspired from frequency division multiplexing idea of communication systems. The coding masks modulate sub-exposure images in such a way that they are placed in non-overlapping regions in Fourier domain. The sub-exposure image extraction process involves digital filtering of the captured signal with proper band-pass filters. The prototype imaging system incorporates a Liquid Crystal over Silicon (LCoS) based spatial light modulator synchronized with a camera for pixel-wise exposure coding.
Simulating SIR processes on networks using weighted shortest paths
Venue: arXiv cs.SI 2018
Year: 2018

We present a framework to simulate SIR processes on networks using weighted shortest paths. Our framework maps the SIR dynamics to weights assigned to the edges of the network, which can be done for Markovian and non-Markovian processes alike. The weights represent the propagation time between the adjacent nodes for a particular realization. We simulate the dynamics by constructing an ensemble of such realizations, which can be done by using a Markov Chain Monte Carlo method or by direct sampling. The former provides a runtime advantage when realizations from all possible sources are computed as the weighted shortest paths can be re-calculated more efficiently. We apply our framework to three empirical networks and analyze the expected propagation time between all pairs of nodes. Furthermore, we have employed our framework to perform efficient source detection and to improve strategies for time-critical vaccination.
Differentiable monotonicity-preserving schemes for discontinuous Galerkin methods on arbitrary meshes
Venue: arXiv cs.NA 2018
Year: 2018

This work is devoted to the design of interior penalty discontinuous Galerkin (dG) schemes that preserve maximum principles at the discrete level for the steady transport and convection-diffusion problems and the respective transient problems with implicit time integration. Monotonic schemes that combine explicit time stepping with dG space discretization are very common, but the design of such schemes for implicit time stepping is rare, and it had only been attained so far for 1D problems. The proposed scheme is based on an artificial diffusion that linearly depends on a shock detector that identifies the troublesome areas. In order to define the new shock detector, we have introduced the concept of discrete local extrema. The diffusion operator is a graph-Laplacian, instead of the more common finite element discretization of the Laplacian operator, which is essential to keep monotonicity on general meshes and in multi-dimension. The resulting nonlinear stabilization is non-smooth and nonlinear solvers can fail to converge. As a result, we propose a smoothed (twice differentiable) version of the nonlinear stabilization, which allows us to use Newton with line search nonlinear solvers and dramatically improve nonlinear convergence. A theoretical numerical analysis of the proposed schemes show that they satisfy the desired monotonicity properties. Further, the resulting operator is Lipschitz continuous and there exists at least one solution of the discrete problem, even in the non-smooth version. We provide a set of numerical results to support our findings.
Randomized algorithms for distributed computation of principal component analysis and singular value decomposition
Venue: arXiv cs.DC 2018
Year: 2018

Randomized algorithms provide solutions to two ubiquitous problems: (1) the distributed calculation of a principal component analysis or singular value decomposition of a highly rectangular matrix, and (2) the distributed calculation of a low-rank approximation (in the form of a singular value decomposition) to an arbitrary matrix. Carefully honed algorithms yield results that are uniformly superior to those of the stock, deterministic implementations in Spark (the popular platform for distributed computation); in particular, whereas the stock software will without warning return left singular vectors that are far from numerically orthonormal, a significantly burnished randomized implementation generates left singular vectors that are numerically orthonormal to nearly the machine precision.
Supervisory Control of Discrete-event Systems under Attacks
Venue: arXiv cs.SY 2018
Year: 2018

We consider a multi-adversary version of the supervisory control problem for discrete-event systems, in which an adversary corrupts the observations available to the supervisor. The supervisor's goal is to enforce a specific language in spite of the opponent's actions and without knowing which adversary it is playing against. This problem is motivated by applications to computer security in which a cyber defense system must make decisions based on reports from sensors that may have been tampered with by an attacker. We start by showing that the problem has a solution if and only if the desired language is controllable (in the Discrete event system classical sense) and observable in a (novel) sense that takes the adversaries into account. For the particular case of attacks that insert symbols into or remove symbols from the sequence of sensor outputs, we show that testing the existence of a supervisor and building the supervisor can be done using tools developed for the classical DES supervisory control problem, by considering a family of automata with modified output maps, but without expanding the size of the state space and without incurring on exponential complexity on the number of attacks considered., we construct observers that are robust against attacks and lead to an automaton representation of the supervisor. We also develop a test for observability under such replacement-removal attacks by using the so-called product automata.
On the Throughput of Channels that Wear Out
Venue: arXiv cs.IT 2018
Year: 2018

This work investigates the fundamental limits of communication over a noisy discrete memoryless channel that wears out, in the sense of signal-dependent catastrophic failure. In particular, we consider a channel that starts as a memoryless binary-input channel and when the number of transmitted ones causes a sufficient amount of damage, the channel ceases to convey signals. Constant composition codes are adopted to obtain an achievability bound and the left-concave right-convex inequality is then refined to obtain a converse bound on the log-volume throughput for channels that wear out. Since infinite blocklength codes will always wear out the channel for any finite threshold of failure and therefore cannot convey information at positive rates, we analyze the performance of finite blocklength codes to determine the maximum expected transmission volume at a given level of average error probability. We show that this maximization problem has a recursive form and can be solved by dynamic programming. Numerical results demonstrate that a sequence of block codes is preferred to a single block code for streaming sources.
Crime Topic Modeling
Venue: arXiv cs.CL 2018
Year: 2018

The classification of crime into discrete categories entails a massive loss of information. Crimes emerge out of a complex mix of behaviors and situations, yet most of these details cannot be captured by singular crime type labels. This information loss impacts our ability to not only understand the causes of crime, but also how to develop optimal crime prevention strategies. We apply machine learning methods to short narrative text descriptions accompanying crime records with the goal of discovering ecologically more meaningful latent crime classes. We term these latent classes "crime topics" in reference to text-based topic modeling methods that produce them. We use topic distributions to measure clustering among formally recognized crime types. Crime topics replicate broad distinctions between violent and property crime, but also reveal nuances linked to target characteristics, situational conditions and the tools and methods of attack. Formal crime types are not discrete in topic space. Rather, crime types are distributed across a range of crime topics. Similarly, individual crime topics are distributed across a range of formal crime types. Key ecological groups include identity theft, shoplifting, burglary and theft, car crimes and vandalism, criminal threats and confidence crimes, and violent crimes. Though not a replacement for formal legal crime classifications, crime topics provide a unique window into the heterogeneous causal processes underlying crime.
Dense Small Cell Networks: From Noise-Limited to Dense Interference-Limited
Venue: arXiv cs.NI 2018
Year: 2018

Considering both non-line-of-sight (NLoS) and line-of-sight (LoS) transmissions, the transitional behaviors from noise-limited regime to dense interference-limited regime have been investigated for the fifth generation (5G) small cell networks (SCNs). Besides, we identify four performance regimes based on base station (BS) density, i.e., (i) the noise-limited regime, (ii) the signal-dominated regime, (iii) the interference-dominated regime, and (iv) the interference-limited regime. To characterize the performance regime, we propose a unified framework analyzing the future 5G wireless networks over generalized shadowing/fading channels, in which the user association schemes based on the strongest instantaneous received power (SIRP) and the strongest average received power (SARP) can be studied, while NLoS/LoS transmissions and multi-slop path loss model are considered. Simulation results indicate that different factors, i.e., noise, desired signal, and interference, successively and separately dominate the network performance with the increase of BS density. Hence, our results shed new light on the design and management of SCNs in urban and rural areas with different BS deployment densities.
Stochastic Optimal Control for Modeling Reaching Movements in the Presence of Obstacles: Theory and Simulation
Venue: arXiv cs.RO 2018
Year: 2018

In many human-in-the-loop robotic applications such as robot-assisted surgery and remote teleoperation, predicting the intended motion of the human operator may be useful for successful implementation of shared control, guidance virtual fixtures, and predictive control. Developing computational models of human movements is a critical foundation for such motion prediction frameworks. With this motivation, we present a computational framework for modeling reaching movements in the presence of obstacles. We propose a stochastic optimal control framework that consists of probabilistic collision avoidance constraints and a cost function that trades-off between effort and end-state variance in the presence of a signal-dependent noise. First, we present a series of reformulations to convert the original non-linear and non-convex optimal control into a parametric quadratic programming problem. We show that the parameters can be tuned to model various collision avoidance strategies, thereby capturing the quintessential variability associated with human motion. Then, we present a simulation study that demonstrates the complex interaction between avoidance strategies, control cost, and the probability of collision avoidance. The proposed framework can benefit a variety of applications that require teleoperation in cluttered spaces, including robot-assisted surgery. In addition, it can also be viewed as a new optimizer which produces smooth and probabilistically-safe trajectories under signal dependent noise.
MonoCap: Monocular Human Motion Capture using a CNN Coupled with a Geometric Prior
Venue: arXiv cs.CV 2018
Year: 2018

Recovering 3D full-body human pose is a challenging problem with many applications. It has been successfully addressed by motion capture systems with body worn markers and multiple cameras. In this paper, we address the more challenging case of not only using a single camera but also not leveraging markers: going directly from 2D appearance to 3D geometry. Deep learning approaches have shown remarkable abilities to discriminatively learn 2D appearance features. The missing piece is how to integrate 2D, 3D and temporal information to recover 3D geometry and account for the uncertainties arising from the discriminative model. We introduce a novel approach that treats 2D joint locations as latent variables whose uncertainty distributions are given by a deep fully convolutional neural network. The unknown 3D poses are modeled by a sparse representation and the 3D parameter estimates are realized via an Expectation-Maximization algorithm, where it is shown that the 2D joint location uncertainties can be conveniently marginalized out during inference. Extensive evaluation on benchmark datasets shows that the proposed approach achieves greater accuracy over state-of-the-art baselines. Notably, the proposed approach does not require synchronized 2D-3D data for training and is applicable to "in-the-wild" images, which is demonstrated with the MPII dataset.
A Linear Algebra Formulation for Boolean Satisfiability Testing
Venue: arXiv cs.CC 2018
Year: 2018

In the article \The State of SAT", the authors asked whether a procedure dramatically different from DPLL can be found for handling unsatisfiable instances. This study proposes a new linear programming approach to address this issue efficiently. Our experiments showed that the new method works for many unsatisfiable instances. However, we must concede that this method should be incomplete; otherwise, it will imply P=co-NP.
Strong Functional Representation Lemma and Applications to Coding Theorems
Venue: arXiv cs.IT 2018
Year: 2018

This paper shows that for any random variables $X$ and $Y$, it is possible to represent $Y$ as a function of $(X,Z)$ such that $Z$ is independent of $X$ and $I(X;Z|Y)\le\log(I(X;Y)+1)+4$ bits. We use this strong functional representation lemma (SFRL) to establish a bound on the rate needed for one-shot exact channel simulation for general (discrete or continuous) random variables, strengthening the results by Harsha et al. and Braverman and Garg, and to establish new and simple achievability results for one-shot variable-length lossy source coding, multiple description coding and Gray-Wyner system. We also show that the SFRL can be used to reduce the channel with state noncausally known at the encoder to a point-to-point channel, which provides a simple achievability proof of the Gelfand-Pinsker theorem.
Looking Beyond Appearances: Synthetic Training Data for Deep CNNs in Re-identification
Venue: arXiv cs.CV 2018
Year: 2018

Re-identification is generally carried out by encoding the appearance of a subject in terms of outfit, suggesting scenarios where people do not change their attire. In this paper we overcome this restriction, by proposing a framework based on a deep convolutional neural network, SOMAnet, that additionally models other discriminative aspects, namely, structural attributes of the human figure (e.g. height, obesity, gender). Our method is unique in many respects. First, SOMAnet is based on the Inception architecture, departing from the usual siamese framework. This spares expensive data preparation (pairing images across cameras) and allows the understanding of what the network learned. Second, and most notably, the training data consists of a synthetic 100K instance dataset, SOMAset, created by photorealistic human body generation software. Synthetic data represents a good compromise between realistic imagery, usually not required in re-identification since surveillance cameras capture low-resolution silhouettes, and complete control of the samples, which is useful in order to customize the data w.r.t. the surveillance scenario at-hand, e.g. ethnicity. SOMAnet, trained on SOMAset and fine-tuned on recent re-identification benchmarks, outperforms all competitors, matching subjects even with different apparel. The combination of synthetic data with Inception architectures opens up new research avenues in re-identification.
Cooperative Multi-Sender Index Coding
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we propose a new coding scheme and establish new bounds on the capacity region for the multi-sender unicast index-coding problem. We revisit existing partitioned Distributed Composite Coding (DCC) proposed by Sadeghi et al. and identify its limitations in the implementation of multi-sender composite coding and in the strategy of sender partitioning. We then propose two new coding components to overcome these limitations and develop a multi-sender Cooperative Composite Coding (CCC). We show that CCC can strictly improve upon partitioned DCC, and is the key to achieve optimality for a number of index-coding instances. The usefulness of CCC and its special cases is illuminated via non-trivial examples, and the capacity region is established for each example. Comparisons between CCC and other non-cooperative schemes in recent works are also provided to further demonstrate the advantage of CCC.
Converse Theorems for Safety and Barrier Certificates
Venue: arXiv cs.SY 2018
Year: 2018

An important tool for proving safety of dynamical systems is the notion of a barrier certificate. In this paper we prove that every robustly safe ordinary differential equation has a barrier certificate. Moreover, we show a construction of such a barrier certificate based on a set of states that is reachable in finite time.
On double-resolution imaging and discrete tomography
Venue: arXiv cs.DS 2018
Year: 2018

Super-resolution imaging aims at improving the resolution of an image by enhancing it with other images or data that might have been acquired using different imaging techniques or modalities. In this paper we consider the task of doubling, in each dimension, the resolution of grayscale images of binary objects by fusion with double-resolution tomographic data that have been acquired from two viewing angles. We show that this task is polynomial-time solvable if the gray levels have been reliably determined. The problem becomes $\mathbb{N}\mathbb{P}$-hard if the gray levels of some pixels come with an error of $\pm1$ or larger. The $\mathbb{N}\mathbb{P}$-hardness persists for any larger resolution enhancement factor. This means that noise does not only affect the quality of a reconstructed image but, less expectedly, also the algorithmic tractability of the inverse problem itself.
Adversarial Variational Bayes: Unifying Variational Autoencoders and Generative Adversarial Networks
Venue: arXiv cs.LG 2018
Year: 2018

Variational Autoencoders (VAEs) are expressive latent variable models that can be used to learn complex probability distributions from training data. However, the quality of the resulting model crucially relies on the expressiveness of the inference model. We introduce Adversarial Variational Bayes (AVB), a technique for training Variational Autoencoders with arbitrarily expressive inference models. We achieve this by introducing an auxiliary discriminative network that allows to rephrase the maximum-likelihood-problem as a two-player game, hence establishing a principled connection between VAEs and Generative Adversarial Networks (GANs). We show that in the nonparametric limit our method yields an exact maximum-likelihood assignment for the parameters of the generative model, as well as the exact posterior distribution over the latent variables given an observation. Contrary to competing approaches which combine VAEs with GANs, our approach has a clear theoretical justification, retains most advantages of standard Variational Autoencoders and is easy to implement.