OpenRaiser/Intern-Atlas huggingface dataset:
Error exponents for Neyman-Pearson detection of a continuous-time Gaussian Markov process from noisy irregular samples
Venue: arXiv cs.IT 2009
Year: 2009

This paper addresses the detection of a stochastic process in noise from irregular samples. We consider two hypotheses. The \emph{noise only} hypothesis amounts to model the observations as a sample of a i.i.d. Gaussian random variables (noise only). The \emph{signal plus noise} hypothesis models the observations as the samples of a continuous time stationary Gaussian process (the signal) taken at known but random time-instants corrupted with an additive noise. Two binary tests are considered, depending on which assumptions is retained as the null hypothesis. Assuming that the signal is a linear combination of the solution of a multidimensional stochastic differential equation (SDE), it is shown that the minimum Type II error probability decreases exponentially in the number of samples when the False Alarm probability is fixed. This behavior is described by \emph{error exponents} that are completely characterized. It turns out that they are related with the asymptotic behavior of the Kalman Filter in random stationary environment, which is studied in this paper. Finally, numerical illustrations of our claims are provided in the context of sensor networks.
A Graph Spectral Approach for Computing Approximate Nash Equilibria
Venue: arXiv cs.GT 2009
Year: 2009

We present a new methodology for computing approximate Nash equilibria for two-person non-cooperative games based upon certain extensions and specializations of an existing optimization approach previously used for the derivation of fixed approximations for this problem. In particular, the general two-person problem is reduced to an indefinite quadratic programming problem of special structure involving the $n \times n$ adjacency matrix of an induced simple graph specified by the input data of the game, where $n$ is the number of players' strategies. Using this methodology and exploiting certain properties of the positive part of the spectrum of the induced graph, we show that for any $\varepsilon > 0$ there is an algorithm to compute an $\varepsilon$-approximate Nash equilibrium in time $n^{ξ(m)/\varepsilon}$, where, $ξ(m) = \sum_{i=1}^m λ_i / n$ and $λ_1, λ_2, >..., λ_m$ are the positive eigenvalues of the adjacency matrix of the graph. For classes of games for which $ξ(m)$ is a constant, there is a PTAS. Based on the best upper bound derived for $ξ(m)$ so far, the worst case complexity of the method is bounded by the subexponential $n^{\sqrt{m}/\varepsilon}$.
Combinatiorial Algorithms for Wireless Information Flow
Venue: arXiv cs.DS 2009
Year: 2009

A long-standing open question in information theory is to characterize the unicast capacity of a wireless relay network. The difficulty arises due to the complex signal interactions induced in the network, since the wireless channel inherently broadcasts the signals and there is interference among transmissions. Recently, Avestimehr, Diggavi and Tse proposed a linear deterministic model that takes into account the shared nature of wireless channels, focusing on the signal interactions rather than the background noise. They generalized the min-cut max-flow theorem for graphs to networks of deterministic channels and proved that the capacity can be achieved using information theoretical tools. They showed that the value of the minimum cut is in this case the minimum rank of all the adjacency matrices describing source-destination cuts. In this paper, we develop a polynomial time algorithm that discovers the relay encoding strategy to achieve the min-cut value in linear deterministic (wireless) networks, for the case of a unicast connection. Our algorithm crucially uses a notion of linear independence between channels to calculate the capacity in polynomial time. Moreover, we can achieve the capacity by using very simple one-symbol processing at the intermediate nodes, thereby constructively yielding finite length strategies that achieve the unicast capacity of the linear deterministic (wireless) relay network.
A New Generic Taxonomy on Hybrid Malware Detection Technique
Venue: arXiv cs.CR 2009
Year: 2009

Malware is a type of malicious program that replicate from host machine and propagate through network. It has been considered as one type of computer attack and intrusion that can do a variety of malicious activity on a computer. This paper addresses the current trend of malware detection techniques and identifies the significant criteria in each technique to improve malware detection in Intrusion Detection System (IDS). Several existing techniques are analyzing from 48 various researches and the capability criteria of malware detection technique have been reviewed. From the analysis, a new generic taxonomy of malware detection technique have been proposed named Hybrid Malware Detection Technique (Hybrid MDT) which consists of Hybrid Signature and Anomaly detection technique and Hybrid Specification based and Anomaly detection technique to complement the weaknesses of the existing malware detection technique in detecting known and unknown attack as well as reducing false alert before and during the intrusion occur.
Modelling and Analysing Dynamic Decentralised Systems
Venue: arXiv cs.SE 2009
Year: 2009

