OpenRaiser/Intern-Atlas huggingface dataset:
Stable recovery of low-dimensional cones in Hilbert spaces: One RIP to rule them all
Venue: arXiv cs.IT 2016
Year: 2016

Many inverse problems in signal processing deal with the robust estimation of unknown data from underdetermined linear observations. Low dimensional models, when combined with appropriate regularizers, have been shown to be efficient at performing this task. Sparse models with the 1-norm or low rank models with the nuclear norm are examples of such successful combinations. Stable recovery guarantees in these settings have been established using a common tool adapted to each case: the notion of restricted isometry property (RIP). In this paper, we establish generic RIP-based guarantees for the stable recovery of cones (positively homogeneous model sets) with arbitrary regularizers. These guarantees are illustrated on selected examples. For block structured sparsity in the infinite dimensional setting, we use the guarantees for a family of regularizers which efficiency in terms of RIP constant can be controlled, leading to stronger and sharper guarantees than the state of the art.
Monitoring Potential Drug Interactions and Reactions via Network Analysis of Instagram User Timelines
Venue: arXiv cs.SI 2016
Year: 2016

Much recent research aims to identify evidence for Drug-Drug Interactions (DDI) and Adverse Drug reactions (ADR) from the biomedical scientific literature. In addition to this "Bibliome", the universe of social media provides a very promising source of large-scale data that can help identify DDI and ADR in ways that have not been hitherto possible. Given the large number of users, analysis of social media data may be useful to identify under-reported, population-level pathology associated with DDI, thus further contributing to improvements in population health. Moreover, tapping into this data allows us to infer drug interactions with natural products--including cannabis--which constitute an array of DDI very poorly explored by biomedical research thus far. Our goal is to determine the potential of Instagram for public health monitoring and surveillance for DDI, ADR, and behavioral pathology at large. Using drug, symptom, and natural product dictionaries for identification of the various types of DDI and ADR evidence, we have collected ~7000 timelines. We report on 1) the development of a monitoring tool to easily observe user-level timelines associated with drug and symptom terms of interest, and 2) population-level behavior via the analysis of co-occurrence networks computed from user timelines at three different scales: monthly, weekly, and daily occurrences. Analysis of these networks further reveals 3) drug and symptom direct and indirect associations with greater support in user timelines, as well as 4) clusters of symptoms and drugs revealed by the collective behavior of the observed population. This demonstrates that Instagram contains much drug- and pathology specific data for public health monitoring of DDI and ADR, and that complex network analysis provides an important toolbox to extract health-related associations and their support from large-scale social media data.
A Sorted Semantic Framework for Applied Process Calculi
Venue: arXiv cs.LO 2016
Year: 2016

Applied process calculi include advanced programming constructs such as type systems, communication with pattern matching, encryption primitives, concurrent constraints, nondeterminism, process creation, and dynamic connection topologies. Several such formalisms, e.g. the applied pi calculus, are extensions of the the pi-calculus; a growing number is geared towards particular applications or computational paradigms. Our goal is a unified framework to represent different process calculi and notions of computation. To this end, we extend our previous work on psi-calculi with novel abstract patterns and pattern matching, and add sorts to the data term language, giving sufficient criteria for subject reduction to hold. Our framework can directly represent several existing process calculi; the resulting transition systems are isomorphic to the originals up to strong bisimulation. We also demonstrate different notions of computation on data terms, including cryptographic primitives and a lambda-calculus with erratic choice. Finally, we prove standard congruence and structural properties of bisimulation; the proof has been machine-checked using Nominal Isabelle in the case of a single name sort.
Basic inequalities for weighted entropies
Venue: arXiv cs.IT 2016
Year: 2016

