OpenRaiser/Intern-Atlas huggingface dataset:
Proposed Approximate Dynamic Programming for Pathfinding under Visible Uncertainty
Venue: arXiv cs.DS 2015
Year: 2015

Continuing our preleminary work \cite{knowles14}, we define the safest-with-sight pathfinding problems and explore its solution using techniques borrowed from measure-theoretic probability theory. We find a simple recursive definition for the probability that an ideal pathfinder will select an edge in a given scenario of an uncertain network where edges have probabilities of failure and vertices provide "vision" of edges via lines-of-sight. We propose an approximate solution based on our theoretical findings that would borrow techniques from approximate dynamic programming.
Fault-Tolerant Entity Resolution with the Crowd
Venue: arXiv cs.DB 2015
Year: 2015

In recent years, crowdsourcing is increasingly applied as a means to enhance data quality. Although the crowd generates insightful information especially for complex problems such as entity resolution (ER), the output quality of crowd workers is often noisy. That is, workers may unintentionally generate false or contradicting data even for simple tasks. The challenge that we address in this paper is how to minimize the cost for task requesters while maximizing ER result quality under the assumption of unreliable input from the crowd. For that purpose, we first establish how to deduce a consistent ER solution from noisy worker answers as part of the data interpretation problem. We then focus on the next-crowdsource problem which is to find the next task that maximizes the information gain of the ER result for the minimal additional cost. We compare our robust data interpretation strategies to alternative state-of-the-art approaches that do not incorporate the notion of fault-tolerance, i.e., the robustness to noise. In our experimental evaluation we show that our approaches yield a quality improvement of at least 20% for two real-world datasets. Furthermore, we examine task-to-worker assignment strategies as well as task parallelization techniques in terms of their cost and quality trade-offs in this paper. Based on both synthetic and crowdsourced datasets, we then draw conclusions on how to minimize cost while maintaining high quality ER results.
Dynamic Multiple-Message Broadcast: Bounding Throughput in the Affectance Model
Venue: arXiv cs.DC 2015
Year: 2015

We study a dynamic version of the Multiple-Message Broadcast problem, where packets are continuously injected in network nodes for dissemination throughout the network. Our performance metric is the ratio of the throughput of such protocol against the optimal one, for any sufficiently long period of time since startup. We present and analyze a dynamic Multiple-Message Broadcast protocol that works under an affectance model, which parameterizes the interference that other nodes introduce in the communication between a given pair of nodes. As an algorithmic tool, we develop an efficient algorithm to schedule a broadcast along a BFS tree under the affectance model. To provide a rigorous and accurate analysis, we define two novel network characteristics based on the network topology and the affectance function. The combination of these characteristics influence the performance of broadcasting with affectance (modulo a logarithmic function). We also carry out simulations of our protocol under affectance. To the best of our knowledge, this is the first dynamic Multiple-Message Broadcast protocol that provides throughput guarantees for continuous injection of messages and works under the affectance model.
Spectrum Sharing in Cooperative Cognitive Radio Networks: A Matching Game Framework
Venue: arXiv cs.NI 2015
Year: 2015

Dynamic spectrum access allows the unlicensed wireless users (secondary users) to dynamically access the licensed bands from legacy spectrum holders (primary users) either on an opportunistic or a cooperative basis. In this paper, we focus on cooperative spectrum sharing in a wireless network consisting of multiple primary and multiple secondary users. In particular, we study the partner-selection and resource-allocation problems within a matching theory framework, in which the primary and secondary users aim at optimizing their utilities in terms of transmission rate and power consumption. We propose a distributed algorithm to find the solution of the developed matching game that results in a stable matching between the sets of the primary and secondary users. Both analytical and numerical results show that the proposed matching model is a promising approach under which the utility functions of both primary and secondary users are maximized.
Object-based World Modeling in Semi-Static Environments with Dependent Dirichlet-Process Mixtures
Venue: arXiv cs.AI 2015
Year: 2015

