OpenRaiser/Intern-Atlas huggingface dataset:
Compressive Diffraction Tomography for Weakly Scattering
Venue: arXiv cs.CE 2009
Year: 2009

An appealing requirement from the well-known diffraction tomography (DT) exists for success reconstruction from few-view and limited-angle data. Inspired by the well-known compressive sensing (CS), the accurate super-resolution reconstruction from highly sparse data for the weakly scatters has been investigated in this paper. To realize the compressive data measurement, in particular, to obtain the super-resolution reconstruction with highly sparse data, the compressive system which is realized by surrounding the probed obstacles by the random media has been proposed and empirically studied. Several interesting conclusions have been drawn: (a) if the desired resolution is within the range from to, the K-sparse N-unknowns imaging can be obtained exactly bymeasurements, which is comparable to the required number of measurement by the Gaussian random matrix in the literatures of compressive sensing. (b) With incorporating the random media which is used to enforce the multi-path effect of wave propagation, the resulting measurement matrix is incoherence with wavelet matrix, in other words, when the probed obstacles are sparse with the framework of wavelet, the required number of measurements for successful reconstruction is similar as above. (c) If the expected resolution is lower than, the required number of measurements of proposed compressive system is almost identical to the case of free space. (d) There is also a requirement to make the tradeoff between the imaging resolutions and the number of measurements. In addition, by the introduction of complex Gaussian variable the kind of fast sparse Bayesian algorithm has been slightly modified to deal with the complex-valued optimization with sparse constraints.
New Branching Rules: Improvements on Independent Set and Vertex Cover in Sparse Graphs
Venue: arXiv cs.DS 2009
Year: 2009

We present an $O^*(1.0919^n)$-time algorithm for finding a maximum independent set in an $n$-vertex graph with degree bounded by 3, which improves the previously known algorithm of running time $O^*(1.0977^n)$ by Bourgeois, Escoffier and Paschos [IWPEC 2008]. We also present an $O^*(1.1923^k)$-time algorithm to decide if a graph with degree bounded by 3 has a vertex cover of size $k$, which improves the previously known algorithm of running time $O^*(1.1939^k)$ by Chen, Kanj and Xia [ISAAC 2003]. Two new branching techniques, \emph{branching on a bottle} and \emph{branching on a 4-cycle}, are introduced, which help us to design simple and fast algorithms for the maximum independent set and minimum vertex cover problems and avoid tedious branching rules.
Error Scaling Laws for Linear Optimal Estimation from Relative Measurements
Venue: arXiv cs.IT 2009
Year: 2009

We study the problem of estimating vector-valued variables from noisy "relative" measurements. This problem arises in several sensor network applications. The measurement model can be expressed in terms of a graph, whose nodes correspond to the variables and edges to noisy measurements of the difference between two variables. We take an arbitrary variable as the reference and consider the optimal (minimum variance) linear unbiased estimate of the remaining variables. We investigate how the error in the optimal linear unbiased estimate of a node variable grows with the distance of the node to the reference node. We establish a classification of graphs, namely, dense or sparse in Rd,1<= d <=3, that determines how the linear unbiased optimal estimation error of a node grows with its distance from the reference node. In particular, if a graph is dense in 1,2, or 3D, then a node variable's estimation error is upper bounded by a linear, logarithmic, or bounded function of distance from the reference, respectively. Corresponding lower bounds are obtained if the graph is sparse in 1, 2 and 3D. Our results also show that naive measures of graph density, such as node degree, are inadequate predictors of the estimation error. Being true for the optimal linear unbiased estimate, these scaling laws determine algorithm-independent limits on the estimation accuracy achievable in large graphs.
Agent-Based Decision Support System to Prevent and Manage Risk Situations
Venue: arXiv cs.AI 2009
Year: 2009