We introduce a method to specify and analyse decentralised dynamic systems; the method is based on the combination of an event-based multi-process system specification approach with a multi-facet analysis approach that considers a reference abstract model and several specific ones derived from the abstract model in order to support facet-wise analysis. The method is illustrated with the modelling and the analysis of a mobile ad-hoc network. The Event-B framework and its related tools B4free and ProB are used to conduct the experiments.
Geometrical Interpretation of Shannon's Entropy Based on the Born Rule
Venue: arXiv cs.IT 2009
Year: 2009

In this paper we will analyze discrete probability distributions in which probabilities of particular outcomes of some experiment (microstates) can be represented by the ratio of natural numbers (in other words, probabilities are represented by digital numbers of finite representation length). We will introduce several results that are based on recently proposed JoyStick Probability Selector, which represents a geometrical interpretation of the probability based on the Born rule. The terms of generic space and generic dimension of the discrete distribution, as well as, effective dimension are going to be introduced. It will be shown how this simple geometric representation can lead to an optimal code length coding of the sequence of signals. Then, we will give a new, geometrical, interpretation of the Shannon entropy of the discrete distribution. We will suggest that the Shannon entropy represents the logarithm of the effective dimension of the distribution. Proposed geometrical interpretation of the Shannon entropy can be used to prove some information inequalities in an elementary way.
Eignets for function approximation on manifolds
Venue: arXiv cs.LG 2009
Year: 2009

Let $\XX$ be a compact, smooth, connected, Riemannian manifold without boundary, $G:\XX\times\XX\to \RR$ be a kernel. Analogous to a radial basis function network, an eignet is an expression of the form $\sum_{j=1}^M a_jG(\circ,y_j)$, where $a_j\in\RR$, $y_j\in\XX$, $1\le j\le M$. We describe a deterministic, universal algorithm for constructing an eignet for approximating functions in $L^p(μ;\XX)$ for a general class of measures $μ$ and kernels $G$. Our algorithm yields linear operators. Using the minimal separation amongst the centers $y_j$ as the cost of approximation, we give modulus of smoothness estimates for the degree of approximation by our eignets, and show by means of a converse theorem that these are the best possible for every \emph{individual function}. We also give estimates on the coefficients $a_j$ in terms of the norm of the eignet. Finally, we demonstrate that if any sequence of eignets satisfies the optimal estimates for the degree of approximation of a smooth function, measured in terms of the minimal separation, then the derivatives of the eignets also approximate the corresponding derivatives of the target function in an optimal manner.
On the Degrees of Freedom of the Compound MIMO Broadcast Channels with Finite States
Venue: arXiv cs.IT 2009
Year: 2009

Multiple-antenna broadcast channels with $M$ transmit antennas and $K$ single-antenna receivers is considered, where the channel of receiver $r$ takes one of the $J_r$ finite values. It is assumed that the channel states of each receiver are randomly selected from $\mathds{R}^{M\times 1}$ (or from $\mathds{C}^{M\times 1}$). It is shown that no matter what $J_r$ is, the degrees of freedom (DoF) of $\frac{MK}{M+K-1}$ is achievable. The achievable scheme relies on the idea of interference alignment at receivers, without exploiting the possibility of cooperation among transmit antennas. It is proven that if $J_r \geq M$, $r=1,...,K$, this scheme achieves the optimal DoF. This results implies that when the uncertainty of the base station about the channel realization is considerable, the system loses the gain of cooperation. However, it still benefits from the gain of interference alignment. In fact, in this case, the compound broadcast channel is treated as a compound X channel. Moreover, it is shown that when the base station knows the channel states of some of the receivers, a combination of transmit cooperation and interference alignment would achieve the optimal DoF. Like time-invariant $K$-user interference channels, the naive vector-space approaches of interference management seem insufficient to achieve the optimal DoF of this channel. In this paper, we use the Number-Theory approach of alignment, recently developed by Motahari et al.[1]. We extend the approach of [1] to complex channels as well, therefore all the results that we present are valid for both real and complex channels.
Achieving Capacity of Bi-Directional Tandem Collision Network by Joint Medium-Access Control and Channel-Network Coding
Venue: arXiv cs.IT 2009
Year: 2009

In ALOHA-type packetized network, the transmission times of packets follow a stochastic process. In this paper, we advocate a deterministic approach for channel multiple-access. Each user is statically assigned a periodic protocol signal, which takes value either zero or one, and transmit packets whenever the value of the protocol signal is equal to one. On top of this multiple-access protocol, efficient channel coding and network coding schemes are devised. We illustrate the idea by constructing a transmission scheme for the tandem collision network, for both slot-synchronous and slot-asynchronous systems. This cross-layer approach is able to achieve the capacity region when the network is bi-directional.
A Conceivable Origin of Machine Consciousness in the IDLE process
Venue: arXiv cs.OS 2009
Year: 2009

