OpenRaiser/Intern-Atlas huggingface dataset:
Frameworks for Designing In-place Graph Algorithms
Venue: arXiv cs.DS 2017
Year: 2017

Read-only memory model is a classical model of computation to study time-space tradeoffs of algorithms. One of the classical results on the ROM model is that any sorting algorithm that uses O(s) words of extra space requires $Ω(n^2/s)$ comparisons for $ \lg n \leq s \leq n/\lg n$ and the bound has also been recently matched by an algorithm. However, if we relax the model (from ROM), we do have sorting algorithms (say Heapsort) that can sort using $O(n \lg n)$ comparisons using $O(\lg n)$ bits of extra space, even keeping a permutation of the given input sequence at any point of time during the algorithm. We address similar questions for graph algorithms. We show that a simple natural relaxation of ROM model allows us to implement fundamental graph search methods like BFS and DFS more space efficiently than in ROM. By simply allowing elements in the adjacency list of a vertex to be permuted, we show that, on an undirected or directed connected graph $G$ having $n$ vertices and $m$ edges, the vertices of $G$ can be output in a DFS or BFS order using $O(\lg n)$ bits of extra space and $O(n^3 \lg n)$ time. Thus we obtain similar bounds for reachability and shortest path distance (both for undirected and directed graphs). With a little more (but still polynomial) time, we can also output vertices in the lex-DFS order. As reachability in directed graphs and shortest path distance are NL-complete, and lex-DFS is P-complete, our results show that our model is more powerful than ROM if L $\neq$ P. En route, we also introduce and develop algorithms for another relaxation of ROM where the adjacency lists of the vertices are circular lists and we can modify only the heads of the lists. All our algorithms are simple but quite subtle, and we believe that these models are practical enough to spur interest for other graph problems in these models.
Distributed Convergence Verification for Gaussian Belief Propagation
Venue: arXiv cs.IT 2017
Year: 2017

Gaussian belief propagation (BP) is a computationally efficient method to approximate the marginal distribution and has been widely used for inference with high dimensional data as well as distributed estimation in large-scale networks. However, the convergence of Gaussian BP is still an open issue. Though sufficient convergence conditions have been studied in the literature, verifying these conditions requires gathering all the information over the whole network, which defeats the main advantage of distributed computing by using Gaussian BP. In this paper, we propose a novel sufficient convergence condition for Gaussian BP that applies to both the pairwise linear Gaussian model and to Gaussian Markov random fields. We show analytically that this sufficient convergence condition can be easily verified in a distributed way that satisfies the network topology constraint.
Encoding Turing Machines into the Deterministic Lambda-Calculus
Venue: arXiv cs.LO 2017
Year: 2017

This note is about encoding Turing machines into the lambda-calculus.
Recent Developments in Aerial Robotics: A Survey and Prototypes Overview
Venue: arXiv cs.RO 2017
Year: 2017

In recent years, research and development in aerial robotics (i.e., unmanned aerial vehicles, UAVs) has been growing at an unprecedented speed, and there is a need to summarize the background, latest developments, and trends of UAV research. Along with a general overview on the definition, types, categories, and topics of UAV, this work describes a systematic way to identify 1,318 high-quality UAV papers from more than thirty thousand that have been appeared in the top journals and conferences. On top of that, we provide a bird's-eye view of UAV research since 2001 by summarizing various statistical information, such as the year, type, and topic distribution of the UAV papers. We make our survey list public and believe that the list can not only help researchers identify, study, and compare their work, but is also useful for understanding research trends in the field. From our survey results, we find there are many types of UAV, and to the best of our knowledge, no literature has attempted to summarize all types in one place. With our survey list, we explain the types within our survey and outline the recent progress of each. We believe this summary can enhance readers' understanding on the UAVs and inspire researchers to propose new methods and new applications.
Saving Space by Dynamic Algebraization Based on Tree Decomposition: Minimum Dominating Set
Venue: arXiv cs.DS 2017
Year: 2017

