OpenRaiser/Intern-Atlas huggingface dataset:
Subspace based low rank and joint sparse matrix recovery
Venue: arXiv cs.NA 2015
Year: 2015

We consider the recovery of a low rank and jointly sparse matrix from under sampled measurements of its columns. This problem is highly relevant in the recovery of dynamic MRI data with high spatio-temporal resolution, where each column of the matrix corresponds to a frame in the image time series; the matrix is highly low-rank since the frames are highly correlated. Similarly the non-zero locations of the matrix in appropriate transform/frame domains (e.g. wavelet, gradient) are roughly the same in different frame. The superset of the support can be safely assumed to be jointly sparse. Unlike the classical multiple measurement vector (MMV) setup that measures all the snapshots using the same matrix, we consider each snapshot to be measured using a different measurement matrix. We show that this approach reduces the total number of measurements, especially when the rank of the matrix is much smaller than than its sparsity. Our experiments in the context of dynamic imaging shows that this approach is very useful in realizing free breathing cardiac MRI.
Computing Covers Using Prefix Tables
Venue: arXiv cs.DS 2015
Year: 2015

An \emph{indeterminate string} $x = x[1..n]$ on an alphabet $Σ$ is a sequence of nonempty subsets of $Σ$; $x$ is said to be \emph{regular} if every subset is of size one. A proper substring $u$ of regular $x$ is said to be a \emph{cover} of $x$ iff for every $i \in 1..n$, an occurrence of $u$ in $x$ includes $x[i]$. The \emph{cover array} $γ= γ[1..n]$ of $x$ is an integer array such that $γ[i]$ is the longest cover of $x[1..i]$. Fifteen years ago a complex, though nevertheless linear-time, algorithm was proposed to compute the cover array of regular $x$ based on prior computation of the border array of $x$. In this paper we first describe a linear-time algorithm to compute the cover array of regular string $x$ based on the prefix table of $x$. We then extend this result to indeterminate strings.
Merging of Bézier curves with box constraints
Venue: arXiv cs.GR 2015
Year: 2015

In this paper, we present a novel approach to the problem of merging of Bézier curves with respect to the $L_2$-norm. We give illustrative examples to show that the solution of the conventional merging problem may not be suitable for further modification and applications. As in the case of the degree reduction problem, we apply the so-called restricted area approach -- proposed recently in (P. Gospodarczyk, Computer-Aided Design 62 (2015), 143--151) -- to avoid certain defects and make the resulting curve more useful. A method of solving the new problem is based on box-constrained quadratic programming approach.
Parallel-Correctness and Transferability for Conjunctive Queries
Venue: arXiv cs.DB 2015
Year: 2015

A dominant cost for query evaluation in modern massively distributed systems is the number of communication rounds. For this reason, there is a growing interest in single-round multiway join algorithms where data is first reshuffled over many servers and then evaluated in a parallel but communication-free way. The reshuffling itself is specified as a distribution policy. We introduce a correctness condition, called parallel-correctness, for the evaluation of queries w.r.t. a distribution policy. We study the complexity of parallel-correctness for conjunctive queries as well as transferability of parallel-correctness between queries. We also investigate the complexity of transferability for certain families of distribution policies, including, for instance, the Hypercube distribution.
Finite Element Method Based Modeling of Cardiac Deformation Estimation under Abnormal Ventricular Muscle Conditions
Venue: arXiv cs.CE 2015
Year: 2015

