OpenRaiser/Intern-Atlas huggingface dataset:
Attack Analysis and Resilient Control Design for Discrete-time Distributed Multi-agent Systems
Venue: arXiv cs.SY 2019
Year: 2019

This work presents a rigorous analysis of the adverse effects of cyber-physical attacks on discrete-time distributed multi-agent systems, and propose a mitigation approach for attacks on sensors and actuators. First, we show how an attack on a compromised agent can propagate and affect intact agents that are reachable from it. This is, an attack on a single node snowballs into a network-wide attack and can even destabilize the entire system. Moreover, we show that the attacker can bypass the robust $H_{\infty}$ control protocol and make it entirely ineffective in attenuating the effect of the adversarial input on the system performance. Finally, to overcome adversarial effects of attacks on sensors and actuators, a distributed adaptive attack compensator is designed by estimating the normal expected behavior of agents. The adaptive attack compensator is augmented with the controller and it is shown that the proposed controller achieves secure consensus in presence of the attacks on sensors and actuators. This controller does not require to make any restrictive assumption on the number of agents or agent's neighbors under direct effect of adversarial input. Moreover, it recovers compromised agents under actuator attacks and avoids propagation of attacks on sensors without removing compromised agents. The effectiveness of the proposed controller and analysis is validated on a network of Sentry autonomous underwater vehicles subject to attacks under different scenarios.
Reliable OFDM Receiver with Ultra-Low Resolution ADC
Venue: arXiv cs.IT 2019
Year: 2019

The use of low-resolution analog-to-digital converters (ADCs) can significantly reduce power consumption and hardware cost. However, their resulting severe nonlinear distortion makes reliable data transmission challenging. For orthogonal frequency division multiplexing (OFDM) transmission, the orthogonality among subcarriers is destroyed. This invalidates conventional OFDM receivers relying heavily on this orthogonality. In this study, we move on to quantized OFDM (Q-OFDM) prototyping implementation based on our previous achievement in optimal Q-OFDM detection. First, we propose a novel Q-OFDM channel estimator by extending the generalized Turbo (GTurbo) framework formerly applied for optimal detection. Specifically, we integrate a type of robust linear OFDM channel estimator into the original GTurbo framework and derive its corresponding extrinsic information to guarantee its convergence. We also propose feasible schemes for automatic gain control, noise power estimation, and synchronization. Combined with the proposed inference algorithms, we develop an efficient Q-OFDM receiver architecture. Furthermore, we construct a proof-of-concept prototyping system and conduct over-the-air (OTA) experiments to examine its feasibility and reliability. This is the first work that focuses on both algorithm design and system implementation in the field of low-resolution quantization communication. The results of the numerical simulation and OTA experiment demonstrate that reliable data transmission can be achieved.
Clustering with Outlier Removal
Venue: arXiv cs.LG 2019
Year: 2019

Cluster analysis and outlier detection are strongly coupled tasks in data mining area. Cluster structure can be easily destroyed by few outliers; on the contrary, outliers are defined by the concept of cluster, which are recognized as the points belonging to none of the clusters. Unfortunately, most existing studies do not notice the coupled relationship between these two task and handle them separately. In light of this, we consider the joint cluster analysis and outlier detection problem, and propose the Clustering with Outlier Removal (COR) algorithm. Generally speaking, the original space is transformed into the binary space via generating basic partitions in order to define clusters. Then an objective function based Holoentropy is designed to enhance the compactness of each cluster with a few outliers removed. With further analyses on the objective function, only partial of the problem can be handled by K-means optimization. To provide an integrated solution, an auxiliary binary matrix is nontrivally introduced so that COR completely and efficiently solves the challenging problem via a unified K-means-- with theoretical supports. Extensive experimental results on numerous data sets in various domains demonstrate the effectiveness and efficiency of COR significantly over state-of-the-art methods in terms of cluster validity and outlier detection. Some key factors in COR are further analyzed for practical use. Finally, an application on flight trajectory is provided to demonstrate the effectiveness of COR in the real-world scenario.
End-to-end detection-segmentation network with ROI convolution
Venue: arXiv cs.CV 2019
Year: 2019

We propose an end-to-end neural network that improves the segmentation accuracy of fully convolutional networks by incorporating a localization unit. This network performs object localization first, which is then used as a cue to guide the training of the segmentation network. We test the proposed method on a segmentation task of small objects on a clinical dataset of ultrasound images. We show that by jointly learning for detection and segmentation, the proposed network is able to improve the segmentation accuracy compared to only learning for segmentation. Code is publicly available at https://github.com/vincentzhang/roi-fcn.
Discrete Stratified Morse Theory: Algorithms and A User's Guide
Venue: arXiv cs.CG 2019
Year: 2019

