OpenRaiser/Intern-Atlas huggingface dataset:
Recovery of Noisy Points on Band-limited Surfaces: Kernel Methods Re-explained
Venue: arXiv cs.CV 2018
Year: 2018

We introduce a continuous domain framework for the recovery of points on a surface in high dimensional space, represented as the zero-level set of a bandlimited function. We show that the exponential maps of the points on the surface satisfy annihilation relations, implying that they lie in a finite dimensional subspace. The subspace properties are used to derive sampling conditions, which will guarantee the perfect recovery of the surface from finite number of points. We rely on nuclear norm minimization to exploit the low-rank structure of the maps to recover the points from noisy measurements. Since the direct estimation of the surface is computationally prohibitive in very high dimensions, we propose an iterative reweighted algorithm using the "kernel trick". The iterative algorithm reveals deep links to Laplacian based algorithms widely used in graph signal processing; the theory and the sampling conditions can serve as a basis for discrete-continuous domain processing of signals on a graph.
How the Taiwanese Do China Studies: Applications of Text Mining
Venue: arXiv cs.DL 2018
Year: 2018

With the rapid evolution of cross-strait situation, "Mainland China" as a subject of social science study has evoked the voice of "Rethinking China Study" among intelligentsia recently. This essay tried to apply an automatic content analysis tool (CATAR) to the journal "Mainland China Studies" (1998-2015) in order to observe the research trends based on the clustering of text from the title and abstract of each paper in the journal. The results showed that the 473 articles published by the journal were clustered into seven salient topics. From the publication number of each topic over time (including "volume of publications", "percentage of publications"), there are two major topics of this journal while other topics varied over time widely. The contribution of this study includes: 1. We could group each "independent" study into a meaningful topic, as a small scale experiment verified that this topic clustering is feasible. 2. This essay reveals the salient research topics and their trends for the Taiwan journal "Mainland China Studies". 3. Various topical keywords were identified, providing easy access to the past study. 4. The yearly trends of the identified topics could be viewed as signature of future research directions.
Shannon Capacity is Achievable for Binary Interactive First-Order Markovian Protocols
Venue: arXiv cs.IT 2018
Year: 2018

We address the problem of simulating an arbitrary binary interactive first-order Markovian protocol over a pair of binary symmetric channels with crossover probability $\varepsilon$. We are interested in the achievable rates of reliable simulation, i.e., in characterizing the smallest possible blowup in communications such that a vanishing error probability (in the protocol length) can be attained. Whereas for general interactive protocols the output of each party may depend on all previous outputs of its counterpart, in a (first-order) Markovian protocol this dependence is limited to the last observed output only. Previous works in the field discuss broader families of protocols but assess the achievable rates only at the limit where $\varepsilon\to0$. In this paper, we prove that the one-way Shannon capacity, $1-h(\varepsilon)$, can be achieved for any binary first-order Markovian protocol. This surprising result, is to the best of our knowledge, the first example in which non-trivial interactive protocol can be simulated in the Shannon capacity. We give two capacity achieving coding schemes, which both divide the protocol into independent blocks, and implement vertical block coding. The first scheme is based on a random separation into blocks with variable lengths. The second scheme is based on a deterministic separation into blocks, and efficiently predicting their last transmission. The prediction can be regarded as a binary pointer jumping game, for which we show that the final step can be calculated with $O(\log m)$ bits, where $m$ is the number of rounds in the game. We conclude the work by discussing possible extensions of the result to higher order models.
Information Bottleneck on General Alphabets
Venue: arXiv cs.IT 2018
Year: 2018

We prove rigorously a source coding theorem that can probably be considered folklore, a generalization to arbitrary alphabets of a problem motivated by the Information Bottleneck method. For general random variables $(Y, X)$, we show essentially that for some $n \in \mathbb{N}$, a function $f$ with rate limit $\log|f| \le nR$ and $I(Y^n; f(X^n)) \ge nS$ exists if and only if there is a random variable $U$ such that the Markov chain $Y - X - U$ holds, $I(U; X) \le R$ and $I(U; Y) \ge S$. The proof relies on the well established discrete case and showcases a technique for lifting discrete coding theorems to arbitrary alphabets.
Computational complexity lower bounds of certain discrete Radon transform approximations
Venue: arXiv cs.CC 2018
Year: 2018

For the computational model where only additions are allowed, the $Ω(n^2\log n)$ lower bound on operations count with respect to image size $n\times n$ is obtained for two types of the discrete Radon transform implementations: the fast Hough transform and a generic strip pattern class which includes the classical Hough transform, implying the fast Hough transform algorithm asymptotic optimality. The proofs are based on a specific result from the boolean circuits complexity theory and are generalized for the case of boolean $\vee$ binary operation.
EXPSPACE-hardness of behavioural equivalences of succinct one-counter nets
Venue: arXiv cs.LO 2018
Year: 2018

