OpenRaiser/Intern-Atlas huggingface dataset:
The Rise of Jihadist Propaganda on Social Networks
Venue: arXiv cs.SI 2017
Year: 2017

Using a dataset of over 1.9 million messages posted on Twitter by about 25,000 ISIS members, we explore how ISIS makes use of social media to spread its propaganda and to recruit militants from the Arab world and across the globe. By distinguishing between violence-driven, theological, and sectarian content, we trace the connection between online rhetoric and key events on the ground. To the best of our knowledge, ours is one of the first studies to focus on Arabic content, while most literature focuses on English content. Our findings yield new important insights about how social media is used by radical militant groups to target the Arab-speaking world, and reveal important patterns in their propaganda efforts.
Decoding from Pooled Data: Phase Transitions of Message Passing
Venue: arXiv cs.IT 2017
Year: 2017

We consider the problem of decoding a discrete signal of categorical variables from the observation of several histograms of pooled subsets of it. We present an Approximate Message Passing (AMP) algorithm for recovering the signal in the random dense setting where each observed histogram involves a random subset of entries of size proportional to n. We characterize the performance of the algorithm in the asymptotic regime where the number of observations $m$ tends to infinity proportionally to n, by deriving the corresponding State Evolution (SE) equations and studying their dynamics. We initiate the analysis of the multi-dimensional SE dynamics by proving their convergence to a fixed point, along with some further properties of the iterates. The analysis reveals sharp phase transition phenomena where the behavior of AMP changes from exact recovery to weak correlation with the signal as m/n crosses a threshold. We derive formulae for the threshold in some special cases and show that they accurately match experimental behavior.
A New Achievable Rate Region for Multiple-Access Channel with States
Venue: arXiv cs.IT 2017
Year: 2017

The problem of reliable communication over the multiple-access channel (MAC) with states is investigated. We propose a new coding scheme for this problem which uses quasi-group codes (QGC). We derive a new computable single-letter characterization of the achievable rate region. As an example, we investigate the problem of doubly-dirty MAC with modulo-$4$ addition. It is shown that the sum-rate $R_1+R_2=1$ bits per channel use is achievable using the new scheme. Whereas, the natural extension of the Gel'fand-Pinsker scheme, sum-rates greater than $0.32$ are not achievable.
Region Ensemble Network: Improving Convolutional Network for Hand Pose Estimation
Venue: arXiv cs.CV 2017
Year: 2017

Hand pose estimation from monocular depth images is an important and challenging problem for human-computer interaction. Recently deep convolutional networks (ConvNet) with sophisticated design have been employed to address it, but the improvement over traditional methods is not so apparent. To promote the performance of directly 3D coordinate regression, we propose a tree-structured Region Ensemble Network (REN), which partitions the convolution outputs into regions and integrates the results from multiple regressors on each regions. Compared with multi-model ensemble, our model is completely end-to-end training. The experimental results demonstrate that our approach achieves the best performance among state-of-the-arts on two public datasets.
Design of Stochastic Robotic Swarms for Target Performance Metrics in Boundary Coverage Tasks
Venue: arXiv cs.RO 2017
Year: 2017

