OpenRaiser/Intern-Atlas huggingface dataset:
The limited blessing of low dimensionality: when $1-1/d$ is the best possible exponent for $d$-dimensional geometric problems
Venue: arXiv cs.DS 2016
Year: 2016

We are studying $d$-dimensional geometric problems that have algorithms with $1-1/d$ appearing in the exponent of the running time, for example, in the form of $2^{n^{1-1/d}}$ or $n^{k^{1-1/d}}$. This means that these algorithms perform somewhat better in low dimensions, but the running time is almost the same r all large values $d$ of the dimension. Our main result is showing that for some of these problems the dependence on $1-1/d$ is best possible under a standard complexity assumption. We show that, assuming the Exponential Time Hypothesis, --- $d$-dimensional Euclidean TSP on $n$ points cannot be solved in time $2^{O(n^{1-1/d-ε})}$ for any $ε>0$, and --- the problem of finding a set of $k$ pairwise nonintersecting $d$-dimensional unit balls/axis parallel unit cubes cannot be solved in time $f(k)n^{o(k^{1-1/d})}$ for any computable function $f$. These lower bounds essentially match the known algorithms for these problems. To obtain these results, we first prove lower bounds on the complexity of Constraint Satisfaction Problems (CSPs) whose constraint graphs are $d$-dimensional grids. We state the complexity results on CSPs in a way to make them convenient starting points for problem-specific reductions to particular $d$-dimensional geometric problems and to be reusable in the future for further results of similar flavor.
Adaptive Work-Efficient Connected Components on the GPU
Venue: arXiv cs.DC 2016
Year: 2016

This report presents an adaptive work-efficient approach for implementing the Connected Components algorithm on GPUs. The results show a considerable increase in performance (up to 6.8$\times$) over current state-of-the-art solutions.
Vector Approximate Message Passing for the Generalized Linear Model
Venue: arXiv cs.IT 2016
Year: 2016

The generalized linear model (GLM), where a random vector $\boldsymbol{x}$ is observed through a noisy, possibly nonlinear, function of a linear transform output $\boldsymbol{z}=\boldsymbol{Ax}$, arises in a range of applications such as robust regression, binary classification, quantized compressed sensing, phase retrieval, photon-limited imaging, and inference from neural spike trains. When $\boldsymbol{A}$ is large and i.i.d. Gaussian, the generalized approximate message passing (GAMP) algorithm is an efficient means of MAP or marginal inference, and its performance can be rigorously characterized by a scalar state evolution. For general $\boldsymbol{A}$, though, GAMP can misbehave. Damping and sequential-updating help to robustify GAMP, but their effects are limited. Recently, a "vector AMP" (VAMP) algorithm was proposed for additive white Gaussian noise channels. VAMP extends AMP's guarantees from i.i.d. Gaussian $\boldsymbol{A}$ to the larger class of rotationally invariant $\boldsymbol{A}$. In this paper, we show how VAMP can be extended to the GLM. Numerical experiments show that the proposed GLM-VAMP is much more robust to ill-conditioning in $\boldsymbol{A}$ than damped GAMP.
Gaussian Process Model Predictive Control of Unknown Nonlinear Systems
Venue: arXiv cs.SY 2016
Year: 2016

Model Predictive Control (MPC) of an unknown system that is modelled by Gaussian Process (GP) techniques is studied in this paper. Using GP, the variances computed during the modelling and inference processes allow us to take model uncertainty into account. The main issue in using MPC to control systems modelled by GP is the propagation of such uncertainties within the control horizon. In this paper, two approaches to solve this problem, called GPMPC1 and GPMPC2, are proposed. With GPMPC1, the original Stochastic Model Predictive Control (SMPC) problem is relaxed to a deterministic nonlinear MPC based on a basic linearized GP local model. The resulting optimization problem, though non-convex, can be solved by the Sequential Quadratic Programming (SQP). By incorporating the model variance into the state vector, an extended local model is derived. This model allows us to relax the non-convex MPC problem to a convex one which can be solved by an active-set method efficiently. The performance of both approaches is demonstrated by applying them to two trajectory tracking problems. Results show that both GPMPC1 and GPMPC2 produce effective controls but GPMPC2 is much more efficient computationally.
Deep Pyramidal Residual Networks with Separated Stochastic Depth
Venue: arXiv cs.CV 2016
Year: 2016

