OpenRaiser/Intern-Atlas huggingface dataset:
Convex block-sparse linear regression with expanders -- provably
Venue: arXiv cs.IT 2016
Year: 2016

Sparse matrices are favorable objects in machine learning and optimization. When such matrices are used, in place of dense ones, the overall complexity requirements in optimization can be significantly reduced in practice, both in terms of space and run-time. Prompted by this observation, we study a convex optimization scheme for block-sparse recovery from linear measurements. To obtain linear sketches, we use expander matrices, i.e., sparse matrices containing only few non-zeros per column. Hitherto, to the best of our knowledge, such algorithmic solutions have been only studied from a non-convex perspective. Our aim here is to theoretically characterize the performance of convex approaches under such setting. Our key novelty is the expression of the recovery error in terms of the model-based norm, while assuring that solution lives in the model. To achieve this, we show that sparse model-based matrices satisfy a group version of the null-space property. Our experimental findings on synthetic and real applications support our claims for faster recovery in the convex setting -- as opposed to using dense sensing matrices, while showing a competitive recovery performance.
Thread Progress Equalization: Dynamically Adaptive Power and Performance Optimization of Multi-threaded Applications
Venue: arXiv cs.DC 2016
Year: 2016

Dynamically adaptive multi-core architectures have been proposed as an effective solution to optimize performance for peak power constrained processors. In processors, the micro-architectural parameters or voltage/frequency of each core to be changed at run-time, thus providing a range of power/performance operating points for each core. In this paper, we propose Thread Progress Equalization (TPEq), a run-time mechanism for power constrained performance maximization of multithreaded applications running on dynamically adaptive multicore processors. Compared to existing approaches, TPEq (i) identifies and addresses two primary sources of inter-thread heterogeneity in multithreaded applications, (ii) determines the optimal core configurations in polynomial time with respect to the number of cores and configurations, and (iii) requires no modifications in the user-level source code. Our experimental evaluations demonstrate that TPEq outperforms state-of-the-art run-time power/performance optimization techniques proposed in literature for dynamically adaptive multicores by up to 23%.
Joint System and Algorithm Design for Computationally Efficient Fan Beam Coded Aperture X-ray Coherent Scatter Imaging
Venue: arXiv cs.CV 2016
Year: 2016

In x-ray coherent scatter tomography, tomographic measurements of the forward scatter distribution are used to infer scatter densities within a volume. A radiopaque 2D pattern placed between the object and the detector array enables the disambiguation between different scatter events. The use of a fan beam source illumination to speed up data acquisition relative to a pencil beam presents computational challenges. To facilitate the use of iterative algorithms based on a penalized Poisson log-likelihood function, efficient computational implementation of the forward and backward models are needed. Our proposed implementation exploits physical symmetries and structural properties of the system and suggests a joint system-algorithm design, where the system design choices are influenced by computational considerations, and in turn lead to reduced reconstruction time. Computational-time speedups of approximately 146 and 32 are achieved in the computation of the forward and backward models, respectively. Results validating the forward model and reconstruction algorithm are presented on simulated analytic and Monte Carlo data.
A Scalable and Distributed Solution to the Inertial Motion Capture Problem
Venue: arXiv cs.SY 2016
Year: 2016

In inertial motion capture, a multitude of body segments are equipped with inertial sensors, consisting of 3D accelerometers and 3D gyroscopes. Using an optimization-based approach to solve the motion capture problem allows for natural inclusion of biomechanical constraints and for modeling the connection of the body segments at the joint locations. The computational complexity of solving this problem grows both with the length of the data set and with the number of sensors and body segments considered. In this work, we present a scalable and distributed solution to this problem using tailored message passing, capable of exploiting the structure that is inherent in the problem. As a proof-of-concept we apply our algorithm to data from a lower body configuration.
On noise-induced synchronization and consensus of nonlinear network systems under input disturbances
Venue: arXiv cs.SY 2016
Year: 2016

This paper is concerned with the study of synchronization and consensus phenomena in complex networks of diffusively-coupled nodes subject to external disturbances. Specifically, we make use of stochastic Lyapunov functions to provide conditions for synchronization and consensus for networks of nonlinear, diffusively coupled nodes, where noise diffusion is not just additive but it depends on the nodes' state. The sufficient condition we provide, wich links together network topology, coupling strength and noise diffusion, offers two interesting interpretations. First, as suggested by {\em intuition}, in order for a network to achieve synchronization/consensus, its nodes need to be sufficiently well connected together. The second implication might seem, instead, counter-intuitive: if noise diffusion is {\em properly} designed, then it can drive an unsynchronized network towards synchronization/consensus. Motivated by our current research in Smart Cities and Internet of Things, we illustrate the effectiveness of our approach by showing how our results can be used to control certain collective decision processes.
Enriching Ontologies with Encyclopedic Background Knowledge for Document Indexing
Venue: arXiv cs.DL 2016
Year: 2016

