OpenRaiser/Intern-Atlas huggingface dataset:
A deterministic pseudorandom perturbation scheme for arbitrary polynomial predicates
Venue: arXiv cs.CG 2013
Year: 2013

We present a symbolic perturbation scheme for arbitrary polynomial geometric predicates which combines the benefits of Emiris and Canny's simple randomized linear perturbation scheme with Yap's multiple infinitesimal scheme for general predicates. Like the randomized scheme, our method accepts black box polynomial functions as input. For nonmaliciously chosen predicates, our method is as fast as the linear scheme, scaling reasonably with the degree of the polynomial even for fully degenerate input. Like Yap's scheme, the computed sign is deterministic, never requiring an algorithmic restart (assuming a high quality pseudorandom generator), and works for arbitrary predicates with no knowledge of their structure. We also apply our technique to exactly or nearly exactly rounded constructions that work correctly for degenerate input, using l'Hopital's rule to compute the necessary singular limits. We provide an open source prototype implementation including example algorithms for Delaunay triangulation and Boolean operations on polygons and circular arcs in the plane.
Signal Reconstruction via H-infinity Sampled-Data Control Theory: Beyond the Shannon Paradigm
Venue: arXiv cs.IT 2013
Year: 2013

This paper presents a new method for signal reconstruction by leveraging sampled-data control theory. We formulate the signal reconstruction problem in terms of an analog performance optimization problem using a stable discrete-time filter. The proposed H-infinity performance criterion naturally takes intersample behavior into account, reflecting the energy distributions of the signal. We present methods for computing optimal solutions which are guaranteed to be stable and causal. Detailed comparisons to alternative methods are provided. We discuss some applications in sound and image reconstruction.
Finite-State Markov Modeling of Leaky Waveguide Channels in Communication-based Train Control (CBTC) Systems
Venue: arXiv cs.DM 2013
Year: 2013

Leaky waveguide has been adopted in communication based train control (CBTC) systems, as it can significantly enhance railway network efficiency, safety and capacity. Since CBTC systems have high requirements for the train ground communications, modeling the leaky waveguide channels is very important to design the wireless networks and evaluate the performance of CBTC systems. In the letter, we develop a finite-state Markov channel (FSMC) model for leaky waveguide channels in CBTC systems based on real field channel measurements obtained from a business operating subway line. The proposed FSMC channel model takes train locations into account to have a more accurate channel model. The overall leaky waveguide is divided into intervals, and an FSMC model is applied in each interval. The accuracy of the proposed FSMC model is illustrated by the simulation results generated from the model and the real field measurement results.
Coding for Random Projections
Venue: arXiv cs.LG 2013
Year: 2013

The method of random projections has become very popular for large-scale applications in statistical learning, information retrieval, bio-informatics and other applications. Using a well-designed coding scheme for the projected data, which determines the number of bits needed for each projected value and how to allocate these bits, can significantly improve the effectiveness of the algorithm, in storage cost as well as computational speed. In this paper, we study a number of simple coding schemes, focusing on the task of similarity estimation and on an application to training linear classifiers. We demonstrate that uniform quantization outperforms the standard existing influential method (Datar et. al. 2004). Indeed, we argue that in many cases coding with just a small number of bits suffices. Furthermore, we also develop a non-uniform 2-bit coding scheme that generally performs well in practice, as confirmed by our experiments on training linear support vector machines (SVM).
Mining Positive and Negative Association Rules Using CoherentApproach
Venue: arXiv cs.DB 2013
Year: 2013

In the data mining field, association rules are discovered having domain knowledge specified as a minimum support threshold. The accuracy in setting up this threshold directly influences the number and the quality of association rules discovered. Typically, before association rules are mined, a user needs to determine a support threshold in order to obtain only the frequent item sets. Having users to determine a support threshold attracts a number of issues. We propose an association rule mining framework that does not require a per-set support threshold. Often, the number of association rules, even though large in number, misses some interesting rules and the rules quality necessitates further analysis. As a result, decision making using these rules could lead to risky actions.
Reachability under Contextual Locking
Venue: arXiv cs.LO 2013
Year: 2013

The pairwise reachability problem for a multi-threaded program asks, given control locations in two threads, whether they can be simultaneously reached in an execution of the program. The problem is important for static analysis and is used to detect statements that are concurrently enabled. This problem is in general undecidable even when data is abstracted and when the threads (with recursion) synchronize only using a finite set of locks. Popular programming paradigms that limit the lock usage patterns have been identified under which the pairwise reachability problem becomes decidable. In this paper, we consider a new natural programming paradigm, called contextual locking, which ties the lock usage to calling patterns in each thread: we assume that locks are released in the same context that they were acquired and that every lock acquired by a thread in a procedure call is released before the procedure returns. Our main result is that the pairwise reachability problem is polynomial-time decidable for this new programming paradigm as well. The problem becomes undecidable if the locks are reentrant; reentrant locking is a \emph{recursive locking} mechanism which allows a thread in a multi-threaded program to acquire the reentrant lock multiple times.
Learning Features and their Transformations by Spatial and Temporal Spherical Clustering
Venue: arXiv cs.NE 2013
Year: 2013