Inspired by the works of Forman on discrete Morse theory, which is a combinatorial adaptation to cell complexes of classical Morse theory on manifolds, we introduce a discrete analogue of the stratified Morse theory of Goresky and MacPherson. We describe the basics of this theory and prove fundamental theorems relating the topology of a general simplicial complex with the critical simplices of a discrete stratified Morse function on the complex. We also provide an algorithm that constructs a discrete stratified Morse function out of an arbitrary function defined on a finite simplicial complex; this is different from simply constructing a discrete Morse function on such a complex. We then give simple examples to convey the utility of our theory. Finally, we relate our theory with the classical stratified Morse theory in terms of triangulated Whitney stratified spaces.
Axiomatizations of inconsistency indices for triads
Venue: arXiv cs.AI 2019
Year: 2019

Pairwise comparison matrices often exhibit inconsistency, therefore many indices have been suggested to measure their deviation from a consistent matrix. A set of axioms has been proposed recently that is required to be satisfied by any reasonable inconsistency index. This set seems to be not exhaustive as illustrated by an example, hence it is expanded by adding two new properties. All axioms are considered on the set of triads, pairwise comparison matrices with three alternatives, which is the simplest case of inconsistency. We choose the logically independent properties and prove that they characterize, that is, uniquely determine the inconsistency ranking induced by most inconsistency indices that coincide on this restricted domain. Since triads play a prominent role in a number of inconsistency indices, our results can also contribute to the measurement of inconsistency for pairwise comparison matrices with more than three alternatives.
A Belief Propagation Algorithm for Multipath-Based SLAM
Venue: arXiv cs.IT 2019
Year: 2019

We present a simultaneous localization and mapping (SLAM) algorithm that is based on radio signals and the association of specular multipath components (MPCs) with geometric features. Especially in indoor scenarios, robust localization from radio signals is challenging due to diffuse multipath propagation, unknown MPC-feature association, and limited visibility of features. In our approach, specular reflections at flat surfaces are described in terms of virtual anchors (VAs) that are mirror images of the physical anchors (PAs). The positions of these VAs and possibly also of the PAs are unknown. We develop a Bayesian model of the SLAM problem and represent it by a factor graph, which enables the use of belief propagation (BP) for efficient marginalization of the joint posterior distribution. The resulting BP-based SLAM algorithm detects the VAs associated with the PAs and estimates jointly the time-varying position of the mobile agent and the positions of the VAs and possibly also of the PAs, thereby leveraging the MPCs in the radio signal for improved accuracy and robustness of agent localization. The algorithm has a low computational complexity and scales well in all relevant system parameters. Experimental results using both synthetic measurements and real ultra-wideband radio signals demonstrate the excellent performance of the algorithm in challenging indoor environments.
Distribution System Monitoring for Smart Power Grids with Distributed Generation Using Artificial Neural Networks
Venue: arXiv cs.CE 2019
Year: 2019

The increasing number of distributed generators connected to distribution grids requires a reliable monitoring of such grids. Economic considerations prevent a full observation of distribution grids with direct measurements. First approaches using a limited number of measurements to monitor such grids exist, some of which use artificial neural networks (ANN). The current ANN-based approaches, however, are limited to static topologies, only estimate voltage magnitudes, do not work properly when confronted with a high amount of distributed generation and often yield inaccurate results. These strong limitations have prevented a true applicability of ANN for distribution grid monitoring. The objective of this paper is to overcome the limitations of existing approaches. We do that by presenting an ANN-based scheme, which advances the state-of-the-art in several ways: Our scheme can cope with a very low number of measurements, far less than is traditionally required by the state-of-the-art weighted least squares state estimation (WLS SE). It can estimate both voltage magnitudes and line loadings with high precision and includes different switching states as inputs. Our contribution consists of a method to generate useful training data by using a scenario generator and a number of hyperparameters that define the ANN architecture. Both can be used for different grids even with a high amount of distributed generation. Simulations are performed with an elaborate evaluation approach on a real distribution grid and a CIGRE benchmark grid both with a high amount of distributed generation from photovoltaics and wind energy converters. They demonstrate that the proposed ANN scheme clearly outperforms state-of-the-art ANN schemes and WLS SE under normal operating conditions and different situations such as gross measurement errors when comparing voltage magnitude and line magnitude estimation errors.
Quantized Compressive Sensing with RIP Matrices: The Benefit of Dithering
Venue: arXiv cs.IT 2019
Year: 2019