In this short paper, we would like to call professional community's attention to a daring idea that is surely unhelpful, but is exciting for programmers and anyway conflicts with the trend of energy consumption in computer systems.
Breaking Generator Symmetry
Venue: arXiv cs.AI 2009
Year: 2009

Dealing with large numbers of symmetries is often problematic. One solution is to focus on just symmetries that generate the symmetry group. Whilst there are special cases where breaking just the symmetries in a generating set is complete, there are also cases where no irredundant generating set eliminates all symmetry. However, focusing on just generators improves tractability. We prove that it is polynomial in the size of the generating set to eliminate all symmetric solutions, but NP-hard to prune all symmetric values. Our proof considers row and column symmetry, a common type of symmetry in matrix models where breaking just generator symmetries is very effective. We show that propagating a conjunction of lexicographical ordering constraints on the rows and columns of a matrix of decision variables is NP-hard.
Cognitive Power Control Under Correlated Fading and Primary-Link CSI
Venue: arXiv cs.IT 2009
Year: 2009

We consider the cognitive power control problem of maximizing the secondary throughput under an outage probability constraint on a constant-power constant-rate primary link. We assume a temporally correlated primary channel with two types of feedback: perfect delayed channel state information (CSI) and one-bit automatic repeat request (ARQ). We use channel correlation to enhance the primary and secondary throughput via exploiting the CSI feedback to predict the future primary channel gain. We provide a numerical solution for the power control optimization problem under delayed CSI. In order to make the solution tractable under ARQ-CSI, we re-formulate the cognitive power control problem as the maximization of the instantaneous weighted sum of primary and secondary throughput. We propose a greedy ARQ-CSI algorithm that is shown to achieve an average throughput comparable to that attained under the delayed-CSI algorithm, which we solve optimally.
PetRBF--A parallel O(N) algorithm for radial basis function interpolation
Venue: arXiv cs.MS 2009
Year: 2009