Deformation modeling of cardiac muscle is an important issue in the field of cardiac analysis. Many approaches have been developed to better estimate the cardiac muscle deformation, and to obtain a practical model to be used in diagnostic procedures. But there are some conditions, like in case of myocardial infarction, in which the regular modeling approaches are not useful. In this article, using a point-wise approach, we try to estimate the deformation under some abnormal conditions of cardiac muscle. First, the endocardial and epicardial contour points are ordered with respect to the center of gravity of the endocardial contour and displacement vectors of boundary points are extracted. Then to solve the governing equations of the deformation, which is an elliptic equation, we apply boundary conditions in accordance with the computed displacement vectors and then the Finite Element method (FEM) will be used to solve the governing equations. Using the obtained displacement field of the cardiac muscle, strain map is extracted to show the mechanical behavior of the cardiac muscle. Several tests are conducted using phantom and real cardiac data in order to show the validity of the proposed method.
GPTIPS 2: an open-source software platform for symbolic data mining
Venue: arXiv cs.MS 2015
Year: 2015

GPTIPS is a free, open source MATLAB based software platform for symbolic data mining (SDM). It uses a multigene variant of the biologically inspired machine learning method of genetic programming (MGGP) as the engine that drives the automatic model discovery process. Symbolic data mining is the process of extracting hidden, meaningful relationships from data in the form of symbolic equations. In contrast to other data-mining methods, the structural transparency of the generated predictive equations can give new insights into the physical systems or processes that generated the data. Furthermore, this transparency makes the models very easy to deploy outside of MATLAB. The rationale behind GPTIPS is to reduce the technical barriers to using, understanding, visualising and deploying GP based symbolic models of data, whilst at the same time remaining highly customisable and delivering robust numerical performance for power users. In this chapter, notable new features of the latest version of the software are discussed with these aims in mind. Additionally, a simplified variant of the MGGP high level gene crossover mechanism is proposed. It is demonstrated that the new functionality of GPTIPS 2 (a) facilitates the discovery of compact symbolic relationships from data using multiple approaches, e.g. using novel gene-centric visualisation analysis to mitigate horizontal bloat and reduce complexity in multigene symbolic regression models (b) provides numerous methods for visualising the properties of symbolic models (c) emphasises the generation of graphically navigable libraries of models that are optimal in terms of the Pareto trade off surface of model performance and complexity and (d) expedites real world applications by the simple, rapid and robust deployment of symbolic models outside the software environment they were developed in.
Equations over free inverse monoids with idempotent variables
Venue: arXiv cs.LO 2015
Year: 2015

We introduce the notion of idempotent variables for studying equations in inverse monoids. It is proved that it is decidable in singly exponential time (DEXPTIME) whether a system of equations in idempotent variables over a free inverse monoid has a solution. The result is proved by a direct reduction to solve language equations with one-sided concatenation and a known complexity result by Baader and Narendran: Unification of concept terms in description logics, 2001. We also show that the problem becomes DEXPTIME hard , as soon as the quotient group of the free inverse monoid has rank at least two. Decidability for systems of typed equations over a free inverse monoid with one irreducible variable and at least one unbalanced equation is proved with the same complexity for the upper bound. Our results improve known complexity bounds by Deis, Meakin, and Senizergues: Equations in free inverse monoids, 2007. Our results also apply to larger families of equations where no decidability has been previously known.
A Robust Regression Approach for Background/Foreground Segmentation
Venue: arXiv cs.CV 2015
Year: 2015

Background/foreground segmentation has a lot of applications in image and video processing. In this paper, a segmentation algorithm is proposed which is mainly designed for text and line extraction in screen content. The proposed method makes use of the fact that the background in each block is usually smoothly varying and can be modeled well by a linear combination of a few smoothly varying basis functions, while the foreground text and graphics create sharp discontinuity. The algorithm separates the background and foreground pixels by trying to fit pixel values in the block into a smooth function using a robust regression method. The inlier pixels that can fit well will be considered as background, while remaining outlier pixels will be considered foreground. This algorithm has been extensively tested on several images from HEVC standard test sequences for screen content coding, and is shown to have superior performance over other methods, such as the k-means clustering based segmentation algorithm in DjVu. This background/foreground segmentation can be used in different applications such as: text extraction, separate coding of background and foreground for compression of screen content and mixed content documents, principle line extraction from palmprint and crease detection in fingerprint images.
The Expressive Power of DL-Lite
Venue: arXiv cs.LO 2015
Year: 2015