In this work, we analyze \textit{stochastic coverage schemes} (SCS) for robotic swarms in which the robots randomly attach to a one-dimensional boundary of interest using local communication and sensing, without relying on global position information or a map of the environment. Robotic swarms may be required to perform boundary coverage in a variety of applications, including environmental monitoring, collective transport, disaster response, and nanomedicine. We present a novel analytical approach to computing and designing the statistical properties of the communication and sensing networks that are formed by random robot configurations on a boundary. We are particularly interested in the event that a robot configuration forms a connected communication network or maintains continuous sensor coverage of the boundary. Using tools from order statistics, random geometric graphs, and computational geometry, we derive formulas for properties of the random graphs generated by robots that are independently and identically distributed along a boundary. We also develop order-of-magnitude estimates of these properties based on Poisson approximations and threshold functions. For cases where the SCS generates a uniform distribution of robots along the boundary, we apply our analytical results to develop a procedure for computing the robot population size, diameter, sensing range, or communication range that yields a random communication network or sensor network with desired properties.
Monocular LSD-SLAM Integration within AR System
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we cover the process of integrating Large-Scale Direct Simultaneous Localization and Mapping (LSD-SLAM) algorithm into our existing AR stereo engine, developed for our modified "Augmented Reality Oculus Rift". With that, we are able to track one of our realworld cameras which are mounted on the rift, within a complete unknown environment. This makes it possible to achieve a constant and full augmentation, synchronizing our 3D movement (x, y, z) in both worlds, the real world and the virtual world. The development for the basic AR setup using the Oculus Rift DK1 and two fisheye cameras is fully documented in our previous paper. After an introduction to image-based registration, we detail the LSD-SLAM algorithm and document our code implementing our integration. The AR stereo engine with Oculus Rift support can be accessed via the GIT repository https://github.com/MaXvanHeLL/ARift.git and the modified LSD-SLAM project used for the integration is available here https://github.com/MaXvanHeLL/LSD-SLAM.git.
Structurally Observable Distributed Networks of Agents under Cost and Robustness Constraints
Venue: arXiv cs.MA 2017
Year: 2017

In many problems, agents cooperate locally so that a leader or fusion center can infer the state of every agent from probing the state of only a small number of agents. Versions of this problem arise when a fusion center reconstructs an extended physical field by accessing the state of just a few of the sensors measuring the field, or a leader monitors the formation of a team of robots. Given a link cost, the paper presents a polynomial time algorithm to design a minimum cost coordinated network dynamics followed by the agents, under an observability constraint. The problem is placed in the context of structural observability and solved even when up to k agents in the coordinated network dynamics fail.
Optimal Detection of Faulty Traffic Sensors Used in Route Planning
Venue: arXiv cs.AI 2017
Year: 2017

In a smart city, real-time traffic sensors may be deployed for various applications, such as route planning. Unfortunately, sensors are prone to failures, which result in erroneous traffic data. Erroneous data can adversely affect applications such as route planning, and can cause increased travel time. To minimize the impact of sensor failures, we must detect them promptly and accurately. However, typical detection algorithms may lead to a large number of false positives (i.e., false alarms) and false negatives (i.e., missed detections), which can result in suboptimal route planning. In this paper, we devise an effective detector for identifying faulty traffic sensors using a prediction model based on Gaussian Processes. Further, we present an approach for computing the optimal parameters of the detector which minimize losses due to false-positive and false-negative errors. We also characterize critical sensors, whose failure can have high impact on the route planning application. Finally, we implement our method and evaluate it numerically using a real-world dataset and the route planning platform OpenTripPlanner.
On the Local Correctabilities of Projective Reed-Muller Codes
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we show that the projective Reed-Muller~(PRM) codes form a family of locally correctable codes~(LCC) in the regime of low query complexities. A PRM code is specified by the alphabet size $q$, the number of variables $m$, and the degree $d$. When $d\leq q-1$, we present a perfectly smooth local decoder to recover a symbol by accessing $γ\leq q$ symbols to the coordinates fall on a line. There are three major parameters considered in LCCs, namely the query complexity, the message length and the code length. This paper shows that PRM codes are shorter than generalized Reed-Muller~(GRM) codes in LCCs. Precisely, given a GRM code over a field of size $q$, there exists a class of shorter codes over a field of size $q-1$, while maintaining the same values on the query complexities and the message lengths.
Capacity Region of Gaussian Multiple-Access Channels with Energy Harvesting and Energy Cooperation
Venue: arXiv cs.IT 2017
Year: 2017

We consider the capacity region of a $K$-user multiple access channel (MAC) with energy harvesting transmitters. Each user stores and schedules the randomly arriving energy using an energy buffer. Users can also perform energy cooperation by transmitting energy to other users or receiving energy from them. We derive the capacity region of this channel and show that 1) the capacity region coincides with that of a traditional $K$-user Gaussian MAC with energy cooperation, where the average power constraints are equal to the battery recharging rates of the energy harvesting case; 2) each rate on the capacity region boundary can be achieved using the save-and-forward power control and a fixed energy cooperation policy.
Manifold Based Low-rank Regularization for Image Restoration and Semi-supervised Learning
Venue: arXiv cs.CV 2017
Year: 2017

