OpenRaiser/Intern-Atlas huggingface dataset:
Energy Efficient Estimation of Gaussian Sources Over Inhomogeneous Gaussian MAC Channels
Venue: arXiv cs.IT 2007
Year: 2007

It has been shown lately the optimality of uncoded transmission in estimating Gaussian sources over homogeneous/symmetric Gaussian multiple access channels (MAC) using multiple sensors. It remains, however, unclear whether it still holds for any arbitrary networks and/or with high channel signal-to-noise ratio (SNR) and high signal-to-measurement-noise ratio (SMNR). In this paper, we first provide a joint source and channel coding approach in estimating Gaussian sources over Gaussian MAC channels, as well as its sufficient and necessary condition in restoring Gaussian sources with a prescribed distortion value. An interesting relationship between our proposed joint approach with a more straightforward separate source and channel coding scheme is then established. We then formulate constrained power minimization problems and transform them to relaxed convex geometric programming problems, whose numerical results exhibit that either separate or uncoded scheme becomes dominant over a linear topology network. In addition, we prove that the optimal decoding order to minimize the total transmission powers for both source and channel coding parts is solely subject to the ranking of MAC channel qualities, and has nothing to do with the ranking of measurement qualities. Finally, asymptotic results for homogeneous networks are obtained which not only confirm the existing optimality of the uncoded approach, but also show that the asymptotic SNR exponents of these three approaches are all the same. Moreover, the proposed joint approach share the same asymptotic ratio with respect to high SNR and high SMNR as the uncoded scheme.
Deciding Unambiguity and Sequentiality starting from a Finitely Ambiguous Max-Plus Automaton
Venue: arXiv cs.CC 2007
Year: 2007

Finite automata with weights in the max-plus semiring are considered. The main result is: it is decidable in an effective way whether a series that is recognized by a finitely ambiguous max-plus automaton is unambiguous, or is sequential. A collection of examples is given to illustrate the hierarchy of max-plus series with respect to ambiguity.
Secrecy Capacity Region of a Multi-Antenna Gaussian Broadcast Channel with Confidential Messages
Venue: arXiv cs.IT 2007
Year: 2007

In wireless data networks, communication is particularly susceptible to eavesdropping due to its broadcast nature. Security and privacy systems have become critical for wireless providers and enterprise networks. This paper considers the problem of secret communication over the Gaussian broadcast channel, where a multi-antenna transmitter sends independent confidential messages to two users with information-theoretic secrecy. That is, each user would like to obtain its own confidential message in a reliable and safe manner. This communication model is referred to as the multi-antenna Gaussian broadcast channel with confidential messages (MGBC-CM). Under this communication scenario, a secret dirty-paper coding scheme and the corresponding achievable secrecy rate region are first developed based on Gaussian codebooks. Next, a computable Sato-type outer bound on the secrecy capacity region is provided for the MGBC-CM. Furthermore, the Sato-type outer bound prove to be consistent with the boundary of the secret dirty-paper coding achievable rate region, and hence, the secrecy capacity region of the MGBC-CM is established. Finally, two numerical examples demonstrate that both users can achieve positive rates simultaneously under the information-theoretic secrecy requirement.
Lagrangian Relaxation for MAP Estimation in Graphical Models
Venue: arXiv cs.AI 2007
Year: 2007

We develop a general framework for MAP estimation in discrete and Gaussian graphical models using Lagrangian relaxation techniques. The key idea is to reformulate an intractable estimation problem as one defined on a more tractable graph, but subject to additional constraints. Relaxing these constraints gives a tractable dual problem, one defined by a thin graph, which is then optimized by an iterative procedure. When this iterative optimization leads to a consistent estimate, one which also satisfies the constraints, then it corresponds to an optimal MAP estimate of the original model. Otherwise there is a ``duality gap'', and we obtain a bound on the optimal solution. Thus, our approach combines convex optimization with dynamic programming techniques applicable for thin graphs. The popular tree-reweighted max-product (TRMP) method may be seen as solving a particular class of such relaxations, where the intractable graph is relaxed to a set of spanning trees. We also consider relaxations to a set of small induced subgraphs, thin subgraphs (e.g. loops), and a connected tree obtained by ``unwinding'' cycles. In addition, we propose a new class of multiscale relaxations that introduce ``summary'' variables. The potential benefits of such generalizations include: reducing or eliminating the ``duality gap'' in hard problems, reducing the number or Lagrange multipliers in the dual problem, and accelerating convergence of the iterative optimization procedure.
New families of cryptographic systems
Venue: arXiv cs.CR 2007
Year: 2007