We note that the remarkable EXPSPACE-hardness result in [Göller, Haase, Ouaknine, Worrell, ICALP 2010] ([GHOW10] for short) allows us to answer an open complexity question for simulation preorder of succinct one counter nets (i.e., one counter automata with no zero tests where counter increments and decrements are integers written in binary). This problem, as well as bisimulation equivalence, turn out to be EXPSPACE-complete. The technique of [GHOW10] was referred to by Hunter [RP 2015] for deriving EXPSPACE-hardness of reachability games on succinct one-counter nets. We first give a direct self-contained EXPSPACE-hardness proof for such reachability games (by adjusting a known PSPACE-hardness proof for emptiness of alternating finite automata with one-letter alphabet); then we reduce reachability games to (bi)simulation games by using a standard "defender-choice" technique.
Recent Advances in Recurrent Neural Networks
Venue: arXiv cs.NE 2018
Year: 2018

Recurrent neural networks (RNNs) are capable of learning features and long term dependencies from sequential and time-series data. The RNNs have a stack of non-linear units where at least one connection between units forms a directed cycle. A well-trained RNN can model any dynamical system; however, training RNNs is mostly plagued by issues in learning long-term dependencies. In this paper, we present a survey on RNNs and several new advances for newcomers and professionals in the field. The fundamentals and recent advances are explained and the research challenges are introduced.
Optimization-based AMP for Phase Retrieval: The Impact of Initialization and $\ell_2$-regularization
Venue: arXiv cs.IT 2018
Year: 2018

We consider an $\ell_2$-regularized non-convex optimization problem for recovering signals from their noisy phaseless observations. We design and study the performance of a message passing algorithm that aims to solve this optimization problem. We consider the asymptotic setting $m,n \rightarrow \infty$, $m/n \rightarrow δ$ and obtain sharp performance bounds, where $m$ is the number of measurements and $n$ is the signal dimension. We show that for complex signals the algorithm can perform accurate recovery with only $m= \left(\frac{64}{π^2}-4\right)n \approx 2.5n$ measurements. Also, we provide sharp analysis on the sensitivity of the algorithm to noise. We highlight the following facts about our message passing algorithm: (i) Adding $\ell_2$ regularization to the non-convex loss function can be beneficial. (ii) Spectral initialization has marginal impact on the performance of the algorithm. The sharp analyses in this paper, not only enable us to compare the performance of our method with other phase recovery schemes, but also shed light on designing better iterative algorithms for other non-convex optimization problems.
Fingerprint Distortion Rectification using Deep Convolutional Neural Networks
Venue: arXiv cs.CV 2018
Year: 2018

Elastic distortion of fingerprints has a negative effect on the performance of fingerprint recognition systems. This negative effect brings inconvenience to users in authentication applications. However, in the negative recognition scenario where users may intentionally distort their fingerprints, this can be a serious problem since distortion will prevent recognition system from identifying malicious users. Current methods aimed at addressing this problem still have limitations. They are often not accurate because they estimate distortion parameters based on the ridge frequency map and orientation map of input samples, which are not reliable due to distortion. Secondly, they are not efficient and requiring significant computation time to rectify samples. In this paper, we develop a rectification model based on a Deep Convolutional Neural Network (DCNN) to accurately estimate distortion parameters from the input image. Using a comprehensive database of synthetic distorted samples, the DCNN learns to accurately estimate distortion bases ten times faster than the dictionary search methods used in the previous approaches. Evaluating the proposed method on public databases of distorted samples shows that it can significantly improve the matching performance of distorted samples.
Ultra-Reliable and Low-Latency Wireless Communication: Tail, Risk and Scale
Venue: arXiv cs.IT 2018
Year: 2018

Ensuring ultra-reliable and low-latency communication (URLLC) for 5G wireless networks and beyond is of capital importance and is currently receiving tremendous attention in academia and industry. At its core, URLLC mandates a departure from expected utility-based network design approaches, in which relying on average quantities (e.g., average throughput, average delay and average response time) is no longer an option but a necessity. Instead, a principled and scalable framework which takes into account delay, reliability, packet size, network architecture, and topology (across access, edge, and core) and decision-making under uncertainty is sorely lacking. The overarching goal of this article is a first step to fill this void. Towards this vision, after providing definitions of latency and reliability, we closely examine various enablers of URLLC and their inherent tradeoffs. Subsequently, we focus our attention on a plethora of techniques and methodologies pertaining to the requirements of ultra-reliable and low-latency communication, as well as their applications through selected use cases. These results provide crisp insights for the design of low-latency and high-reliable wireless networks.
DeepTriage: Exploring the Effectiveness of Deep Learning for Bug Triaging
Venue: arXiv cs.SE 2018
Year: 2018