Learning features invariant to arbitrary transformations in the data is a requirement for any recognition system, biological or artificial. It is now widely accepted that simple cells in the primary visual cortex respond to features while the complex cells respond to features invariant to different transformations. We present a novel two-layered feedforward neural model that learns features in the first layer by spatial spherical clustering and invariance to transformations in the second layer by temporal spherical clustering. Learning occurs in an online and unsupervised manner following the Hebbian rule. When exposed to natural videos acquired by a camera mounted on a cat's head, the first and second layer neurons in our model develop simple and complex cell-like receptive field properties. The model can predict by learning lateral connections among the first layer neurons. A topographic map to their spatial features emerges by exponentially decaying the flow of activation with distance from one neuron to another in the first layer that fire in close temporal proximity, thereby minimizing the pooling length in an online manner simultaneously with feature learning.
Hidden Structure and Function in the Lexicon
Venue: arXiv cs.CL 2013
Year: 2013

How many words are needed to define all the words in a dictionary? Graph-theoretic analysis reveals that about 10% of a dictionary is a unique Kernel of words that define one another and all the rest, but this is not the smallest such subset. The Kernel consists of one huge strongly connected component (SCC), about half its size, the Core, surrounded by many small SCCs, the Satellites. Core words can define one another but not the rest of the dictionary. The Kernel also contains many overlapping Minimal Grounding Sets (MGSs), each about the same size as the Core, each part-Core, part-Satellite. MGS words can define all the rest of the dictionary. They are learned earlier, more concrete and more frequent than the rest of the dictionary. Satellite words, not correlated with age or frequency, are less concrete (more abstract) words that are also needed for full lexical power.
Faster gradient descent and the efficient recovery of images
Venue: arXiv cs.CV 2013
Year: 2013

Much recent attention has been devoted to gradient descent algorithms where the steepest descent step size is replaced by a similar one from a previous iteration or gets updated only once every second step, thus forming a {\em faster gradient descent method}. For unconstrained convex quadratic optimization these methods can converge much faster than steepest descent. But the context of interest here is application to certain ill-posed inverse problems, where the steepest descent method is known to have a smoothing, regularizing effect, and where a strict optimization solution is not necessary. Specifically, in this paper we examine the effect of replacing steepest descent by a faster gradient descent algorithm in the practical context of image deblurring and denoising tasks. We also propose several highly efficient schemes for carrying out these tasks independently of the step size selection, as well as a scheme for the case where both blur and significant noise are present. In the above context there are situations where many steepest descent steps are required, thus building slowness into the solution procedure. Our general conclusion regarding gradient descent methods is that in such cases the faster gradient descent methods offer substantial advantages. In other situations where no such slowness buildup arises the steepest descent method can still be very effective.
Bounding the Inefficiency of Altruism Through Social Contribution Games
Venue: arXiv cs.GT 2013
Year: 2013

We introduce a new class of games, called social contribution games (SCGs), where each player's individual cost is equal to the cost he induces on society because of his presence. Our results reveal that SCGs constitute useful abstractions of altruistic games when it comes to the analysis of the robust price of anarchy. We first show that SCGs are altruism-independently smooth, i.e., the robust price of anarchy of these games remains the same under arbitrary altruistic extensions. We then devise a general reduction technique that enables us to reduce the problem of establishing smoothness for an altruistic extension of a base game to a corresponding SCG. Our reduction applies whenever the base game relates to a canonical SCG by satisfying a simple social contribution boundedness property. As it turns out, several well-known games satisfy this property and are thus amenable to our reduction technique. Examples include min-sum scheduling games, congestion games, second price auctions and valid utility games. Using our technique, we derive mostly tight bounds on the robust price of anarchy of their altruistic extensions. For the majority of the mentioned game classes, the results extend to the more differentiated friendship setting. As we show, our reduction technique covers this model if the base game satisfies three additional natural properties.
Coding and Compression of Three Dimensional Meshes by Planes
Venue: arXiv cs.CG 2013
Year: 2013

