OpenRaiser/Intern-Atlas huggingface dataset:
Robust Regression For Image Binarization Under Heavy Noises and Nonuniform Background
Venue: arXiv cs.CV 2017
Year: 2017

This paper presents a robust regression approach for image binarization under significant background variations and observation noises. The work is motivated by the need of identifying foreground regions in noisy microscopic image or degraded document images, where significant background variation and severe noise make an image binarization challenging. The proposed method first estimates the background of an input image, subtracts the estimated background from the input image, and apply a global thresholding to the subtracted outcome for achieving a binary image of foregrounds. A robust regression approach was proposed to estimate the background intensity surface with minimal effects of foreground intensities and noises, and a global threshold selector was proposed on the basis of a model selection criterion in a sparse regression. The proposed approach was validated using 26 test images and the corresponding ground truths, and the outcomes of the proposed work were compared with those from nine existing image binarization methods. The approach was also combined with three state-of-the-art morphological segmentation methods to show how the proposed approach can improve their image segmentation outcomes.
Availability-Aware Cell Association for Hybrid Power Supply Networks with Adaptive Bias
Venue: arXiv cs.IT 2017
Year: 2017

New challenges have emerged from the integration of renewable energy sources within the conventional electrical grid which powers base stations (BS). Energy-aware traffic offloading brings a promising solution to maintain the user performance while reducing the carbon footprint. Focusing on downlink cellular networks consisting of on-grid, off-grid and hybrid BSs, we propose a novel power-aware biased cell association where each user independently partitions BSs into two sets and applies different association biases for each, depending on the type of power, renewable or not, that can be requested for service. The gain provided by such strategy regarding the probability of power outage and the average grid power consumption is investigated. To capture their dual nature, the bias applied for association with a hybrid BS is not constant among users nor over time, and is dynamically tailored to the fluctuations of the BS battery level, the user power requirement and the estimated power consumed to serve other users potentially associated with the same BS. Such approach allows to efficiently share the available energy among BSs and turns high heterogeneity in the BS powering into advantage.
A Moving Target Approach for Identifying Malicious Sensors in Control Systems
Venue: arXiv cs.SY 2017
Year: 2017

In this paper, we consider the problem of attack identification in cyber-physical systems (CPS). Attack identification is often critical for the recovery and performance of a CPS that is targeted by malicious entities, allowing defenders to construct algorithms which bypass harmful nodes. Previous work has characterized limitations in the perfect identification of adversarial attacks on deterministic LTI systems. For instance, a system must remain observable after removing any 2q sensors to only identify q attacks. However, the ability for an attacker to create an unidentifiable attack requires knowledge of the system model. In this paper, we aim to limit the adversary's knowledge of the system model with the goal of accurately identifying all sensor attacks. Such a scheme will allow systems to withstand larger attacks or system operators to allocate fewer sensing devices to a control system while maintaining security. We explore how changing the dynamics of the system as a function of time allows us to actively identify malicious/faulty sensors in a control system. We discuss the design of time varying system matrices to meet this goal and evaluate performance in deterministic and stochastic systems.
Early Signals from Volumetric DDoS Attacks: An Empirical Study
Venue: arXiv cs.NI 2017
Year: 2017

Distributed Denial of Service (DDoS) is a common type of Cybercrime. It can strongly damage a company reputation and increase its costs. Attackers improve continuously their strategies. They doubled the amount of unleashed communication requests in volume, size, and frequency in the last few years. This occurs against different hosts, causing resource exhaustion. Previous studies focused on detecting or mitigating ongoing DDoS attacks. Yet, addressing DDoS attacks when they are already in place may be too late. In this article, we consider network resilience by early prediction of attack trends. We show empirically the advantage of using non-parametric leading indicators for early prediction of volumetric DDoS attacks. We report promising results over a real dataset from CAIDA. Our results raise new questions and opportunities for further research in early predicting trends of DDoS attacks.
Sparse Methods for Direction-of-Arrival Estimation
Venue: arXiv cs.IT 2017
Year: 2017

Direction-of-arrival (DOA) estimation refers to the process of retrieving the direction information of several electromagnetic waves/sources from the outputs of a number of receiving antennas that form a sensor array. DOA estimation is a major problem in array signal processing and has wide applications in radar, sonar, wireless communications, etc. With the development of sparse representation and compressed sensing, the last decade has witnessed a tremendous advance in this research topic. The purpose of this article is to provide an overview of these sparse methods for DOA estimation, with a particular highlight on the recently developed gridless sparse methods, e.g., those based on covariance fitting and the atomic norm. Several future research directions are also discussed.
Algebraic and logical descriptions of generalized trees
Venue: arXiv cs.LO 2017
Year: 2017