Quantized compressive sensing (QCS) deals with the problem of coding compressive measurements of low-complexity signals with quantized, finite precision representations, i.e., a mandatory process involved in any practical sensing model. While the resolution of this quantization clearly impacts the quality of signal reconstruction, there actually exist incompatible combinations of quantization functions and sensing matrices that proscribe arbitrarily low reconstruction error when the number of measurements increases. This work shows that a large class of random matrix constructions known to respect the restricted isometry property (RIP) is "compatible" with a simple scalar and uniform quantization if a uniform random vector, or a random dither, is added to the compressive signal measurements before quantization. In the context of estimating low-complexity signals (e.g., sparse or compressible signals, low-rank matrices) from their quantized observations, this compatibility is demonstrated by the existence of (at least) one signal reconstruction method, the projected back projection (PBP), whose reconstruction error decays when the number of measurements increases. Interestingly, given one RIP matrix and a single realization of the dither, a small reconstruction error can be proved to hold uniformly for all signals in the considered low-complexity set. We confirm these observations numerically in several scenarios involving sparse signals, low-rank matrices, and compressible signals, with various RIP matrix constructions such as sub-Gaussian random matrices and random partial discrete cosine transform (DCT) matrices.
Sparsely Aggregated Convolutional Networks
Venue: arXiv cs.CV 2019
Year: 2019

We explore a key architectural aspect of deep convolutional neural networks: the pattern of internal skip connections used to aggregate outputs of earlier layers for consumption by deeper layers. Such aggregation is critical to facilitate training of very deep networks in an end-to-end manner. This is a primary reason for the widespread adoption of residual networks, which aggregate outputs via cumulative summation. While subsequent works investigate alternative aggregation operations (e.g. concatenation), we focus on an orthogonal question: which outputs to aggregate at a particular point in the network. We propose a new internal connection structure which aggregates only a sparse set of previous outputs at any given depth. Our experiments demonstrate this simple design change offers superior performance with fewer parameters and lower computational requirements. Moreover, we show that sparse aggregation allows networks to scale more robustly to 1000+ layers, thereby opening future avenues for training long-running visual processes.
Overcoming the vanishing gradient problem in plain recurrent networks
Venue: arXiv cs.NE 2019
Year: 2019

Plain recurrent networks greatly suffer from the vanishing gradient problem while Gated Neural Networks (GNNs) such as Long-short Term Memory (LSTM) and Gated Recurrent Unit (GRU) deliver promising results in many sequence learning tasks through sophisticated network designs. This paper shows how we can address this problem in a plain recurrent network by analyzing the gating mechanisms in GNNs. We propose a novel network called the Recurrent Identity Network (RIN) which allows a plain recurrent network to overcome the vanishing gradient problem while training very deep models without the use of gates. We compare this model with IRNNs and LSTMs on multiple sequence modeling benchmarks. The RINs demonstrate competitive performance and converge faster in all tasks. Notably, small RIN models produce 12%--67% higher accuracy on the Sequential and Permuted MNIST datasets and reach state-of-the-art performance on the bAbI question answering dataset.
On the Power Allocation Limits for Downlink Multi-user NOMA with QoS
Venue: arXiv cs.IT 2019
Year: 2019

The fundamental power allocation requirements for NOMA systems with minimum quality of service (QoS) requirements are investigated. For any minimum QoS rate $R_0$, the limits on the power allocation coefficients for each user are derived, such that any power allocation coefficient outside of these limits creates an outage with probability equal to 1. The power allocation coefficients that facilitate each user's success of performing successive interference cancellation (SIC) and decoding its own signal are derived, and are found to depend only on the target rate $R_0$ and the number of total users $K$. It is then proven that using these power allocation coefficients create the same outage event as if using orthogonal multiple access (OMA), which proves that the outage performance of NOMA with a fixed-power scheme can matched that of OMA for all users simultaneously. Simulations confirm the theoretical results, and also demonstrate that a power allocation strategy exists that can improve the outage performance of NOMA over OMA, even with a fixed-power strategy.
Courtesy as a Means to Coordinate
Venue: arXiv cs.MA 2019
Year: 2019

We investigate the problem of multi-agent coordination under rationality constraints. Specifically, role allocation, task assignment, resource allocation, etc. Inspired by human behavior, we propose a framework (CA^3NONY) that enables fast convergence to efficient and fair allocations based on a simple convention of courtesy. We prove that following such convention induces a strategy which constitutes an $ε$-subgame-perfect equilibrium of the repeated allocation game with discounting. Simulation results highlight the effectiveness of CA^3NONY as compared to state-of-the-art bandit algorithms, since it achieves more than two orders of magnitude faster convergence, higher efficiency, fairness, and average payoff.
Deanonymizing Tor hidden service users through Bitcoin transactions analysis
Venue: arXiv cs.CR 2019
Year: 2019