The topic of risk prevention and emergency response has become a key social and political concern. One approach to address this challenge is to develop Decision Support Systems (DSS) that can help emergency planners and responders to detect emergencies, as well as to suggest possible course of actions to deal with the emergency. Our research work comes in this framework and aims to develop a DSS that must be generic as much as possible and independent from the case study.
Efficient Construction of Neighborhood Graphs by the Multiple Sorting Method
Venue: arXiv cs.DS 2009
Year: 2009

Neighborhood graphs are gaining popularity as a concise data representation in machine learning. However, naive graph construction by pairwise distance calculation takes $O(n^2)$ runtime for $n$ data points and this is prohibitively slow for millions of data points. For strings of equal length, the multiple sorting method (Uno, 2008) can construct an $ε$-neighbor graph in $O(n+m)$ time, where $m$ is the number of $ε$-neighbor pairs in the data. To introduce this remarkably efficient algorithm to continuous domains such as images, signals and texts, we employ a random projection method to convert vectors to strings. Theoretical results are presented to elucidate the trade-off between approximation quality and computation time. Empirical results show the efficiency of our method in comparison to fast nearest neighbor alternatives.
Efficient Measurement of Complex Networks Using Link Queries
Venue: arXiv cs.NI 2009
Year: 2009

Complex networks are at the core of an intense research activity. However, in most cases, intricate and costly measurement procedures are needed to explore their structure. In some cases, these measurements rely on link queries: given two nodes, it is possible to test the existence of a link between them. These tests may be costly, and thus minimizing their number while maximizing the number of discovered links is a key issue. This paper studies this problem: we observe that properties classically observed on real-world complex networks give hints for their efficient measurement; we derive simple principles and several measurement strategies based on this, and experimentally evaluate their efficiency on real-world cases. In order to do so, we introduce methods to evaluate the efficiency of strategies. We also explore the bias that different measurement strategies may induce.
The Business of Selling Electronic Documents
Venue: arXiv cs.GL 2009
Year: 2009

The music industry has huge troubles adapting to the new technologies. As many pointed out, when copying music is essentially free and socially accepted it becomes increasingly tempting for users to infringe copyrights and copy music from one person to another. The answer of the music industry is to outlaw a majority of citizens. This article describes how the music industry should reinvent itself and adapt to a world where the network is ubiquitous and exchanging information is essentially free. It relies on adapting prices to the demand and lower costs of electronic documents in a dramatic way.
A Thermodynamic Turing Machine: Artificial Molecular Computing Using Classical Reversible Logic Switching Networks
Venue: arXiv cs.CC 2009
Year: 2009

This paper discusses how to implement certain classes of quantum computer algorithms using classical discrete switching networks that are amenable to implementation in main stream CMOS transistor IC technology. The methods differ from other classical approaches in that asynchronous feedback is exploited in classical transistor reversible logic circuits to implement the Hadamard transform in one simultaneous step over all qubits as in a true quantum computer. The Simon problem is used as an example. The method is used to provide an order n execution speed method for the Gaussian elimination step in the Simon problem. The approach is referred to as a Thermodynamic Turing Machine in that it behaves like an artificial molecule where solutions to a problem are found by evolving the classical circuits from one thermodynamic equilibrium state to another.
Relation between the Usual Order and the Enumeration Orders of Elements of r.e. Sets
Venue: arXiv cs.FL 2009
Year: 2009

In this paper, we have compared r.e. sets based on their enumeration orders with Turing machines. Accordingly, we have defined novel concept uniformity for Turing machines and r.e. sets and have studied some relationships between uniformity and both one-reducibility and Turing reducibility. Furthermore, we have defined type-2 uniformity concept and studied r.e. sets and Turing machines based on this concept. In the end, we have introduced a new structure called Turing Output Binary Search Tree that helps us lighten some ideas.
Variations of the Turing Test in the Age of Internet and Virtual Reality
Venue: arXiv cs.AI 2009
Year: 2009

