OpenRaiser/Intern-Atlas huggingface dataset:
Joint Trajectory and Communication Design for Multi-UAV Enabled Wireless Networks
Venue: arXiv cs.IT 2018
Year: 2018

Unmanned aerial vehicles (UAVs) have attracted significant interest recently in assisting wireless communication due to their high maneuverability, flexible deployment, and low cost. This paper considers a multi-UAV enabled wireless communication system, where multiple UAV-mounted aerial base stations (BSs) are employed to serve a group of users on the ground. To achieve fair performance among users, we maximize the minimum throughput over all ground users in the downlink communication by optimizing the multiuser communication scheduling and association jointly with the UAVs' trajectory and power control. The formulated problem is a mixed integer non-convex optimization problem that is challenging to solve. As such, we propose an efficient iterative algorithm for solving it by applying the block coordinate descent and successive convex optimization techniques. Specifically, the user scheduling and association, UAV trajectory, and transmit power are alternately optimized in each iteration. In particular, for the non-convex UAV trajectory and transmit power optimization problems, two approximate convex optimization problems are solved, respectively. We further show that the proposed algorithm is guaranteed to converge to at least a locally optimal solution. To speed up the algorithm convergence and achieve good throughput, a low-complexity and systematic initialization scheme is also proposed for the UAV trajectory design based on the simple circular trajectory and the circle packing scheme. Extensive simulation results are provided to demonstrate the significant throughput gains of the proposed design as compared to other benchmark schemes.
The adaptive interpolation method: A simple scheme to prove replica formulas in Bayesian inference
Venue: arXiv cs.IT 2018
Year: 2018

In recent years important progress has been achieved towards proving the validity of the replica predictions for the (asymptotic) mutual information (or "free energy") in Bayesian inference problems. The proof techniques that have emerged appear to be quite general, despite they have been worked out on a case-by-case basis. Unfortunately, a common point between all these schemes is their relatively high level of technicality. We present a new proof scheme that is quite straightforward with respect to the previous ones. We call it the adaptive interpolation method because it can be seen as an extension of the interpolation method developped by Guerra and Toninelli in the context of spin glasses, with an interpolation path that is adaptive. In order to illustrate our method we show how to prove the replica formula for three non-trivial inference problems. The first one is symmetric rank-one matrix estimation (or factorisation), which is the simplest problem considered here and the one for which the method is presented in full details. Then we generalize to symmetric tensor estimation and random linear estimation. We believe that the present method has a much wider range of applicability and also sheds new insights on the reasons for the validity of replica formulas in Bayesian inference.
Generative Cooperative Net for Image Generation and Data Augmentation
Venue: arXiv cs.CV 2018
Year: 2018

How to build a good model for image generation given an abstract concept is a fundamental problem in computer vision. In this paper, we explore a generative model for the task of generating unseen images with desired features. We propose the Generative Cooperative Net (GCN) for image generation. The idea is similar to generative adversarial networks except that the generators and discriminators are trained to work accordingly. Our experiments on hand-written digit generation and facial expression generation show that GCN's two cooperative counterparts (the generator and the classifier) can work together nicely and achieve promising results. We also discovered a usage of such generative model as an data-augmentation tool. Our experiment of applying this method on a recognition task shows that it is very effective comparing to other existing methods. It is easy to set up and could help generate a very large synthesized dataset.
Game Theoretic Dynamic Channel Allocation for Frequency-Selective Interference Channels
Venue: arXiv cs.IT 2018
Year: 2018

We consider the problem of distributed channel allocation in large networks under the frequency-selective interference channel. Performance is measured by the weighted sum of achievable rates. Our proposed algorithm is a modified Fictitious Play algorithm that can be implemented distributedly and its stable points are the pure Nash equilibria of a given game. Our goal is to design a utility function for a non-cooperative game such that all of its pure Nash equilibria have close to optimal global performance. This will make the algorithm close to optimal while requiring no communication between users. We propose a novel technique to analyze the Nash equilibria of a random interference game, determined by the random channel gains. Our analysis is asymptotic in the number of users. First we present a natural non-cooperative game where the utility of each user is his achievable rate. It is shown that, asymptotically in the number of users and for strong enough interference, this game exhibits many bad equilibria. Then we propose a novel non-cooperative M Frequency-Selective Interference Channel Game (M-FSIG), as a slight modification of the former, where the utility of each user is artificially limited. We prove that even its worst equilibrium has asymptotically optimal weighted sum-rate for any interference regime and even for correlated channels. This is based on an order statistics analysis of the fading channels that is valid for a broad class of fading distributions (including Rayleigh, Rician, m-Nakagami and more). We carry out simulations that show fast convergence of our algorithm to the proven asymptotically optimal pure Nash equilibria.
Solving Constrained Horn Clauses Using Dependence-Disjoint Expansions
Venue: arXiv cs.LO 2018
Year: 2018

