OpenRaiser/Intern-Atlas huggingface dataset:
Edge-Orders
Venue: arXiv cs.DM 2016
Year: 2016

Canonical orderings and their relatives such as st-numberings have been used as a key tool in algorithmic graph theory for the last decades. Recently, a unifying concept behind all these orders has been shown: they can be described by a graph decomposition into parts that have a prescribed vertex-connectivity. Despite extensive interest in canonical orderings, no analogue of this unifying concept is known for edge-connectivity. In this paper, we establish such a concept named edge-orders and show how to compute (1,1)-edge-orders of 2-edge-connected graphs as well as (2,1)-edge-orders of 3-edge-connected graphs in linear time, respectively. While the former can be seen as the edge-variants of st-numberings, the latter are the edge-variants of Mondshein sequences and non-separating ear decompositions. The methods that we use for obtaining such edge-orders differ considerably in almost all details from the ones used for their vertex-counterparts, as different graph-theoretic constructions are used in the inductive proof and standard reductions from edge- to vertex-connectivity are bound to fail. As a first application, we consider the famous Edge-Independent Spanning Tree Conjecture, which asserts that every k-edge-connected graph contains k rooted spanning trees that are pairwise edge-independent. We illustrate the impact of the above edge-orders by deducing algorithms that construct 2- and 3-edge independent spanning trees of 2- and 3-edge-connected graphs, the latter of which improves the best known running time from O(n^2) to linear time.
End-to-End Learning for Image Burst Deblurring
Venue: arXiv cs.CV 2016
Year: 2016

We present a neural network model approach for multi-frame blind deconvolution. The discriminative approach adopts and combines two recent techniques for image deblurring into a single neural network architecture. Our proposed hybrid-architecture combines the explicit prediction of a deconvolution filter and non-trivial averaging of Fourier coefficients in the frequency domain. In order to make full use of the information contained in all images in one burst, the proposed network embeds smaller networks, which explicitly allow the model to transfer information between images in early layers. Our system is trained end-to-end using standard backpropagation on a set of artificially generated training examples, enabling competitive performance in multi-frame blind deconvolution, both with respect to quality and runtime.
Online Grammar Compression for Frequent Pattern Discovery
Venue: arXiv cs.DS 2016
Year: 2016

Various grammar compression algorithms have been proposed in the last decade. A grammar compression is a restricted CFG deriving the string deterministically. An efficient grammar compression develops a smaller CFG by finding duplicated patterns and removing them. This process is just a frequent pattern discovery by grammatical inference. While we can get any frequent pattern in linear time using a preprocessed string, a huge working space is required for longer patterns, and the whole string must be loaded into the memory preliminarily. We propose an online algorithm approximating this problem within a compressed space. The main contribution is an improvement of the previously best known approximation ratio $Ω(\frac{1}{\lg^2m})$ to $Ω(\frac{1}{\lg^*N\lg m})$ where $m$ is the length of an optimal pattern in a string of length $N$ and $\lg^*$ is the iteration of the logarithm base $2$. For a sufficiently large $N$, $\lg^*N$ is practically constant. The experimental results show that our algorithm extracts nearly optimal patterns and achieves a significant improvement in memory consumption compared to the offline algorithm.
Multi-body Non-rigid Structure-from-Motion
Venue: arXiv cs.CV 2016
Year: 2016

