OpenRaiser/Intern-Atlas huggingface dataset:
Clustering with Spectral Norm and the k-means Algorithm
Venue: arXiv cs.DS 2010
Year: 2010

There has been much progress on efficient algorithms for clustering data points generated by a mixture of $k$ probability distributions under the assumption that the means of the distributions are well-separated, i.e., the distance between the means of any two distributions is at least $Ω(k)$ standard deviations. These results generally make heavy use of the generative model and particular properties of the distributions. In this paper, we show that a simple clustering algorithm works without assuming any generative (probabilistic) model. Our only assumption is what we call a "proximity condition": the projection of any data point onto the line joining its cluster center to any other cluster center is $Ω(k)$ standard deviations closer to its own center than the other center. Here the notion of standard deviations is based on the spectral norm of the matrix whose rows represent the difference between a point and the mean of the cluster to which it belongs. We show that in the generative models studied, our proximity condition is satisfied and so we are able to derive most known results for generative models as corollaries of our main result. We also prove some new results for generative models - e.g., we can cluster all but a small fraction of points only assuming a bound on the variance. Our algorithm relies on the well known $k$-means algorithm, and along the way, we prove a result of independent interest -- that the $k$-means algorithm converges to the "true centers" even in the presence of spurious points provided the initial (estimated) centers are close enough to the corresponding actual centers and all but a small fraction of the points satisfy the proximity condition. Finally, we present a new technique for boosting the ratio of inter-center separation to standard deviation.
About the embedding of one dimensional cellular automata into hyperbolic cellular automata
Venue: arXiv cs.FL 2010
Year: 2010

In this paper, we look at two ways to implement determinisitic one dimensional cellular automata into hyperbolic cellular automata in three contexts: the pentagrid, the heptagrid and the dodecagrid, these tilings being classically denoted by $\{5,4\}$, $\{7,3\}$ and $\{5,3,4\}$ respectively.
Feature Level Fusion of Face and Palmprint Biometrics by Isomorphic Graph-based Improved K-Medoids Partitioning
Venue: arXiv cs.CV 2010
Year: 2010

This paper presents a feature level fusion approach which uses the improved K-medoids clustering algorithm and isomorphic graph for face and palmprint biometrics. Partitioning around medoids (PAM) algorithm is used to partition the set of n invariant feature points of the face and palmprint images into k clusters. By partitioning the face and palmprint images with scale invariant features SIFT points, a number of clusters is formed on both the images. Then on each cluster, an isomorphic graph is drawn. In the next step, the most probable pair of graphs is searched using iterative relaxation algorithm from all possible isomorphic graphs for a pair of corresponding face and palmprint images. Finally, graphs are fused by pairing the isomorphic graphs into augmented groups in terms of addition of invariant SIFT points and in terms of combining pair of keypoint descriptors by concatenation rule. Experimental results obtained from the extensive evaluation show that the proposed feature level fusion with the improved K-medoids partitioning algorithm increases the performance of the system with utmost level of accuracy.
An optimized recursive learning algorithm for three-layer feedforward neural networks for mimo nonlinear system identifications
Venue: arXiv cs.NE 2010
Year: 2010

Back-propagation with gradient method is the most popular learning algorithm for feed-forward neural networks. However, it is critical to determine a proper fixed learning rate for the algorithm. In this paper, an optimized recursive algorithm is presented for online learning based on matrix operation and optimization methods analytically, which can avoid the trouble to select a proper learning rate for the gradient method. The proof of weak convergence of the proposed algorithm also is given. Although this approach is proposed for three-layer, feed-forward neural networks, it could be extended to multiple layer feed-forward neural networks. The effectiveness of the proposed algorithms applied to the identification of behavior of a two-input and two-output non-linear dynamic system is demonstrated by simulation experiments.
Matrix Coherence and the Nystrom Method
Venue: arXiv cs.AI 2010
Year: 2010

The Nystrom method is an efficient technique to speed up large-scale learning applications by generating low-rank approximations. Crucial to the performance of this technique is the assumption that a matrix can be well approximated by working exclusively with a subset of its columns. In this work we relate this assumption to the concept of matrix coherence and connect matrix coherence to the performance of the Nystrom method. Making use of related work in the compressed sensing and the matrix completion literature, we derive novel coherence-based bounds for the Nystrom method in the low-rank setting. We then present empirical results that corroborate these theoretical bounds. Finally, we present more general empirical results for the full-rank setting that convincingly demonstrate the ability of matrix coherence to measure the degree to which information can be extracted from a subset of columns.
A New Full-diversity Criterion and Low-complexity STBCs with Partial Interference Cancellation Decoding
Venue: arXiv cs.IT 2010
Year: 2010