To accomplish tasks in human-centric indoor environments, robots need to represent and understand the world in terms of objects and their attributes. We refer to this attribute-based representation as a world model, and consider how to acquire it via noisy perception and maintain it over time, as objects are added, changed, and removed in the world. Previous work has framed this as multiple-target tracking problem, where objects are potentially in motion at all times. Although this approach is general, it is computationally expensive. We argue that such generality is not needed in typical world modeling tasks, where objects only change state occasionally. More efficient approaches are enabled by restricting ourselves to such semi-static environments. We consider a previously-proposed clustering-based world modeling approach that assumed static environments, and extend it to semi-static domains by applying a dependent Dirichlet-process (DDP) mixture model. We derive a novel MAP inference algorithm under this model, subject to data association constraints. We demonstrate our approach improves computational performance in semi-static environments.
Uplink Achievable Rate for Massive MIMO with Low-Resolution ADC
Venue: arXiv cs.IT 2015
Year: 2015

In this letter, we derive an approximate analytical expression for the uplink achievable rate of a massive multi-input multi-output (MIMO) antenna system when finite precision analog-digital converters (ADCs) and the common maximal ratio combining technique are used at the receivers. To obtain this expression, we treat quantization noise as an additive quantization noise model. Considering the obtained expression, we show that low-resolution ADCs lead to a decrease in the achievable rate but the performance loss can be compensated by increasing the number of receiving antennas. In addition, we investigate the relation between the number of antennas and the ADC resolution, as well as the power-scaling law. These discussions support the feasibility of equipping highly economical ADCs with low resolution in practical massive MIMO systems.
MMSE Estimation for Poisson Noise Removal in Images
Venue: arXiv cs.CV 2015
Year: 2015

Poisson noise suppression is an important preprocessing step in several applications, such as medical imaging, microscopy, and astronomical imaging. In this work, we propose a novel patch-wise Poisson noise removal strategy, in which the MMSE estimator is utilized in order to produce the denoising result for each image patch. Fast and accurate computation of the MMSE estimator is carried out using k-d tree search followed by search in the K-nearest neighbor graph. Our experiments show that the proposed method is the preferable choice for low signal-to-noise ratios.
Uncertainty Principle and Sampling of Signals Defined on Graphs
Venue: arXiv cs.IT 2015
Year: 2015

In many applications, from sensor to social networks, gene regulatory networks or big data, observations can be represented as a signal defined over the vertices of a graph. Building on the recently introduced Graph Fourier Transform, the first contribution of this paper is to provide an uncertainty principle for signals on graph. As a by-product of this theory, we show how to build a dictionary of maximally concentrated signals on vertex/frequency domains. Then, we establish a direct relation between uncertainty principle and sampling, which forms the basis for a sampling theorem of signals defined on graph. Based on this theory, we show that, besides sampling rate, the samples' location plays a key role in the performance of signal recovery algorithms. Hence, we suggest a few alternative sampling strategies and compare them with recently proposed methods.
Cleaning Schedule Optimization of Heat Exchanger Networks Using Particle Swarm Optimization
Venue: arXiv cs.NE 2015
Year: 2015

Oil refinery is one of industries that require huge energy consumption. The today technology advance requires energy saving. Heat integration is a method used to minimize the energy comsumption though the implementation of Heat Exchanger Network (HEN). CPT is one of types of Heat Exchanger Network (HEN) that functions to recover the heat in the flow of product or waste. HEN comprises a number of heat exchangers (HEs) that are serially connected. However, the presence of fouling in the heat exchanger has caused the decline of the performance of both heat exchangers and all heat exchanger networks. Fouling can not be avoided. However, it can be mitigated. In industry, periodic heat exchanger cleaning is the most effective and widely used mitigation technique. On the other side, a very frequent cleaning of heat exchanger can be much costly in maintenance and lost of production. In this way, an accurate optimization technique of cleaning schedule interval of heat exchanger is very essential. Commonly, this technique involves three elements: model to simulate the heat exchanger network, representative fouling model to describe the fouling behavior and suitable optimization algorithm to solve the problem of clening schedule interval for heat exchanger network. This paper describe the optimization of interval cleaning schedule of HEN within the 44-month period using PSO (particle swarm optimization). The number of iteration used to achieve the convergent is 100 iterations and the fitness value in PSO correlated with the amount of heat recovery, cleaning cost, and additional pumping cost. The saving after the optimization of cleaning schedule of HEN in this research achieved at $ 1.236 millions or 23% of maximum potential savings.
A Literature Survey of various Fingerprint De-noising Techniques to justify the need of a new De-noising model based upon Pixel Component Analysis
Venue: arXiv cs.CV 2015
Year: 2015