The rapidly increasing number of scientific documents available publicly on the Internet creates the challenge of efficiently organizing and indexing these documents. Due to the time consuming and tedious nature of manual classification and indexing, there is a need for better methods to automate this process. This thesis proposes an approach which leverages encyclopedic background knowledge for enriching domain-specific ontologies with textual and structural information about the semantic vicinity of the ontologies' concepts. The proposed approach aims to exploit this information for improving both ontology-based methods for classifying and indexing documents and methods based on supervised machine learning.
Channel Reconstruction for SVD-ZF Precoding in Massive 3D-MIMO Systems Low-Complexity Algorithm
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we study the low-complexity channel reconstruction methods for downlink precoding in massive MIMO systems. When the user is allocated less streams than the number of its antennas, the BS or user usually utilizes the singular value decomposition (SVD) factorizations to get the effective channels, whose dimension is equal to the num of streams. This process is called channel reconstruction in BS for TDD mode. However, with the increasing of antennas in BS, the computation burden of SVD is becoming incredibly high. As a countermeasure, we propose a series of novel low-complexity channel reconstruction methods for downlink zero-forcing precoding (ZF). We adopt randomized algorithms to construct an approximate SVD, which could reduce the dimensions of the matrix, especially when approximating an input matrix with a low-rank element. Besides, this method could automatically modify the parameters to adapt arbitrary number demand of streams from users. The simulation results show that the proposed methods only cost less than 30% float computation than the traditional SVD-ZF method, while keeping nearly the same performance of 1Gbps with 128 BS antennas.
Learning Executable Semantic Parsers for Natural Language Understanding
Venue: arXiv cs.CL 2016
Year: 2016

For building question answering systems and natural language interfaces, semantic parsing has emerged as an important and powerful paradigm. Semantic parsers map natural language into logical forms, the classic representation for many important linguistic phenomena. The modern twist is that we are interested in learning semantic parsers from data, which introduces a new layer of statistical and computational issues. This article lays out the components of a statistical semantic parser, highlighting the key challenges. We will see that semantic parsing is a rich fusion of the logical and the statistical world, and that this fusion will play an integral role in the future of natural language understanding systems.
Early Warning of Human Crowds Based on Query Data from Baidu Map: Analysis Based on Shanghai Stampede
Venue: arXiv cs.SI 2016
Year: 2016

Without sufficient preparation and on-site management, the mass scale unexpected huge human crowd is a serious threat to public safety. A recent impressive tragedy is the 2014 Shanghai Stampede, where 36 people were killed and 49 were injured in celebration of the New Year's Eve on December 31th 2014 in the Shanghai Bund. Due to the innately stochastic and complicated individual movement, it is not easy to predict collective gatherings, which potentially leads to crowd events. In this paper, with leveraging the big data generated on Baidu map, we propose a novel approach to early warning such potential crowd disasters, which has profound public benefits. An insightful observation is that, with the prevalence and convenience of mobile map service, users usually search on the Baidu map to plan a routine. Therefore, aggregating users' query data on Baidu map can obtain priori and indication information for estimating future human population in a specific area ahead of time. Our careful analysis and deep investigation on the Baidu map data on various events also demonstrates a strong correlation pattern between the number of map query and the number of positioning users in an area. Based on such observation, we propose a decision method utilizing query data on Baidu map to invoke warnings for potential crowd events about 1-3 hours in advance. Then we also construct a machine learning model with heterogeneous data (such as query data and mobile positioning data) to quantitatively measure the risk of the potential crowd disasters. We evaluate the effectiveness of our methods on the data of Baidu map.
Adaptive Parameter Selection in Evolutionary Algorithms by Reinforcement Learning with Dynamic Discretization of Parameter Range
Venue: arXiv cs.NE 2016
Year: 2016