A symmetric encryption method based on properties of quasicrystals is proposed. The advantages of the cipher are strict aperiodicity and everywhere discontinuous property as well as the speed of computation, simplicity of implementation and a straightforward possibility of extending the method to encryption of higher dimensional data.
Graph rigidity, Cyclic Belief Propagation and Point Pattern Matching
Venue: arXiv cs.CV 2007
Year: 2007

A recent paper \cite{CaeCaeSchBar06} proposed a provably optimal, polynomial time method for performing near-isometric point pattern matching by means of exact probabilistic inference in a chordal graphical model. Their fundamental result is that the chordal graph in question is shown to be globally rigid, implying that exact inference provides the same matching solution as exact inference in a complete graphical model. This implies that the algorithm is optimal when there is no noise in the point patterns. In this paper, we present a new graph which is also globally rigid but has an advantage over the graph proposed in \cite{CaeCaeSchBar06}: its maximal clique size is smaller, rendering inference significantly more efficient. However, our graph is not chordal and thus standard Junction Tree algorithms cannot be directly applied. Nevertheless, we show that loopy belief propagation in such a graph converges to the optimal solution. This allows us to retain the optimality guarantee in the noiseless case, while substantially reducing both memory requirements and processing time. Our experimental results show that the accuracy of the proposed solution is indistinguishable from that of \cite{CaeCaeSchBar06} when there is noise in the point patterns.
High-Order Nonparametric Belief-Propagation for Fast Image Inpainting
Venue: arXiv cs.CV 2007
Year: 2007

In this paper, we use belief-propagation techniques to develop fast algorithms for image inpainting. Unlike traditional gradient-based approaches, which may require many iterations to converge, our techniques achieve competitive results after only a few iterations. On the other hand, while belief-propagation techniques are often unable to deal with high-order models due to the explosion in the size of messages, we avoid this problem by approximating our high-order prior model using a Gaussian mixture. By using such an approximation, we are able to inpaint images quickly while at the same time retaining good visual results.
The Problem of Localization in Networks of Randomly Deployed Nodes: Asymptotic and Finite Analysis, and Thresholds
Venue: arXiv cs.DM 2007
Year: 2007

We derive the probability that a randomly chosen NL-node over $S$ gets localized as a function of a variety of parameters. Then, we derive the probability that the whole network of NL-nodes over $S$ gets localized. In connection with the asymptotic thresholds, we show the presence of asymptotic thresholds on the network localization probability in two different scenarios. The first refers to dense networks, which arise when the domain $S$ is bounded and the densities of the two kinds of nodes tend to grow unboundedly. The second kind of thresholds manifest themselves when the considered domain increases but the number of nodes grow in such a way that the L-node density remains constant throughout the investigated domain. In this scenario, what matters is the minimum value of the maximum transmission range averaged over the fading process, denoted as $d_{max}$, above which the network of NL-nodes almost surely gets asymptotically localized.
Spreadsheets in Clinical Medicine
Venue: arXiv cs.CY 2007
Year: 2007