An algorithm is presented that solves the Minimum Dominating Set problem exactly using polynomial space based on dynamic programming for a tree decomposition. A direct application of dynamic programming based on a tree decomposition would result in an exponential space algorithm, but we use zeta transforms to obtain a polynomial space algorithm in exchange for a moderate increase of the time. This framework was pioneered by Lokshtanov and Nederlof 2010 and adapted to a dynamic setting by Fürer and Yu 2017. Our space-efficient algorithm is a parametrized algorithm based on tree-depth and treewidth. The naive algorithm for Minimum Dominating Set runs in $\mathcal{O}^*(2^n)$ time. Most of the previous works have focused on time complexity. But space optimization is a crucial aspect of algorithm design, since in several scenarios space is a more valuable resource than time. Our parametrized algorithm runs in $\mathcal{O}^*(3^{d})$, and its space complexity is $\mathcal{O}(nk)$, where $d$ is the depth and $k$ is the width of the given tree decomposition. We observe that Reed's 1992 algorithm constructing a tree decomposition of a graph uses only polynomial space. So, even if the tree decomposition is not given, we still obtain an efficient polynomial space algorithm. There are some other algorithms which use polynomial space for this problem, but they are not efficient for graphs with small tree depth.
Near Capacity Signaling over Fading Channels using Coherent Turbo Coded OFDM and Massive MIMO
Venue: arXiv cs.IT 2017
Year: 2017

The minimum average signal-to-noise ratio (SNR) per bit required for error-free transmission over a fading channel is derived, and is shown to be equal to that of the additive white Gaussian noise (AWGN) channel, which is $-1.6$ dB. Discrete-time algorithms are presented for timing and carrier synchronization, as well as channel estimation, for turbo coded multiple input multiple output (MIMO) orthogonal frequency division multiplexed (OFDM) systems. Simulation results show that it is possible to achieve a bit error rate of $10^{-5}$ at an average SNR per bit of 5.5 dB, using two transmit and two receive antennas. We then propose a near-capacity signaling method in which each transmit antenna uses a different carrier frequency. Using the near-capacity approach, we show that it is possible to achieve a BER of $2\times 10^{-5}$ at an average SNR per bit of just 2.5 dB, with one receive antenna for each transmit antenna. When the number of receive antennas for each transmit antenna is increased to 128, then a BER of $2\times 10^{-5}$ is attained at an average SNR per bit of 1.25 dB. In all cases, the number of transmit antennas is two and the spectral efficiency is 1 bit/transmission or 1 bit/sec/Hz. In other words, each transmit antenna sends 0.5 bit/transmission. It is possible to obtain higher spectral efficiency by increasing the number of transmit antennas, with no loss in BER performance, as long as each transmit antenna uses a different carrier frequency. The transmitted signal spectrum for the near-capacity approach can be restricted by pulse-shaping. In all the simulations, a four-state turbo code is used. The corresponding turbo decoder uses eight iterations. The algorithms can be implemented on programmable hardware and there is a large scope for parallel processing.
3D-A-Nets: 3D Deep Dense Descriptor for Volumetric Shapes with Adversarial Networks
Venue: arXiv cs.CV 2017
Year: 2017