Recursion-free Constrained Horn Clauses (CHCs) are logic-programming problems that can model safety properties of programs with bounded iteration and recursion. In addition, many CHC solvers reduce recursive systems to a series of recursion-free CHC systems that can each be solved efficiently. In this paper, we define a novel class of recursion-free systems, named Clause-Dependence Disjoint (CDD), that generalizes classes defined in previous work. The advantage of this class is that many CDD systems are smaller than systems which express the same constraints but are part of a different class. This advantage in size allows CDD systems to be solved more efficiently than their counterparts in other classes. We implemented a CHC solver named Shara. Shara solves arbitrary CHC systems by reducing the input to a series of CDD systems. Our evaluation indicates that Shara outperforms state-of-the-art implementations in many practical cases.
Receive Spatial Modulation for Massive MIMO Systems
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we consider the downlink of a massive multiple-input-multiple-output (MIMO) single user transmission system operating in the millimeter wave outdoor narrowband channel environment. We propose a novel receive spatial modulation architecture aimed to reduce the power consumption at the user terminal, while attaining a significant throughput. The energy consumption reduction is obtained through the use of analog devices (amplitude detector), which reduces the number of radio frequency chains and analog-to-digital-converters (ADCs). The base station transmits spatial and modulation symbols per channel use. We show that the optimal spatial symbol detector is a threshold detector that can be implemented by using one bit ADC. We derive closed form expressions for the detection threshold at different signal-to-noise-ratio (SNR) regions showing that a simple threshold can be obtained at high SNR and its performance approaches the exact threshold. We derive expressions for the average bit error probability in the presence and absence of the threshold estimation error showing that a small number of pilot symbols is needed. A performance comparison is done between the proposed system and fully digital MIMO showing that a suitable constellation selection can reduce the performance gap.
Explicit polynomial sequences with maximal spaces of partial derivatives and a question of K. Mulmuley
Venue: arXiv cs.CC 2018
Year: 2018

We answer a question of K. Mulmuley: In [Efremenko-Landsberg-Schenck-Weyman] it was shown that the method of shifted partial derivatives cannot be used to separate the padded permanent from the determinant. Mulmuley asked if this "no-go" result could be extended to a model without padding. We prove this is indeed the case using the iterated matrix multiplication polynomial. We also provide several examples of polynomials with maximal space of partial derivatives, including the complete symmetric polynomials. We apply Koszul flattenings to these polynomials to have the first explicit sequence of polynomials with symmetric border rank lower bounds higher than the bounds attainable via partial derivatives.
Mining Communication Data in a Music Community: A Preliminary Analysis
Venue: arXiv cs.SI 2018
Year: 2018

Comments play an important role within online creative communities because they make it possible to foster the production and improvement of authors' artifacts. We investigate how comment-based communication help shape members' behavior within online creative communities. In this paper, we report the results of a preliminary study aimed at mining the communication network of a music community for collaborative songwriting, where users collaborate online by first uploading new songs and then by adding new tracks and providing feedback in forms of comments.
Leveraging Intel SGX to Create a Nondisclosure Cryptographic library
Venue: arXiv cs.CR 2018
Year: 2018

Enforcing integrity and confidentiality of users' application code and data is a challenging mission that any software developer working on an online production grade service is facing. Since cryptology is not a widely understood subject, people on the cutting edge of research and industry are always seeking for new technologies to naturally expand the security of their programs and systems. Intel Software Guard Extension (Intel SGX) is an Intel technology for developers who are looking to protect their software binaries from plausible attacks using hardware instructions. The Intel SGX puts sensitive code and data into CPU-hardened protected regions called enclaves. In this project we leverage the Intel SGX to produce a secure cryptographic library which keeps the generated keys inside an enclave restricting use and dissemination of confidential cryptographic keys. Using enclaves to store the keys we maintain a small Trusted Computing Base (TCB) where we also perform computation on temporary buffers to and from untrusted application code. As a proof of concept, we implemented hashes and symmetric encryption algorithms inside the enclave where we stored hashes, Initialization Vectors (IVs) and random keys and open sourced the code (https://github.com/hmofrad/CryptoEnclave).
Music generation with variational recurrent autoencoder supported by history
Venue: arXiv cs.SD 2018
Year: 2018

A new architecture of an artificial neural network that helps to generate longer melodic patterns is introduced alongside with methods for post-generation filtering. The proposed approach called variational autoencoder supported by history is based on a recurrent highway gated network combined with a variational autoencoder. Combination of this architecture with filtering heuristics allows generating pseudo-live acoustically pleasing and melodically diverse music.
Constrained Submodular Maximization via Greedy Local Search
Venue: arXiv cs.DS 2018
Year: 2018