Low-rank structures play important role in recent advances of many problems in image science and data science. As a natural extension of low-rank structures for data with nonlinear structures, the concept of the low-dimensional manifold structure has been considered in many data processing problems. Inspired by this concept, we consider a manifold based low-rank regularization as a linear approximation of manifold dimension. This regularization is less restricted than the global low-rank regularization, and thus enjoy more flexibility to handle data with nonlinear structures. As applications, we demonstrate the proposed regularization to classical inverse problems in image sciences and data sciences including image inpainting, image super-resolution, X-ray computer tomography (CT) image reconstruction and semi-supervised learning. We conduct intensive numerical experiments in several image restoration problems and a semi-supervised learning problem of classifying handwritten digits using the MINST data. Our numerical tests demonstrate the effectiveness of the proposed methods and illustrate that the new regularization methods produce outstanding results by comparing with many existing methods.
Challenges in Providing Automatic Affective Feedback in Instant Messaging Applications
Venue: arXiv cs.CL 2017
Year: 2017

Instant messaging is one of the major channels of computer mediated communication. However, humans are known to be very limited in understanding others' emotions via text-based communication. Aiming on introducing emotion sensing technologies to instant messaging, we developed EmotionPush, a system that automatically detects the emotions of the messages end-users received on Facebook Messenger and provides colored cues on their smartphones accordingly. We conducted a deployment study with 20 participants during a time span of two weeks. In this paper, we revealed five challenges, along with examples, that we observed in our study based on both user's feedback and chat logs, including (i)the continuum of emotions, (ii)multi-user conversations, (iii)different dynamics between different users, (iv)misclassification of emotions and (v)unconventional content. We believe this discussion will benefit the future exploration of affective computing for instant messaging, and also shed light on research of conversational emotion sensing.
L1-regularized Reconstruction Error as Alpha Matte
Venue: arXiv cs.CV 2017
Year: 2017

Sampling-based alpha matting methods have traditionally followed the compositing equation to estimate the alpha value at a pixel from a pair of foreground (F) and background (B) samples. The (F,B) pair that produces the least reconstruction error is selected, followed by alpha estimation. The significance of that residual error has been left unexamined. In this letter, we propose a video matting algorithm that uses L1-regularized reconstruction error of F and B samples as a measure of the alpha matte. A multi-frame non-local means framework using coherency sensitive hashing is utilized to ensure temporal coherency in the video mattes. Qualitative and quantitative evaluations on a dataset exclusively for video matting demonstrate the effectiveness of the proposed matting algorithm.
Spin Transfer Torque Driven Coupled Oscillators for Self-Oscillating RF Mixers
Venue: arXiv cs.ET 2017
Year: 2017

Spin transfer torque oscillators (STOs) based on magnetic tunnel junction (MTJ) devices are emerging as a possible replacement for complementary metal-oxide semiconductors for radio-frequency (RF) signal generation. Advantages include low power consumption, small device area, and large frequency tunability. But such a single device cannot achieve the necessary noise performance for RF applications. It has been reported lately that a network of globally coupled STOs achieves significant improvement in phase noise. The study here is to propose use of such coupled STOs as self-oscillating RF mixers. Critical mixer performance parameters, including conversion gain, output power, and linearity, are discussed.
Unveiling Eilenberg-type Correspondences: Birkhoff's Theorem for (finite) Algebras + Duality
Venue: arXiv cs.FL 2017
Year: 2017

