OpenRaiser/Intern-Atlas huggingface dataset:
Near Minimax Line Spectral Estimation
Venue: arXiv cs.IT 2013
Year: 2013

This paper establishes a nearly optimal algorithm for estimating the frequencies and amplitudes of a mixture of sinusoids from noisy equispaced samples. We derive our algorithm by viewing line spectral estimation as a sparse recovery problem with a continuous, infinite dictionary. We show how to compute the estimator via semidefinite programming and provide guarantees on its mean-square error rate. We derive a complementary minimax lower bound on this estimation rate, demonstrating that our approach nearly achieves the best possible estimation error. Furthermore, we establish bounds on how well our estimator localizes the frequencies in the signal, showing that the localization error tends to zero as the number of samples grows. We verify our theoretical results in an array of numerical experiments, demonstrating that the semidefinite programming approach outperforms two classical spectral estimation techniques.
Adaptive Distributed Space-Time Coding in Cooperative MIMO Relaying Systems using Limited Feedback
Venue: arXiv cs.IT 2013
Year: 2013

An adaptive randomized distributed space-time coding (DSTC) scheme is proposed for two-hop cooperative MIMO networks. Linear minimum mean square error (MMSE) receiver filters and randomized matrices subject to a power constraint are considered with an amplify-and-forward (AF) cooperation strategy. In the proposed DSTC scheme, a randomized matrix obtained by a feedback channel is employed to transform the space-time coded matrix at the relay node. The effect of the limited feedback and feedback errors are considered. Linear MMSE expressions are devised to compute the parameters of the adaptive randomized matrix and the linear receive filters. A stochastic gradient algorithm is also developed with reduced computational complexity. The simulation results show that the proposed algorithms obtain significant performance gains as compared to existing DSTC schemes.
BICM Performance Improvement via Online LLR Optimization
Venue: arXiv cs.IT 2013
Year: 2013

We consider bit interleaved coded modulation (BICM) receiver performance improvement based on the concept of generalized mutual information (GMI). Increasing achievable rates of BICM receiver with GMI maximization by proper scaling of the log likelihood ratio (LLR) is investigated. While it has been shown in the literature that look-up table based LLR scaling functions matched to each specific transmission scenario may provide close to optimal solutions, this method is difficult to adapt to time-varying channel conditions. To solve this problem, an online adaptive scaling factor searching algorithm is developed. Uniform scaling factors are applied to LLRs from different bit channels of each data frame by maximizing an approximate GMI that characterizes the transmission conditions of current data frame. Numerical analysis on effective achievable rates as well as link level simulation of realistic mobile transmission scenarios indicate that the proposed method is simple yet effective.
Geospatial Optimization Problems
Venue: arXiv cs.DS 2013
Year: 2013

There are numerous applications which require the ability to take certain actions (e.g. distribute money, medicines, people etc.) over a geographic region. A disaster relief organization must allocate people and supplies to parts of a region after a disaster. A public health organization must allocate limited vaccine to people across a region. In both cases, the organization is trying to optimize something (e.g. minimize expected number of people with a disease). We introduce "geospatial optimization problems" (GOPs) where an organization has limited resources and budget to take actions in a geographic area. The actions result in one or more properties changing for one or more locations. There are also certain constraints on the combinations of actions that can be taken. We study two types of GOPs - goal-based and benefit-maximizing (GBGOP and BMGOP respectively). A GBGOP ensures that certain properties must be true at specified locations after the actions are taken while a BMGOP optimizes a linear benefit function. We show both problems to be NP-hard (with membership in NP for the associated decision problems). Additionally, we prove limits on approximation for both problems. We present integer programs for both GOPs that provide exact solutions. We also correctly reduce the number of variables in for the GBGOP integer constraints. For BMGOP, we present the BMGOP-Compute algorithm that runs in PTIME and provides a reasonable approximation guarantee in most cases.
An Ant-Based Algorithm with Local Optimization for Community Detection in Large-Scale Networks
Venue: arXiv cs.SI 2013
Year: 2013