The concept of weighted entropy takes into account values of different outcomes, i.e., makes entropy context-dependent, through the weight function. In this paper, we establish a number of simple inequalities for the weighted entropies (general as well as specific), mirroring similar bounds on standard (Shannon) entropies and related quantities. The required assumptions are written in terms of various expectations of the weight functions. Examples are weighted Ky Fan and weighted Hadamard inequalities involving determinants of positive-definite matrices, and weighted Cramér-Rao inequalities involving the weighted Fisher information matrix.
Distributed Estimation of Graph 4-Profiles
Venue: arXiv cs.SI 2016
Year: 2016

We present a novel distributed algorithm for counting all four-node induced subgraphs in a big graph. These counts, called the $4$-profile, describe a graph's connectivity properties and have found several uses ranging from bioinformatics to spam detection. We also study the more complicated problem of estimating the local $4$-profiles centered at each vertex of the graph. The local $4$-profile embeds every vertex in an $11$-dimensional space that characterizes the local geometry of its neighborhood: vertices that connect different clusters will have different local $4$-profiles compared to those that are only part of one dense cluster. Our algorithm is a local, distributed message-passing scheme on the graph and computes all the local $4$-profiles in parallel. We rely on two novel theoretical contributions: we show that local $4$-profiles can be calculated using compressed two-hop information and also establish novel concentration results that show that graphs can be substantially sparsified and still retain good approximation quality for the global $4$-profile. We empirically evaluate our algorithm using a distributed GraphLab implementation that we scaled up to $640$ cores. We show that our algorithm can compute global and local $4$-profiles of graphs with millions of edges in a few minutes, significantly improving upon the previous state of the art.
Differential Evolution with Generalized Mutation Operator for Parameters Optimization in Gene Selection for Cancer Classification
Venue: arXiv cs.NE 2016
Year: 2016

Differential Evolution (DE) proved to be one of the most successful evolutionary algorithms for global optimization purposes in continuous problems. The core operator in DE is mutation which can provide the algorithm with both exploration and exploitation. In this article, a new notation for DE is proposed which has a formula that can be utilized for generating and extracting novel mutations and by applying this new notation, four novel mutations are proposed. More importantly, by combining these novel trial vector generation strategies and four other well-known ones, we proposed Generalized Mutation Differential Evolution (GMDE) that takes advantage of two mutation pools that have both explorative and exploitative strategies inside them. Results and experimental analysis are performed on CEC2005 benchmarks and the results stated that GMDE is surprisingly competitive and significantly improved the performance of this algorithm. Finally, GMDE is also applied to parameters optimization, modification and improvement of a feature selection method for cancer classification purposes over gene expression microarray profiles.
An Instantiation-Based Approach for Solving Quantified Linear Arithmetic
Venue: arXiv cs.LO 2016
Year: 2016

This paper presents a framework to derive instantiation-based decision procedures for satisfiability of quantified formulas in first-order theories, including its correctness, implementation, and evaluation. Using this framework we derive decision procedures for linear real arithmetic (LRA) and linear integer arithmetic (LIA) formulas with one quantifier alternation. Our procedure can be integrated into the solving architecture used by typical SMT solvers. Experimental results on standardized benchmarks from model checking, static analysis, and synthesis show that our implementation of the procedure in the SMT solver CVC4 outperforms existing tools for quantified linear arithmetic.
A Comparison of MIMO Techniques in Downlink Millimeter Wave Cellular Networks with Hybrid Beamforming
Venue: arXiv cs.IT 2016
Year: 2016

Large antenna arrays will be needed in future millimeter wave (mmWave) cellular networks, enabling a large number of different possible antenna architectures and multiple-input multiple-output (MIMO) techniques. It is still unclear which MIMO technique is most desirable as a function of different network parameters. This paper, therefore, compares the coverage and rate performance of hybrid beamforming enabled multi-user (MU) MIMO and single-user spatial multiplexing (SM) with single-user analog beamforming (SU-BF). A stochastic geometry model for coverage and rate analysis is proposed for MU-MIMO mmWave cellular networks, taking into account important mmWave-specific hardware constraints for hybrid analog/digital precoders and combiners, and a blockage-dependent channel model which is sparse in angular domain. The analytical results highlight the coverage, rate and power consumption tradeoffs in multiuser mmWave networks. With perfect channel state information at the transmitter and round robin scheduling, MU-MIMO is usually a better choice than SM or SU-BF in mmWave cellular networks. This observation, however, neglects any overhead due to channel acquisition or computational complexity. Incorporating the impact of such overheads, our results can be re-interpreted so as to quantify the minimum allowable efficiency of MU-MIMO to provide higher rates than SM or SU-BF.
Row Reduction Applied to Decoding of Rank Metric and Subspace Codes
Venue: arXiv cs.IT 2016
Year: 2016