Quasi-trees generalize trees in that the unique "path" between two nodes may be infinite and have any countable order type. They are used to define the rank-width of a countable graph in such a way that it is equal to the least upper-bound of the rank-widths of its finite induced subgraphs. Join-trees are the corresponding directed trees. They are useful to define the modular decomposition of a countable graph. We also consider ordered join-trees, that generalize rooted trees equipped with a linear order on the set of sons of each node. We define algebras with finitely many operations that generate (via infinite terms) these generalized trees. We prove that the associated regular objects (those defined by regular terms) are exactly the ones that are the unique models of monadic second-order sentences. These results use and generalize a similar result by W. Thomas for countable linear orders.
On the Complexity of Bounded Context Switching
Venue: arXiv cs.FL 2017
Year: 2017

Bounded context switching (BCS) is an under-approximate method for finding violations to safety properties in shared memory concurrent programs. Technically, BCS is a reachability problem that is known to be NP-complete. Our contribution is a parameterized analysis of BCS. The first result is an algorithm that solves BCS when parameterized by the number of context switches (cs) and the size of the memory (m) in O*(m^(cs)2^(cs)). This is achieved by creating instances of the easier problem Shuff which we solve via fast subset convolution. We also present a lower bound for BCS of the form m^o(cs / log(cs)), based on the exponential time hypothesis. Interestingly, closing the gap means settling a conjecture that has been open since FOCS'07. Further, we prove that BCS admits no polynomial kernel. Next, we introduce a measure, called scheduling dimension, that captures the complexity of schedules. We study BCS parameterized by the scheduling dimension (sdim) and show that it can be solved in O*((2m)^(4sdim)4^t)$, where t is the number of threads. We consider variants of the problem for which we obtain (matching) upper and lower bounds.
Sprout: A functional caching approach to minimize service latency in erasure-coded storage
Venue: arXiv cs.DC 2017
Year: 2017

Modern distributed storage systems often use erasure codes to protect against disk and node failures to increase reliability, while trying to meet the latency requirements of the applications and clients. Storage systems may have caches at the proxy or client ends in order to reduce the latency. In this paper, we consider a novel caching framework with erasure code called functional caching. Functional Caching involves using erasure-coded chunks in the cache such that the code formed by the chunks in storage nodes and cache combined are maximal-distance-separable (MDS) erasure codes. Based on the arrival rates of different files, placement of file chunks on the servers, and service time distribution of storage servers, an optimal functional caching placement and the access probabilities of the file request from different disks are considered. The proposed algorithm gives significant latency improvement in both simulations and a prototyped solution in an open-source, cloud storage deployment.
How many three-dimensional Hilbert curves are there?
Venue: arXiv cs.CG 2017
Year: 2017

Hilbert's two-dimensional space-filling curve is appreciated for its good locality-preserving properties and easy implementation for many applications. However, Hilbert did not describe how to generalize his construction to higher dimensions. In fact, the number of ways in which this may be done ranges from zero to infinite, depending on what properties of the Hilbert curve one considers to be essential. In this work we take the point of view that a Hilbert curve should at least be self-similar and traverse cubes octant by octant. We organize and explore the space of possible three-dimensional Hilbert curves and the potentially useful properties which they may have. We discuss a notation system that allows us to distinguish the curves from one another and enumerate them. This system has been implemented in a software prototype, available from the author's website. Several examples of possible three-dimensional Hilbert curves are presented, including a curve that visits the points on most sides of the unit cube in the order of the two-dimensional Hilbert curve; curves of which not only the eight octants are similar to each other, but also the four quarters; a curve with excellent locality-preserving properties and endpoints that are not vertices of the cube; a curve in which all but two octants are each other's images with respect to reflections in axis-parallel planes; and curves that can be sketched on a grid without using vertical line segments. In addition, we discuss several four-dimensional Hilbert curves.
Recursion-Theoretic Ranking and Compression
Venue: arXiv cs.LO 2017
Year: 2017

For which sets A does there exist a mapping, computed by a total or partial recursive function, such that the mapping, when its domain is restricted to A, is a 1-to-1, onto mapping to $Σ^*$? And for which sets A does there exist such a mapping that respects the lexicographical ordering within A? Both cases are types of perfect, minimal hash functions. The complexity-theoretic versions of these notions are known as compression functions and ranking functions. The present paper defines and studies the recursion-theoretic versions of compression and ranking functions, and in particular studies the question of which sets have, or lack, such functions. Thus, this is a case where, in contrast to the usual direction of notion transferal, notions from complexity theory are inspiring notions, and an investigation, in computability theory. We show that the rankable and compressible sets broadly populate the 1-truth-table degrees, and we prove that every nonempty coRE cylinder is recursively compressible.
Robust Quaternion-based Cooperative Manipulation without Force/Torque Information
Venue: arXiv cs.RO 2017
Year: 2017