In this paper, we propose a multi-layer ant-based algorithm MABA, which detects communities from networks by means of locally optimizing modularity using individual ants. The basic version of MABA, namely SABA, combines a self-avoiding label propagation technique with a simulated annealing strategy for ant diffusion in networks. Once the communities are found by SABA, this method can be reapplied to a higher level network where each obtained community is regarded as a new vertex. The aforementioned process is repeated iteratively, and this corresponds to MABA. Thanks to the intrinsic multi-level nature of our algorithm, it possesses the potential ability to unfold multi-scale hierarchical structures. Furthermore, MABA has the ability that mitigates the resolution limit of modularity. The proposed MABA has been evaluated on both computer-generated benchmarks and widely used real-world networks, and has been compared with a set of competitive algorithms. Experimental results demonstrate that MABA is both effective and efficient (in near linear time with respect to the size of network) for discovering communities.
The State of the Art Recognize in Arabic Script through Combination of Online and Offline
Venue: arXiv cs.CV 2013
Year: 2013

Handwriting recognition refers to the identification of written characters. Handwriting recognition has become an acute research area in recent years for the ease of access of computer science. In this paper primarily discussed On-line and Off-line handwriting recognition methods for Arabic words which are often used among then across the Middle East and North Africa People. Arabic word online handwriting recognition is a very challenging task due to its cursive nature. Because of the characteristic of the whole body of the Arabic script, namely connectivity between the characters, thereby the segmentation of An Arabic script is very difficult. In this paper we introduced an Arabic script multiple classifier system for recognizing notes written on a Starboard. This Arabic script multiple classifier system combines one off-line and on-line handwriting recognition systems. The Arabic script recognizers are all based on Hidden Markov Models but vary in the way of preprocessing and normalization. To combine the Arabic script output sequences of the recognizers, we incrementally align the word sequences using a norm string matching algorithm. The Arabic script combination we could increase the system performance over the excellent character recognizer by about 3%. The proposed technique is also the necessary step towards character recognition, person identification, personality determination where input data is processed from all perspectives.
Study On Universal Lossless Data Compression by using Context Dependence Multilevel Pattern Matching Grammar Transform
Venue: arXiv cs.DM 2013
Year: 2013

In this paper, the context dependence multilevel pattern matching(in short CDMPM) grammar transform is proposed; based on this grammar transform, the universal lossless data compression algorithm, CDMPM code is then developed. Moreover we get a upper bound of this algorithms' worst case redundancy among all individual sequences of length n from a finite alphabet.
Does query performance optimization lead to energy efficiency? A comparative analysis of energy efficiency of database operations under different workload scenarios
Venue: arXiv cs.DB 2013
Year: 2013

With the continuous increase of online services as well as energy costs, energy consumption becomes a significant cost factor for the evaluation of data center operations. A significant contributor to that is the performance of database servers which are found to constitute the backbone of online services. From a software approach, while a set of novel data management technologies appear in the market e.g. key-value based or in-memory databases, classic relational database management systems (RDBMS) are still widely used. In addition from a hardware perspective, the majority of database servers is still using standard magnetic hard drives (HDDs) instead of solid state drives (SSDs) due to lower cost of storage per gigabyte, disregarding the performance boost that might be given due to high cost. In this study we focus on a software based assessment of the energy consumption of a database server by running three different and complete database workloads namely TCP-H, Star Schema Benchmark -SSB as well a modified benchmark we have derived for this study called W22. We profile the energy distribution among the ost important server components and by using different resource allocation we assess the energy consumption of a typical open source RDBMS (PostgreSQL) on a standard server in relation with its performance (measured by query time). Results confirm the well-known fact that even for complete workloads, optimization of the RDBMS results to lower energy consumption.
The automorphism group of a self-dual [72,36,16] code does not contain S_3, A_4, or D_8
Venue: arXiv cs.IT 2013
Year: 2013