We show that decoding of $\ell$-Interleaved Gabidulin codes, as well as list-$\ell$ decoding of Mahdavifar--Vardy codes can be performed by row reducing skew polynomial matrices. Inspired by row reduction of $\F[x]$ matrices, we develop a general and flexible approach of transforming matrices over skew polynomial rings into a certain reduced form. We apply this to solve generalised shift register problems over skew polynomial rings which occur in decoding $\ell$-Interleaved Gabidulin codes. We obtain an algorithm with complexity $O(\ell μ^2)$ where $μ$ measures the size of the input problem and is proportional to the code length $n$ in the case of decoding. Further, we show how to perform the interpolation step of list-$\ell$-decoding Mahdavifar--Vardy codes in complexity $O(\ell n^2)$, where $n$ is the number of interpolation constraints.
On the Placement Delivery Array Design in Centralized Coded Caching Scheme
Venue: arXiv cs.IT 2016
Year: 2016

Caching is a promising solution to satisfy the ever increasing demands for the multi-media traffics. In caching networks, coded caching is a recently proposed technique that achieves significant performance gains over the uncoded caching schemes. However, to implement the coded caching schemes, each file has to be split into $F$ packets, which usually increases exponentially with the number of users $K$. Thus, designing caching schemes that decrease the order of $F$ is meaningful for practical implementations. In this paper, by reviewing the Ali-Niesen caching scheme, the placement delivery array (PDA) design problem is firstly formulated to characterize the placement issue and the delivery issue with a single array. Moreover, we show that, through designing appropriate PDA, new centralized coded caching schemes can be discovered. Secondly, it is shown that the Ali-Niesen scheme corresponds to a special class of PDA, which realizes the best coding gain with the least $F$. Thirdly, we present a new construction of PDA for the centralized caching system, wherein the cache size of each user $M$ (identical cache size is assumed at all users) and the number of files $N$ satisfies $M/N=1/q$ or ${(q-1)}/{q}$ ($q$ is an integer such that $q\geq 2$). The new construction can decrease the required $F$ from the order $O\left(e^{K\cdot\left(\frac{M}{N}\ln \frac{N}{M} +(1-\frac{M}{N})\ln \frac{N}{N-M}\right)}\right)$ of Ali-Niesen scheme to $O\left(e^{K\cdot\frac{M}{N}\ln \frac{N}{M}}\right)$ or $O\left(e^{K\cdot(1-\frac{M}{N})\ln\frac{N}{N-M}}\right)$ respectively, while the coding gain loss is only $1$.
Network Flows that Solve Linear Equations
Venue: arXiv cs.SY 2016
Year: 2016