Recently, Guo and Xia gave sufficient conditions for an STBC to achieve full diversity when a PIC (Partial Interference Cancellation) or a PIC-SIC (PIC with Successive Interference Cancellation) decoder is used at the receiver. In this paper, we give alternative conditions for an STBC to achieve full diversity with PIC and PIC-SIC decoders, which are equivalent to Guo and Xia's conditions, but are much easier to check. Using these conditions, we construct a new class of full diversity PIC-SIC decodable codes, which contain the Toeplitz codes and a family of codes recently proposed by Zhang, Xu et. al. as proper subclasses. With the help of the new criteria, we also show that a class of PIC-SIC decodable codes recently proposed by Zhang, Shi et. al. can be decoded with much lower complexity than what is reported, without compromising on full diversity.
Constraint-based Query Distribution Framework for an Integrated Global Schema
Venue: arXiv cs.DB 2010
Year: 2010

Distributed heterogeneous data sources need to be queried uniformly using global schema. Query on global schema is reformulated so that it can be executed on local data sources. Constraints in global schema and mappings are used for source selection, query optimization,and querying partitioned and replicated data sources. The provided system is all XML-based which poses query in XML form, transforms, and integrates local results in an XML document. Contributions include the use of constraints in our existing global schema which help in source selection and query optimization, and a global query distribution framework for querying distributed heterogeneous data sources.
Learning Deterministic Regular Expressions for the Inference of Schemas from XML Data
Venue: arXiv cs.DB 2010
Year: 2010

Inferring an appropriate DTD or XML Schema Definition (XSD) for a given collection of XML documents essentially reduces to learning deterministic regular expressions from sets of positive example words. Unfortunately, there is no algorithm capable of learning the complete class of deterministic regular expressions from positive examples only, as we will show. The regular expressions occurring in practical DTDs and XSDs, however, are such that every alphabet symbol occurs only a small number of times. As such, in practice it suffices to learn the subclass of deterministic regular expressions in which each alphabet symbol occurs at most k times, for some small k. We refer to such expressions as k-occurrence regular expressions (k-OREs for short). Motivated by this observation, we provide a probabilistic algorithm that learns k-OREs for increasing values of k, and selects the deterministic one that best describes the sample based on a Minimum Description Length argument. The effectiveness of the method is empirically validated both on real world and synthetic data. Furthermore, the method is shown to be conservative over the simpler classes of expressions considered in previous work.
Autoplot: A browser for scientific data on the web
Venue: arXiv cs.GR 2010
Year: 2010

Autoplot is software developed for the Virtual Observatories in Heliophysics to provide intelligent and automated plotting capabilities for many typical data products that are stored in a variety of file formats or databases. Autoplot has proven to be a flexible tool for exploring, accessing, and viewing data resources as typically found on the web, usually in the form of a directory containing data files with multiple parameters contained in each file. Data from a data source is abstracted into a common internal data model called QDataSet. Autoplot is built from individually useful components, and can be extended and reused to create specialized data handling and analysis applications and is being used in a variety of science visualization and analysis applications. Although originally developed for viewing heliophysics-related time series and spectrograms, its flexible and generic data representation model makes it potentially useful for the Earth sciences.
Symmetry within Solutions
Venue: arXiv cs.AI 2010
Year: 2010

We define the concept of an internal symmetry. This is a symmety within a solution of a constraint satisfaction problem. We compare this to solution symmetry, which is a mapping between different solutions of the same problem. We argue that we may be able to exploit both types of symmetry when finding solutions. We illustrate the potential of exploiting internal symmetries on two benchmark domains: Van der Waerden numbers and graceful graphs. By identifying internal symmetries we are able to extend the state of the art in both cases.
Balanced Vertices in Trees and a Simpler Algorithm to Compute the Genomic Distance
Venue: arXiv cs.DM 2010
Year: 2010

This paper provides a short and transparent solution for the covering cost of white-grey trees which play a crucial role in the algorithm of Bergeron {\it et al.}\ to compute the rearrangement distance between two multichromosomal genomes in linear time ({\it Theor. Comput. Sci.}, 410:5300-5316, 2009). In the process it introduces a new {\em center} notion for trees, which seems to be interesting on its own.
Fault Diagnosis with Dynamic Observers
Venue: arXiv cs.FL 2010
Year: 2010