Description logics are knowledge representation formalisms that provide the formal underpinning of the semantic web and in particular of the $\text{OWL}$ Ontology Web Language. In this paper we investigate the expressive power of logic $\text{DL-Lite}_{R,\sqcap}$, and some of its computational properties. We rely on simulations to characterize the absolute expressive power of $\text{DL-Lite}_{R,\sqcap}$ as a concept language, and to show that disjunction is not expressible. We also show that no simulation-based closure property exists for $\text{DL-Lite}_{R,\sqcap}$ assertions. Finally, we show that query answering of unions of conjunctive queries is $\text{NP-complete}$.
Minimizing the Number of Matching Queries for Object Retrieval
Venue: arXiv cs.CV 2015
Year: 2015

To increase the computational efficiency of interest-point based object retrieval, researchers have put remarkable research efforts into improving the efficiency of kNN-based feature matching, pursuing to match thousands of features against a database within fractions of a second. However, due to the high-dimensional nature of image features that reduces the effectivity of index structures (curse of dimensionality), due to the vast amount of features stored in image databases (images are often represented by up to several thousand features), this ultimate goal demanded to trade query runtimes for query precision. In this paper we address an approach complementary to indexing in order to improve the runtimes of retrieval by querying only the most promising keypoint descriptors, as this affects matching runtimes linearly and can therefore lead to increased efficiency. As this reduction of kNN queries reduces the number of tentative correspondences, a loss of query precision is minimized by an additional image-level correspondence generation stage with a computational performance independent of the underlying indexing structure. We evaluate such an adaption of the standard recognition pipeline on a variety of datasets using both SIFT and state-of-the-art binary descriptors. Our results suggest that decreasing the number of queried descriptors does not necessarily imply a reduction in the result quality as long as alternative ways of increasing query recall (by thoroughly selecting k) and MAP (using image-level correspondence generation) are considered.
Incorporating Both Distributional and Relational Semantics in Word Representations
Venue: arXiv cs.CL 2015
Year: 2015

We investigate the hypothesis that word representations ought to incorporate both distributional and relational semantics. To this end, we employ the Alternating Direction Method of Multipliers (ADMM), which flexibly optimizes a distributional objective on raw text and a relational objective on WordNet. Preliminary results on knowledge base completion, analogy tests, and parsing show that word representations trained on both objectives can give improvements in some cases.
Robust Cooperative Spectrum Sensing Scheduling Optimization in Multi-Channel Dynamic Spectrum Access Networks
Venue: arXiv cs.IT 2015
Year: 2015

Dynamic spectrum access (DSA) enables secondary networks to find and efficiently exploit spectrum opportunities. A key factor to design a DSA network is the spectrum sensing algorithms for multiple channels with multiple users. Multi-user cooperative channel sensing reduces the sensing time, and thus it increases transmission throughput. However, in a multi-channel system, the problem becomes more complex since the benefits of assigning users to sense channels in parallel must also be considered. A sensing schedule, indicating to each user the channel that it should sense at different sensing moments, must be thus created to optimize system performance. In this paper, we formulate the general sensing scheduling optimization problem and then propose several sensing strategies to schedule the users according to network parameters with homogeneous sensors. Later on we extend the results to heterogeneous sensors and propose a robust scheduling design when we have traffic and channel uncertainty. We propose three sensing strategies, and, within each one of them, several solutions, striking a balance between throughput performance and computational complexity, are proposed. In addition, we show that a sequential channel sensing strategy is the one to be preferred when the sensing time is small, the number of channels is large, and the number of users is small. For all the other cases, a parallel channel sensing strategy is recommended in terms of throughput performance. We also show that a proposed hybrid sequential-parallel channel sensing strategy achieves the best performance in all scenarios at the cost of extra memory and computation complexity.
Point Process-based Monte Carlo estimation
Venue: arXiv cs.CE 2015
Year: 2015