Recently researchers have been shifting their focus towards learned 3D shape descriptors from hand-craft ones to better address challenging issues of the deformation and structural variation inherently present in 3D objects. 3D geometric data are often transformed to 3D Voxel grids with regular format in order to be better fed to a deep neural net architecture. However, the computational intractability of direct application of 3D convolutional nets to 3D volumetric data severely limits the efficiency (i.e. slow processing) and effectiveness (i.e. unsatisfied accuracy) in processing 3D geometric data. In this paper, powered with a novel design of adversarial networks (3D-A-Nets), we have developed a novel 3D deep dense shape descriptor (3D-DDSD) to address the challenging issues of efficient and effective 3D volumetric data processing. We developed new definition of 2D multilayer dense representation (MDR) of 3D volumetric data to extract concise but geometrically informative shape description and a novel design of adversarial networks that jointly train a set of convolution neural network (CNN), recurrent neural network (RNN) and an adversarial discriminator. More specifically, the generator network produces 3D shape features that encourages the clustering of samples from the same category with correct class label, whereas the discriminator network discourages the clustering by assigning them misleading adversarial class labels. By addressing the challenges posed by the computational inefficiency of direct application of CNN to 3D volumetric data, 3D-A-Nets can learn high-quality 3D-DSDD which demonstrates superior performance on 3D shape classification and retrieval over other state-of-the-art techniques by a great margin.
Self-Organizing Maps Classification with Application to Laptop's Adapters Magnetic Field
Venue: arXiv cs.CY 2017
Year: 2017

This paper presents an application of the Self-Organizing-Map classification method, which is used for classification of the extremely low frequency magnetic field emission in the near neighborhood of the laptop adapters. The experiment is performed on different laptop adapters of the same characteristics. After that, the Self-Organizing-Map classification on the obtained emission data is performed. The classification results establish the typical emission levels of the laptop adapters, which are far above the safety standards' limit. At the end, a discussion is carried out about the importance of using the classification as a possible solution for safely use the laptop adapters in order to reduce the negative effects of the magnetic field emission to the laptop users.
Revisiting hand-crafted feature for action recognition: a set of improved dense trajectories
Venue: arXiv cs.CV 2017
Year: 2017

We propose a feature for action recognition called Trajectory-Set (TS), on top of the improved Dense Trajectory (iDT). The TS feature encodes only trajectories around densely sampled interest points, without any appearance features. Experimental results on the UCF50, UCF101, and HMDB51 action datasets demonstrate that TS is comparable to state-of-the-arts, and outperforms many other methods; for HMDB the accuracy of 85.4%, compared to the best accuracy of 80.2% obtained by a deep method. Our code is available on-line at https://github.com/Gauffret/TrajectorySet .
Deformation estimation of an elastic object by partial observation using a neural network
Venue: arXiv cs.CV 2017
Year: 2017

Deformation estimation of elastic object assuming an internal organ is important for the computer navigation of surgery. The aim of this study is to estimate the deformation of an entire three-dimensional elastic object using displacement information of very few observation points. A learning approach with a neural network was introduced to estimate the entire deformation of an object. We applied our method to two elastic objects; a rectangular parallelepiped model, and a human liver model reconstructed from computed tomography data. The average estimation error for the human liver model was 0.041 mm when the object was deformed up to 66.4 mm, from only around 3 % observations. These results indicate that the deformation of an entire elastic object can be estimated with an acceptable level of error from limited observations by applying a trained neural network to a new deformation.
Hyper-dimensional computing for a visual question-answering system that is trainable end-to-end
Venue: arXiv cs.AI 2017
Year: 2017

In this work we propose a system for visual question answering. Our architecture is composed of two parts, the first part creates the logical knowledge base given the image. The second part evaluates questions against the knowledge base. Differently from previous work, the knowledge base is represented using hyper-dimensional computing. This choice has the advantage that all the operations in the system, namely creating the knowledge base and evaluating the questions against it, are differentiable, thereby making the system easily trainable in an end-to-end fashion.
Abaqus2Matlab: A suitable tool for finite element post-processing
Venue: arXiv cs.MS 2017
Year: 2017