Image Preprocessing is a vital step in the field of image processing for biometric pattern recognition. This paper studies and reviews various classical and modern fingerprint image de-noising models. The various model used for de-noising ranges widely from transform matrix using frequency, histogram model de-noising, de-noising by introducing Gabor filter and its types to enhance fingerprint images. The output efficiency of various de-noising model proposed earlier is calculated on the basis of SNR (signal to noise ratio) and MSE (mean square error rate). Our simulated experimental results indicates that incorporating the de-noising model based on Gabor filter inside domain of wavelet ranges with composite method only betters MSE (Mean Square Error). Improved MSE without significant improvement in SNR improves the fingerprint images only by a little margin which is non-optimal in nature. Thus the objective of this research paper is to build an optimal de-noising model for fingerprint images so that its usage in biometric authentication can be more robust in nature.
Exploiting Hidden Structure in Selecting Dimensions that Distinguish Vectors
Venue: arXiv cs.DM 2015
Year: 2015

The NP-hard Distinct Vectors problem asks to delete as many columns as possible from a matrix such that all rows in the resulting matrix are still pairwise distinct. Our main result is that, for binary matrices, there is a complexity dichotomy for Distinct Vectors based on the maximum (H) and the minimum (h) pairwise Hamming distance between matrix rows: Distinct Vectors can be solved in polynomial time if H <= 2 ceil(h/2) + 1, and is NP-complete otherwise. Moreover, we explore connections of Distinct Vectors to hitting sets, thereby providing several fixed-parameter tractability and intractability results also for general matrices.
A Monte Carlo method for the spread of mobile malware
Venue: arXiv cs.SI 2015
Year: 2015

A new model for the spread of mobile malware based on proximity (i.e. Bluetooth, ad-hoc WiFi or NFC) is introduced. The spread of malware is analyzed using a Monte Carlo method and the results of the simulation are compared with those from mean field theory.
Costly Circuits, Submodular Schedules: Hybrid Switch Scheduling for Data Centers
Venue: arXiv cs.NI 2015
Year: 2015

Hybrid switching - in which a high bandwidth circuit switch (optical or wireless) is used in conjunction with a low bandwidth packet switch - is a promising alternative to interconnect servers in today's large scale data-centers. Circuit switches offer a very high link rate, but incur a non-trivial reconfiguration delay which makes their scheduling challenging. In this paper, we demonstrate a lightweight, simple and nearly-optimal scheduling algorithm that trades-off configuration costs with the benefits of reconfiguration that match the traffic demands. The algorithm has strong connections to submodular optimization, has performance at least half that of the optimal schedule and strictly outperforms state of the art in a variety of traffic demand settings. These ideas naturally generalize: we see that indirect routing leads to exponential connectivity; this is another phenomenon of the power of multi hop routing, distinct from the well-known load balancing effects.
Model Validation for Vision Systems via Graphics Simulation
Venue: arXiv cs.CV 2015
Year: 2015