For a given software bug report, identifying an appropriate developer who could potentially fix the bug is the primary task of a bug triaging process. A bug title (summary) and a detailed description is present in most of the bug tracking systems. Automatic bug triaging algorithm can be formulated as a classification problem, with the bug title and description as the input, mapping it to one of the available developers (classes). The major challenge is that the bug description usually contains a combination of free unstructured text, code snippets, and stack trace making the input data noisy. The existing bag-of-words (BOW) feature models do not consider the syntactical and sequential word information available in the unstructured text. We propose a novel bug report representation algorithm using an attention based deep bidirectional recurrent neural network (DBRNN-A) model that learns a syntactic and semantic feature from long word sequences in an unsupervised manner. Instead of BOW features, the DBRNN-A based bug representation is then used for training the classifier. Using an attention mechanism enables the model to learn the context representation over a long word sequence, as in a bug report. To provide a large amount of data to learn the feature learning model, the unfixed bug reports (~70% bugs in an open source bug tracking system) are leveraged, which were completely ignored in the previous studies. Another contribution is to make this research reproducible by making the source code available and creating a public benchmark dataset of bug reports from three open source bug tracking system: Google Chromium (383,104 bug reports), Mozilla Core (314,388 bug reports), and Mozilla Firefox (162,307 bug reports). Experimentally we compare our approach with BOW model and machine learning approaches and observe that DBRNN-A provides a higher rank-10 average accuracy.
Narrating Networks
Venue: arXiv cs.SI 2018
Year: 2018

Networks have become the de facto diagram of the Big Data age (try searching Google Images for [big data AND visualisation] and see). The concept of networks has become central to many fields of human inquiry and is said to revolutionise everything from medicine to markets to military intelligence. While the mathematical and analytical capabilities of networks have been extensively studied over the years, in this article we argue that the storytelling affordances of networks have been comparatively neglected. In order to address this we use multimodal analysis to examine the stories that networks evoke in a series of journalism articles. We develop a protocol by means of which narrative meanings can be construed from network imagery and the context in which it is embedded, and discuss five different kinds of narrative readings of networks, illustrated with analyses of examples from journalism. Finally, to support further research in this area, we discuss methodological issues that we encountered and suggest directions for future study to advance and broaden research around this defining aspect of visual culture after the digital turn.
Asymptotic bounds for spherical codes
Venue: arXiv cs.IT 2018
Year: 2018

The set of all error-correcting codes C over a fixed finite alphabet F of cardinality q determines the set of code points in the unit square with coordinates (R(C), delta (C)):= (relative transmission rate, relative minimal distance). The central problem of the theory of such codes consists in maximizing simultaneously the transmission rate of the code and the relative minimum Hamming distance between two different code words. The classical approach to this problem explored in vast literature consists in the inventing explicit constructions of "good codes" and comparing new classes of codes with earlier ones. Less classical approach studies the geometry of the whole set of code points (R,delta) (with q fixed), at first independently of its computability properties, and only afterwords turning to the problems of computability, analogies with statistical physics etc. The main purpose of this article consists in extending this latter strategy to domain of spherical codes.
On-the-fly Augmented Reality for Orthopaedic Surgery Using a Multi-Modal Fiducial
Venue: arXiv cs.CV 2018
Year: 2018

Fluoroscopic X-ray guidance is a cornerstone for percutaneous orthopaedic surgical procedures. However, two-dimensional observations of the three-dimensional anatomy suffer from the effects of projective simplification. Consequently, many X-ray images from various orientations need to be acquired for the surgeon to accurately assess the spatial relations between the patient's anatomy and the surgical tools. In this paper, we present an on-the-fly surgical support system that provides guidance using augmented reality and can be used in quasi-unprepared operating rooms. The proposed system builds upon a multi-modality marker and simultaneous localization and mapping technique to co-calibrate an optical see-through head mounted display to a C-arm fluoroscopy system. Then, annotations on the 2D X-ray images can be rendered as virtual objects in 3D providing surgical guidance. We quantitatively evaluate the components of the proposed system, and finally, design a feasibility study on a semi-anthropomorphic phantom. The accuracy of our system was comparable to the traditional image-guided technique while substantially reducing the number of acquired X-ray images as well as procedure time. Our promising results encourage further research on the interaction between virtual and real objects, that we believe will directly benefit the proposed method. Further, we would like to explore the capabilities of our on-the-fly augmented reality support system in a larger study directed towards common orthopaedic interventions.
Computational Higher Type Theory IV: Inductive Types
Venue: arXiv cs.LO 2018
Year: 2018