We study distributed network flows as solvers in continuous time for the linear algebraic equation $\mathbf{z}=\mathbf{H}\mathbf{y}$. Each node $i$ has access to a row $\mathbf{h}_i^{\rm T}$ of the matrix $\mathbf{H}$ and the corresponding entry $z_i$ in the vector $\mathbf{z}$. The first "consensus + projection" flow under investigation consists of two terms, one from standard consensus dynamics and the other contributing to projection onto each affine subspace specified by the $\mathbf{h}_i$ and $z_i$. The second "projection consensus" flow on the other hand simply replaces the relative state feedback in consensus dynamics with projected relative state feedback. Without dwell-time assumption on switching graphs as well as without positively lower bounded assumption on arc weights, we prove that all node states converge to a common solution of the linear algebraic equation, if there is any. The convergence is global for the "consensus + projection" flow while local for the "projection consensus" flow in the sense that the initial values must lie on the affine subspaces. If the linear equation has no exact solutions, we show that the node states can converge to a ball around the least squares solution whose radius can be made arbitrarily small through selecting a sufficiently large gain for the "consensus + projection" flow under fixed bidirectional graphs. Semi-global convergence to approximate least squares solutions is demonstrated for general switching directed graphs under suitable conditions. It is also shown that the "projection consensus" flow drives the average of the node states to the least squares solution with complete graph. Numerical examples are provided as illustrations of the established results.
On the flora of asynchronous locally non-monotonic Boolean automata networks
Venue: arXiv cs.DM 2016
Year: 2016

Boolean automata networks (BANs) are a well established model for biological regulation systems such as neural networks or genetic networks. Studies on the dynamics of BANs, whether it is synchronous or asynchronous, have mainly focused on monotonic networks, where fundamental questions on the links relating their static and dynamical properties have been raised and addressed. This paper explores analogous questions on asynchronous non-monotonic networks, xor-BANs, that are BANs where all the local transition functions are xor-functions. Using algorithmic tools, we give a general characterisation of the asynchronous transition graphs for most of the cactus xor-BANs and strongly connected xor-BANs. As an illustration of the results, we provide a complete description of the asynchronous dynamics of two particular classes of xor-BAN, namely xor-Flowers and xor-Cycle Chains. This work also leads to new bisimulation equivalences specific to xor-BANs.
Dynamic Spectrum Management: A Complete Complexity Characterization
Venue: arXiv cs.IT 2016
Year: 2016

Consider a multi-user multi-carrier communication system where multiple users share multiple discrete subcarriers. To achieve high spectrum efficiency, the users in the system must choose their transmit power dynamically in response to fast channel fluctuations. Assuming perfect channel state information, two formulations for the spectrum management (power control) problem are considered in this paper: the first is to minimize the total transmission power subject to all users' transmission data rate constraints, and the second is to maximize the min-rate utility subject to individual power constraints at each user. It is known in the literature that both formulations of the problem are polynomial time solvable when the number of subcarriers is one and strongly NP-hard when the number of subcarriers are greater than or equal to three. However, the complexity characterization of the problem when the number of subcarriers is two has been missing for a long time. This paper answers this long-standing open question: both formulations of the problem are strongly NP-hard when the number of subcarriers is two.
Automated Synchronization of Driving Data Using Vibration and Steering Events
Venue: arXiv cs.RO 2016
Year: 2016

We propose a method for automated synchronization of vehicle sensors useful for the study of multi-modal driver behavior and for the design of advanced driver assistance systems. Multi-sensor decision fusion relies on synchronized data streams in (1) the offline supervised learning context and (2) the online prediction context. In practice, such data streams are often out of sync due to the absence of a real-time clock, use of multiple recording devices, or improper thread scheduling and data buffer management. Cross-correlation of accelerometer, telemetry, audio, and dense optical flow from three video sensors is used to achieve an average synchronization error of 13 milliseconds. The insight underlying the effectiveness of the proposed approach is that the described sensors capture overlapping aspects of vehicle vibrations and vehicle steering allowing the cross-correlation function to serve as a way to compute the delay shift in each sensor. Furthermore, we show the decrease in synchronization error as a function of the duration of the data stream.
Reciprocal Altruism-based Cooperation in a Social Network Game
Venue: arXiv cs.SI 2016
Year: 2016

