OpenRaiser/Intern-Atlas huggingface dataset:
Kinematics and Workspace Analysis of a Three-Axis Parallel Manipulator: the Orthoglide
Venue: arXiv cs.RO 2007
Year: 2007

The paper addresses kinematic and geometrical aspects of the Orthoglide, a three-DOF parallel mechanism. This machine consists of three fixed linear joints, which are mounted orthogonally, three identical legs and a mobile platform, which moves in the Cartesian x-y-z space with fixed orientation. New solutions to solve inverse/direct kinematics are proposed and we perform a detailed workspace and singularity analysis, taking into account specific joint limit constraints.
Relative-Error CUR Matrix Decompositions
Venue: arXiv cs.DS 2007
Year: 2007

Many data analysis applications deal with large matrices and involve approximating the matrix using a small number of ``components.'' Typically, these components are linear combinations of the rows and columns of the matrix, and are thus difficult to interpret in terms of the original features of the input data. In this paper, we propose and study matrix approximations that are explicitly expressed in terms of a small number of columns and/or rows of the data matrix, and thereby more amenable to interpretation in terms of the original data. Our main algorithmic results are two randomized algorithms which take as input an $m \times n$ matrix $A$ and a rank parameter $k$. In our first algorithm, $C$ is chosen, and we let $A'=CC^+A$, where $C^+$ is the Moore-Penrose generalized inverse of $C$. In our second algorithm $C$, $U$, $R$ are chosen, and we let $A'=CUR$. ($C$ and $R$ are matrices that consist of actual columns and rows, respectively, of $A$, and $U$ is a generalized inverse of their intersection.) For each algorithm, we show that with probability at least $1-δ$: $$ ||A-A'||_F \leq (1+ε) ||A-A_k||_F, $$ where $A_k$ is the ``best'' rank-$k$ approximation provided by truncating the singular value decomposition (SVD) of $A$. The number of columns of $C$ and rows of $R$ is a low-degree polynomial in $k$, $1/ε$, and $\log(1/δ)$. Our two algorithms are the first polynomial time algorithms for such low-rank matrix approximations that come with relative-error guarantees; previously, in some cases, it was not even known whether such matrix decompositions exist. Both of our algorithms are simple, they take time of the order needed to approximately compute the top $k$ singular vectors of $A$, and they use a novel, intuitive sampling method called ``subspace sampling.''
Verified Real Number Calculations: A Library for Interval Arithmetic
Venue: arXiv cs.MS 2007
Year: 2007

Real number calculations on elementary functions are remarkably difficult to handle in mechanical proofs. In this paper, we show how these calculations can be performed within a theorem prover or proof assistant in a convenient and highly automated as well as interactive way. First, we formally establish upper and lower bounds for elementary functions. Then, based on these bounds, we develop a rational interval arithmetic where real number calculations take place in an algebraic setting. In order to reduce the dependency effect of interval arithmetic, we integrate two techniques: interval splitting and taylor series expansions. This pragmatic approach has been developed, and formally verified, in a theorem prover. The formal development also includes a set of customizable strategies to automate proofs involving explicit calculations over real numbers. Our ultimate goal is to provide guaranteed proofs of numerical properties with minimal human theorem-prover interaction.
Searching for a dangerous host: randomized vs. deterministic
Venue: arXiv cs.DC 2007
Year: 2007

A Black Hole is an harmful host in a network that destroys incoming agents without leaving any trace of such event. The problem of locating the black hole in a network through a team of agent coordinated by a common protocol is usually referred in literature as the Black Hole Search problem (or BHS for brevity) and it is a consolidated research topic in the area of distributed algorithms. The aim of this paper is to extend the results for BHS by considering more general (and hence harder) classes of dangerous host. In particular we introduce rB-hole as a probabilistic generalization of the Black Hole, in which the destruction of an incoming agent is a purely random event happening with some fixed probability (like flipping a biased coin). The main result we present is that if we tolerate an arbitrarily small error probability in the result then the rB-hole Search problem, or RBS, is not harder than the usual BHS. We establish this result in two different communication model, specifically both in presence or absence of whiteboards non-located at the homebase. The core of our methods is a general reduction tool for transforming algorithms for the black hole into algorithms for the rB-hole.
A course on Combinatorial Algorithms
Venue: arXiv cs.DM 2007
Year: 2007

The paper presents a course on Combinatorial Algorithms that is based on the drafts of the author that he used while teaching the course in the Department of Informatics and Applied Mathematics of Yerevan State University, Armenia from February 2007 to June 2007.
Graph Isomorphism is PSPACE-complete
Venue: arXiv cs.CC 2007
Year: 2007