Conventional structure-from-motion (SFM) research is primarily concerned with the 3D reconstruction of a single, rigidly moving object seen by a static camera, or a static and rigid scene observed by a moving camera --in both cases there are only one relative rigid motion involved. Recent progress have extended SFM to the areas of {multi-body SFM} (where there are {multiple rigid} relative motions in the scene), as well as {non-rigid SFM} (where there is a single non-rigid, deformable object or scene). Along this line of thinking, there is apparently a missing gap of "multi-body non-rigid SFM", in which the task would be to jointly reconstruct and segment multiple 3D structures of the multiple, non-rigid objects or deformable scenes from images. Such a multi-body non-rigid scenario is common in reality (e.g. two persons shaking hands, multi-person social event), and how to solve it represents a natural {next-step} in SFM research. By leveraging recent results of subspace clustering, this paper proposes, for the first time, an effective framework for multi-body NRSFM, which simultaneously reconstructs and segments each 3D trajectory into their respective low-dimensional subspace. Under our formulation, 3D trajectories for each non-rigid structure can be well approximated with a sparse affine combination of other 3D trajectories from the same structure (self-expressiveness). We solve the resultant optimization with the alternating direction method of multipliers (ADMM). We demonstrate the efficacy of the proposed framework through extensive experiments on both synthetic and real data sequences. Our method clearly outperforms other alternative methods, such as first clustering the 2D feature tracks to groups and then doing non-rigid reconstruction in each group or first conducting 3D reconstruction by using single subspace assumption and then clustering the 3D trajectories into groups.
Local Search for Max-Sum Diversification
Venue: arXiv cs.DS 2016
Year: 2016

We provide simple and fast polynomial time approximation schemes (PTASs) for several variants of the max-sum diversification problem which, in its most basic form, is as follows: Given n points p_1,...,p_n in R^d and an integer k, select k points such that the average Euclidean distance between these points is maximized. This problem commonly appears in information retrieval and web-search in order to select a diverse set of points from the input. In this context, it has recently received a lot of attention. We present new techniques to analyze natural local search algorithms. This leads to a (1-O(1/k))-approximation for distances of negative type, even subject to any matroid constraint of rank k, in time O(n k^2 log k), when assuming that distance evaluations and calls to the independence oracle are constant time. Negative type distances include as special cases Euclidean distances and many further natural distances. Our result easily transforms into a PTAS and improves on the only previously known PTAS for this setting, which relies on convex optimization techniques in an n-dimensional space and is impractical for large data sets. In contrast, our procedure has an (optimal) linear dependence on n. Using generalized exchange properties of matroid intersection, we show that a PTAS can be obtained for matroid intersection constraints as well. Moreover, our techniques, being based on local search, are conceptually simple and allow for various extensions. In particular, we get asymptotically optimal O(1)-approximations when combining the classic dispersion function with a monotone submodular objective, which is a very common class of functions to measure diversity and relevance. This result leverages recent advances on local search techniques based on proxy functions to obtain optimal approximations for monotone submodular function maximization subject to a matroid constraint.
Analyzing features learned for Offline Signature Verification using Deep CNNs
Venue: arXiv cs.CV 2016
Year: 2016

Research on Offline Handwritten Signature Verification explored a large variety of handcrafted feature extractors, ranging from graphology, texture descriptors to interest points. In spite of advancements in the last decades, performance of such systems is still far from optimal when we test the systems against skilled forgeries - signature forgeries that target a particular individual. In previous research, we proposed a formulation of the problem to learn features from data (signature images) in a Writer-Independent format, using Deep Convolutional Neural Networks (CNNs), seeking to improve performance on the task. In this research, we push further the performance of such method, exploring a range of architectures, and obtaining a large improvement in state-of-the-art performance on the GPDS dataset, the largest publicly available dataset on the task. In the GPDS-160 dataset, we obtained an Equal Error Rate of 2.74%, compared to 6.97% in the best result published in literature (that used a combination of multiple classifiers). We also present a visual analysis of the feature space learned by the model, and an analysis of the errors made by the classifier. Our analysis shows that the model is very effective in separating signatures that have a different global appearance, while being particularly vulnerable to forgeries that very closely resemble genuine signatures, even if their line quality is bad, which is the case of slowly-traced forgeries.
New version of Gram-Schmidt Process with inverse for Signal and Image Processing
Venue: arXiv cs.CV 2016
Year: 2016

The Gram-Schmidt Process (GSP) is used to convert a non-orthogonal basis (a set of linearly independent vectors, matrices, etc) into an orthonormal basis (a set of orthogonal, unit-length vectors, bi or tri dimensional matrices). The process consists of taking each array and then subtracting the projections in common with the previous arrays. This paper introduces an enhanced version of the Gram-Schmidt Process (EGSP) with inverse, which is useful for Digital Signal and Image Processing, among others applications.
Shesop Healthcare: Android application to monitor heart rate variance, display influenza and stress condition using Polar H7
Venue: arXiv cs.CY 2016
Year: 2016