There is overwhelming evidence that the continued and widespread use of untested spreadsheets in business gives rise to regular, significant and unexpected financial losses. Whilst this is worrying, it is perhaps a relatively minor concern compared with the risks arising from the use of poorly constructed and/or untested spreadsheets in medicine, a practice that is already occurring. This article is intended as a warning that the use of poorly constructed and/or untested spreadsheets in clinical medicine cannot be tolerated. It supports this warning by reporting on potentially serious weaknesses found while testing a limited number of publicly available clinical spreadsheets.
A New Achievability Scheme for the Relay Channel
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, we propose a new coding scheme for the general relay channel. This coding scheme is in the form of a block Markov code. The transmitter uses a superposition Markov code. The relay compresses the received signal and maps the compressed version of the received signal into a codeword conditioned on the codeword of the previous block. The receiver performs joint decoding after it has received all of the B blocks. We show that this coding scheme can be viewed as a generalization of the well-known Compress-And-Forward (CAF) scheme proposed by Cover and El Gamal. Our coding scheme provides options for preserving the correlation between the channel inputs of the transmitter and the relay, which is not possible in the CAF scheme. Thus, our proposed scheme may potentially yield a larger achievable rate than the CAF scheme.
Degeneracy of Angular Voronoi Diagram
Venue: arXiv cs.CG 2007
Year: 2007

Angular Voronoi diagram was introduced by Asano et al. as fundamental research for a mesh generation. In an angular Voronoi diagram, the edges are curves of degree three. From view of computational robustness we need to treat the curves carefully, because they might have a singularity. We enumerate all the possible types of curves that appear as an edge of an angular Voronoi diagram, which tells us what kind of degeneracy is possible and tells us necessity of considering a singularity for computational robustness.
Z2Z4-linear codes: generator matrices and duality
Venue: arXiv cs.IT 2007
Year: 2007

A code ${\cal C}$ is $\Z_2\Z_4$-additive if the set of coordinates can be partitioned into two subsets $X$ and $Y$ such that the punctured code of ${\cal C}$ by deleting the coordinates outside $X$ (respectively, $Y$) is a binary linear code (respectively, a quaternary linear code). In this paper $\Z_2\Z_4$-additive codes are studied. Their corresponding binary images, via the Gray map, are $\Z_2\Z_4$-linear codes, which seem to be a very distinguished class of binary group codes. As for binary and quaternary linear codes, for these codes the fundamental parameters are found and standard forms for generator and parity check matrices are given. For this, the appropriate inner product is deduced and the concept of duality for $\Z_2\Z_4$-additive codes is defined. Moreover, the parameters of the dual codes are computed. Finally, some conditions for self-duality of $\Z_2\Z_4$-additive codes are given.
Power Efficient Scheduling under Delay Constraints over Multi-user Wireless Channels
Venue: arXiv cs.NI 2007
Year: 2007

In this paper, we consider the problem of power efficient uplink scheduling in a Time Division Multiple Access (TDMA) system over a fading wireless channel. The objective is to minimize the power expenditure of each user subject to satisfying individual user delay. We make the practical assumption that the system statistics are unknown, i.e., the probability distributions of the user arrivals and channel states are unknown. The problem has the structure of a Constrained Markov Decision Problem (CMDP). Determining an optimal policy under for the CMDP faces the problems of state space explosion and unknown system statistics. To tackle the problem of state space explosion, we suggest determining the transmission rate of a particular user in each slot based on its channel condition and buffer occupancy only. The rate allocation algorithm for a particular user is a learning algorithm that learns about the buffer occupancy and channel states of that user during system execution and thus addresses the issue of unknown system statistics. Once the rate of each user is determined, the proposed algorithm schedules the user with the best rate. Our simulations within an IEEE 802.16 system demonstrate that the algorithm is indeed able to satisfy the user specified delay constraints. We compare the performance of our algorithm with the well known M-LWDF algorithm. Moreover, we demonstrate that the power expended by the users under our algorithm is quite low.
What's in a Name?
Venue: arXiv cs.CL 2007
Year: 2007

This paper describes experiments on identifying the language of a single name in isolation or in a document written in a different language. A new corpus has been compiled and made available, matching names against languages. This corpus is used in a series of experiments measuring the performance of general language models and names-only language models on the language identification task. Conclusions are drawn from the comparison between using general language models and names-only language models and between identifying the language of isolated names and the language of very short document fragments. Future research directions are outlined.
An explicit universal cycle for the (n-1)-permutations of an n-set
Venue: arXiv cs.DM 2007
Year: 2007