We have developed a parallel algorithm for radial basis function (RBF) interpolation that exhibits O(N) complexity,requires O(N) storage, and scales excellently up to a thousand processes. The algorithm uses a GMRES iterative solver with a restricted additive Schwarz method (RASM) as a preconditioner and a fast matrix-vector algorithm. Previous fast RBF methods, --,achieving at most O(NlogN) complexity,--, were developed using multiquadric and polyharmonic basis functions. In contrast, the present method uses Gaussians with a small variance (a common choice in particle methods for fluid simulation, our main target application). The fast decay of the Gaussian basis function allows rapid convergence of the iterative solver even when the subdomains in the RASM are very small. The present method was implemented in parallel using the PETSc library (developer version). Numerical experiments demonstrate its capability in problems of RBF interpolation with more than 50 million data points, timing at 106 seconds (19 iterations for an error tolerance of 10^-15 on 1024 processors of a Blue Gene/L (700 MHz PowerPC processors). The parallel code is freely available in the open-source model.
Information tracking approach to segmentation of ultrasound imagery of prostate
Venue: arXiv cs.CV 2009
Year: 2009

The size and geometry of the prostate are known to be pivotal quantities used by clinicians to assess the condition of the gland during prostate cancer screening. As an alternative to palpation, an increasing number of methods for estimation of the above-mentioned quantities are based on using imagery data of prostate. The necessity to process large volumes of such data creates a need for automatic segmentation tools which would allow the estimation to be carried out with maximum accuracy and efficiency. In particular, the use of transrectal ultrasound (TRUS) imaging in prostate cancer screening seems to be becoming a standard clinical practice due to the high benefit-to-cost ratio of this imaging modality. Unfortunately, the segmentation of TRUS images is still hampered by relatively low contrast and reduced SNR of the images, thereby requiring the segmentation algorithms to incorporate prior knowledge about the geometry of the gland. In this paper, a novel approach to the problem of segmenting the TRUS images is described. The proposed approach is based on the concept of distribution tracking, which provides a unified framework for modeling and fusing image-related and morphological features of the prostate. Moreover, the same framework allows the segmentation to be regularized via using a new type of "weak" shape priors, which minimally bias the estimation procedure, while rendering the latter stable and robust.
Improvements of the 3D images captured with Time-of-Flight cameras
Venue: arXiv cs.CV 2009
Year: 2009

3D Time-of-Flight camera's images are affected by errors due to the diffuse (indirect) light and to the flare light. The presented method improves the 3D image reducing the distance's errors to dark surface objects. This is achieved by placing one or two contrast tags in the scene at different distances from the ToF camera. The white and black parts of the tags are situated at the same distance to the camera but the distances measured by the camera are different. This difference is used to compute a correction vector. The distance to black surfaces is corrected by subtracting this vector from the captured vector image.
Partition Arguments in Multiparty Communication Complexity
Venue: arXiv cs.CC 2009
Year: 2009

Consider the "Number in Hand" multiparty communication complexity model, where k players holding inputs x_1,...,x_k in {0,1}^n communicate to compute the value f(x_1,...,x_k) of a function f known to all of them. The main lower bound technique for the communication complexity of such problems is that of partition arguments: partition the k players into two disjoint sets of players and find a lower bound for the induced two-party communication complexity problem. In this paper, we study the power of partition arguments. Our two main results are very different in nature: (i) For randomized communication complexity, we show that partition arguments may yield bounds that are exponentially far from the true communication complexity. Specifically, we prove that there exists a 3-argument function f whose communication complexity is Omega(n), while partition arguments can only yield an Omega(log n) lower bound. The same holds for nondeterministic communication complexity. (ii) For deterministic communication complexity, we prove that finding significant gaps between the true communication complexity and the best lower bound that can be obtained via partition arguments, would imply progress on a generalized version of the "log-rank conjecture" in communication complexity. We conclude with two results on the multiparty "fooling set technique", another method for obtaining communication complexity lower bounds.
Variable sigma Gaussian processes: An expectation propagation perspective
Venue: arXiv cs.LG 2009
Year: 2009

Gaussian processes (GPs) provide a probabilistic nonparametric representation of functions in regression, classification, and other problems. Unfortunately, exact learning with GPs is intractable for large datasets. A variety of approximate GP methods have been proposed that essentially map the large dataset into a small set of basis points. The most advanced of these, the variable-sigma GP (VSGP) (Walder et al., 2008), allows each basis point to have its own length scale. However, VSGP was only derived for regression. We describe how VSGP can be applied to classification and other problems, by deriving it as an expectation propagation algorithm. In this view, sparse GP approximations correspond to a KL-projection of the true posterior onto a compact exponential family of GPs. VSGP constitutes one such family, and we show how to enlarge this family to get additional accuracy. In particular, we show that endowing each basis point with its own full covariance matrix provides a significant increase in approximation power.
A methodology for semi-automatic classification schema building
Venue: arXiv cs.OH 2009
Year: 2009

This paper describe a methodology for semi-automatic classification schema definition (a classification schema is a taxonomy of categories useful for automatic document classification). The methodology is based on: (i) an extensional approach useful to create a typology starting from a document base, and (ii) an intensional approach to build the classification schema starting from the typology. The extensional approach uses clustering techniques to group together documents on the basis of a similarity measure, whereas the intensional approach uses different operations (aggregation, reduction, generalization specialization) to define classes. keywords: ontology, classification schema, fundamentum divisionis, cluster analysis classification task.
A Framework for Specifying, Prototyping, and Reasoning about Computational Systems
Venue: arXiv cs.LO 2009
Year: 2009

This thesis concerns the development of a framework that facilitates the design and analysis of formal systems. Specifically, this framework provides a specification language which supports the concise and direct description of formal systems, a mechanism for animating the specification language thereby producing prototypes of encoded systems, and a logic for proving properties of specifications and therefore of the systems they encode. A defining characteristic of the proposed framework is that it is based on two separate but closely intertwined logics: a specification logic that facilitates the description of computational structure and another logic that exploits the special characteristics of the specification logic to support reasoning about the computational behavior of systems that are described using it. Both logics embody a natural treatment of binding structure by using the lambda-calculus as a means for representing objects and by incorporating special mechanisms for working with such structure. By using this technique, they lift the treatment of binding from the object language into the domain of the relevant meta logic, thereby allowing the specification or analysis components to focus on the more essential logical aspects of the systems that are encoded. The primary contributions of these thesis are the development of a rich meta-logic called G with capabilities for sophisticated reasoning that includes induction and co-induction over high-level specifications of computations and with an associated cut-elimination result; an interactive reasoning system called Abella based on G; and several reasoning examples which demonstrate the expressiveness and naturalness of both G and Abella.
When Watchdog Meets Coding
Venue: arXiv cs.CR 2009
Year: 2009

In this work we study the problem of misbehavior detection in wireless networks. A commonly adopted approach is to utilize the broadcasting nature of the wireless medium and have nodes monitor their neighborhood. We call such nodes the Watchdogs. In this paper, we first show that even if a watchdog can overhear all packet transmissions of a flow, any linear operation of the overheard packets can not eliminate miss-detection and is inefficient in terms of bandwidth. We propose a light-weigh misbehavior detection scheme which integrates the idea of watchdogs and error detection coding. We show that even if the watchdog can only observe a fraction of packets, by choosing the encoder properly, an attacker will be detected with high probability while achieving throughput arbitrarily close to optimal. Such properties reduce the incentive for the attacker to attack.