Online parameter controllers for evolutionary algorithms adjust values of parameters during the run of an evolutionary algorithm. Recently a new efficient parameter controller based on reinforcement learning was proposed by Karafotias et al. In this method ranges of parameters are discretized into several intervals before the run. However, performing adaptive discretization during the run may increase efficiency of an evolutionary algorithm. Aleti et al. proposed another efficient controller with adaptive discretization. In the present paper we propose a parameter controller based on reinforcement learning with adaptive discretization. The proposed controller is compared with the existing parameter adjusting methods on several test problems using different configurations of an evolutionary algorithm. For the test problems, we consider four continuous functions, namely the sphere function, the Rosenbrock function, the Levi function and the Rastrigin function. Results show that the new controller outperforms the other controllers on most of the considered test problems.
Multi-velocity neural networks for gesture recognition in videos
Venue: arXiv cs.CV 2016
Year: 2016

We present a new action recognition deep neural network which adaptively learns the best action velocities in addition to the classification. While deep neural networks have reached maturity for image understanding tasks, we are still exploring network topologies and features to handle the richer environment of video clips. Here, we tackle the problem of multiple velocities in action recognition, and provide state-of-the-art results for gesture recognition, on known and new collected datasets. We further provide the training steps for our semi-supervised network, suited to learn from huge unlabeled datasets with only a fraction of labeled examples.
Reconstruction of Frequency Hopping Signals From Multi-Coset Samples
Venue: arXiv cs.IT 2016
Year: 2016