Combining the the results of A.R. Meyer and L.J. Stockmeyer "The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space", and K.S. Booth "Isomorphism testing for graphs, semigroups, and finite automata are polynomiamlly equivalent problems" shows that graph isomorphism is PSPACE-complete.
The road coloring problem
Venue: arXiv cs.DM 2007
Year: 2007

The synchronizing word of deterministic automaton is a word in the alphabet of colors (considered as letters) of its edges that maps the automaton to a single state. A coloring of edges of a directed graph is synchronizing if the coloring turns the graph into deterministic finite automaton possessing a synchronizing word. The road coloring problem is a problem of synchronizing coloring of directed finite strongly connected graph with constant outdegree of all its vertices if the greatest common divisor of lengths of all its cycles is one. The problem was posed by Adler, Goodwyn and Weiss over 30 years ago and evoked a noticeable interest among the specialists in theory of graphs, deterministic automata and symbolic dynamics. The problem is described even in "Wikipedia" - the popular Internet Encyclopedia. The positive solution of the road coloring problem is presented.
On Ultrametric Algorithmic Information
Venue: arXiv cs.AI 2007
Year: 2007

How best to quantify the information of an object, whether natural or artifact, is a problem of wide interest. A related problem is the computability of an object. We present practical examples of a new way to address this problem. By giving an appropriate representation to our objects, based on a hierarchical coding of information, we exemplify how it is remarkably easy to compute complex objects. Our algorithmic complexity is related to the length of the class of objects, rather than to the length of the object.
Do oral messages help visual search?
Venue: arXiv cs.HC 2007
Year: 2007

A preliminary experimental study is presented, that aims at eliciting the contribution of oral messages to facilitating visual search tasks on crowded visual displays. Results of quantitative and qualitative analyses suggest that appropriate verbal messages can improve both target selection time and accuracy. In particular, multimodal messages including a visual presentation of the isolated target together with absolute spatial oral information on its location in the displayed scene seem most effective. These messages also got top-ranking ratings from most subjects.
Filtering Additive Measurement Noise with Maximum Entropy in the Mean
Venue: arXiv cs.LG 2007
Year: 2007

The purpose of this note is to show how the method of maximum entropy in the mean (MEM) may be used to improve parametric estimation when the measurements are corrupted by large level of noise. The method is developed in the context on a concrete example: that of estimation of the parameter in an exponential distribution. We compare the performance of our method with the bayesian and maximum likelihood approaches.
Discovering Patterns in Multi-neuronal Spike Trains using the Frequent Episode Method
Venue: arXiv cs.DB 2007
Year: 2007