Inspired by Hofstadter's Coffee-House Conversation (1982) and by the science fiction short story SAM by Schattschneider (1988), we propose and discuss criteria for non-mechanical intelligence. Firstly, we emphasize the practical need for such tests in view of massively multiuser online role-playing games (MMORPGs) and virtual reality systems like Second Life. Secondly, we demonstrate Second Life as a useful framework for implementing (some iterations of) that test.
Direction-of-Arrival Estimation for Temporally Correlated Narrowband Signals
Venue: arXiv cs.IT 2009
Year: 2009

signal direction-of-arrival estimation using an array of sensors has been the subject of intensive research and development during the last two decades. Efforts have been directed to both, better solutions for the general data model and to develop more realistic models. So far, many authors have assumed the data to be iid samples of a multivariate statistical model. Although this assumption reduces the complexity of the model, it may not be true in certain situations where signals show temporal correlation. Some results are available on the temporally correlated signal model in the literature. The temporally correlated stochastic Cramer-Rao bound (CRB) has been calculated and an instrumental variable-based method called IV-SSF is introduced. Also, it has been shown that temporally correlated CRB is lower bounded by the deterministic CRB. In this paper, we show that temporally correlated CRB is also upper bounded by the stochastic iid CRB. We investigate the effect of temporal correlation of the signals on the best achievable performance. We also show that the IV-SSF method is not efficient and based on an analysis of the CRB, propose a variation in the method which boosts its performance. Simulation results show the improved performance of the proposed method in terms of lower bias and error variance.
Computer Aided Optimization of the Unconventional Processing
Venue: arXiv cs.SE 2009
Year: 2009

The unconventional technologies, currently applied at a certain category of materials, difficult to be processed through usual techniques, have undergone during the last 60 years all the stages, since their discovery to their use on a large scale. They are based on elementary mechanisms which run the processing through classic methods, yet, they use in addition the interconnections of these methods. This leads to a plus in performance by increasing the outcomes precision, reducing the processing time, increasing the quality of the finite product, etc. This performance can be much increased by using the computer and a software product in assisting the human operator in the processing by an unconventional method such as; the electric or electro-chemical erosion, the complex electric-electro-chemical erosion, the processing by a laser fascicle and so on. The present work presents such an application based on a data base combining the previous experimental results, which proposes a method of optimization of the outcomes.
The new multimedia educational technologies, used in open and distance learning
Venue: arXiv cs.MM 2009
Year: 2009

This paper reviews and refers to the latest telematics technology that has turned the open system learning and helped it to become an institutional alternative to the face-to-face traditional one. Most technologies, briefly presented here, will be implemented in the "ARTeFACt" project - telematic system for vocational education system of open system learning, system which will be officially launched at the end of 2006, in the institutional offer of the Faculty of Arts of the University West of Timisoara. The scientific coordination of the doctoral project "ARTeFACt" is done by Mr. Prof. Dr. Eng. Savi G. George, representing the Department of Mechatronics Faculty of Mechanical Engineering from the University "Politehnica" of Timisoara, Romania
Word-Valued Sources: an Ergodic Theorem, an AEP and the Conservation of Entropy
Venue: arXiv cs.IT 2009
Year: 2009

A word-valued source $\mathbf{Y} = Y_1,Y_2,...$ is discrete random process that is formed by sequentially encoding the symbols of a random process $\mathbf{X} = X_1,X_2,...$ with codewords from a codebook $\mathscr{C}$. These processes appear frequently in information theory (in particular, in the analysis of source-coding algorithms), so it is of interest to give conditions on $\mathbf{X}$ and $\mathscr{C}$ for which $\mathbf{Y}$ will satisfy an ergodic theorem and possess an Asymptotic Equipartition Property (AEP). In this correspondence, we prove the following: (1) if $\mathbf{X}$ is asymptotically mean stationary, then $\mathbf{Y}$ will satisfy a pointwise ergodic theorem and possess an AEP; and, (2) if the codebook $\mathscr{C}$ is prefix-free, then the entropy rate of $\mathbf{Y}$ is equal to the entropy rate of $\mathbf{X}$ normalized by the average codeword length.
Joint Source-Channel Coding on a Multiple Access Channel with Side Information
Venue: arXiv cs.IT 2009
Year: 2009