This paper proposes a task-space control protocol for the collaborative manipulation of a single object by N robotic agents. The proposed methodology is decentralized in the sense that each agent utilizes information associated with its own and the object's dynamic/kinematic parameters and no on-line communication takes place. Moreover, no feedback of the contact forces/torques is required, therefore employment of corresponding sensors is avoided. An adaptive version of the control scheme is also introduced, where the agents' and object's dynamic parameters are considered unknown. We also use unit quaternions to represent the object's orientation. In addition, load sharing coefficients between the agents are employed and internal force regulation is guaranteed. Finally, experimental studies with two robotic arms verify the validity and effectiveness of the proposed control protocol.
Downlink Coordinated Joint Transmission for Mutual Information Accumulation
Venue: arXiv cs.IT 2017
Year: 2017

In this letter, we propose a new coordinated multipoint (CoMP) technique based on mutual information (MI) accumulation using rateless codes. Using a stochastic geometry model for the cellular downlink, we quantify the performance enhancements in coverage probability and rate due to MI accumulation. By simulation and analysis, we show that MI accumulation using rateless codes leads to remarkable improvements in coverage and rate for general users and specific cell edge users.
A Coordination Language for Databases
Venue: arXiv cs.LO 2017
Year: 2017

We present a coordination language for the modeling of distributed database applications. The language, baptized Klaim-DB, borrows the concepts of localities and nets of the coordination language Klaim but re-incarnates the tuple spaces of Klaim as databases. It provides high-level abstractions and primitives for the access and manipulation of structured data, with integrity and atomicity considerations. We present the formal semantics of Klaim-DB and develop a type system that avoids potential runtime errors such as certain evaluation errors and mismatches of data format in tables, which are monitored in the semantics. The use of the language is illustrated in a scenario where the sales from different branches of a chain of department stores are aggregated from their local databases. Raising the abstraction level and encapsulating integrity checks in the language primitives have benefited the modeling task considerably.
Automatic chemical design using a data-driven continuous representation of molecules
Venue: arXiv cs.LG 2017
Year: 2017

We report a method to convert discrete representations of molecules to and from a multidimensional continuous representation. This model allows us to generate new molecules for efficient exploration and optimization through open-ended spaces of chemical compounds. A deep neural network was trained on hundreds of thousands of existing chemical structures to construct three coupled functions: an encoder, a decoder and a predictor. The encoder converts the discrete representation of a molecule into a real-valued continuous vector, and the decoder converts these continuous vectors back to discrete molecular representations. The predictor estimates chemical properties from the latent continuous vector representation of the molecule. Continuous representations allow us to automatically generate novel chemical structures by performing simple operations in the latent space, such as decoding random vectors, perturbing known chemical structures, or interpolating between molecules. Continuous representations also allow the use of powerful gradient-based optimization to efficiently guide the search for optimized functional compounds. We demonstrate our method in the domain of drug-like molecules and also in the set of molecules with fewer that nine heavy atoms.
Frequency Estimation of Multiple Sinusoids with Three Sub-Nyquist Channels
Venue: arXiv cs.IT 2017
Year: 2017

Frequency estimation of multiple sinusoids is significant in both theory and application. In some application scenarios, only sub-Nyquist samples are available to estimate the frequencies. A conventional approach is to sample the signals at several lower rates. In this paper, we address frequency estimation of the signals in the time domain through undersampled data. We analyze the impact of undersampling and demonstrate that three sub-Nyquist channels are generally enough to estimate the frequencies provided the undersampling ratios are pairwise coprime. We deduce the condition that leads to the failure of resolving frequency ambiguity when two coprime undersampling channels are utilized. When three-channel sub-Nyquist samples are used jointly, the frequencies can be determined uniquely and the correct frequencies are estimated. Numerical experiments verify the correctness of our analysis and conclusion.
A categorization of arguments for counting methods for publication and citation indicators
Venue: arXiv cs.DL 2017
Year: 2017

Most publication and citation indicators are based on datasets with multi-authored publications and thus a change in counting method will often change the value of an indicator. Therefore it is important to know why a specific counting method has been applied. I have identified arguments for counting methods in a sample of 32 bibliometric studies published in 2016 and compared the result with discussions of arguments for counting methods in three older studies. Based on the underlying logics of the arguments I have arranged the arguments in four groups. Group 1 focuses on arguments related to what an indicator measures, Group 2 on the additivity of a counting method, Group 3 on pragmatic reasons for the choice of counting method, and Group 4 on an indicator's influence on the research community or how it is perceived by researchers. This categorization can be used to describe and discuss how bibliometric studies with publication and citation indicators argue for counting methods.
Real-time Error Control for Surgical Simulation
Venue: arXiv cs.NA 2017
Year: 2017