This is the fourth in a series of papers extending Martin-Löf's meaning explanation of dependent type theory to higher-dimensional types. In this installment, we show how to define cubical type systems supporting a general schema of indexed cubical inductive types whose constructors may take dimension parameters and have a specified boundary. Using this schema, we are able to specify and implement many of the higher inductive types which have been postulated in homotopy type theory, including homotopy pushouts, the torus, $W$-quotients, truncations, arbitrary localizations. By including indexed inductive types, we enable the definition of identity types. The addition of higher inductive types makes computational higher type theory a model of homotopy type theory, capable of interpreting almost all of the constructions in the HoTT Book (with the exception of inductive-inductive types). This is the first such model with an explicit canonicity theorem, which specifies the canonical values of higher inductive types and confirms that every term in an inductive type evaluates to such a value.
Optimal Pilot Symbols Ratio in terms of Spectrum and Energy Efficiency in Uplink CoMP Networks
Venue: arXiv cs.IT 2018
Year: 2018

In wireless networks, Spectrum Efficiency (SE) and Energy Efficiency (EE) can be affected by the channel estimation that needs to be well designed in practice. In this paper, considering channel estimation error and non-ideal backhaul links, we optimize the pilot symbols ratio in terms of SE and EE in uplink Coordinated Multi-point (CoMP) networks. Modeling the channel estimation error, we formulate the SE and EE maximization problems by analyzing the system capacity with imperfect channel estimation. The maximal system capacity in SE optimization and the minimal transmit power in EE optimization, which both have the closed-form expressions, are derived by some reasonable approximations to reduce the complexity of solving complicated equations. Simulations are carried out to validate the superiority of our scheme, verify the accuracy of our approximation, and show the effect of pilot symbols ratio.
Secure Sensor Design Against Undetected Infiltration: Minimum Impact-Minimum Damage
Venue: arXiv cs.SY 2018
Year: 2018

We propose a new defense mechanism against undetected infiltration into controllers in cyber-physical systems. To this end, we cautiously design the outputs of the sensors that monitor the state of the system. Different from the defense mechanisms that seek to detect infiltration, the proposed approach seeks to minimize the damage of possible attacks before they have been detected. Controller of a cyber-physical system could have been infiltrated into by an undetected attacker at any time of the operation. Disregarding such a possibility and disclosing system's state without caution benefits the attacker in his/her malicious objective. Therefore, secure sensor design can improve the security of cyber-physical systems further when incorporated along with other defense mechanisms. We, specifically, consider a controlled Gauss-Markov process, where the controller could have been infiltrated into at any time within the system's operation. In the sense of game-theoretic hierarchical equilibrium, we provide a semi-definite programming based algorithm to compute the optimal linear secure sensor outputs and analyze the performance for various scenarios numerically.
Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch
Venue: arXiv cs.CG 2018
Year: 2018

We present a number of breakthroughs for coordinated motion planning, in which the objective is to reconfigure a swarm of labeled convex objects by a combination of parallel, continuous, collision-free translations into a given target arrangement. Problems of this type can be traced back to the classic work of Schwartz and Sharir (1983), who gave a method for deciding the existence of a coordinated motion for a set of disks between obstacles; their approach is polynomial in the complexity of the obstacles, but exponential in the number of disks. Other previous work has largely focused on {\em sequential} schedules, in which one robot moves at a time. We provide constant-factor approximation algorithms for minimizing the execution time of a coordinated, {\em parallel} motion plan for a swarm of robots in the absence of obstacles, provided some amount of separability. Our algorithm achieves {\em constant stretch factor}: If all robots are at most $d$ units from their respective starting positions, the total duration of the overall schedule is $O(d)$. Extensions include unlabeled robots and different classes of robots. We also prove that finding a plan with minimal execution time is NP-hard, even for a grid arrangement without any stationary obstacles. On the other hand, we show that for densely packed disks that cannot be well separated, a stretch factor $Ω(N^{1/4})$ may be required. On the positive side, we establish a stretch factor of $O(N^{1/2})$ even in this case.
Tree based classification of tabla strokes
Venue: arXiv cs.SD 2018
Year: 2018

The paper attempts to validate the effectiveness of tree classifiers to classify tabla strokes especially the ones which are overlapping in nature. It uses decision tree, ID3 and random forest as classifiers. A custom made data sets of 650 samples of 13 different tabla strokes were used for experimental purpose. 31 different features with their mean and variances were extracted for classification. Three data sets consisting of 21361, 18802 and 19543 instances respectively were used for the purpose. Validation has been done using measures like ROC curve and accuracy. The experimental results showed that all the classifiers showing excellent results with random forest outperforming the other two. The effectiveness of random forest in classifying strokes which are overlapping in nature is done by comparing the known results of that with multi-layer perceptron.