Shesop is an integrated system to make human lives more easily and to help people in terms of healthcare. Stress and influenza classification is a part of Shesop's application for a healthcare devices such as smartwatch, polar and fitbit. The main objective of this paper is to create a proper application to implement the stress and influenza classification. The application use Android studio, XML and Java. Also, while creating this application, all design and program is considered to be available for future updates. The application needs an android smartphone with Bluetooth Low Energy technology (bluetooth v4.0 or above). SheSop application will accommodate data entry, device picker, data gathering process, result and saving the result. In the end, we could use the polar H7 and this application to get a real-time heart rate, Heart rate variability and diagnose our stress and influenza condition.
Construction of extended 3D field of views of the internal bladder wall surface: a proof of concept
Venue: arXiv cs.CV 2016
Year: 2016

3D extended field of views (FOVs) of the internal bladder wall facilitate lesion diagnosis, patient follow-up and treatment traceability. In this paper, we propose a 3D image mosaicing algorithm guided by 2D cystoscopic video-image registration for obtaining textured FOV mosaics. In this feasibility study, the registration makes use of data from a 3D cystoscope prototype providing, in addition to each small FOV image, some 3D points located on the surface. This proof of concept shows that textured surfaces can be constructed with minimally modified cystoscopes. The potential of the method is demonstrated on numerical and real phantoms reproducing various surface shapes. Pig and human bladder textures are superimposed on phantoms with known shape and dimensions. These data allow for quantitative assessment of the 3D mosaicing algorithm based on the registration of images simulating bladder textures.
Learning to Decode Linear Codes Using Deep Learning
Venue: arXiv cs.IT 2016
Year: 2016

A novel deep learning method for improving the belief propagation algorithm is proposed. The method generalizes the standard belief propagation algorithm by assigning weights to the edges of the Tanner graph. These edges are then trained using deep learning techniques. A well-known property of the belief propagation algorithm is the independence of the performance on the transmitted codeword. A crucial property of our new method is that our decoder preserved this property. Furthermore, this property allows us to learn only a single codeword instead of exponential number of code-words. Improvements over the belief propagation algorithm are demonstrated for various high density parity check codes.
Collision detection or nearest-neighbor search? On the computational bottleneck in sampling-based motion planning
Venue: arXiv cs.RO 2016
Year: 2016

The complexity of nearest-neighbor search dominates the asymptotic running time of many sampling-based motion-planning algorithms. However, collision detection is often considered to be the computational bottleneck in practice. Examining various asymptotically optimal planning algorithms, we characterize settings, which we call NN-sensitive, in which the practical computational role of nearest-neighbor search is far from being negligible, i.e., the portion of running time taken up by nearest-neighbor search is comparable, or sometimes even greater than the portion of time taken up by collision detection. This reinforces and substantiates the claim that motion-planning algorithms could significantly benefit from efficient and possibly specifically-tailored nearest-neighbor data structures. The asymptotic (near) optimality of these algorithms relies on a prescribed connection radius, defining a ball around a configuration $q$, such that $q$ needs to be connected to all other configurations in that ball. To facilitate our study, we show how to adapt this radius to non-Euclidean spaces, which are prevalent in motion planning. This technical result is of independent interest, as it enables to compare the radial-connection approach with the common alternative, namely, connecting each configuration to its $k$ nearest neighbors ($k$-NN). Indeed, as we demonstrate, there are scenarios where using the radial connection scheme, a solution path of a specific cost is produced ten-fold (and more) faster than with $k$-NN.
Inferring solutions of differential equations using noisy multi-fidelity data
Venue: arXiv cs.LG 2016
Year: 2016