The purpose of the present paper is to show that: Eilenberg-type correspondences = Birkhoff's theorem for (finite) algebras + duality. We consider algebras for a monad T on a category D and we study (pseudo)varieties of T-algebras. Pseudovarieties of algebras are also known in the literature as varieties of finite algebras. Two well-known theorems that characterize varieties and pseudovarieties of algebras play an important role here: Birkhoff's theorem and Birkhoff's theorem for finite algebras, the latter also known as Reiterman's theorem. We prove, under mild assumptions, a categorical version of Birkhoff's theorem for (finite) algebras to establish a one-to-one correspondence between (pseudo)varieties of T-algebras and (pseudo)equational T-theories. Now, if C is a category that is dual to D and B is the comonad on C that is the dual of T, we get a one-to-one correspondence between (pseudo)equational T-theories and their dual, (pseudo)coequational B-theories. Particular instances of (pseudo)coequational B-theories have been already studied in language theory under the name of "varieties of languages" to establish Eilenberg-type correspondences. All in all, we get a one-to-one correspondence between (pseudo)varieties of T-algebras and (pseudo)coequational B-theories, which will be shown to be exactly the nature of Eilenberg-type correspondences.
Decoding Delay Performance of Random Linear Network Coding for Broadcast
Venue: arXiv cs.IT 2017
Year: 2017

Characterization of the delay profile of systems employing random linear network coding is important for the reliable provision of broadcast services. Previous studies focused on network coding over large finite fields or developed Markov chains to model the delay distribution but did not look at the effect of transmission deadlines on the delay. In this work, we consider generations of source packets that are encoded and transmitted over the erasure broadcast channel. The transmission of packets associated to a generation is taken to be deadline-constrained, that is, the transmitter drops a generation and proceeds to the next one when a predetermined deadline expires. Closed-form expressions for the average number of required packet transmissions per generation are obtained in terms of the generation size, the field size, the erasure probability and the deadline choice. An upper bound on the average decoding delay, which is tighter than previous bounds found in the literature, is also derived. Analysis shows that the proposed framework can be used to fine-tune the system parameters and ascertain that neither insufficient nor excessive amounts of packets are sent over the broadcast channel.
EAC-Net: A Region-based Deep Enhancing and Cropping Approach for Facial Action Unit Detection
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we propose a deep learning based approach for facial action unit detection by enhancing and cropping the regions of interest. The approach is implemented by adding two novel nets (layers): the enhancing layers and the cropping layers, to a pretrained CNN model. For the enhancing layers, we designed an attention map based on facial landmark features and applied it to a pretrained neural network to conduct enhanced learning (The E-Net). For the cropping layers, we crop facial regions around the detected landmarks and design convolutional layers to learn deeper features for each facial region (C-Net). We then fuse the E-Net and the C-Net to obtain our Enhancing and Cropping (EAC) Net, which can learn both feature enhancing and region cropping functions. Our approach shows significant improvement in performance compared to the state-of-the-art methods applied to BP4D and DISFA AU datasets.
A Generalization of Permanent Inequalities and Applications in Counting and Optimization
Venue: arXiv cs.DS 2017
Year: 2017

A polynomial $p\in\mathbb{R}[z_1,\dots,z_n]$ is real stable if it has no roots in the upper-half complex plane. Gurvits's permanent inequality gives a lower bound on the coefficient of the $z_1z_2\dots z_n$ monomial of a real stable polynomial $p$ with nonnegative coefficients. This fundamental inequality has been used to attack several counting and optimization problems. Here, we study a more general question: Given a stable multilinear polynomial $p$ with nonnegative coefficients and a set of monomials $S$, we show that if the polynomial obtained by summing up all monomials in $S$ is real stable, then we can lowerbound the sum of coefficients of monomials of $p$ that are in $S$. We also prove generalizations of this theorem to (real stable) polynomials that are not multilinear. We use our theorem to give a new proof of Schrijver's inequality on the number of perfect matchings of a regular bipartite graph, generalize a recent result of Nikolov and Singh, and give deterministic polynomial time approximation algorithms for several counting problems.
Comparative benchmarking of cloud computing vendors with High Performance Linpack
Venue: arXiv cs.PF 2017
Year: 2017