Cooperative behaviors are common in humans and are fundamental to our society. Theoretical and experimental studies have modeled environments in which the behaviors of humans, or agents, have been restricted to analyze their social behavior. However, it is important that such studies are generalized to less restrictive environments to understand human society. Social network games (SNGs) provide a particularly powerful tool for the quantitative study of human behavior. In SNGs, numerous players can behave more freely than in the environments used in previous studies; moreover, their relationships include apparent conflicts of interest and every action can be recorded. We focused on reciprocal altruism, one of the mechanisms that generate cooperative behavior. This study aims to investigate cooperative behavior based on reciprocal altruism in a less restrictive environment. For this purpose, we analyzed the social behavior underlying such cooperative behavior in an SNG. We focused on a game scenario in which the relationship between the players was similar to that in the Leader game. We defined cooperative behaviors by constructing a payoff matrix in the scenario. The results showed that players maintained cooperative behavior based on reciprocal altruism, and cooperators received more advantages than noncooperators. We found that players constructed reciprocal relationships based on two types of interactions, cooperative behavior and unproductive communication.
Link Prediction with Node Clustering Coefficient
Venue: arXiv cs.SI 2016
Year: 2016

Predicting missing links in incomplete complex networks efficiently and accurately is still a challenging problem. The recently proposed CAR (Cannistrai-Alanis-Ravai) index shows the power of local link/triangle information in improving link-prediction accuracy. With the information of level-2 links, which are links between common-neighbors, most classical similarity indices can be improved. Nevertheless, calculating the number of level-2 links makes CAR index not efficient enough. Inspired by the idea of employing local link/triangle information, we propose a new similarity index with more local structure information. In our method, local link/triangle structure information can be conveyed by clustering coefficient of common neighbors directly. The reason why clustering coefficient has good effectiveness in estimating the contribution of a common-neighbor is because that it employs links existing between neighbors of the common-neighbor and these links have the same structural position with the candidate link to this common-neighbor. Ten real-world networks drawn from five various fields are used to test the performance of our method against to classical similarity indices and recently proposed CAR index. Two estimators: precision and AUP, are used to evaluate the accuracy of link prediction algorithms. Generally speaking, our new index only performs competitively with CAR, but it is a good complement to CAR for networks with not very high LCP-corr, which is a measure to estimate the correlation between number of common-neighbors and number of links between common-neighbors. Besides, the proposed index is also more efficient than CAR index.
"We're on the Same Page": A Usability Study of Secure Email Using Pairs of Novice Users
Venue: arXiv cs.CR 2016
Year: 2016

Secure email is increasingly being touted as usable by novice users, with a push for adoption based on recent concerns about government surveillance. To determine whether secure email is for grassroots adoption, we employ a laboratory user study that recruits pairs of novice to install and use several of the latest systems to exchange secure messages. We present quantitative and qualitative results from 25 pairs of novice users as they use Pwm, Tutanota, and Virtru. Participants report being more at ease with this type of study and better able to cope with mistakes since both participants are "on the same page". We find that users prefer integrated solutions over depot-based solutions, and that tutorials are important in helping first-time users. Hiding the details of how a secure email system provides security can lead to a lack of trust in the system. Participants expressed a desire to use secure email, but few wanted to use it regularly and most were unsure of when they might use it.
My Reflections on the First Man vs. Machine No-Limit Texas Hold 'em Competition
Venue: arXiv cs.GT 2016
Year: 2016

The first ever human vs. computer no-limit Texas hold 'em competition took place from April 24-May 8, 2015 at River's Casino in Pittsburgh, PA. In this article I present my thoughts on the competition design, agent architecture, and lessons learned.
RATM: Recurrent Attentive Tracking Model
Venue: arXiv cs.LG 2016
Year: 2016

We present an attention-based modular neural framework for computer vision. The framework uses a soft attention mechanism allowing models to be trained with gradient descent. It consists of three modules: a recurrent attention module controlling where to look in an image or video frame, a feature-extraction module providing a representation of what is seen, and an objective module formalizing why the model learns its attentive behavior. The attention module allows the model to focus computation on task-related information in the input. We apply the framework to several object tracking tasks and explore various design choices. We experiment with three data sets, bouncing ball, moving digits and the real-world KTH data set. The proposed Recurrent Attentive Tracking Model performs well on all three tasks and can generalize to related but previously unseen sequences from a challenging tracking data set.