We present a simple combinatorial $\frac{1 -e^{-2}}{2}$-approximation algorithm for maximizing a monotone submodular function subject to a knapsack and a matroid constraint. This classic problem is known to be hard to approximate within factor better than $1 - 1/e$. We show that the algorithm can be extended to yield a ratio of $\frac{1 - e^{-(k+1)}}{k+1}$ for the problem with a single knapsack and the intersection of $k$ matroid constraints, for any fixed $k > 1$. Our algorithms, which combine the greedy algorithm of [Khuller, Moss and Naor, 1999] and [Sviridenko, 2004] with local search, show the power of this natural framework in submodular maximization with combined constraints.
Re3 : Real-Time Recurrent Regression Networks for Visual Tracking of Generic Objects
Venue: arXiv cs.CV 2018
Year: 2018

Robust object tracking requires knowledge and understanding of the object being tracked: its appearance, its motion, and how it changes over time. A tracker must be able to modify its underlying model and adapt to new observations. We present Re3, a real-time deep object tracker capable of incorporating temporal information into its model. Rather than focusing on a limited set of objects or training a model at test-time to track a specific instance, we pretrain our generic tracker on a large variety of objects and efficiently update on the fly; Re3 simultaneously tracks and updates the appearance model with a single forward pass. This lightweight model is capable of tracking objects at 150 FPS, while attaining competitive results on challenging benchmarks. We also show that our method handles temporary occlusion better than other comparable trackers using experiments that directly measure performance on sequences with occlusion.
Pricing Multi-Unit Markets
Venue: arXiv cs.GT 2018
Year: 2018

We study the power and limitations of posted prices in multi-unit markets, where agents arrive sequentially in an arbitrary order. We prove upper and lower bounds on the largest fraction of the optimal social welfare that can be guaranteed with posted prices, under a range of assumptions about the designer's information and agents' valuations. Our results provide insights about the relative power of uniform and non-uniform prices, the relative difficulty of different valuation classes, and the implications of different informational assumptions. Among other results, we prove constant-factor guarantees for agents with (symmetric) subadditive valuations, even in an incomplete-information setting and with uniform prices.
Unbiased estimates for linear regression via volume sampling
Venue: arXiv cs.LG 2018
Year: 2018

Given a full rank matrix $X$ with more columns than rows, consider the task of estimating the pseudo inverse $X^+$ based on the pseudo inverse of a sampled subset of columns (of size at least the number of rows). We show that this is possible if the subset of columns is chosen proportional to the squared volume spanned by the rows of the chosen submatrix (ie, volume sampling). The resulting estimator is unbiased and surprisingly the covariance of the estimator also has a closed form: It equals a specific factor times $X^{+\top}X^+$. Pseudo inverse plays an important part in solving the linear least squares problem, where we try to predict a label for each column of $X$. We assume labels are expensive and we are only given the labels for the small subset of columns we sample from $X$. Using our methods we show that the weight vector of the solution for the sub problem is an unbiased estimator of the optimal solution for the whole problem based on all column labels. We believe that these new formulas establish a fundamental connection between linear least squares and volume sampling. We use our methods to obtain an algorithm for volume sampling that is faster than state-of-the-art and for obtaining bounds for the total loss of the estimated least-squares solution on all labeled columns.
Global Guarantees for Enforcing Deep Generative Priors by Empirical Risk
Venue: arXiv cs.IT 2018
Year: 2018

We examine the theoretical properties of enforcing priors provided by generative deep neural networks via empirical risk minimization. In particular we consider two models, one in which the task is to invert a generative neural network given access to its last layer and another in which the task is to invert a generative neural network given only compressive linear observations of its last layer. We establish that in both cases, in suitable regimes of network layer sizes and a randomness assumption on the network weights, that the non-convex objective function given by empirical risk minimization does not have any spurious stationary points. That is, we establish that with high probability, at any point away from small neighborhoods around two scalar multiples of the desired solution, there is a descent direction. Hence, there are no local minima, saddle points, or other stationary points outside these neighborhoods. These results constitute the first theoretical guarantees which establish the favorable global geometry of these non-convex optimization problems, and they bridge the gap between the empirical success of enforcing deep generative priors and a rigorous understanding of non-linear inverse problems.
LOGAN: Membership Inference Attacks Against Generative Models
Venue: arXiv cs.CR 2018
Year: 2018