We show how to construct an explicit Hamilton cycle in the directed Cayley graph Cay({σ_n, sigma_{n-1}} : \mathbb{S}_n), where σ_k = (1 2 >... k). The existence of such cycles was shown by Jackson (Discrete Mathematics, 149 (1996) 123-129) but the proof only shows that a certain directed graph is Eulerian, and Knuth (Volume 4 Fascicle 2, Generating All Tuples and Permutations (2005)) asks for an explicit construction. We show that a simple recursion describes our Hamilton cycle and that the cycle can be generated by an iterative algorithm that uses O(n) space. Moreover, the algorithm produces each successive edge of the cycle in constant time; such algorithms are said to be loopless.
Comparison and Combination of State-of-the-art Techniques for Handwritten Character Recognition: Topping the MNIST Benchmark
Venue: arXiv cs.CV 2007
Year: 2007

Although the recognition of isolated handwritten digits has been a research topic for many years, it continues to be of interest for the research community and for commercial applications. We show that despite the maturity of the field, different approaches still deliver results that vary enough to allow improvements by using their combination. We do so by choosing four well-motivated state-of-the-art recognition systems for which results on the standard MNIST benchmark are available. When comparing the errors made, we observe that the errors made differ between all four systems, suggesting the use of classifier combination. We then determine the error rate of a hypothetical system that combines the output of the four systems. The result obtained in this manner is an error rate of 0.35% on the MNIST data, the best result published so far. We furthermore discuss the statistical significance of the combined result and of the results of the individual classifiers.
Geometric Analogue of Holographic Reduced Representation
Venue: arXiv cs.AI 2007
Year: 2007