For more than two centuries, solutions of differential equations have been obtained either analytically or numerically based on typically well-behaved forcing and boundary conditions for well-posed problems. We are changing this paradigm in a fundamental way by establishing an interface between probabilistic machine learning and differential equations. We develop data-driven algorithms for general linear equations using Gaussian process priors tailored to the corresponding integro-differential operators. The only observables are scarce noisy multi-fidelity data for the forcing and solution that are not required to reside on the domain boundary. The resulting predictive posterior distributions quantify uncertainty and naturally lead to adaptive solution refinement via active learning. This general framework circumvents the tyranny of numerical discretization as well as the consistency and stability issues of time-integration, and is scalable to high-dimensions.
Knowledge Representation on the Web revisited: Tools for Prototype Based Ontologies
Venue: arXiv cs.AI 2016
Year: 2016

In recent years RDF and OWL have become the most common knowledge representation languages in use on the Web, propelled by the recommendation of the W3C. In this paper we present a practical implementation of a different kind of knowledge representation based on Prototypes. In detail, we present a concrete syntax easily and effectively parsable by applications. We also present extensible implementations of a prototype knowledge base, specifically designed for storage of Prototypes. These implementations are written in Java and can be extended by using the implementation as a library. Alternatively, the software can be deployed as such. Further, results of benchmarks for both local and web deployment are presented. This paper augments a research paper, in which we describe the more theoretical aspects of our Prototype system.
A Faster Algorithm for Asymptotic Communication for Omniscience
Venue: arXiv cs.IT 2016
Year: 2016

We propose a modified decomposition algorithm (MDA) to solve the asymptotic communication for omniscience (CO) problem where the communication rates could be real or fractional. By starting with a lower estimation of the minimum sum-rate, the MDA algorithm iteratively updates the estimation by the optimizer of a Dilworth truncation problem until the minimum is reached with a corresponding optimal rate vector. We also propose a fusion method implementation of the coordinate-wise saturation capacity algorithm (CoordSatCapFus) for solving the Dilworth truncation problem, where the minimization is done over a fused user set with a cardinality smaller than the original one. We show that the MDA algorithm is less complex than the existing ones. In addition, we show that the non-asymptotic CO problem, where the communication rates are integral, can be solved by one more call of the CoordSatCapfus algorithm. By choosing a proper linear ordering of the user indices in the MDA algorithm, the optimal rate vector is also the one with the minimum weighted sum-rate.
Robust Automated Human Activity Recognition and its Application to Sleep Research
Venue: arXiv cs.LG 2016
Year: 2016

Human Activity Recognition (HAR) is a powerful tool for understanding human behaviour. Applying HAR to wearable sensors can provide new insights by enriching the feature set in health studies, and enhance the personalisation and effectiveness of health, wellness, and fitness applications. Wearable devices provide an unobtrusive platform for user monitoring, and due to their increasing market penetration, feel intrinsic to the wearer. The integration of these devices in daily life provide a unique opportunity for understanding human health and wellbeing. This is referred to as the "quantified self" movement. The analyses of complex health behaviours such as sleep, traditionally require a time-consuming manual interpretation by experts. This manual work is necessary due to the erratic periodicity and persistent noisiness of human behaviour. In this paper, we present a robust automated human activity recognition algorithm, which we call RAHAR. We test our algorithm in the application area of sleep research by providing a novel framework for evaluating sleep quality and examining the correlation between the aforementioned and an individual's physical activity. Our results improve the state-of-the-art procedure in sleep research by 15 percent for area under ROC and by 30 percent for F1 score on average. However, application of RAHAR is not limited to sleep analysis and can be used for understanding other health problems such as obesity, diabetes, and cardiac diseases.
Stochastic Broadcast Control of Multi-Agent Swarms
Venue: arXiv cs.RO 2016
Year: 2016