Rapid advances in computation, combined with latest advances in computer graphics simulations have facilitated the development of vision systems and training them in virtual environments. One major stumbling block is in certification of the designs and tuned parameters of these systems to work in real world. In this paper, we begin to explore the fundamental question: Which type of information transfer is more analogous to real world? Inspired from the performance characterization methodology outlined in the 90's, we note that insights derived from simulations can be qualitative or quantitative depending on the degree of the fidelity of models used in simulations and the nature of the questions posed by the experimenter. We adapt the methodology in the context of current graphics simulation tools for modeling data generation processes and, for systematic performance characterization and trade-off analysis for vision system design leading to qualitative and quantitative insights. In concrete, we examine invariance assumptions used in vision algorithms for video surveillance settings as a case study and assess the degree to which those invariance assumptions deviate as a function of contextual variables on both graphics simulations and in real data. As computer graphics rendering quality improves, we believe teasing apart the degree to which model assumptions are valid via systematic graphics simulation can be a significant aid to assisting more principled ways of approaching vision system design and performance modeling.
Discussion on "AC Drive Observability Analysis"
Venue: arXiv cs.SY 2015
Year: 2015

In the paper by Vaclavek et al. (IEEE Trans. Ind. Electron., vol. 60, no. 8, pp. 3047-3059, Aug. 2013), the local observability of both induction machine and permanent-magnet synchronous machine (PMSM) under motion-sensorless operation is studied. In this letter, the "slowly varying" speed assumption is discussed, and the PMSM observability condition at standstill is revisited.
A Shapley Value Solution to Game Theoretic-based Feature Reduction in False Alarm Detection
Venue: arXiv cs.CV 2015
Year: 2015

False alarm is one of the main concerns in intensive care units and can result in care disruption, sleep deprivation, and insensitivity of care-givers to alarms. Several methods have been proposed to suppress the false alarm rate through improving the quality of physiological signals by filtering, and developing more accurate sensors. However, significant intrinsic correlation among the extracted features limits the performance of most currently available data mining techniques, as they often discard the predictors with low individual impact that may potentially have strong discriminatory power when grouped with others. We propose a model based on coalition game theory that considers the inter-features dependencies in determining the salient predictors in respect to false alarm, which results in improved classification accuracy. The superior performance of this method compared to current methods is shown in simulation results using PhysionNet's MIMIC II database.
Restricted Low-Rank Approximation via ADMM
Venue: arXiv cs.NA 2015
Year: 2015

The matrix low-rank approximation problem with additional convex constraints can find many applications and has been extensively studied before. However, this problem is shown to be nonconvex and NP-hard; most of the existing solutions are heuristic and application-dependent. In this paper, we show that, other than tons of application in current literature, this problem can be used to recover a feasible solution for SDP relaxation. By some sophisticated tricks, it can be equivalently posed in an appropriate form for the Alternating Direction Method of Multipliers (ADMM) to solve. The two updates of ADMM include the basic matrix low-rank approximation and projection onto a convex set. Different from the general non-convex problems, the sub-problems in each step of ADMM can be solved exactly and efficiently in spite of their non-convexity. Moreover, the algorithm will converge exponentially under proper conditions. The simulation results confirm its superiority over existing solutions. We believe that the results in this paper provide a useful tool for this important problem and will help to extend the application of ADMM to the non-convex regime.
The interference immunity of the telemetric information data exchange with autonomous mobile robots
Venue: arXiv cs.RO 2015
Year: 2015

Purpose. To obtain the interference immunity of the data exchange by spread spectrum signals with variable entropy of the telemetric information data exchange with autonomous mobile robots. Methodology. The results have been obtained by the theoretical investigations and have been confirmed by the modeling experiments. Findings. The interference immunity in form of dependence of bit error probability on normalized signal/noise ratio of the data exchange by spread spectrum signals with variable entropy has been obtained.It has been proved that the interference immunity factor (needed normalized signal/noise ratio) is at least 2 dB better under condition of equal time complexity as compared with correlation processing methods of orthogonal signals. Originality. For the first time the interference immunity in form of dependence of bit error probability on normalized signal/noise ratio of the data exchange by spread spectrum signals with variable entropy has been obtained. Practical value. The obtained results prove the feasibility of using variable entropy spread spectrum signals data exchange method in the distributed telemetric information processing systems in specific circumstances.
k-Trails: Recognition, Complexity, and Approximations
Venue: arXiv cs.DS 2015
Year: 2015