We consider the problem of transmission of several distributed correlated sources over a multiple access channel (MAC) with side information at the sources and the decoder. Source-channel separation does not hold for this channel. Sufficient conditions are provided for transmission of sources with a given distortion. The source and/or the channel could have continuous alphabets (thus Gaussian sources and Gaussian MACs are special cases). Various previous results are obtained as special cases. We also provide several good joint source-channel coding schemes for discrete sources and discrete/continuous alphabet channel.
Content-Based Sub-Image Retrieval with Relevance Feedback
Venue: arXiv cs.DB 2009
Year: 2009

The typical content-based image retrieval problem is to find images within a database that are similar to a given query image. This paper presents a solution to a different problem, namely that of content based sub-image retrieval, i.e., finding images from a database that contains another image. Note that this is different from finding a region in a (segmented) image that is similar to another image region given as a query. We present a technique for CBsIR that explores relevance feedback, i.e., the user's input on intermediary results, in order to improve retrieval efficiency. Upon modeling images as a set of overlapping and recursive tiles, we use a tile re-weighting scheme that assigns penalties to each tile of the database images and updates the tile penalties for all relevant images retrieved at each iteration using both the relevant and irrelevant images identified by the user. Each tile is modeled by means of its color content using a compact but very efficient method which can, indirectly, capture some notion of texture as well, despite the fact that only color information is maintained. Performance evaluation on a largely heterogeneous dataset of over 10,000 images shows that the system can achieve a stable average recall value of 70% within the top 20 retrieved (and presented) images after only 5 iterations, with each such iteration taking about 2 seconds on an off-the-shelf desktop computer.
Security impact ratings considered harmful
Venue: arXiv cs.CR 2009
Year: 2009

In this paper, we question the common practice of assigning security impact ratings to OS updates. Specifically, we present evidence that ranking updates by their perceived security importance, in order to defer applying some updates, exposes systems to significant risk. We argue that OS vendors and security groups should not focus on security updates to the detriment of other updates, but should instead seek update technologies that make it feasible to distribute updates for all disclosed OS bugs in a timely manner.
Computing the biases of parity-check relations
Venue: arXiv cs.CR 2009
Year: 2009

A divide-and-conquer cryptanalysis can often be mounted against some keystream generators composed of several (nonlinear) independent devices combined by a Boolean function. In particular, any parity-check relation derived from the periods of some constituent sequences usually leads to a distinguishing attack whose complexity is determined by the bias of the relation. However, estimating this bias is a difficult problem since the piling-up lemma cannot be used. Here, we give two exact expressions for this bias. Most notably, these expressions lead to a new algorithm for computing the bias of a parity-check relation, and they also provide some simple formulae for this bias in some particular cases which are commonly used in cryptography.
Software Model Checking via Large-Block Encoding
Venue: arXiv cs.SE 2009
Year: 2009