We present a model for controlling swarms of mobile agents via broadcast control, assumed to be detected by a random set of agents in the swarm. The agents that detect the control signal become ad-hoc leaders of the swarm. The agents are assumed to be velocity controlled, identical, anonymous, memory-less units with limited capabilities of sensing their neighborhood. Each agent is programmed to behave according to a linear local gathering process, based on the relative position of all its neighbors. The detected exogenous control, which is a desired velocity vector, is added by the leaders to the local gathering control. The graph induced by the agents adjacency is referred to as the visibility graph. We show that for piece-wise constant system parameters and a connected visibility graph, the swarm asymptotically aligns in each time-interval on a line in the direction of the exogenous control signal, and all the agents move with identical speed. These results hold for two models of pairwise influence in the gathering process, uniform and scaled. The impact of the influence model is mostly evident when the visibility graph is incomplete. These results are conditioned by the preservation of the connectedness of the visibility graph. In the second part of the report we analyze sufficient conditions for preserving the connectedness of the visibility graph. We show that if the visibility graph is complete then certain bounds on the control signal suffice to preserve the completeness of the graph. However, when the graph is incomplete, general conditions, independent of the leaders topology, could not be found.
On the likelihood of normalisation in combinatory logic
Venue: arXiv cs.LO 2016
Year: 2016

We present a quantitative basis-independent analysis of combinatory logic. Using a general argument regarding plane binary trees with labelled leaves, we generalise the results of David et al. and Bendkowski et al. to all Turing-complete combinator bases proving, inter alia, that asymptotically almost no combinator is strongly normalising nor typeable. We exploit the structure of recently discovered normal-order reduction grammars showing that for each positive $n$, the set of $\mathbf{S} \mathbf{K}$-combinators reducing in $n$ normal-order reduction steps has positive asymptotic density in the set of all combinators. Our approach is constructive, allowing us to systematically find new asymptotically significant fractions of normalising combinators. We show that the density of normalising combinators cannot be less than $34\%$, improving the previously best lower bound of approximately $3\%$. Finally, we present some super-computer experimental results, conjecturing that the density of normalising combinators is close to $85\%$.
Near-Optimal Induced Universal Graphs for Bounded Degree Graphs
Venue: arXiv cs.DS 2016
Year: 2016

A graph $U$ is an induced universal graph for a family $F$ of graphs if every graph in $F$ is a vertex-induced subgraph of $U$. For the family of all undirected graphs on $n$ vertices Alstrup, Kaplan, Thorup, and Zwick [STOC 2015] give an induced universal graph with $O\!\left(2^{n/2}\right)$ vertices, matching a lower bound by Moon [Proc. Glasgow Math. Assoc. 1965]. Let $k= \lceil D/2 \rceil$. Improving asymptotically on previous results by Butler [Graphs and Combinatorics 2009] and Esperet, Arnaud and Ochem [IPL 2008], we give an induced universal graph with $O\!\left(\frac{k2^k}{k!}n^k \right)$ vertices for the family of graphs with $n$ vertices of maximum degree $D$. For constant $D$, Butler gives a lower bound of $Ω\!\left(n^{D/2}\right)$. For an odd constant $D\geq 3$, Esperet et al. and Alon and Capalbo [SODA 2008] give a graph with $O\!\left(n^{k-\frac{1}{D}}\right)$ vertices. Using their techniques for any (including constant) even values of $D$ gives asymptotically worse bounds than we present. For large $D$, i.e. when $D = Ω\left(\log^3 n\right)$, the previous best upper bound was ${n\choose\lceil D/2\rceil} n^{O(1)}$ due to Adjiashvili and Rotbart [ICALP 2014]. We give upper and lower bounds showing that the size is ${\lfloor n/2\rfloor\choose\lfloor D/2 \rfloor}2^{\pm\tilde{O}\left(\sqrt{D}\right)}$. Hence the optimal size is $2^{\tilde{O}(D)}$ and our construction is within a factor of $2^{\tilde{O}\left(\sqrt{D}\right)}$ from this. The previous results were larger by at least a factor of $2^{Ω(D)}$. As a part of the above, proving a conjecture by Esperet et al., we construct an induced universal graph with $2n-1$ vertices for the family of graphs with max degree $2$. In addition, we give results for acyclic graphs with max degree $2$ and cycle graphs. Our results imply the first labeling schemes that for any $D$ are at most $o(n)$ bits from optimal.