A suitable piece of software is presented to connect Abaqus, a sophisticated finite element package, with Matlab, the most comprehensive program for mathematical analysis. This interface between these well-known codes not only benefits from the image processing and the integrated graph-plotting features of Matlab but also opens up new opportunities in results post-processing, statistical analysis and mathematical optimization, among many other possibilities. The software architecture and usage are appropriately described and two problems of particular engineering significance are addressed to demonstrate its capabilities. Firstly, the software is employed to assess cleavage fracture through a novel 3-parameter Weibull probabilistic framework. Then, its potential to create and train neural networks is used to identify damage parameters through a hybrid experimental-numerical scheme, and model crack propagation in structural materials by means of a cohesive zone approach. The source code, detailed documentation and a large number of tutorials can be freely downloaded from www.abaqus2matlab.com.
On Structural Parameterizations of Firefighting
Venue: arXiv cs.DS 2017
Year: 2017

The Firefighting problem is defined as follows. At time $t=0$, a fire breaks out at a vertex of a graph. At each time step $t \geq 0$, a firefighter permanently defends (protects) an unburned vertex, and the fire then spread to all undefended neighbors from the vertices on fire. This process stops when the fire cannot spread anymore. The goal is to find a sequence of vertices for the firefighter that maximizes the number of saved (non burned) vertices. The Firefighting problem turns out to be NP-hard even when restricted to bipartite graphs or trees of maximum degree three. We study the parameterized complexity of the Firefighting problem for various structural parameterizations. All our parameters measure the distance to a graph class (in terms of vertex deletion) on which the firefighting problem admits a polynomial time algorithm. Specifically, for a graph class $\mathcal{F}$ and a graph $G$, a vertex subset $S$ is called a modulator to $\mathcal{F}$ if $G \setminus S$ belongs to $\mathcal{F}$. The parameters we consider are the sizes of modulators to graph classes such as threshold graphs, bounded diameter graphs, disjoint unions of stars, and split graphs. To begin with, we show that the problem is W[1]-hard when parameterized by the size of a modulator to diameter at most two graphs and split graphs. In contrast to the above intractability results, we show that Firefighting is fixed parameter tractable (FPT) when parameterized by the size of a modulator to threshold graphs and disjoint unions of stars, which are subclasses of diameter at most two graphs. We further investigate the kernelization complexity of these problems to find that firefighting admits a polynomial kernel when parameterized by the size of a modulator to a clique, while it is unlikely to admit a polynomial kernel when parameterized by the size of a modulator to a disjoint union of stars.
3D Semantic Segmentation with Submanifold Sparse Convolutional Networks
Venue: arXiv cs.CV 2017
Year: 2017

Convolutional networks are the de-facto standard for analyzing spatio-temporal data such as images, videos, and 3D shapes. Whilst some of this data is naturally dense (e.g., photos), many other data sources are inherently sparse. Examples include 3D point clouds that were obtained using a LiDAR scanner or RGB-D camera. Standard "dense" implementations of convolutional networks are very inefficient when applied on such sparse data. We introduce new sparse convolutional operations that are designed to process spatially-sparse data more efficiently, and use them to develop spatially-sparse convolutional networks. We demonstrate the strong performance of the resulting models, called submanifold sparse convolutional networks (SSCNs), on two tasks involving semantic segmentation of 3D point clouds. In particular, our models outperform all prior state-of-the-art on the test set of a recent semantic segmentation competition.
Hidden attractors in aircraft control systems with saturated inputs
Venue: arXiv cs.SY 2017
Year: 2017

In the paper, the control problem with limitations on the magnitude and rate of the control action in aircraft control systems, is studied. Existence of hidden oscillations in the case of actuator position and rate limitations is demonstrated by the examples of piloted aircraft pilot involved oscillations (PIO) phenomenon and the airfoil flutter suppression system.
Super-Resolution for Overhead Imagery Using DenseNets and Adversarial Learning
Venue: arXiv cs.CV 2017
Year: 2017