In this paper, we review some recent results about the use of dynamic observers for fault diagnosis of discrete event systems. Fault diagnosis consists in synthesizing a diagnoser that observes a given plant and identifies faults in the plant as soon as possible after their occurrence. Existing literature on this problem has considered the case of fixed static observers, where the set of observable events is fixed and does not change during execution of the system. In this paper, we consider dynamic observers: an observer can "switch" sensors on or off, thus dynamically changing the set of events it wishes to observe. It is known that checking diagnosability (i.e., whether a given observer is capable of identifying faults) can be solved in polynomial time for static observers, and we show that the same is true for dynamic ones. We also solve the problem of dynamic observers' synthesis and prove that a most permissive observer can be computed in doubly exponential time, using a game-theoretic approach. We further investigate optimization problems for dynamic observers and define a notion of cost of an observer.
Approximation Algorithms for the Capacitated Domination Problem
Venue: arXiv cs.DM 2010
Year: 2010

We consider the {\em Capacitated Domination} problem, which models a service-requirement assignment scenario and is also a generalization of the well-known {\em Dominating Set} problem. In this problem, given a graph with three parameters defined on each vertex, namely cost, capacity, and demand, we want to find an assignment of demands to vertices of least cost such that the demand of each vertex is satisfied subject to the capacity constraint of each vertex providing the service. In terms of polynomial time approximations, we present logarithmic approximation algorithms with respect to different demand assignment models for this problem on general graphs, which also establishes the corresponding approximation results to the well-known approximations of the traditional {\em Dominating Set} problem. Together with our previous work, this closes the problem of generally approximating the optimal solution. On the other hand, from the perspective of parameterization, we prove that this problem is {\it W[1]}-hard when parameterized by a structure of the graph called treewidth. Based on this hardness result, we present exact fixed-parameter tractable algorithms when parameterized by treewidth and maximum capacity of the vertices. This algorithm is further extended to obtain pseudo-polynomial time approximation schemes for planar graphs.
Code forking in open-source software: a requirements perspective
Venue: arXiv cs.SE 2010
Year: 2010

To fork a project is to copy the existing code base and move in a direction different than that of the erstwhile project leadership. Forking provides a rapid way to address new requirements by adapting an existing solution. However, it can also create a plethora of similar tools, and fragment the developer community. Hence, it is not always clear whether forking is the right strategy. In this paper, we describe a mixed-methods exploratory case study that investigated the process of forking a project. The study concerned the forking of an open-source tool for managing software projects, Trac. Trac was forked to address differing requirements in an academic setting. The paper makes two contributions to our understanding of code forking. First, our exploratory study generated several theories about code forking in open source projects, for further research. Second, we investigated one of these theories in depth, via a quantitative study. We conjectured that the features of the OSS forking process would allow new requirements to be addressed. We show that the forking process in this case was successful at fulfilling the new projects requirements.
The Online Laboratory: Conducting Experiments in a Real Labor Market
Venue: arXiv cs.HC 2010
Year: 2010

Online labor markets have great potential as platforms for conducting experiments, as they provide immediate access to a large and diverse subject pool and allow researchers to conduct randomized controlled trials. We argue that online experiments can be just as valid---both internally and externally---as laboratory and field experiments, while requiring far less money and time to design and to conduct. In this paper, we first describe the benefits of conducting experiments in online labor markets; we then use one such market to replicate three classic experiments and confirm their results. We confirm that subjects (1) reverse decisions in response to how a decision-problem is framed, (2) have pro-social preferences (value payoffs to others positively), and (3) respond to priming by altering their choices. We also conduct a labor supply field experiment in which we confirm that workers have upward sloping labor supply curves. In addition to reporting these results, we discuss the unique threats to validity in an online setting and propose methods for coping with these threats. We also discuss the external validity of results from online domains and explain why online results can have external validity equal to or even better than that of traditional methods, depending on the research question. We conclude with our views on the potential role that online experiments can play within the social sciences, and then recommend software development priorities and best practices.
Online Sparse System Identification and Signal Reconstruction using Projections onto Weighted $\ell_1$ Balls
Venue: arXiv cs.IT 2010
Year: 2010

This paper presents a novel projection-based adaptive algorithm for sparse signal and system identification. The sequentially observed data are used to generate an equivalent sequence of closed convex sets, namely hyperslabs. Each hyperslab is the geometric equivalent of a cost criterion, that quantifies "data mismatch". Sparsity is imposed by the introduction of appropriately designed weighted $\ell_1$ balls. The algorithm develops around projections onto the sequence of the generated hyperslabs as well as the weighted $\ell_1$ balls. The resulting scheme exhibits linear dependence, with respect to the unknown system's order, on the number of multiplications/additions and an $\mathcal{O}(L\log_2L)$ dependence on sorting operations, where $L$ is the length of the system/signal to be estimated. Numerical results are also given to validate the performance of the proposed method against the LASSO algorithm and two very recently developed adaptive sparse LMS and LS-type of adaptive algorithms, which are considered to belong to the same algorithmic family.
Focusing in Asynchronous Games
Venue: arXiv cs.LO 2010
Year: 2010