A computer calculation with Magma shows that there is no extremal self-dual binary code C of length 72, whose automorphism group contains the symmetric group of degree 3, the alternating group of degree 4 or the dihedral group of order 8. Combining this with the known results in the literature one obtains that Aut(C) has order at most 5 or isomorphic to the elementary abelian group of order 8.
A Novel Algorithm for Linear Programming
Venue: arXiv cs.NA 2013
Year: 2013

The problem of optimizing a linear objective function,given a number of linear constraints has been a long standing problem ever since the times of Kantorovich, Dantzig and von Neuman. These developments have been followed by a different approach pioneered by Khachiyan and Karmarkar. In this paper we present an entirely new method for solving an old optimization problem in a novel manner, a technique that reduces the dimension of the problem step by step and interestingly is recursive. A theorem which proves the correctness of the approach is given. The method can be extended to other types of optimization problems in convex space, e.g. for solving a linear optimization problem subject to nonlinear constraints in a convex region.
Towards an Integrated Approach to Crowd Analysis and Crowd Synthesis: a Case Study and First Results
Venue: arXiv cs.MA 2013
Year: 2013

Studies related to crowds of pedestrians, both those of theoretical nature and application oriented ones, have generally focused on either the analysis or the synthesis of the phenomena related to the interplay between individual pedestrians, each characterised by goals, preferences and potentially relevant relationships with others, and the environment in which they are situated. The cases in which these activities have been systematically integrated for a mutual benefit are still very few compared to the corpus of crowd related literature. This paper presents a case study of an integrated approach to the definition of an innovative model for pedestrian and crowd simulation (on the side of synthesis) that was actually motivated and supported by the analyses of empirical data acquired from both experimental settings and observations in real world scenarios. In particular, we will introduce a model for the adaptive behaviour of pedestrians that are also members of groups, that strive to maintain their cohesion even in difficult (e.g. high density) situations. The paper will show how the synthesis phase also provided inputs to the analysis of empirical data, in a virtuous circle.
Feasibility Conditions of Interference Alignment via Two Orthogonal Subcarriers
Venue: arXiv cs.IT 2013
Year: 2013

Conditions are derived on line-of-sight channels to ensure the feasibility of interference alignment. The conditions involve choosing only the spacing between two subcarriers of an orthogonal frequency division multiplexing (OFDM) scheme. The maximal degrees-of-freedom are achieved and even an upper bound on the sum-rate of interference alignment is approached arbitrarily closely.
Reasoning With Qualitative Probabilities Can Be Tractable
Venue: arXiv cs.AI 2013
Year: 2013