Discovering the 'Neural Code' from multi-neuronal spike trains is an important task in neuroscience. For such an analysis, it is important to unearth interesting regularities in the spiking patterns. In this report, we present an efficient method for automatically discovering synchrony, synfire chains, and more general sequences of neuronal firings. We use the Frequent Episode Discovery framework of Laxman, Sastry, and Unnikrishnan (2005), in which the episodes are represented and recognized using finite-state automata. Many aspects of functional connectivity between neuronal populations can be inferred from the episodes. We demonstrate these using simulated multi-neuronal data from a Poisson model. We also present a method to assess the statistical significance of the discovered episodes. Since the Temporal Data Mining (TDM) methods used in this report can analyze data from hundreds and potentially thousands of neurons, we argue that this framework is appropriate for discovering the `Neural Code'.
Simple Algorithmic Principles of Discovery, Subjective Beauty, Selective Attention, Curiosity & Creativity
Venue: arXiv cs.AI 2007
Year: 2007

I postulate that human or other intelligent agents function or should function as follows. They store all sensory observations as they come - the data is holy. At any time, given some agent's current coding capabilities, part of the data is compressible by a short and hopefully fast program / description / explanation / world model. In the agent's subjective eyes, such data is more regular and more "beautiful" than other data. It is well-known that knowledge of regularity and repeatability may improve the agent's ability to plan actions leading to external rewards. In absence of such rewards, however, known beauty is boring. Then "interestingness" becomes the first derivative of subjective beauty: as the learning agent improves its compression algorithm, formerly apparently random data parts become subjectively more regular and beautiful. Such progress in compressibility is measured and maximized by the curiosity drive: create action sequences that extend the observation history and yield previously unknown / unpredictable but quickly learnable algorithmic regularity. We discuss how all of the above can be naturally implemented on computers, through an extension of passive unsupervised learning to the case of active data selection: we reward a general reinforcement learner (with access to the adaptive compressor) for actions that improve the subjective compressibility of the growing data. An unusually large breakthrough in compressibility deserves the name "discovery". The "creativity" of artists, dancers, musicians, pure mathematicians can be viewed as a by-product of this principle. Several qualitative examples support this hypothesis.
Geometric Complexity Theory: Introduction
Venue: arXiv cs.CC 2007
Year: 2007

These are lectures notes for the introductory graduate courses on geometric complexity theory (GCT) in the computer science department, the university of Chicago. Part I consists of the lecture notes for the course given by the first author in the spring quarter, 2007. It gives introduction to the basic structure of GCT. Part II consists of the lecture notes for the course given by the second author in the spring quarter, 2003. It gives introduction to invariant theory with a view towards GCT. No background in algebraic geometry or representation theory is assumed. These lecture notes in conjunction with the article \cite{GCTflip1}, which describes in detail the basic plan of GCT based on the principle called the flip, should provide a high level picture of GCT assuming familiarity with only basic notions of algebra, such as groups, rings, fields etc.
Finding Paths and Cycles in Graphs
Venue: arXiv cs.DM 2007
Year: 2007

A polynomial time algorithm which detects all paths and cycles of all lengths in form of vertex pairs (start, finish).
The Description of Information in 4-Dimensional Pseudo-Euclidean Information Space
Venue: arXiv cs.IT 2007
Year: 2007

This article is presented new method of description information systems in abstract 4-dimensional pseudo-Euclidean information space (4-DPIES) with using special relativity (SR) methods. This purpose core postulates of existence 4-DPIES are formulated. The theorem setting existence criteria of the invariant velocity of the information transference is formulated and proved. One more theorem allowed relating discrete parameters of information and continuous space-time treating and also row of supplementary theorems is formulated and proved. For description of dynamics and interaction of information, in article is introduced general parameter of information - generalized information emotion (GIE), reminding simultaneously on properties the mass and the charge. At performing calculation of information observable parameters in the information space is introduced continual integration methods of Feynman. The applying idea about existence of GIE as measures of the information inertness and the interaction carrier, and using continual integration methods of Feynman can be calculated probability of information process in 4-DPIES. In this frame presented approach has allowed considering information systems when interest is presented with information processes, their related with concrete definition without necessity. The relation between 4-DPIES and real systems parameters is set at modelling of matching between observable processes and real phenomena from information interpretation.
Bandwidth selection for kernel estimation in mixed multi-dimensional spaces
Venue: arXiv cs.CV 2007
Year: 2007

Kernel estimation techniques, such as mean shift, suffer from one major drawback: the kernel bandwidth selection. The bandwidth can be fixed for all the data set or can vary at each points. Automatic bandwidth selection becomes a real challenge in case of multidimensional heterogeneous features. This paper presents a solution to this problem. It is an extension of \cite{Comaniciu03a} which was based on the fundamental property of normal distributions regarding the bias of the normalized density gradient. The selection is done iteratively for each type of features, by looking for the stability of local bandwidth estimates across a predefined range of bandwidths. A pseudo balloon mean shift filtering and partitioning are introduced. The validity of the method is demonstrated in the context of color image segmentation based on a 5-dimensional space.
Distributed Decision Through Self-Synchronizing Sensor Networks in the Presence of Propagation Delays and Asymmetric Channels
Venue: arXiv cs.MA 2007
Year: 2007

In this paper we propose and analyze a distributed algorithm for achieving globally optimal decisions, either estimation or detection, through a self-synchronization mechanism among linearly coupled integrators initialized with local measurements. We model the interaction among the nodes as a directed graph with weights (possibly) dependent on the radio channels and we pose special attention to the effect of the propagation delay occurring in the exchange of data among sensors, as a function of the network geometry. We derive necessary and sufficient conditions for the proposed system to reach a consensus on globally optimal decision statistics. One of the major results proved in this work is that a consensus is reached with exponential convergence speed for any bounded delay condition if and only if the directed graph is quasi-strongly connected. We provide a closed form expression for the global consensus, showing that the effect of delays is, in general, the introduction of a bias in the final decision. Finally, we exploit our closed form expression to devise a double-step consensus mechanism able to provide an unbiased estimate with minimum extra complexity, without the need to know or estimate the channel parameters.
Incremental Satisfiability and Implication for UTVPI Constraints
Venue: arXiv cs.DS 2007
Year: 2007

Unit two-variable-per-inequality (UTVPI) constraints form one of the largest class of integer constraints which are polynomial time solvable (unless P=NP). There is considerable interest in their use for constraint solving, abstract interpretation, spatial databases, and theorem proving. In this paper we develop a new incremental algorithm for UTVPI constraint satisfaction and implication checking that requires O(m + n log n + p) time and O(n+m+p) space to incrementally check satisfiability of m UTVPI constraints on n variables and check implication of p UTVPI constraints.
Une adaptation des cartes auto-organisatrices pour des données décrites par un tableau de dissimilarités
Venue: arXiv cs.NE 2007
Year: 2007

Many data analysis methods cannot be applied to data that are not represented by a fixed number of real values, whereas most of real world observations are not readily available in such a format. Vector based data analysis methods have therefore to be adapted in order to be used with non standard complex data. A flexible and general solution for this adaptation is to use a (dis)similarity measure. Indeed, thanks to expert knowledge on the studied data, it is generally possible to define a measure that can be used to make pairwise comparison between observations. General data analysis methods are then obtained by adapting existing methods to (dis)similarity matrices. In this article, we propose an adaptation of Kohonen's Self Organizing Map (SOM) to (dis)similarity data. The proposed algorithm is an adapted version of the vector based batch SOM. The method is validated on real world data: we provide an analysis of the usage patterns of the web site of the Institut National de Recherche en Informatique et Automatique, constructed thanks to web log mining method.
Self-organizing maps and symbolic data
Venue: arXiv cs.NE 2007
Year: 2007

In data analysis new forms of complex data have to be considered like for example (symbolic data, functional data, web data, trees, SQL query and multimedia data, ...). In this context classical data analysis for knowledge discovery based on calculating the center of gravity can not be used because input are not $\mathbb{R}^p$ vectors. In this paper, we present an application on real world symbolic data using the self-organizing map. To this end, we propose an extension of the self-organizing map that can handle symbolic data.
Algorithm of Static Deadlock Detection in MPI Synchronization Communication Sequential Model
Venue: arXiv cs.DC 2007
Year: 2007

Detecting deadlocks in MPI synchronization communication programs is very difficult and need building program models. All complex models are based on sequential models. The sequential model is mapped into a set of character strings and its deadlock detection problem is translated into an equivalent multi-queue string matching problem. An algorithm is devised and implemented to statically detect deadlocks in sequential models of MPI synchronization communication programs. The time and space complexity of the algorithm is O(n) where n is the amount of message in model. The algorithm is better than usual circle-detection methods and can adapt well to dynamic message stream.
On Real-Time Communication Systems with Noisy Feedback
Venue: arXiv cs.IT 2007
Year: 2007

We consider a real-time communication system with noisy feedback consisting of a Markov source, a forward and a backward discrete memoryless channels, and a receiver with finite memory. The objective is to design an optimal communication strategy (that is, encoding, decoding, and memory update strategies) to minimize the total expected distortion over a finite horizon. We present a sequential decomposition for the problem, which results in a set of nested optimality equations to determine optimal communication strategies. This provides a systematic methodology to determine globally optimal joint source-channel encoding and decoding strategies for real-time communication systems with noisy feedback.
Fitness landscape of the cellular automata majority problem: View from the Olympus
Venue: arXiv cs.AI 2007
Year: 2007

In this paper we study cellular automata (CAs) that perform the computational Majority task. This task is a good example of what the phenomenon of emergence in complex systems is. We take an interest in the reasons that make this particular fitness landscape a difficult one. The first goal is to study the landscape as such, and thus it is ideally independent from the actual heuristics used to search the space. However, a second goal is to understand the features a good search technique for this particular problem space should possess. We statistically quantify in various ways the degree of difficulty of searching this landscape. Due to neutrality, investigations based on sampling techniques on the whole landscape are difficult to conduct. So, we go exploring the landscape from the top. Although it has been proved that no CA can perform the task perfectly, several efficient CAs for this task have been found. Exploiting similarities between these CAs and symmetries in the landscape, we define the Olympus landscape which is regarded as the ''heavenly home'' of the best local optima known (blok). Then we measure several properties of this subspace. Although it is easier to find relevant CAs in this subspace than in the overall landscape, there are structural reasons that prevent a searcher from finding overfitted CAs in the Olympus. Finally, we study dynamics and performance of genetic algorithms on the Olympus in order to confirm our analysis and to find efficient CAs for the Majority problem with low computational cost.
From Texts to Structured Documents: The Case of Health Practice Guidelines
Venue: arXiv cs.AI 2007
Year: 2007

This paper describes a system capable of semi-automatically filling an XML template from free texts in the clinical domain (practice guidelines). The XML template includes semantic information not explicitly encoded in the text (pairs of conditions and actions/recommendations). Therefore, there is a need to compute the exact scope of conditions over text sequences expressing the required actions. We present in this paper the rules developed for this task. We show that the system yields good performance when applied to the analysis of French practice guidelines.