On general object recognition, Deep Convolutional Neural Networks (DCNNs) achieve high accuracy. In particular, ResNet and its improvements have broken the lowest error rate records. In this paper, we propose a method to successfully combine two ResNet improvements, ResDrop and PyramidNet. We confirmed that the proposed network outperformed the conventional methods; on CIFAR-100, the proposed network achieved an error rate of 16.18% in contrast to PiramidNet achieving that of 18.29% and ResNeXt 17.31%.
Cancerous Nuclei Detection and Scoring in Breast Cancer Histopathological Images
Venue: arXiv cs.CV 2016
Year: 2016

Early detection and prognosis of breast cancer are feasible by utilizing histopathological grading of biopsy specimens. This research is focused on detection and grading of nuclear pleomorphism in histopathological images of breast cancer. The proposed method consists of three internal steps. First, unmixing colors of H&E is used in the preprocessing step. Second, nuclei boundaries are extracted incorporating the center of cancerous nuclei which are detected by applying morphological operations and Difference of Gaussian filter on the preprocessed image. Finally, segmented nuclei are scored to accomplish one parameter of the Nottingham grading system for breast cancer. In this approach, the nuclei area, chromatin density, contour regularity, and nucleoli presence, are features for nuclear pleomorphism scoring. Experimental results showed that the proposed algorithm, with an accuracy of 86.6%, made significant advancement in detecting cancerous nuclei compared to existing methods in the related literature.
Deep Symbolic Representation Learning for Heterogeneous Time-series Classification
Venue: arXiv cs.LG 2016
Year: 2016

In this paper, we consider the problem of event classification with multi-variate time series data consisting of heterogeneous (continuous and categorical) variables. The complex temporal dependencies between the variables combined with sparsity of the data makes the event classification problem particularly challenging. Most state-of-art approaches address this either by designing hand-engineered features or breaking up the problem over homogeneous variates. In this work, we propose and compare three representation learning algorithms over symbolized sequences which enables classification of heterogeneous time-series data using a deep architecture. The proposed representations are trained jointly along with the rest of the network architecture in an end-to-end fashion that makes the learned features discriminative for the given task. Experiments on three real-world datasets demonstrate the effectiveness of the proposed approaches.
On the Capacity of Discrete-Time Laguerre Channel
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, new upper and lower bounds are proposed for the capacity of discrete-time Laguerre channel. Laguerre behavior is used to model various types of optical systems and networks such as optical amplifiers, short distance visible light communication systems with direct detection and coherent code division multiple access (CDMA) networks. Bounds are derived for short distance visible light communication systems and coherent CDMA networks. These bounds are separated in three main cases: when both average and peak power constraints are imposed, when peak power constraint is inactive and when only peak power constraint is active.
Building Code with Dynamic Staging
Venue: arXiv cs.PL 2016
Year: 2016

When creating a new domain-specific language (DSL) it is common to embed it as a part of a flexible host language, rather than creating it entirely from scratch. The semantics of an embedded DSL (EDSL) is either given directly as a set of functions (shallow embedding), or an AST is constructed that is later processed (deep embedding). Typically, the deep embedding is used when the EDSL specifies domain-specific optimizations (DSO) in a form of AST transformations. In this paper we show that deep embedding is not necessary to specify most optimizations. We define language semantics as action functions that are executed during parsing. These actions build incrementally a new, arbitrary complex program function. The EDSL designer is able to specify many aspects of the semantics as a runnable code, such as variable scoping rules, custom type checking, arbitrary control flow structures, or DSO. A sufficiently powerful staging mechanism helps assembling the code from different actions, as well as evaluate the semantics in arbitrarily many stages. In the end, we obtain code that is as efficient as one written by hand. We never create any object representation of the code. No external traversing algorithm is used to process the code. All program fragments are functions with their entire semantics embedded within the function bodies. This approach allows reusing the code between EDSL and the host language, as well as combining actions of many different EDSLs.
Consensus analysis of large-scale nonlinear homogeneous multi-agent formations with polynomial dynamics
Venue: arXiv cs.SY 2016
Year: 2016