This paper addresses the issue of estimating the expectation of a real-valued random variable of the form $X = g(\mathbf{U})$ where $g$ is a deterministic function and $\mathbf{U}$ can be a random finite- or infinite-dimensional vector. Using recent results on rare event simulation, we propose a unified framework for dealing with both probability and mean estimation for such random variables, \emph{i.e.} linking algorithms such as Tootsie Pop Algorithm (TPA) or Last Particle Algorithm with nested sampling. Especially, it extends nested sampling as follows: first the random variable $X$ does not need to be bounded any more: it gives the principle of an ideal estimator with an infinite number of terms that is unbiased and always better than a classical Monte Carlo estimator -- in particular it has a finite variance as soon as there exists $k \in \mathbb{R} > 1$ such that $\operatorname{E}[X^k] < \infty$. Moreover we address the issue of nested sampling termination and show that a random truncation of the sum can preserve unbiasedness while increasing the variance only by a factor up to 2 compared to the ideal case. We also build an unbiased estimator with fixed computational budget which supports a Central Limit Theorem and discuss parallel implementation of nested sampling, which can dramatically reduce its computational cost. Finally we extensively study the case where $X$ is heavy-tailed.
Educational Technology as Seen Through the Eyes of the Readers
Venue: arXiv cs.DL 2015
Year: 2015

In this paper, I present the evaluation of a novel knowledge domain visualization of educational technology. The interactive visualization is based on readership patterns in the online reference management system Mendeley. It comprises of 13 topic areas, spanning psychological, pedagogical, and methodological foundations, learning methods and technologies, and social and technological developments. The visualization was evaluated with (1) a qualitative comparison to knowledge domain visualizations based on citations, and (2) expert interviews. The results show that the co-readership visualization is a recent representation of pedagogical and psychological research in educational technology. Furthermore, the co-readership analysis covers more areas than comparable visualizations based on co-citation patterns. Areas related to computer science, however, are missing from the co-readership visualization and more research is needed to explore the interpretations of size and placement of research areas on the map.
Empirically Estimable Classification Bounds Based on a New Divergence Measure
Venue: arXiv cs.IT 2015
Year: 2015

Information divergence functions play a critical role in statistics and information theory. In this paper we show that a non-parametric f-divergence measure can be used to provide improved bounds on the minimum binary classification probability of error for the case when the training and test data are drawn from the same distribution and for the case where there exists some mismatch between training and test distributions. We confirm the theoretical results by designing feature selection algorithms using the criteria from these bounds and by evaluating the algorithms on a series of pathological speech classification tasks.
Planar lower envelope of monotone polygonal chains
Venue: arXiv cs.CG 2015
Year: 2015

A simple linear search algorithm running in $O(n+mk)$ time is proposed for constructing the lower envelope of $k$ vertices from $m$ monotone polygonal chains in 2D with $n$ vertices in total. This can be applied to output-sensitive construction of lower envelopes for arbitrary line segments in optimal $O(n\log k)$ time, where $k$ is the output size. Compared to existing output-sensitive algorithms for lower envelopes, this is simpler to implement, does not require complex data structures, and is a constant factor faster.
Incremental Adaptation Strategies for Neural Network Language Models
Venue: arXiv cs.NE 2015
Year: 2015

It is today acknowledged that neural network language models outperform backoff language models in applications like speech recognition or statistical machine translation. However, training these models on large amounts of data can take several days. We present efficient techniques to adapt a neural network language model to new data. Instead of training a completely new model or relying on mixture approaches, we propose two new methods: continued training on resampled data or insertion of adaptation layers. We present experimental results in an CAT environment where the post-edits of professional translators are used to improve an SMT system. Both methods are very fast and achieve significant improvements without overfitting the small adaptation data.
Visualizing the Invisible Hand of Markets: Simulating complex dynamic economic interactions
Venue: arXiv cs.MA 2015
Year: 2015