We present a comparative analysis of the maximum performance achieved by the Linpack benchmark on compute intensive hardware publicly available from multiple cloud providers. We study both performance within a single compute node, and speedup for distributed memory calculations with up to 32 nodes or at least 512 computing cores. We distinguish between hyper-threaded and non-hyper-threaded scenarios and estimate the performance per single computing core. We also compare results with a traditional supercomputing system for reference. Our findings provide a way to rank the cloud providers and demonstrate the viability of the cloud for high performance computing applications.
Multi-step Off-policy Learning Without Importance Sampling Ratios
Venue: arXiv cs.LG 2017
Year: 2017

To estimate the value functions of policies from exploratory data, most model-free off-policy algorithms rely on importance sampling, where the use of importance sampling ratios often leads to estimates with severe variance. It is thus desirable to learn off-policy without using the ratios. However, such an algorithm does not exist for multi-step learning with function approximation. In this paper, we introduce the first such algorithm based on temporal-difference (TD) learning updates. We show that an explicit use of importance sampling ratios can be eliminated by varying the amount of bootstrapping in TD updates in an action-dependent manner. Our new algorithm achieves stability using a two-timescale gradient-based TD update. A prior algorithm based on lookup table representation called Tree Backup can also be retrieved using action-dependent bootstrapping, becoming a special case of our algorithm. In two challenging off-policy tasks, we demonstrate that our algorithm is stable, effectively avoids the large variance issue, and can perform substantially better than its state-of-the-art counterpart.
H(infinitude) Controller Design based on the T-S Triangular Cloud Model
Venue: arXiv cs.SY 2017
Year: 2017

In this paper, we propose a design method for controller based it on that describe plants as T-S triangular cloud models in case of uncertainty in them.
Graph Fourier Transform with Negative Edges for Depth Image Coding
Venue: arXiv cs.CV 2017
Year: 2017

Recent advent in graph signal processing (GSP) has led to the development of new graph-based transforms and wavelets for image / video coding, where the underlying graph describes inter-pixel correlations. In this paper, we develop a new transform called signed graph Fourier transform (SGFT), where the underlying graph G contains negative edges that describe anti-correlations between pixel pairs. Specifically, we first construct a one-state Markov process that models both inter-pixel correlations and anti-correlations. We then derive the corresponding precision matrix, and show that the loopy graph Laplacian matrix Q of a graph G with a negative edge and two self-loops at its end nodes is approximately equivalent. This proves that the eigenvectors of Q - called SGFT - approximates the optimal Karhunen-Lo`eve Transform (KLT). We show the importance of the self-loops in G to ensure Q is positive semi-definite. We prove that the first eigenvector of Q is piecewise constant (PWC), and thus can well approximate a piecewise smooth (PWS) signal like a depth image. Experimental results show that a block-based coding scheme based on SGFT outperforms a previous scheme using graph transforms with only positive edges for several depth images.
A Variation of Levin Search for All Well-Defined Problems
Venue: arXiv cs.CC 2017
Year: 2017

In 1973, L.A. Levin published an algorithm that solves any inversion problem $π$ as quickly as the fastest algorithm $p^*$ computing a solution for $π$ in time bounded by $2^{l(p^*)}.t^*$, where $l(p^*)$ is the length of the binary encoding of $p^*$, and $t^*$ is the runtime of $p^*$ plus the time to verify its correctness. In 2002, M. Hutter published an algorithm that solves any well-defined problem $π$ as quickly as the fastest algorithm $p^*$ computing a solution for $π$ in time bounded by $5.t_{p}(x)+d_p.time_{t_{p}}(x)+c_p$, where $d_p=40.2^{l(p)+l(t_{p})}$ and $c_p=40.2^{l(f)+1}.O(l(f)^2)$, where $l(f)$ is the length of the binary encoding of a proof $f$ that produces a pair $(p,t_p)$, where $t_p(x)$ is a provable time bound on the runtime of the fastest program $p$ provably equivalent to $p^*$. In this paper, we rewrite Levin Search using the ideas of Hutter so that we have a new simple algorithm that solves any well-defined problem $π$ as quickly as the fastest algorithm $p^*$ computing a solution for $π$ in time bounded by $O(l(f)^2).t_p(x)$.