With the rapid increase of threats on the Internet, people are continuously seeking privacy and anonymity. Services such as Bitcoin and Tor were introduced to provide anonymity for online transactions and Web browsing. Due to its pseudonymity model, Bitcoin lacks retroactive operational security, which means historical pieces of information could be used to identify a certain user. We investigate the feasibility of deanonymizing users of Tor hidden services who rely on Bitcoin as a payment method by exploiting public information leaked from online social networks, the Blockchain, and onion websites. This, for example, allows an adversary to link a user with @alice Twitter address to a Tor hidden service with private.onion address by finding at least one past transaction in the Blockchain that involves their publicly declared Bitcoin addresses. To demonstrate the feasibility of this deanonymization attack, we carried out a real-world experiment simulating a passive, limited adversary. We crawled 1.5K hidden services and collected 88 unique Bitcoin addresses. We then crawled 5B tweets and 1M BitcoinTalk forum pages and collected 4.2K and 41K unique Bitcoin addresses, respectively. Each user address was associated with an online identity along with its public profile information. By analyzing the transactions in the Blockchain, we were able to link 125 unique users to 20 Tor hidden services, including sensitive ones, such as The Pirate Bay and Silk Road. We also analyzed two case studies in detail to demonstrate the implications of the resulting information leakage on user anonymity. In particular, we confirm that Bitcoin addresses should always be considered exploitable, as they can be used to deanonymize users retroactively. This is especially important for Tor hidden service users who actively seek and expect privacy and anonymity.
Computer-Assisted Proving of Combinatorial Conjectures Over Finite Domains: A Case Study of a Chess Conjecture
Venue: arXiv cs.LO 2019
Year: 2019

There are several approaches for using computers in deriving mathematical proofs. For their illustration, we provide an in-depth study of using computer support for proving one complex combinatorial conjecture -- correctness of a strategy for the chess KRK endgame. The final, machine verifiable, result presented in this paper is that there is a winning strategy for white in the KRK endgame generalized to $n \times n$ board (for natural $n$ greater than $3$). We demonstrate that different approaches for computer-based theorem proving work best together and in synergy and that the technology currently available is powerful enough for providing significant help to humans deriving complex proofs.
Dynamic Graph CNN for Learning on Point Clouds
Venue: arXiv cs.CV 2019
Year: 2019

Point clouds provide a flexible geometric representation suitable for countless applications in computer graphics; they also comprise the raw output of most 3D data acquisition devices. While hand-designed features on point clouds have long been proposed in graphics and vision, however, the recent overwhelming success of convolutional neural networks (CNNs) for image analysis suggests the value of adapting insight from CNN to the point cloud world. Point clouds inherently lack topological information so designing a model to recover topology can enrich the representation power of point clouds. To this end, we propose a new neural network module dubbed EdgeConv suitable for CNN-based high-level tasks on point clouds including classification and segmentation. EdgeConv acts on graphs dynamically computed in each layer of the network. It is differentiable and can be plugged into existing architectures. Compared to existing modules operating in extrinsic space or treating each point independently, EdgeConv has several appealing properties: It incorporates local neighborhood information; it can be stacked applied to learn global shape properties; and in multi-layer systems affinity in feature space captures semantic characteristics over potentially long distances in the original embedding. We show the performance of our model on standard benchmarks including ModelNet40, ShapeNetPart, and S3DIS.
Integrality Gaps for Colorful Matchings
Venue: arXiv cs.DM 2019
Year: 2019

We study the integrality gap of the natural linear programming relaxation for the \textit{Bounded Color Matching} (BCM) problem. We provide several families of instances and establish lower bounds on their integrality gaps and we study how the Sherali-Adams "lift-and-project" technique behaves on these instances. We complement these results by showing that if we exclude certain simple sub-structures from our input graphs, then the integrality gap of the natural linear formulation strictly improves. To prove this, we adapt for our purposes the results of Füredi [\emph{Combinatorica}, 1(2):155-162, 1981]. We further leverage this to show upper bounds on the performance of the Sherali-Adams hierarchy when applied to the natural LP relaxation of the BCM problem.
Reasoning about effects: from lists to cyber-physical agents
Venue: arXiv cs.PL 2019
Year: 2019

Theories for reasoning about programs with effects initially focused on basic manipulation of lists and other mutable data. The next challenge was to consider higher-order programming, adding functions as first class objects to mutable data. Reasoning about actors added the challenge of dealing with distributed open systems of entities interacting asynchronously. The advent of cyber-physical agents introduces the need to consider uncertainty, faults, physical as well as logical effects. In addition cyber-physical agents have sensors and actuators giving rise to a much richer class of effects with broader scope: think of self-driving cars, autonomous drones, or smart medical devices. This paper gives a retrospective on reasoning about effects highlighting key principles and techniques and closing with challenges for future work.
Higher-dimensional automata modeling shared-variable systems
Venue: arXiv cs.LO 2019
Year: 2019

The purpose of this paper is to provide a construction to model shared-variable systems using higher-dimensional automata which is compositional in the sense that the parallel composition of completely independent systems is modeled by the standard tensor product of HDAs and nondeterministic choice is represented by the coproduct.