Game semantics provides an interactive point of view on proofs, which enables one to describe precisely their dynamical behavior during cut elimination, by considering formulas as games on which proofs induce strategies. We are specifically interested here in relating two such semantics of linear logic, of very different flavor, which both take in account concurrent features of the proofs: asynchronous games and concurrent games. Interestingly, we show that associating a concurrent strategy to an asynchronous strategy can be seen as a semantical counterpart of the focusing property of linear logic.
Watermarking Java Programs using Dummy Methods with Dynamically Opaque Predicates
Venue: arXiv cs.CR 2010
Year: 2010

Software piracy, the illegal using, copying, and resale of applications is a major concern for anyone develops software. Software developers also worry about their applications being reverse engineered by extracting data structures and algorithms from an application and incorporated into competitor's code. A defense against software piracy is watermarking, a process that embeds a secret message in a cover software. Watermarking is a method that does not aim to stop piracy copying, but to prove ownership of the software and possibly even the data structures and algorithms used in the software. The language Java was designed to be compiled into a platform independent bytecode format. Much of the information contained in the source code remains in the bytecode, which means that decompilation is easier than with traditional native codes. In this thesis, we present a technique for watermarking Java programs by using a never-executed dummy method (Monden et.al., 2000) combined with opaque predicates (Collberg et.al., 1998; Arboit, 2002) and improved with dynamically opaque predicates (Palsberg et.al., 2000). This work presents a method to construct a dynamic opaque predicates by grouping two or more opaque predicates according to predefined rules. Any software watermarking technique will exhibit a trade-off between resilience, data rate, cost, and stealth. To evaluate the quality of a watermarking scheme we must also know how well it stands up to different types of attacks. Ideally, we would like our watermarks to survive translation (compilation, decompilation, and binary translation), optimization, and obfuscation. Add a single watermark will increasing source code approximate 3.854 bytes with dummy method that cover up to 15 characters, two dynamic data structures, two threads and two opaque predicates. Application loading-time increase approximate 6108 milliseconds.
Adaptive Neuro-Fuzzy Extended Kalman Filtering for Robot Localization
Venue: arXiv cs.OH 2010
Year: 2010

Extended Kalman Filter (EKF) has been a popular approach to localization a mobile robot. However, the performance of the EKF and the quality of the estimation depends on the correct a priori knowledge of process and measurement noise covariance matrices (Qk and Rk, respectively). Imprecise knowledge of these statistics can cause significant degradation in performance. This paper proposed the development of an Adaptive Neuro- Fuzzy Extended Kalman Filtering (ANFEKF) for localization of robot. The Adaptive Neuro-Fuzzy attempts to estimate the elements of Qk and Rk matrices of the EKF algorithm, at each sampling instant when measurement update step is carried out. The ANFIS supervises the performance of the EKF with the aim of reducing the mismatch between the theoretical and actual covariance of the innovation sequences. The free parameters of ANFIS are trained using the steepest gradient descent (SD) to minimize the differences of the actual value of the covariance of the residual with its theoretical value as much possible. The simulation results show the effectiveness of the proposed algorithm.
C Implementation & comparison of companding & silence audio compression techniques
Venue: arXiv cs.MM 2010
Year: 2010

Just about all the newest living room audio-video electronics and PC multimedia products being designed today will incorporate some form of compressed digitized-audio processing capability. Audio compression reduces the bit rate required to represent an analog audio signal while maintaining the perceived audio quality. Discarding inaudible data reduces the storage, transmission and compute requirements of handling high-quality audio files. This paper covers wave audio file format & algorithm of silence compression method and companding method to compress and decompress wave audio file. Then it compares the result of these two methods.
Wireless Network Code Design and Performance Analysis using Diversity-Multiplexing Tradeoff
Venue: arXiv cs.IT 2010
Year: 2010

Network coding and cooperative communication have received considerable attention from the research community recently in order to mitigate the adverse effects of fading in wireless transmissions and at the same time to achieve high throughput and better spectral efficiency. In this work, we design and analyze deterministic and random network coding schemes for a cooperative communication setup with multiple sources and destinations. We show that our schemes outperform conventional cooperation in terms of the diversity-multiplexing tradeoff (DMT). Specifically, it achieves the full-diversity order at the expense of a slightly reduced multiplexing rate. We establish the link between the parity-check matrix for a $(N+M,M,N+1)$ systematic MDS code and the network coding coefficients in a cooperative communication system of $N$ source-destination pairs and $M$ relays. We present two ways to generate the network coding matrix: using the Cauchy matrices and the Vandermonde matrices, and establish that they both offer the maximum diversity order.