We recently described a formalism for reasoning with if-then rules that re expressed with different levels of firmness [18]. The formalism interprets these rules as extreme conditional probability statements, specifying orders of magnitude of disbelief, which impose constraints over possible rankings of worlds. It was shown that, once we compute a priority function Z+ on the rules, the degree to which a given query is confirmed or denied can be computed in O(log n`) propositional satisfiability tests, where n is the number of rules in the knowledge base. In this paper, we show that computing Z+ requires O(n2 X log n) satisfiability tests, not an exponential number as was conjectured in [18], which reduces to polynomial complexity in the case of Horn expressions. We also show how reasoning with imprecise observations can be incorporated in our formalism and how the popular notions of belief revision and epistemic entrenchment are embodied naturally and tractably.
A computational scheme for Reasoning in Dynamic Probabilistic Networks
Venue: arXiv cs.AI 2013
Year: 2013

A computational scheme for reasoning about dynamic systems using (causal) probabilistic networks is presented. The scheme is based on the framework of Lauritzen and Spiegelhalter (1988), and may be viewed as a generalization of the inference methods of classical time-series analysis in the sense that it allows description of non-linear, multivariate dynamic systems with complex conditional independence structures. Further, the scheme provides a method for efficient backward smoothing and possibilities for efficient, approximate forecasting methods. The scheme has been implemented on top of the HUGIN shell.
Calculating Uncertainty Intervals From Conditional Convex Sets of Probabilities
Venue: arXiv cs.AI 2013
Year: 2013

In Moral, Campos (1991) and Cano, Moral, Verdegay-Lopez (1991) a new method of conditioning convex sets of probabilities has been proposed. The result of it is a convex set of non-necessarily normalized probability distributions. The normalizing factor of each probability distribution is interpreted as the possibility assigned to it by the conditioning information. From this, it is deduced that the natural value for the conditional probability of an event is a possibility distribution. The aim of this paper is to study methods of transforming this possibility distribution into a probability (or uncertainty) interval. These methods will be based on the use of Sugeno and Choquet integrals. Their behaviour will be compared in basis to some selected examples.
aHUGIN: A System Creating Adaptive Causal Probabilistic Networks
Venue: arXiv cs.AI 2013
Year: 2013

The paper describes aHUGIN, a tool for creating adaptive systems. aHUGIN is an extension of the HUGIN shell, and is based on the methods reported by Spiegelhalter and Lauritzen (1990a). The adaptive systems resulting from aHUGIN are able to adjust the C011ditional probabilities in the model. A short analysis of the adaptation task is given and the features of aHUGIN are described. Finally a session with experiments is reported and the results are discussed.
Decision Methods for Adaptive Task-Sharing in Associate Systems
Venue: arXiv cs.AI 2013
Year: 2013

This paper describes some results of research on associate systems: knowledge-based systems that flexibly and adaptively support their human users in carrying out complex, time-dependent problem-solving tasks under uncertainty. Based on principles derived from decision theory and decision analysis, a problem-solving approach is presented which can overcome many of the limitations of traditional expert-systems. This approach implements an explicit model of the human user's problem-solving capabilities as an integral element in the overall problem solving architecture. This integrated model, represented as an influence diagram, is the basis for achieving adaptive task sharing behavior between the associate system and the human user. This associate system model has been applied toward ongoing research on a Mars Rover Manager's Associate (MRMA). MRMA's role would be to manage a small fleet of robotic rovers on the Martian surface. The paper describes results for a specific scenario where MRMA examines the benefits and costs of consulting human experts on Earth to assist a Mars rover with a complex resource management decision.
Conditional Independence in Uncertainty Theories
Venue: arXiv cs.AI 2013
Year: 2013

This paper introduces the notions of independence and conditional independence in valuation-based systems (VBS). VBS is an axiomatic framework capable of representing many different uncertainty calculi. We define independence and conditional independence in terms of factorization of the joint valuation. The definitions of independence and conditional independence in VBS generalize the corresponding definitions in probability theory. Our definitions apply not only to probability theory, but also to Dempster-Shafer's belief-function theory, Spohn's epistemic-belief theory, and Zadeh's possibility theory. In fact, they apply to any uncertainty calculi that fit in the framework of valuation-based systems.
Towards Precision of Probabilistic Bounds Propagation
Venue: arXiv cs.AI 2013
Year: 2013

The DUCK-calculus presented here is a recent approach to cope with probabilistic uncertainty in a sound and efficient way. Uncertain rules with bounds for probabilities and explicit conditional independences can be maintained incrementally. The basic inference mechanism relies on local bounds propagation, implementable by deductive databases with a bottom-up fixpoint evaluation. In situations, where no precise bounds are deducible, it can be combined with simple operations research techniques on a local scope. In particular, we provide new precise analytical bounds for probabilistic entailment.
Novel O(H(N)+N/H(N)) Algorithmic Techniques for Several Types of Queries and Updates on Rooted Trees and Lists
Venue: arXiv cs.DS 2013
Year: 2013

In this paper we present novel algorithmic techniques with a O(H(N)+N/H(N)) time complexity for performing several types of queries and updates on general rooted trees, binary search trees and lists of size N. For rooted trees we introduce a new compressed super-node tree representation which can be used for efficiently addressing a wide range of applications. For binary search trees we discuss the idea of globally rebuilding the entire tree in a fully balanced manner whenever the height of the tree exceeds the value of a conveniently chosen function of the number of tree nodes. In the end of the paper we introduce the H-list data structure which supports concatenation, split and several types of queries. Note that when choosing H(N)=sqrt(N) we obtain O(H(N)+N/H(N))=O(sqrt(N)).
Network Detection Theory and Performance
Venue: arXiv cs.SI 2013
Year: 2013

Network detection is an important capability in many areas of applied research in which data can be represented as a graph of entities and relationships. Oftentimes the object of interest is a relatively small subgraph in an enormous, potentially uninteresting background. This aspect characterizes network detection as a "big data" problem. Graph partitioning and network discovery have been major research areas over the last ten years, driven by interest in internet search, cyber security, social networks, and criminal or terrorist activities. The specific problem of network discovery is addressed as a special case of graph partitioning in which membership in a small subgraph of interest must be determined. Algebraic graph theory is used as the basis to analyze and compare different network detection methods. A new Bayesian network detection framework is introduced that partitions the graph based on prior information and direct observations. The new approach, called space-time threat propagation, is proved to maximize the probability of detection and is therefore optimum in the Neyman-Pearson sense. This optimality criterion is compared to spectral community detection approaches which divide the global graph into subsets or communities with optimal connectivity properties. We also explore a new generative stochastic model for covert networks and analyze using receiver operating characteristics the detection performance of both classes of optimal detection techniques.
ARCO1: An Application of Belief Networks to the Oil Market
Venue: arXiv cs.AI 2013
Year: 2013

Belief networks are a new, potentially important, class of knowledge-based models. ARCO1, currently under development at the Atlantic Richfield Company (ARCO) and the University of Southern California (USC), is the most advanced reported implementation of these models in a financial forecasting setting. ARCO1's underlying belief network models the variables believed to have an impact on the crude oil market. A pictorial market model-developed on a MAC II- facilitates consensus among the members of the forecasting team. The system forecasts crude oil prices via Monte Carlo analyses of the network. Several different models of the oil market have been developed; the system's ability to be updated quickly highlights its flexibility.
Combination of Upper and Lower Probabilities
Venue: arXiv cs.AI 2013
Year: 2013

In this paper, we consider several types of information and methods of combination associated with incomplete probabilistic systems. We discriminate between 'a priori' and evidential information. The former one is a description of the whole population, the latest is a restriction based on observations for a particular case. Then, we propose different combination methods for each one of them. We also consider conditioning as the heterogeneous combination of 'a priori' and evidential information. The evidential information is represented as a convex set of likelihood functions. These will have an associated possibility distribution with behavior according to classical Possibility Theory.
A Probabilistic Analysis of Marker-Passing Techniques for Plan-Recognition
Venue: arXiv cs.AI 2013
Year: 2013

Useless paths are a chronic problem for marker-passing techniques. We use a probabilistic analysis to justify a method for quickly identifying and rejecting useless paths. Using the same analysis, we identify key conditions and assumptions necessary for marker-passing to perform well.
Local Expression Languages for Probabilistic Dependence: a Preliminary Report
Venue: arXiv cs.AI 2013
Year: 2013

We present a generalization of the local expression language used in the Symbolic Probabilistic Inference (SPI) approach to inference in belief nets [1l, [8]. The local expression language in SPI is the language in which the dependence of a node on its antecedents is described. The original language represented the dependence as a single monolithic conditional probability distribution. The extended language provides a set of operators (*, +, and -) which can be used to specify methods for combining partial conditional distributions. As one instance of the utility of this extension, we show how this extended language can be used to capture the semantics, representational advantages, and inferential complexity advantages of the "noisy or" relationship.