Drawing inspiration from the theory of linear "decomposable systems", we provide a method, based on linear matrix inequalities (LMIs), which makes it possible to prove the convergence (or consensus) of a set of interacting agents with polynomial dynamic. We also show that the use of a generalised version of the famous Kalman-Yakubovic-Popov lemma allows the development of an LMI test whose size does not depend on the number of agents. The method is validated experimentally on two academic examples.
A Distance Function for Comparing Straight-Edge Geometric Figures
Venue: arXiv cs.CV 2016
Year: 2016

This paper defines a distance function that measures the dissimilarity between planar geometric figures formed with straight lines. This function can in turn be used in partial matching of different geometric figures. For a given pair of geometric figures that are graphically isomorphic, one function measures the angular dissimilarity and another function measures the edge length disproportionality. The distance function is then defined as the convex sum of these two functions. The novelty of the presented function is that it satisfies all properties of a distance function and the computation of the same is done by projecting appropriate features to a cartesian plane. To compute the deviation from the angular similarity property, the Euclidean distance between the given angular pairs and the corresponding points on the $y=x$ line is measured. Further while computing the deviation from the edge length proportionality property, the best fit line, for the set of edge lengths, which passes through the origin is found, and the Euclidean distance between the given edge length pairs and the corresponding point on a $y=mx$ line is calculated. Iterative Proportional Fitting Procedure (IPFP) is used to find this best fit line. We demonstrate the behavior of the defined function for some sample pairs of figures.
Three practical field normalised alternative indicator formulae for research evaluation
Venue: arXiv cs.DL 2016
Year: 2016

Although altmetrics and other web-based alternative indicators are now commonplace in publishers' websites, they can be difficult for research evaluators to use because of the time or expense of the data, the need to benchmark in order to assess their values, the high proportion of zeros in some alternative indicators, and the time taken to calculate multiple complex indicators. These problems are addressed here by (a) a field normalisation formula, the Mean Normalised Log-transformed Citation Score (MNLCS) that allows simple confidence limits to be calculated and is similar to a proposal of Lundberg, (b) field normalisation formulae for the proportion of cited articles in a set, the Equalised Mean-based Normalised Proportion Cited (EMNPC) and the Mean-based Normalised Proportion Cited (MNPC), to deal with mostly uncited data sets, (c) a sampling strategy to minimise data collection costs, and (d) free unified software to gather the raw data, implement the sampling strategy, and calculate the indicator formulae and confidence limits. The approach is demonstrated (but not fully tested) by comparing the Scopus citations, Mendeley readers and Wikipedia mentions of research funded by Wellcome, NIH, and MRC in three large fields for 2013-2016. Within the results, statistically significant differences in both citation counts and Mendeley reader counts were found even for sets of articles that were less than six months old. Mendeley reader counts were more precise than Scopus citations for the most recent articles and all three funders could be demonstrated to have an impact in Wikipedia that was significantly above the world average.
ROAM: a Rich Object Appearance Model with Application to Rotoscoping
Venue: arXiv cs.CV 2016
Year: 2016