In complex systems, many different parts interact in non-obvious ways. Traditional research focuses on a few or a single aspect of the problem so as to analyze it with the tools available. To get a better insight of phenomena that emerge from complex interactions, we need instruments that can analyze simultaneously complex interactions between many parts. Here, a simulator modeling different types of economies, is used to visualize complex quantitative aspects that affect economic dynamics. The main conclusions are: 1- Relatively simple economic settings produce complex non-linear dynamics and therefore linear regressions are often unsuitable to capture complex economic dynamics; 2- Flexible pricing of goods by individual agents according to their micro-environment increases the health and wealth of the society, but asymmetries in price sensitivity between buyers and sellers increase price inflation; 3- Prices for goods conferring risky long term benefits are not tracked efficiently by simple market forces. 4- Division of labor creates synergies that improve enormously the health and wealth of the society by increasing the efficiency of economic activity. 5- Stochastic modeling improves our understanding of real economies, and didactic games based on them might help policy makers and non specialists in grasping the complex dynamics underlying even simple economic settings.
Language Recognition using Random Indexing
Venue: arXiv cs.CL 2015
Year: 2015

Random Indexing is a simple implementation of Random Projections with a wide range of applications. It can solve a variety of problems with good accuracy without introducing much complexity. Here we use it for identifying the language of text samples. We present a novel method of generating language representation vectors using letter blocks. Further, we show that the method is easily implemented and requires little computational power and space. Experiments on a number of model parameters illustrate certain properties about high dimensional sparse vector representations of data. Proof of statistically relevant language vectors are shown through the extremely high success of various language recognition tasks. On a difficult data set of 21,000 short sentences from 21 different languages, our model performs a language recognition task and achieves 97.8% accuracy, comparable to state-of-the-art methods.
Short-Packet Communications over Multiple-Antenna Rayleigh-Fading Channels
Venue: arXiv cs.IT 2015
Year: 2015

Motivated by the current interest in ultra-reliable, low-latency, machine-type communication systems, we investigate the tradeoff between reliability, throughput, and latency in the transmission of information over multiple-antenna Rayleigh block-fading channels. Specifically, we obtain finite-blocklength, finite-SNR upper and lower bounds on the maximum coding rate achievable over such channels for a given constraint on the packet error probability. Numerical evidence suggests that our bounds delimit tightly the maximum coding rate already for short blocklengths (packets of about 100 symbols). Furthermore, our bounds reveal the existence of a tradeoff between the rate gain obtainable by spreading each codeword over all available time-frequency-spatial degrees of freedom, and the rate loss caused by the need of estimating the fading coefficients over these degrees of freedom. In particular, our bounds allow us to determine the optimal number of transmit antennas and the optimal number of time-frequency diversity branches that maximize the rate. Finally, we show that infinite-blocklength performance metrics such as the ergodic capacity and the outage capacity yield inaccurate throughput estimates.
An Effective Semi-supervised Divisive Clustering Algorithm
Venue: arXiv cs.LG 2015
Year: 2015

Nowadays, data are generated massively and rapidly from scientific fields as bioinformatics, neuroscience and astronomy to business and engineering fields. Cluster analysis, as one of the major data analysis tools, is therefore more significant than ever. We propose in this work an effective Semi-supervised Divisive Clustering algorithm (SDC). Data points are first organized by a minimal spanning tree. Next, this tree structure is transitioned to the in-tree structure, and then divided into sub-trees under the supervision of the labeled data, and in the end, all points in the sub-trees are directly associated with specific cluster centers. SDC is fully automatic, non-iterative, involving no free parameter, insensitive to noise, able to detect irregularly shaped cluster structures, applicable to the data sets of high dimensionality and different attributes. The power of SDC is demonstrated on several datasets.