Holographic reduced representations (HRR) are based on superpositions of convolution-bound $n$-tuples, but the $n$-tuples cannot be regarded as vectors since the formalism is basis dependent. This is why HRR cannot be associated with geometric structures. Replacing convolutions by geometric products one arrives at reduced representations analogous to HRR but interpretable in terms of geometry. Variable bindings occurring in both HRR and its geometric analogue mathematically correspond to two different representations of $Z_2\times...\times Z_2$ (the additive group of binary $n$-tuples with addition modulo 2). As opposed to standard HRR, variable binding performed by means of geometric product allows for computing exact inverses of all nonzero vectors, a procedure even simpler than approximate inverses employed in HRR. The formal structure of the new reduced representation is analogous to cartoon computation, a geometric analogue of quantum computation.
Rigidity and persistence for ensuring shape maintenance of multiagent meta formations (ext'd version)
Venue: arXiv cs.MA 2007
Year: 2007

This paper treats the problem of the merging of formations, where the underlying model of a formation is graphical. We first analyze the rigidity and persistence of meta-formations, which are formations obtained by connecting several rigid or persistent formations. Persistence is a generalization to directed graphs of the undirected notion of rigidity. In the context of moving autonomous agent formations, persistence characterizes the efficacy of a directed structure of unilateral distance constraints seeking to preserve a formation shape. We derive then, for agents evolving in a two- or three-dimensional space, the conditions under which a set of persistent formations can be merged into a persistent meta-formation, and give the minimal number of interconnections needed for such a merging. We also give conditions for a meta-formation obtained by merging several persistent formations to be persistent.
Linguistic Information Energy
Venue: arXiv cs.CL 2007
Year: 2007

In this treatment a text is considered to be a series of word impulses which are read at a constant rate. The brain then assembles these units of information into higher units of meaning. A classical systems approach is used to model an initial part of this assembly process. The concepts of linguistic system response, information energy, and ordering energy are defined and analyzed. Finally, as a demonstration, information energy is used to estimate the publication dates of a series of texts and the similarity of a set of texts.
DPA on quasi delay insensitive asynchronous circuits: formalization and improvement
Venue: arXiv cs.AR 2007
Year: 2007

The purpose of this paper is to formally specify a flow devoted to the design of Differential Power Analysis (DPA) resistant QDI asynchronous circuits. The paper first proposes a formal modeling of the electrical signature of QDI asynchronous circuits. The DPA is then applied to the formal model in order to identify the source of leakage of this type of circuits. Finally, a complete design flow is specified to minimize the information leakage. The relevancy and efficiency of the approach is demonstrated using the design of an AES crypto-processor.
Design of a Distributed Reachability Algorithm for Analysis of Linear Hybrid Automata
Venue: arXiv cs.LO 2007
Year: 2007

This paper presents the design of a novel distributed algorithm d-IRA for the reachability analysis of linear hybrid automata. Recent work on iterative relaxation abstraction (IRA) is leveraged to distribute the computational problem among multiple computational nodes in a non-redundant manner by performing careful infeasibility analysis of linear programs corresponding to spurious counterexamples. The d-IRA algorithm is resistant to failure of multiple computational nodes. The experimental results provide promising evidence for the possible successful application of this technique.
A Deterministic Approach to Wireless Relay Networks
Venue: arXiv cs.IT 2007
Year: 2007

We present a deterministic channel model which captures several key features of multiuser wireless communication. We consider a model for a wireless network with nodes connected by such deterministic channels, and present an exact characterization of the end-to-end capacity when there is a single source and a single destination and an arbitrary number of relay nodes. This result is a natural generalization of the max-flow min-cut theorem for wireline networks. Finally to demonstrate the connections between deterministic model and Gaussian model, we look at two examples: the single-relay channel and the diamond network. We show that in each of these two examples, the capacity-achieving scheme in the corresponding deterministic model naturally suggests a scheme in the Gaussian model that is within 1 bit and 2 bit respectively from cut-set upper bound, for all values of the channel gains. This is the first part of a two-part paper; the sequel [1] will focus on the proof of the max-flow min-cut theorem of a class of deterministic networks of which our model is a special case.
Universal coding for correlated sources with complementary delivery
Venue: arXiv cs.IT 2007
Year: 2007

This paper deals with a universal coding problem for a certain kind of multiterminal source coding system that we call the complementary delivery coding system. In this system, messages from two correlated sources are jointly encoded, and each decoder has access to one of the two messages to enable it to reproduce the other message. Both fixed-to-fixed length and fixed-to-variable length lossless coding schemes are considered. Explicit constructions of universal codes and bounds of the error probabilities are clarified via type-theoretical and graph-theoretical analyses. [[Keywords]] multiterminal source coding, complementary delivery, universal coding, types of sequences, bipartite graphs
Survivable MPLS Over Optical Transport Networks: Cost and Resource Usage Analysis
Venue: arXiv cs.NI 2007
Year: 2007

In this paper we study different options for the survivability implementation in MPLS over Optical Transport Networks (OTN) in terms of network resource usage and configuration cost. We investigate two approaches to the survivability deployment: single layer and multilayer survivability and present various methods for spare capacity allocation (SCA) to reroute disrupted traffic. The comparative analysis shows the influence of the offered traffic granularity and the physical network structure on the survivability cost: for high bandwidth LSPs, close to the optical channel capacity, the multilayer survivability outperforms the single layer one, whereas for low bandwidth LSPs the single layer survivability is more cost-efficient. On the other hand, sparse networks of low connectivity parameter use more wavelengths for optical path routing and increase the configuration cost, as compared with dense networks. We demonstrate that by mapping efficiently the spare capacity of the MPLS layer onto the resources of the optical layer one can achieve up to 22% savings in the total configuration cost and up to 37% in the optical layer cost. Further savings (up to 9 %) in the wavelength use can be obtained with the integrated approach to network configuration over the sequential one, however, at the increase in the optimization problem complexity. These results are based on a cost model with different cost variations, and were obtained for networks targeted to a nationwide coverage.