The present paper suggests a new approach for geometric representation of 3D spatial models and provides a new compression algorithm for 3D meshes, which is based on mathematical theory of convex geometry. In our approach we represent a 3D convex polyhedron by means of planes, containing only its faces. This allows not to consider topological aspects of the problem (connectivity information among vertices and edges) since by means of the planes we construct the polyhedron uniquely. Due to the fact that the topological data is ignored this representation provides high degree of compression. Also planes based representation provides a compression of geometrical data because most of the faces of the polyhedron are not triangles but polygons with more than three vertices.
Achieving Speedup in Aggregate Risk Analysis using Multiple GPUs
Venue: arXiv cs.DC 2013
Year: 2013

Stochastic simulation techniques employed for the analysis of portfolios of insurance/reinsurance risk, often referred to as `Aggregate Risk Analysis', can benefit from exploiting state-of-the-art high-performance computing platforms. In this paper, parallel methods to speed-up aggregate risk analysis for supporting real-time pricing are explored. An algorithm for analysing aggregate risk is proposed and implemented for multi-core CPUs and for many-core GPUs. Experimental studies indicate that GPUs offer a feasible alternative solution over traditional high-performance computing systems. A simulation of 1,000,000 trials with 1,000 catastrophic events per trial on a typical exposure set and contract structure is performed in less than 5 seconds on a multiple GPU platform. The key result is that the multiple GPU implementation can be used in real-time pricing scenarios as it is approximately 77x times faster than the sequential counterpart implemented on a CPU.
Line-of-Sight Obstruction Analysis for Vehicle-to-Vehicle Network Simulations in a Two-Lane Highway Scenario
Venue: arXiv cs.NI 2013
Year: 2013

In vehicular ad-hoc networks (VANETs) the impact of vehicles as obstacles has largely been neglected in the past. Recent studies have reported that the vehicles that obstruct the line-of-sight (LOS) path may introduce 10-20 dB additional loss, and as a result reduce the communication range. Most of the traffic mobility models (TMMs) today do not treat other vehicles as obstacles and thus can not model the impact of LOS obstruction in VANET simulations. In this paper the LOS obstruction caused by other vehicles is studied in a highway scenario. First a car-following model is used to characterize the motion of the vehicles driving in the same direction on a two-lane highway. Vehicles are allowed to change lanes when necessary. The position of each vehicle is updated by using the car-following rules together with the lane-changing rules for the forward motion. Based on the simulated traffic a simple TMM is proposed for VANET simulations, which is capable to identify the vehicles that are in the shadow region of other vehicles. The presented traffic mobility model together with the shadow fading path loss model can take in to account the impact of LOS obstruction on the total received power in the multiple-lane highway scenarios.
Local image registration a comparison for bilateral registration mammography
Venue: arXiv cs.CV 2013
Year: 2013

Early tumor detection is key in reducing the number of breast cancer death and screening mammography is one of the most widely available and reliable method for early detection. However, it is difficult for the radiologist to process with the same attention each case, due the large amount of images to be read. Computer aided detection (CADe) systems improve tumor detection rate; but the current efficiency of these systems is not yet adequate and the correct interpretation of CADe outputs requires expert human intervention. Computer aided diagnosis systems (CADx) are being designed to improve cancer diagnosis accuracy, but they have not been efficiently applied in breast cancer. CADx efficiency can be enhanced by considering the natural mirror symmetry between the right and left breast. The objective of this work is to evaluate co-registration algorithms for the accurate alignment of the left to right breast for CADx enhancement. A set of mammograms were artificially altered to create a ground truth set to evaluate the registration efficiency of DEMONs, and SPLINE deformable registration algorithms. The registration accuracy was evaluated using mean square errors, mutual information and correlation. The results on the 132 images proved that the SPLINE deformable registration over-perform the DEMONS on mammography images.
B(eo)W(u)LF: Facilitating recurrence analysis on multi-level language
Venue: arXiv cs.CL 2013
Year: 2013

Discourse analysis may seek to characterize not only the overall composition of a given text but also the dynamic patterns within the data. This technical report introduces a data format intended to facilitate multi-level investigations, which we call the by-word long-form or B(eo)W(u)LF. Inspired by the long-form data format required for mixed-effects modeling, B(eo)W(u)LF structures linguistic data into an expanded matrix encoding any number of researchers-specified markers, making it ideal for recurrence-based analyses. While we do not necessarily claim to be the first to use methods along these lines, we have created a series of tools utilizing Python and MATLAB to enable such discourse analyses and demonstrate them using 319 lines of the Old English epic poem, Beowulf, translated into modern English.
H-infinity Design of Periodically Nonuniform Interpolation and Decimation for Non-Band-Limited Signals
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we consider signal interpolation of discrete-time signals which are decimated nonuniformly. A conventional interpolation method is based on the sampling theorem, and the resulting system consists of an ideal filter with complex-valued coefficients. While the conventional method assumes band limitation of signals, we propose a new method by sampled-data H-infinity optimization. By this method, we can remove the band-limiting assumption and the optimal filter can be with real-valued coefficients. Moreover, we show that without band-limited assumption, there can be the optimal decimation patterns among ones with the same ratio. By examples, we show the effectiveness of our method.
Extended Capabilities for a Privacy-Enhanced Participatory Sensing Infrastructure (PEPSI)
Venue: arXiv cs.CR 2013
Year: 2013

Participatory sensing is emerging as an innovative computing paradigm that targets the ubiquity of always-connected mobile phones and their sensing capabilities. In this context, a multitude of pioneering applications increasingly carry out pervasive collection and dissemination of information and environmental data, such as, traffic conditions, pollution, temperature, etc. Participants collect and report measurements from their mobile devices and entrust them to the cloud to be made available to applications and users. Naturally, due to the personal information associated to the reports (e.g., location, movements, etc.), a number of privacy concerns need to be taken into account prior to a large-scale deployment of these applications. Motivated by the need for privacy protection in Participatory Sensing, this work presents PEPSI: a Privacy-Enhanced Participatory Sensing Infrastructure. We explore realistic architectural assumptions and a minimal set of formal requirements aiming at protecting privacy of both data producers and consumers. We propose two instantiations that attain privacy guarantees with provable security at very low additional computational cost and almost no extra communication overhead.
Smart business networks and business genetics with a high tech communications supplier selection industry case
Venue: arXiv cs.CY 2013
Year: 2013

Despite the emergence of event driven business process management, smart business networks, social networks, etc. as important research areas in management, for all the attractiveness of these concepts, two major challenges remain around their design and the partner selection rules while learning from interaction events.While smart business networks should provide advantages due to the quick connect of business partners for selected functions in a process common to several parties, literature does not provide constructive methods whereby the selection of temporary partners and functions can be done. Most discussions only rely solely on human judgment. This paper introduces both computational geometry, and genetic programming, as systematic methods whereby to identify, characterize, and then display on a continuing basis from event monitoring such possible partnerships; such techniques also allow to plan for their effect on the organizations and thus to carry out selection. The two methods are being put in the context of emergence theory. Tessellations address the identification and categorization issues; business maps address the display and monitoring challenge with the use of Voronoii diagrams. Cellular automata mimicking living bodies, with genetic algorithms of which parameters are estimated by learning, address the selection and effect issues. To illustrate the approach, some experimental results from the sourcing function in a high tech industry, are discussed; they address the case of how to determine the selection process for a systems integrator to set up joint ventures with smaller technology suppliers.
On Generalized Bayesian Data Fusion with Complex Models in Large Scale Networks
Venue: arXiv cs.RO 2013
Year: 2013

Recent advances in communications, mobile computing, and artificial intelligence have greatly expanded the application space of intelligent distributed sensor networks. This in turn motivates the development of generalized Bayesian decentralized data fusion (DDF) algorithms for robust and efficient information sharing among autonomous agents using probabilistic belief models. However, DDF is significantly challenging to implement for general real-world applications requiring the use of dynamic/ad hoc network topologies and complex belief models, such as Gaussian mixtures or hybrid Bayesian networks. To tackle these issues, we first discuss some new key mathematical insights about exact DDF and conservative approximations to DDF. These insights are then used to develop novel generalized DDF algorithms for complex beliefs based on mixture pdfs and conditional factors. Numerical examples motivated by multi-robot target search demonstrate that our methods lead to significantly better fusion results, and thus have great potential to enhance distributed intelligent reasoning in sensor networks.
Percolation on the Information-Theoretically Secure Signal to Interference Ratio Graph
Venue: arXiv cs.IT 2013
Year: 2013

We consider a continuum percolation model consisting of two types of nodes, namely legitimate and eavesdropper nodes, distributed according to independent Poisson point processes (PPPs) in $\bbR ^2$ of intensities $λ$ and $λ_E$ respectively. A directed edge from one legitimate node $A$ to another legitimate node $B$ exists provided the strength of the {\it signal} transmitted from node $A$ that is received at node $B$ is higher than that received at any eavesdropper node. The strength of the received signal at a node from a legitimate node depends not only on the distance between these nodes, but also on the location of the other legitimate nodes and an interference suppression parameter $γ$. The graph is said to percolate when there exists an infinite connected component. We show that for any finite intensity $λ_E$ of eavesdropper nodes, there exists a critical intensity $λ_c < \infty$ such that for all $λ> λ_c$ the graph percolates for sufficiently small values of the interference parameter. Furthermore, for the sub-critical regime, we show that there exists a $λ_0$ such that for all $λ< λ_0 \leq λ_c$ a suitable graph defined over eavesdropper node connections percolates that precludes percolation in the graphs formed by the legitimate nodes.