Recent advances in Generative Adversarial Learning allow for new modalities of image super-resolution by learning low to high resolution mappings. In this paper we present our work using Generative Adversarial Networks (GANs) with applications to overhead and satellite imagery. We have experimented with several state-of-the-art architectures. We propose a GAN-based architecture using densely connected convolutional neural networks (DenseNets) to be able to super-resolve overhead imagery with a factor of up to 8x. We have also investigated resolution limits of these networks. We report results on several publicly available datasets, including SpaceNet data and IARPA Multi-View Stereo Challenge, and compare performance with other state-of-the-art architectures.
Role of Deep LSTM Neural Networks And WiFi Networks in Support of Occupancy Prediction in Smart Buildings
Venue: arXiv cs.AI 2017
Year: 2017

Knowing how many people occupy a building, and where they are located, is a key component of smart building services. Commercial, industrial and residential buildings often incorporate systems used to determine occupancy. However, relatively simple sensor technology and control algorithms limit the effectiveness of smart building services. In this paper we propose to replace sensor technology with time series models that can predict the number of occupants at a given location and time. We use Wi-Fi data sets readily available in abundance for smart building services and train Auto Regression Integrating Moving Average (ARIMA) models and Long Short-Term Memory (LSTM) time series models. As a use case scenario of smart building services, these models allow forecasting of the number of people at a given time and location in 15, 30 and 60 minutes time intervals at building as well as Access Point (AP) level. For LSTM, we build our models in two ways: a separate model for every time scale, and a combined model for the three time scales. Our experiments show that LSTM combined model reduced the computational resources with respect to the number of neurons by 74.48 % for the AP level, and by 67.13 % for the building level. Further, the root mean square error (RMSE) was reduced by 88.2% - 93.4% for LSTM in comparison to ARIMA for the building levels models and by 80.9% - 87% for the AP level models.
A Transprecision Floating-Point Platform for Ultra-Low Power Computing
Venue: arXiv cs.AR 2017
Year: 2017

In modern low-power embedded platforms, floating-point (FP) operations emerge as a major contributor to the energy consumption of compute-intensive applications with large dynamic range. Experimental evidence shows that 50% of the energy consumed by a core and its data memory is related to FP computations. The adoption of FP formats requiring a lower number of bits is an interesting opportunity to reduce energy consumption, since it allows to simplify the arithmetic circuitry and to reduce the memory bandwidth between memory and registers by enabling vectorization. From a theoretical point of view, the adoption of multiple FP types perfectly fits with the principle of transprecision computing, allowing fine-grained control of approximation while meeting specified constraints on the precision of final results. In this paper we propose an extended FP type system with complete hardware support to enable transprecision computing on low-power embedded processors, including two standard formats (binary32 and binary16) and two new formats (binary8 and binary16alt). First, we introduce a software library that enables exploration of FP types by tuning both precision and dynamic range of program variables. Then, we present a methodology to integrate our library with an external tool for precision tuning, and experimental results that highlight the clear benefits of introducing the new formats. Finally, we present the design of a transprecision FP unit capable of handling 8-bit and 16-bit operations in addition to standard 32-bit operations. Experimental results on FP-intensive benchmarks show that up to 90% of FP operations can be safely scaled down to 8-bit or 16-bit formats. Thanks to precision tuning and vectorization, execution time is decreased by 12% and memory accesses are reduced by 27% on average, leading to a reduction of energy consumption up to 30%.
Adversarial Networks for Prostate Cancer Detection
Venue: arXiv cs.NE 2017
Year: 2017

The large number of trainable parameters of deep neural networks renders them inherently data hungry. This characteristic heavily challenges the medical imaging community and to make things even worse, many imaging modalities are ambiguous in nature leading to rater-dependant annotations that current loss formulations fail to capture. We propose employing adversarial training for segmentation networks in order to alleviate aforementioned problems. We learn to segment aggressive prostate cancer utilizing challenging MRI images of 152 patients and show that the proposed scheme is superior over the de facto standard in terms of the detection sensitivity and the dice-score for aggressive prostate cancer. The achieved relative gains are shown to be particularly pronounced in the small dataset limit.