Rotoscoping, the detailed delineation of scene elements through a video shot, is a painstaking task of tremendous importance in professional post-production pipelines. While pixel-wise segmentation techniques can help for this task, professional rotoscoping tools rely on parametric curves that offer the artists a much better interactive control on the definition, editing and manipulation of the segments of interest. Sticking to this prevalent rotoscoping paradigm, we propose a novel framework to capture and track the visual aspect of an arbitrary object in a scene, given a first closed outline of this object. This model combines a collection of local foreground/background appearance models spread along the outline, a global appearance model of the enclosed object and a set of distinctive foreground landmarks. The structure of this rich appearance model allows simple initialization, efficient iterative optimization with exact minimization at each step, and on-line adaptation in videos. We demonstrate qualitatively and quantitatively the merit of this framework through comparisons with tools based on either dynamic segmentation with a closed curve or pixel-wise binary labelling.
Technology Beats Algorithms (in Exact String Matching)
Venue: arXiv cs.DS 2016
Year: 2016

More than 120 algorithms have been developed for exact string matching within the last 40 years. We show by experiments that the \naive{} algorithm exploiting SIMD instructions of modern CPUs (with symbols compared in a special order) is the fastest one for patterns of length up to about 50 symbols and extremely good for longer patterns and small alphabets. The algorithm compares 16 or 32 characters in parallel by applying SSE2 or AVX2 instructions, respectively. Moreover, it uses loop peeling to further speed up the searching phase. We tried several orders for comparisons of pattern symbols and the increasing order of their probabilities in the text was the best.
MIMO Secret Communications Against an Active Eavesdropper
Venue: arXiv cs.IT 2016
Year: 2016

This paper considers a scenario in which an Alice-Bob pair wishes to communicate in secret in the presence of an active Eve, who is capable of jamming as well as eavesdropping in Full-Duplex (FD) mode. As countermeasure, Bob also operates in FD mode, using a subset of its antennas to act as receiver, and the remaining antennas to act as jammer and transmit noise. With a goal to maximize the achievable secrecy degrees of freedom (S.D.o.F.) of the system, we provide the optimal transmit/receive antennas allocation at Bob, based on which we determine in closed form the maximum achievable S.D.o.F.. We further investigate the adverse scenario in which Eve knows Bob's transmission strategy and optimizes its transmit/receive antennas allocation in order to minimize the achievable S.D.o.F.. For that case we find the worst-case achievable S.D.o.F.. We also provide a method for constructing the precoding matrices of Alice and Bob, based on which the maximum S.D.o.F. can be achieved. Numerical results validate the theoretical findings and demonstrate the performance of the proposed method in realistic settings.
High-Bandwidth and Large Coupling Tolerance Graded-Index Multimode Polymer Waveguides for On-board High-Speed Optical Interconnects
Venue: arXiv cs.ET 2016
Year: 2016

Optical interconnects have attracted significant research interest for use in short-reach board-level optical communication links in supercomputers and data centres. Multimode polymer waveguides in particular constitute an attractive technology for on-board optical interconnects as they provide high bandwidth, offer relaxed alignment tolerances, and can be cost-effectively integrated onto standard printed circuit boards (PCBs). However, the continuing improvements in bandwidth performance of optical sources make it important to investigate approaches to develop high bandwidth polymer waveguides. In this paper, we present dispersion studies on a graded-index (GI) waveguide in siloxane materials designed to deliver high bandwidth over a range of launch conditions. Bandwidth-length products of >70 GHzxm and ~65 GHzxm are observed using a 50/125 um multimode fibre (MMF) launch for input offsets of +/- 10 um without and with the use of a mode mixer respectively; and enhanced values of >100 GHzxm are found under a 10x microscope objective launch for input offsets of ~18 x 20 um^2. The large range of offsets is within the -1 dB alignment tolerances. A theoretical model is developed using the measured refractive index profile of the waveguide, and general agreement is found with experimental bandwidth measurements. The reported results clearly demonstrate the potential of this technology for use in high-speed board-level optical links, and indicate that data transmission of 100 Gb/s over a multimode polymer waveguide is feasible with appropriate refractive index engineering.
A One-Field Monolithic Fictitious Domain Method for Fluid-Structure Interactions
Venue: arXiv cs.CE 2016
Year: 2016