Multi-Coset (MC) sampling is a well established, practically feasible scheme for sampling multiband analog signals below the Nyquist rate. MC sampling has gained renewed interest in the Compressive Sensing (CS) community, due partly to the fact that in the frequency domain, MC sampling bears a strong resemblance to other sub-Nyquist CS acquisition protocols. In this paper, we consider MC sampling of analog frequency hopping signals, which can be viewed as multiband signals with changing band positions. This nonstationarity motivates our consideration of a segment-based reconstruction framework, in which the sample stream is broken into short segments for reconstruction. In contrast, previous works focusing on the reconstruction of multiband signals have used a segment-less reconstruction framework such as the modified MUSIC algorithm. We outline the challenges associated with segment-based recovery of frequency hopping signals from MC samples, and we explain how these challenges can be addressed using conventional CS recovery techniques. We also demonstrate the utility of the Discrete Prolate Spheroidal Sequences (DPSS's) as an efficient dictionary for reducing the computational complexity of segment-based reconstruction.
Performance-Oriented Association in Large Cellular Networks with Technology Diversity
Venue: arXiv cs.IT 2016
Year: 2016

The development of mobile virtual network operators, where multiple wireless technologies (e.g. 3G and 4G) or operators with non-overlapping bandwidths are pooled and shared is expected to provide enhanced service with broader coverage, without incurring additional infrastructure cost. However, their emergence poses an unsolved question on how to harness such a technology and bandwidth diversity. This paper addresses one of the simplest questions in this class, namely, the issue of associating each mobile to one of those bandwidths. Intriguingly, this association issue is intrinsically distinct from those in traditional networks. We first propose a generic stochastic geometry model lending itself to analyzing a wide class of association policies exploiting various information on the network topology, e.g. received pilot powers and fading values. This model firstly paves the way for tailoring and designing an optimal association scheme to maximize any performance metric of interest (e.g. the probability of coverage) subject to the information known about the network. In this class of optimal association, we prove a result that the performance improves as the information known about the network increases. Secondly, this model is used to quantify the performance of any arbitrary association policy and not just the optimal association policy. We propose a simple policy called the Max-Ratio which is not-parametric, i.e. it dispenses with the statistical knowledge of base station deployments in stochastic geometry models. We also prove that this simple policy is optimal in a certain limiting regime of the wireless environment. Through simulations, we provide insights into (i) a practical compromise between performance gain and cost of estimating information and; (ii) the selection of association schemes under environments with different propagation models, i.e. path-loss exponents.
Optimal Sparse Recovery for Multi-Sensor Measurements
Venue: arXiv cs.IT 2016
Year: 2016

Many practical sensing applications involve multiple sensors simultaneously acquiring measurements of a single object. Conversely, most existing sparse recovery guarantees in compressed sensing concern only single-sensor acquisition scenarios. In this paper, we address the optimal recovery of compressible signals from multi-sensor measurements using compressed sensing techniques, thereby confirming the benefits of multi- over single-sensor environments. Throughout the paper, we consider a broad class of sensing matrices, and two fundamentally different sampling scenarios (distinct and identical respectively), both of which are relevant to applications. For the case of diagonal sensor profile matrices (which characterize environmental conditions between a source and the sensors), this paper presents two key improvements over existing results. First, a simpler optimal recovery guarantee for distinct sampling, and second, an improved recovery guarantee for identical sampling, based on the so-called sparsity in levels signal model.
Graphs Drawing through Fuzzy Clustering
Venue: arXiv cs.GR 2016
Year: 2016

Many problems can be presented in an abstract form through a wide range of binary objects and relations which are defined over problem domain. In these problems, graphical demonstration of defined binary objects and solutions is the most suitable representation approach. In this regard, graph drawing problem discusses the methods for transforming combinatorial graphs to geometrical drawings in order to visualize them. This paper studies the force-directed algorithms and multi-surface techniques for drawing general undirected graphs. Particularly, this research describes force-directed approach to model the drawing of a general graph as a numerical optimization problem. So, it can use rich knowledge which is presented as an established system by the numerical optimization. Moreover, this research proposes the multi-surface approach as an efficient tool for overcoming local minimums in standard force-directed algorithms. Next, we introduce a new method for multi-surface approach based on fuzzy clustering algorithms.
On the Separability of Stochastic Geometric Objects, with Applications
Venue: arXiv cs.CG 2016
Year: 2016

In this paper, we study the linear separability problem for stochastic geometric objects under the well-known unipoint/multipoint uncertainty models. Let $S=S_R \cup S_B$ be a given set of stochastic bichromatic points, and define $n = \min\{|S_R|, |S_B|\}$ and $N = \max\{|S_R|, |S_B|\}$. We show that the separable-probability (SP) of $S$ can be computed in $O(nN^{d-1})$ time for $d \geq 3$ and $O(\min\{nN \log N, N^2\})$ time for $d=2$, while the expected separation-margin (ESM) of $S$ can be computed in $O(nN^{d})$ time for $d \geq 2$. In addition, we give an $Ω(nN^{d-1})$ witness-based lower bound for computing SP, which implies the optimality of our algorithm among all those in this category. Also, a hardness result for computing ESM is given to show the difficulty of further improving our algorithm. As an extension, we generalize the same problems from points to general geometric objects, i.e., polytopes and/or balls, and extend our algorithms to solve the generalized SP and ESM problems in $O(nN^{d})$ and $O(nN^{d+1})$ time, respectively. Finally, we present some applications of our algorithms to stochastic convex-hull related problems.
A 3-D Spatial Model for In-building Wireless Networks with Correlated Shadowing
Venue: arXiv cs.IT 2016
Year: 2016

Consider orthogonal planes in the 3-D space representing floors and walls in a large building. These planes divide the space into rooms where a wireless infrastructure is deployed. This paper is focused on the analysis of the correlated shadowing field created by this wireless infrastructure through the set of walls and floors. When the locations of the planes and of the wireless nodes are governed by Poisson processes, we obtain a simple stochastic model which captures the non-uniform nature of node deployment and room sizes. This model, which we propose to call the Poisson building, captures the complex in-building shadowing correlations, is scalable in the number of dimensions and is tractable for network performance analysis. It allows an exact mathematical characterization of the interference distribution in both infinite and finite buildings, which further leads to closed-form expressions for the coverage probabilities in in-building cellular networks and the success probability of in-building underlay D2D transmissions.
Computing Nonsimple Polygons of Minimum Perimeter
Venue: arXiv cs.CG 2016
Year: 2016

We provide exact and approximation methods for solving a geometric relaxation of the Traveling Salesman Problem (TSP) that occurs in curve reconstruction: for a given set of vertices in the plane, the problem Minimum Perimeter Polygon (MPP) asks for a (not necessarily simply connected) polygon with shortest possible boundary length. Even though the closely related problem of finding a minimum cycle cover is polynomially solvable by matching techniques, we prove how the topological structure of a polygon leads to NP-hardness of the MPP. On the positive side, we show how to achieve a constant-factor approximation. When trying to solve MPP instances to provable optimality by means of integer programming, an additional difficulty compared to the TSP is the fact that only a subset of subtour constraints is valid, depending not on combinatorics, but on geometry. We overcome this difficulty by establishing and exploiting additional geometric properties. This allows us to reliably solve a wide range of benchmark instances with up to 600 vertices within reasonable time on a standard machine. We also show that using a natural geometry-based sparsification yields results that are on average within 0.5% of the optimum.
Are easily usable security libraries possible and how should experts work together to create them?
Venue: arXiv cs.CR 2016
Year: 2016

Due to non-experts also developing security relevant applications it is necessary to support them too. Some improvements in the current research may not reach or impact these developers. Nonetheless these developers use security libraries. There are findings that even their usage is not easily possible and applications are left vulnerable to supposedly treated threats. So it is important to improve the usability of the security libraries. This is itself is not straightforward because of a required maturing process for example. By getting together experts of different involved areas, especially cryptographic and API-usability experts, both of the problems can be tackled.