The construction and analysis of an abstract reachability tree (ART) are the basis for a successful method for software verification. The ART represents unwindings of the control-flow graph of the program. Traditionally, a transition of the ART represents a single block of the program, and therefore, we call this approach single-block encoding (SBE). SBE may result in a huge number of program paths to be explored, which constitutes a fundamental source of inefficiency. We propose a generalization of the approach, in which transitions of the ART represent larger portions of the program; we call this approach large-block encoding (LBE). LBE may reduce the number of paths to be explored up to exponentially. Within this framework, we also investigate symbolic representations: for representing abstract states, in addition to conjunctions as used in SBE, we investigate the use of arbitrary Boolean formulas; for computing abstract-successor states, in addition to Cartesian predicate abstraction as used in SBE, we investigate the use of Boolean predicate abstraction. The new encoding leverages the efficiency of state-of-the-art SMT solvers, which can symbolically compute abstract large-block successors. Our experiments on benchmark C programs show that the large-block encoding outperforms the single-block encoding.
The Secrecy Capacity Region of the Degraded Vector Gaussian Broadcast Channel
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we consider a scenario where a source node wishes to broadcast two confidential messages for two respective receivers via a Gaussian MIMO broadcast channel. A wire-tapper also receives the transmitted signal via another MIMO channel. It is assumed that the channels are degraded and the wire-tapper has the worst channel. We establish the capacity region of this scenario. Our achievability scheme is a combination of the superposition of Gaussian codes and randomization within the layers which we will refer to as Secret Superposition Coding. For the outerbound, we use the notion of enhanced channel to show that the secret superposition of Gaussian codes is optimal. It is shown that we only need to enhance the channels of the legitimate receivers, and the channel of the eavesdropper remains unchanged.
On optimal precoding in linear vector Gaussian channels with arbitrary input distribution
Venue: arXiv cs.IT 2009
Year: 2009

The design of the precoder the maximizes the mutual information in linear vector Gaussian channels with an arbitrary input distribution is studied. Precisely, the precoder optimal left singular vectors and singular values are derived. The characterization of the right singular vectors is left, in general, as an open problem whose computational complexity is then studied in three cases: Gaussian signaling, low SNR, and high SNR. For the Gaussian signaling case and the low SNR regime, the dependence of the mutual information on the right singular vectors vanishes, making the optimal precoder design problem easy to solve. In the high SNR regime, however, the dependence on the right singular vectors cannot be avoided and we show the difficulty of computing the optimal precoder through an NP-hardness analysis.
Variable-Rate M-PSK Communications without Channel Amplitude Estimation
Venue: arXiv cs.IT 2009
Year: 2009

Channel estimation at the receiver side is essential to adaptive modulation schemes, prohibiting low complexity systems from using variable rate and/or variable power transmissions. Towards providing a solution to this problem, we introduce a variable-rate (VR) M-PSK modulation scheme, for communications over fading channels, in the absence of channel gain estimation at the receiver. The choice of the constellation size is based on the signal-plus-noise (S+N) sampling value rather than on the signal-to-noise ratio (S/N). It is analytically shown that S+N can serve as an excellent simpler criterion, alternative to S/N, for determining the modulation order in VR systems. In this way, low complexity transceivers can use VR transmissions in order to increase their spectral efficiency under an error performance constraint. As an application, we utilize the proposed VR modulation scheme in equal gain combining (EGC) diversity receivers.
On the Secrecy Rate Region for the Interference Channel
Venue: arXiv cs.IT 2009
Year: 2009

This paper studies interference channels with security constraints. The existence of an external eavesdropper in a two-user interference channel is assumed, where the network users would like to secure their messages from the external eavesdropper. The cooperative binning and channel prefixing scheme is proposed for this system model which allows users to cooperatively add randomness to the channel in order to degrade the observations of the external eavesdropper. This scheme allows users to add randomness to the channel in two ways: 1) Users cooperate in their design of the binning codebooks, and 2) Users cooperatively exploit the channel prefixing technique. As an example, the channel prefixing technique is exploited in the Gaussian case to transmit a superposition signal consisting of binning codewords and independently generated noise samples. Gains obtained form the cooperative binning and channel prefixing scheme compared to the single user scenario reveals the positive effect of interference in increasing the network security. Remarkably, interference can be exploited to cooperatively add randomness into the network in order to enhance the security.
Fuzzy Mnesors
Venue: arXiv cs.AI 2009
Year: 2009

A fuzzy mnesor space is a semimodule over the positive real numbers. It can be used as theoretical framework for fuzzy sets. Hence we can prove a great number of properties for fuzzy sets without refering to the membership functions.