In this article, we present a one-field monolithic fictitious domain (FD) method for simulation of general fluid-structure interactions (FSI). One-field means only one velocity field is solved in the whole domain, based upon the use of an appropriate L2 projection. Monolithic means the fluid and solid equations are solved synchronously (rather than sequentially). We argue that the proposed method has the same generality and robustness as FD methods with distributed Lagrange multiplier (DLM) but is significantly more computationally efficient (because of one-field) whilst being very straightforward to implement. The method is described in detail, followed by the presentation of multiple computational examples in order to validate it across a wide range of fluid and solid parameters and interactions.
Type Annotation for Adaptive Systems
Venue: arXiv cs.SE 2016
Year: 2016

We introduce type annotations as a flexible typing mechanism for graph systems and discuss their advantages with respect to classical typing based on graph morphisms. In this approach the type system is incorporated with the graph and elements can adapt to changes in context by changing their type annotations. We discuss some case studies in which this mechanism is relevant.
An EMOF-Compliant Abstract Syntax for Bigraphs
Venue: arXiv cs.SE 2016
Year: 2016

Bigraphs are an emerging modeling formalism for structures in ubiquitous computing. Besides an algebraic notation, which can be adopted to provide an algebraic syntax for bigraphs, the bigraphical theory introduces a visual concrete syntax which is intuitive and unambiguous at the same time; the standard visual notation can be customized and thus tailored to domain-specific requirements. However, in contrast to modeling standards based on the Meta-Object Facility (MOF) and domain-specific languages typically used in model-driven engineering (MDE), the bigraphical theory lacks a precise definition of an abstract syntax for bigraphical modeling languages. As a consequence, available modeling and analysis tools use proprietary formats for representing bigraphs internally and persistently, which hampers the exchange of models across tool boundaries. Moreover, tools can be hardly integrated with standard MDE technologies in order to build sophisticated tool chains and modeling environments, as required for systematic engineering of large systems or fostering experimental work to evaluate the bigraphical theory in real-world applications. To overcome this situation, we propose an abstract syntax for bigraphs which is compliant to the Essential MOF (EMOF) standard defined by the Object Management Group (OMG). We use typed graphs as a formal underpinning of EMOF-based models and present a canonical mapping which maps bigraphs to typed graphs in a natural way. We also discuss application-specific variation points in the graph-based representation of bigraphs. Following standard techniques from software product line engineering, we present a framework to customize the graph-based representation to support a variety of application scenarios.
Fine-grained Recurrent Neural Networks for Automatic Prostate Segmentation in Ultrasound Images
Venue: arXiv cs.CV 2016
Year: 2016

Boundary incompleteness raises great challenges to automatic prostate segmentation in ultrasound images. Shape prior can provide strong guidance in estimating the missing boundary, but traditional shape models often suffer from hand-crafted descriptors and local information loss in the fitting procedure. In this paper, we attempt to address those issues with a novel framework. The proposed framework can seamlessly integrate feature extraction and shape prior exploring, and estimate the complete boundary with a sequential manner. Our framework is composed of three key modules. Firstly, we serialize the static 2D prostate ultrasound images into dynamic sequences and then predict prostate shapes by sequentially exploring shape priors. Intuitively, we propose to learn the shape prior with the biologically plausible Recurrent Neural Networks (RNNs). This module is corroborated to be effective in dealing with the boundary incompleteness. Secondly, to alleviate the bias caused by different serialization manners, we propose a multi-view fusion strategy to merge shape predictions obtained from different perspectives. Thirdly, we further implant the RNN core into a multiscale Auto-Context scheme to successively refine the details of the shape prediction map. With extensive validation on challenging prostate ultrasound images, our framework bridges severe boundary incompleteness and achieves the best performance in prostate boundary delineation when compared with several advanced methods. Additionally, our approach is general and can be extended to other medical image segmentation tasks, where boundary incompleteness is one of the main challenges.