The notion of degree-constrained spanning hierarchies, also called k-trails, was recently introduced in the context of network routing problems. They describe graphs that are homomorphic images of connected graphs of degree at most k. First results highlight several interesting advantages of k-trails compared to previous routing approaches. However, so far, only little is known regarding computational aspects of k-trails. In this work we aim to fill this gap by presenting how k-trails can be analyzed using techniques from algorithmic matroid theory. Exploiting this connection, we resolve several open questions about k-trails. In particular, we show that one can recognize efficiently whether a graph is a k-trail. Furthermore, we show that deciding whether a graph contains a k-trail is NP-complete; however, every graph that contains a k-trail is a (k+1)-trail. Moreover, further leveraging the connection to matroids, we consider the problem of finding a minimum weight k-trail contained in a graph G. We show that one can efficiently find a (2k-1)-trail contained in G whose weight is no more than the cheapest k-trail contained in G, even when allowing negative weights. The above results settle several open questions raised by Molnar, Newman, and Sebo.
Explaining reviews and ratings with PACO: Poisson Additive Co-Clustering
Venue: arXiv cs.LG 2015
Year: 2015

Understanding a user's motivations provides valuable information beyond the ability to recommend items. Quite often this can be accomplished by perusing both ratings and review texts, since it is the latter where the reasoning for specific preferences is explicitly expressed. Unfortunately matrix factorization approaches to recommendation result in large, complex models that are difficult to interpret and give recommendations that are hard to clearly explain to users. In contrast, in this paper, we attack this problem through succinct additive co-clustering. We devise a novel Bayesian technique for summing co-clusterings of Poisson distributions. With this novel technique we propose a new Bayesian model for joint collaborative filtering of ratings and text reviews through a sum of simple co-clusterings. The simple structure of our model yields easily interpretable recommendations. Even with a simple, succinct structure, our model outperforms competitors in terms of predicting ratings with reviews.
Modular implicits
Venue: arXiv cs.PL 2015
Year: 2015

We present modular implicits, an extension to the OCaml language for ad-hoc polymorphism inspired by Scala implicits and modular type classes. Modular implicits are based on type-directed implicit module parameters, and elaborate straightforwardly into OCaml's first-class functors. Basing the design on OCaml's modules leads to a system that naturally supports many features from other languages with systematic ad-hoc overloading, including inheritance, instance constraints, constructor classes and associated types.
Real-Time scheduling: from hard to soft real-time systems
Venue: arXiv cs.OS 2015
Year: 2015

Real-time systems are traditionally classified into hard real-time and soft real-time: in the first category we have safety critical real-time systems where missing a deadline can have catastrophic consequences, whereas in the second class we find systems or which we need to optimise the Quality of service provided to the user. However, the frontier between these two classes is thinner than one may think, and many systems that were considered as hard real-time in the past should now be reconsidered under a different light. In this paper we shall first recall the fundamental notion of time-predictability and criticality, in order to understand where the real-time deadlines that we use in our theoretical models come from. We shall then introduce the model of a soft real-time system and present one popular method for scheduling hard and soft real-time tasks, the resource reservation framework. Finally, we shall show how resource reservation techniques can be successfully applied to the design of classical control systems, thus adding robustness to the system and increasing resource utilisation and performance.
Hypercube Unfoldings that Tile R^3 and R^2
Venue: arXiv cs.CG 2015
Year: 2015

We show that the hypercube has a face-unfolding that tiles space, and that unfolding has an edge-unfolding that tiles the plane. So the hypercube is a "dimension-descending tiler." We also show that the hypercube cross unfolding made famous by Dali tiles space, but we leave open the question of whether or not it has an edge-unfolding that tiles the plane.