Generative models estimate the underlying distribution of a dataset to generate realistic samples according to that distribution. In this paper, we present the first membership inference attacks against generative models: given a data point, the adversary determines whether or not it was used to train the model. Our attacks leverage Generative Adversarial Networks (GANs), which combine a discriminative and a generative model, to detect overfitting and recognize inputs that were part of training datasets, using the discriminator's capacity to learn statistical differences in distributions. We present attacks based on both white-box and black-box access to the target model, against several state-of-the-art generative models, over datasets of complex representations of faces (LFW), objects (CIFAR-10), and medical images (Diabetic Retinopathy). We also discuss the sensitivity of the attacks to different training parameters, and their robustness against mitigation strategies, finding that defenses are either ineffective or lead to significantly worse performances of the generative models in terms of training stability and/or sample quality.
Combinatorial Semi-Bandits with Knapsacks
Venue: arXiv cs.LG 2018
Year: 2018

We unify two prominent lines of work on multi-armed bandits: bandits with knapsacks (BwK) and combinatorial semi-bandits. The former concerns limited "resources" consumed by the algorithm, e.g., limited supply in dynamic pricing. The latter allows a huge number of actions but assumes combinatorial structure and additional feedback to make the problem tractable. We define a common generalization, support it with several motivating examples, and design an algorithm for it. Our regret bounds are comparable with those for BwK and combinatorial semi- bandits.
Distributed Synthesis for Parameterized Temporal Logics
Venue: arXiv cs.LO 2018
Year: 2018

We consider the synthesis of distributed implementations for specifications in parameterized temporal logics such as PROMPT-LTL, which extends LTL by temporal operators equipped with parameters that bound their scope. For single process synthesis it is well-established that such parametric extensions do not increase worst-case complexities. For synchronous distributed systems we show that, despite being more powerful, the realizability problem for PROMPT-LTL is not harder than its LTL counterpart. For asynchronous systems we have to express scheduling assumptions and therefore consider an assume-guarantee synthesis problem. As asynchronous distributed synthesis is already undecidable for LTL, we give a semi-decision procedure for the PROMPT-LTL assume-guarantee synthesis problem based on bounded synthesis. Finally, we show that our results extend to the stronger logics PLTL and PLDL.
Parallel Accelerated Custom Correlation Coefficient Calculations for Genomics Applications
Venue: arXiv cs.DC 2018
Year: 2018

The massive quantities of genomic data being made available through gene sequencing techniques are enabling breakthroughs in genomic science in many areas such as medical advances in the diagnosis and treatment of diseases. Analyzing this data, however, is a computational challenge insofar as the computational costs of the relevant algorithms can grow with quadratic, cubic or higher complexity-leading to the need for leadership scale computing. In this paper we describe a new approach to calculations of the Custom Correlation Coefficient (CCC) between Single Nucleotide Polymorphisms (SNPs) across a population, suitable for parallel systems equipped with graphics processing units (GPUs) or Intel Xeon Phi processors. We describe the mapping of the algorithms to accelerated processors, techniques used for eliminating redundant calculations due to symmetries, and strategies for efficient mapping of the calculations to many-node parallel systems. Results are presented demonstrating high per-node performance and near-ideal parallel scalability with rates of more than nine quadrillion elementwise comparisons achieved per second with the latest optimized code on the ORNL Titan system, this being orders of magnitude faster than rates achieved using other codes and platforms as reported in the literature. Also it is estimated that as many as 90 quadrillion comparisons per second may be achievable on the upcoming ORNL Summit system, an additional 10X performance increase. In a companion paper we describe corresponding techniques applied to calculations of the Proportional Similarity metric for comparative genomics applications.
Developing an edge computing platform for real-time descriptive analytics
Venue: arXiv cs.CY 2018
Year: 2018

The Internet of Mobile Things encompasses stream data being generated by sensors, network communications that pull and push these data streams, as well as running processing and analytics that can effectively leverage actionable information for transportation planning, management, and business advantage. Edge computing emerges as a new paradigm that decentralizes the communication, computation, control and storage resources from the cloud to the edge of the network. This paper proposes an edge computing platform where mobile edge nodes are physical devices deployed on a transit bus where descriptive analytics is used to uncover meaningful patterns from real-time transit data streams. An application experiment is used to evaluate the advantages and disadvantages of our proposed platform to support descriptive analytics at a mobile edge node and generate actionable information to transit managers.
Vehicle Traffic Driven Camera Placement for Better Metropolis Security Surveillance
Venue: arXiv cs.CY 2018
Year: 2018

Security surveillance is one of the most important issues in smart cities, especially in an era of terrorism. Deploying a number of (video) cameras is a common surveillance approach. Given the never-ending power offered by vehicles to metropolises, exploiting vehicle traffic to design camera placement strategies could potentially facilitate security surveillance. This article constitutes the first effort toward building the linkage between vehicle traffic and security surveillance, which is a critical problem for smart cities. We expect our study could influence the decision making of surveillance camera placement, and foster more research of principled ways of security surveillance beneficial to our physical-world life. Code has been made publicly available.