Objective: To present the first real-time a posteriori error-driven adaptive finite element approach for real-time simulation and to demonstrate the method on a needle insertion problem. Methods: We use corotational elasticity and a frictional needle/tissue interaction model. The problem is solved using finite elements within SOFA. The refinement strategy relies upon a hexahedron-based finite element method, combined with a posteriori error estimation driven local $h$-refinement, for simulating soft tissue deformation. Results: We control the local and global error level in the mechanical fields (e.g. displacement or stresses) during the simulation. We show the convergence of the algorithm on academic examples, and demonstrate its practical usability on a percutaneous procedure involving needle insertion in a liver. For the latter case, we compare the force displacement curves obtained from the proposed adaptive algorithm with that obtained from a uniform refinement approach. Conclusions: Error control guarantees that a tolerable error level is not exceeded during the simulations. Local mesh refinement accelerates simulations. Significance: Our work provides a first step to discriminate between discretization error and modeling error by providing a robust quantification of discretization error during simulations.
Learning Spatial-Semantic Context with Fully Convolutional Recurrent Network for Online Handwritten Chinese Text Recognition
Venue: arXiv cs.CV 2017
Year: 2017

Online handwritten Chinese text recognition (OHCTR) is a challenging problem as it involves a large-scale character set, ambiguous segmentation, and variable-length input sequences. In this paper, we exploit the outstanding capability of path signature to translate online pen-tip trajectories into informative signature feature maps using a sliding window-based method, successfully capturing the analytic and geometric properties of pen strokes with strong local invariance and robustness. A multi-spatial-context fully convolutional recurrent network (MCFCRN) is proposed to exploit the multiple spatial contexts from the signature feature maps and generate a prediction sequence while completely avoiding the difficult segmentation problem. Furthermore, an implicit language model is developed to make predictions based on semantic context within a predicting feature sequence, providing a new perspective for incorporating lexicon constraints and prior knowledge about a certain language in the recognition procedure. Experiments on two standard benchmarks, Dataset-CASIA and Dataset-ICDAR, yielded outstanding results, with correct rates of 97.10% and 97.15%, respectively, which are significantly better than the best result reported thus far in the literature.
Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs
Venue: arXiv cs.CC 2017
Year: 2017

We show that for constraint satisfaction problems (CSPs), sub-exponential size linear programming relaxations are as powerful as $n^{Ω(1)}$-rounds of the Sherali-Adams linear programming hierarchy. As a corollary, we obtain sub-exponential size lower bounds for linear programming relaxations that beat random guessing for many CSPs such as MAX-CUT and MAX-3SAT. This is a nearly-exponential improvement over previous results, previously, it was only known that linear programs of size $n^{o(\log n)}$ cannot beat random guessing for any CSP (Chan-Lee-Raghavendra-Steurer 2013). Our bounds are obtained by exploiting and extending the recent progress in communication complexity for "lifting" query lower bounds to communication problems. The main ingredient in our results is a new structural result on "high-entropy rectangles" that may of independent interest in communication complexity.
Channel Estimation in Broadband Millimeter Wave MIMO Systems with Few-Bit ADCs
Venue: arXiv cs.IT 2017
Year: 2017

We develop a broadband channel estimation algorithm for millimeter wave (mmWave) multiple input multiple output (MIMO) systems with few-bit analog-to-digital converters (ADCs). Our methodology exploits the joint sparsity of the mmWave MIMO channel in the angle and delay domains. We formulate the estimation problem as a noisy quantized compressed-sensing problem and solve it using efficient approximate message passing (AMP) algorithms. In particular, we model the angle-delay coefficients using a Bernoulli-Gaussian-mixture distribution with unknown parameters and use the expectation-maximization (EM) forms of the generalized AMP (GAMP) and vector AMP (VAMP) algorithms to simultaneously learn the distributional parameters and compute approximately minimum mean-squared error (MSE) estimates of the channel coefficients. We design a training sequence that allows fast, FFT-based implementation of these algorithms while minimizing peak-to-average power ratio at the transmitter, making our methods scale efficiently to large numbers of antenna elements and delays. We present the results of a detailed simulation study that compares our algorithms to several benchmarks. Our study investigates the effect of SNR, training length, training type, ADC resolution, and runtime on channel estimation MSE, mutual information, and achievable rate. It shows that our methods allow one-bit ADCs to perform comparably to infinite-bit ADCs at low SNR, and 4-bit ADCs to perform comparably to infinite-bit ADCs at medium SNR.