OpenRaiser/Intern-Atlas huggingface dataset:
Multi-Robot Informative Path Planning for Active Sensing of Environmental Phenomena: A Tale of Two Algorithms
Venue: arXiv cs.LG 2013
Year: 2013

A key problem of robotic environmental sensing and monitoring is that of active sensing: How can a team of robots plan the most informative observation paths to minimize the uncertainty in modeling and predicting an environmental phenomenon? This paper presents two principled approaches to efficient information-theoretic path planning based on entropy and mutual information criteria for in situ active sensing of an important broad class of widely-occurring environmental phenomena called anisotropic fields. Our proposed algorithms are novel in addressing a trade-off between active sensing performance and time efficiency. An important practical consequence is that our algorithms can exploit the spatial correlation structure of Gaussian process-based anisotropic fields to improve time efficiency while preserving near-optimal active sensing performance. We analyze the time complexity of our algorithms and prove analytically that they scale better than state-of-the-art algorithms with increasing planning horizon length. We provide theoretical guarantees on the active sensing performance of our algorithms for a class of exploration tasks called transect sampling, which, in particular, can be improved with longer planning time and/or lower spatial correlation along the transect. Empirical evaluation on real-world anisotropic field data shows that our algorithms can perform better or at least as well as the state-of-the-art algorithms while often incurring a few orders of magnitude less computational time, even when the field conditions are less favorable.
Explicit MBR All-Symbol Locality Codes
Venue: arXiv cs.IT 2013
Year: 2013

Node failures are inevitable in distributed storage systems (DSS). To enable efficient repair when faced with such failures, two main techniques are known: Regenerating codes, i.e., codes that minimize the total repair bandwidth; and codes with locality, which minimize the number of nodes participating in the repair process. This paper focuses on regenerating codes with locality, using pre-coding based on Gabidulin codes, and presents constructions that utilize minimum bandwidth regenerating (MBR) local codes. The constructions achieve maximum resilience (i.e., optimal minimum distance) and have maximum capacity (i.e., maximum rate). Finally, the same pre-coding mechanism can be combined with a subclass of fractional-repetition codes to enable maximum resilience and repair-by-transfer simultaneously.
Incomplete Transition Complexity of Basic Operations on Finite Languages
Venue: arXiv cs.FL 2013
Year: 2013

The state complexity of basic operations on finite languages (considering complete DFAs) has been in studied the literature. In this paper we study the incomplete (deterministic) state and transition complexity on finite languages of boolean operations, concatenation, star, and reversal. For all operations we give tight upper bounds for both description measures. We correct the published state complexity of concatenation for complete DFAs and provide a tight upper bound for the case when the right automaton is larger than the left one. For all binary operations the tightness is proved using family languages with a variable alphabet size. In general the operational complexities depend not only on the complexities of the operands but also on other refined measures.
Search using queries on indistinguishable items
Venue: arXiv cs.DS 2013
Year: 2013

We investigate the problem of determining a set S of k indistinguishable integers in the range [1,n]. The algorithm is allowed to query an integer $q\in [1,n]$, and receive a response comparing this integer to an integer randomly chosen from S. The algorithm has no control over which element of S the query q is compared to. We show tight bounds for this problem. In particular, we show that in the natural regime where $k\le n$, the optimal number of queries to attain $n^{-Ω(1)}$ error probability is $Θ(k^3 \log n)$. In the regime where $k>n$, the optimal number of queries is $Θ(n^2 k \log n)$. Our main technical tools include the use of information theory to derive the lower bounds, and the application of noisy binary search in the spirit of Feige, Raghavan, Peleg, and Upfal (1994). In particular, our lower bound technique is likely to be applicable in other situations that involve search under uncertainty.
Channel Coding and Lossy Source Coding Using a Constrained Random Number Generator
Venue: arXiv cs.IT 2013
Year: 2013

Stochastic encoders for channel coding and lossy source coding are introduced with a rate close to the fundamental limits, where the only restriction is that the channel input alphabet and the reproduction alphabet of the lossy source code are finite. Random numbers, which satisfy a condition specified by a function and its value, are used to construct stochastic encoders. The proof of the theorems is based on the hash property of an ensemble of functions, where the results are extended to general channels/sources and alternative formulas are introduced for channel capacity and the rate-distortion region. Since an ensemble of sparse matrices has a hash property, we can construct a code by using sparse matrices, where the sum-product algorithm can be used for encoding and decoding by assuming that channels/sources are memoryless.
Validasi data dengan menggunakan objek lookup pada borland delphi 7.0
Venue: arXiv cs.DB 2013
Year: 2013

Developing an application with some tables must concern the validation of input (specially in Table Child). In order to maximize the accuracy and data input validation. Its called lookup (took data from other dataset). There are two ways to look up data from Table Parent: 1) Using Objects (DBLookupComboBox and DBookupListBox), or 2) Arranging the properties of data types fields (shown by using DBGrid). In this article is using Borland Delphi software (Inprise product). The method is offered using 5 (five) practise steps: 1) Relational Database Scheme, 2) Form Design, 3) Object DatabasesRelationships Scheme, 4) Properties and Field Type Arrangement, and 5) Procedures. The result of this paper are: 1) The relationship that using lookup objects are valid, and 2) Delphi Lookup Objects can be used for 1-1, 1-N, and M-N relationship.
Image Denoising Using Interquartile Range Filter with Local Averaging
Venue: arXiv cs.CV 2013
Year: 2013

Image denoising is one of the fundamental problems in image processing. In this paper, a novel approach to suppress noise from the image is conducted by applying the interquartile range (IQR) which is one of the statistical methods used to detect outlier effect from a dataset. A window of size kXk was implemented to support IQR filter. Each pixel outside the IQR range of the kXk window is treated as noisy pixel. The estimation of the noisy pixels was obtained by local averaging. The essential advantage of applying IQR filter is to preserve edge sharpness better of the original image. A variety of test images have been used to support the proposed filter and PSNR was calculated and compared with median filter. The experimental results on standard test images demonstrate this filter is simpler and better performing than median filter.
Improving Mixed-Criticality System Consistency and Behavior on Multiprocessor Platforms by Means of Multi-Moded Approaches
Venue: arXiv cs.OH 2013
Year: 2013

Recent research in the domain of real-time scheduling theory has tackled the problem of scheduling mixed-criticality systems upon uniprocessor or multiprocessor platforms, with the main objective being to respect the timeliness of the most critical tasks, at the expense of the requirements of the less critical ones. In particular, the less critical tasks are carelessly discarded when the computation demand of (some of) the high critical tasks increases. This might nevertheless result in system failure, as these less critical tasks could be accessing data, the consistency of which should be preserved. In this paper, we address this problem and propose a method to cautiously handle task suspension. Furthermore, it is usually assumed that the less critical tasks will never be re-enabled once discarded. In this paper, we also address this concern by proposing an approach to re-enable the less critical tasks, without jeopardizing the timeliness of the high critical ones. The suggested approaches apply to systems having two or more criticality levels.
Performance Evaluation of Sparse Matrix Multiplication Kernels on Intel Xeon Phi
Venue: arXiv cs.PF 2013
Year: 2013

Intel Xeon Phi is a recently released high-performance coprocessor which features 61 cores each supporting 4 hardware threads with 512-bit wide SIMD registers achieving a peak theoretical performance of 1Tflop/s in double precision. Many scientific applications involve operations on large sparse matrices such as linear solvers, eigensolver, and graph mining algorithms. The core of most of these applications involves the multiplication of a large, sparse matrix with a dense vector (SpMV). In this paper, we investigate the performance of the Xeon Phi coprocessor for SpMV. We first provide a comprehensive introduction to this new architecture and analyze its peak performance with a number of micro benchmarks. Although the design of a Xeon Phi core is not much different than those of the cores in modern processors, its large number of cores and hyperthreading capability allow many application to saturate the available memory bandwidth, which is not the case for many cutting-edge processors. Yet, our performance studies show that it is the memory latency not the bandwidth which creates a bottleneck for SpMV on this architecture. Finally, our experiments show that Xeon Phi's sparse kernel performance is very promising and even better than that of cutting-edge general purpose processors and GPUs.
Analysis Based Blind Compressive Sensing
Venue: arXiv cs.IT 2013
Year: 2013

In this work we address the problem of blindly reconstructing compressively sensed signals by exploiting the co-sparse analysis model. In the analysis model it is assumed that a signal multiplied by an analysis operator results in a sparse vector. We propose an algorithm that learns the operator adaptively during the reconstruction process. The arising optimization problem is tackled via a geometric conjugate gradient approach. Different types of sampling noise are handled by simply exchanging the data fidelity term. Numerical experiments are performed for measurements corrupted with Gaussian as well as impulsive noise to show the effectiveness of our method.
The Design and Demonstration of an Actor-Based, Application-Aware Access Control Evaluation Framework
Venue: arXiv cs.CR 2013
Year: 2013

To date, most work regarding the formal analysis of access control schemes has focused on quantifying and comparing the expressive power of a set of schemes. Although expressive power is important, it is a property that exists in an absolute sense, detached from the application-specific context within which an access control scheme will ultimately be deployed. In this paper, by contrast, we formalize the access control suitability analysis problem, which seeks to evaluate the degree to which a set of candidate access control schemes can meet the needs of an application-specific workload. This process involves both reductions to assess whether a scheme is capable of implementing a workload, as well as cost analysis using ordered measures to quantify the overheads of using each candidate scheme to service the workload. We develop a mathematical framework for analyzing instances of the suitability analysis problem, and evaluate this framework both formally (by quantifying its efficiency and accuracy properties) and practically (by exploring a group-based messaging workload from the literature). An ancillary contribution of our work is the identification of auxiliary machines, which are a useful class of modifications that can be made to enhance the expressive power of an access control scheme without negatively impacting the safety properties of the scheme.
Computability of the entropy of one-tape Turing Machines
Venue: arXiv cs.FL 2013
Year: 2013

We prove that the maximum speed and the entropy of a one-tape Turing machine are computable, in the sense that we can approximate them to any given precision $ε$. This is contrary to popular belief, as all dynamical properties are usually undecidable for Turing machines. The result is quite specific to one-tape Turing machines, as it is not true anymore for two-tape Turing machines by the results of Blondel et al., and uses the approach of crossing sequences introduced by Hennie.
Sharp RIP Bound for Sparse Signal and Low-Rank Matrix Recovery
Venue: arXiv cs.IT 2013
Year: 2013

This paper establishes a sharp condition on the restricted isometry property (RIP) for both the sparse signal recovery and low-rank matrix recovery. It is shown that if the measurement matrix $A$ satisfies the RIP condition $δ_k^A<1/3$, then all $k$-sparse signals $β$ can be recovered exactly via the constrained $\ell_1$ minimization based on $y=Aβ$. Similarly, if the linear map $\cal M$ satisfies the RIP condition $δ_r^{\cal M}<1/3$, then all matrices $X$ of rank at most $r$ can be recovered exactly via the constrained nuclear norm minimization based on $b={\cal M}(X)$. Furthermore, in both cases it is not possible to do so in general when the condition does not hold. In addition, noisy cases are considered and oracle inequalities are given under the sharp RIP condition.
Key User Extraction Based on Telecommunication Data (aka. Key Users in Social Network. How to find them?)
Venue: arXiv cs.SI 2013
Year: 2013

The number of systems that collect vast amount of data about users rapidly grow during last few years. Many of these systems contain data not only about people characteristics but also about their relationships with other system users. From this kind of data it is possible to extract a social network that reflects the connections between system's users. Moreover, the analysis of such social network enables to investigate different characteristics of its members and their linkages. One of the types of examining such network is key users extraction. Key users are these who have the biggest impact on other network members as well as have big influence on network evolution. The obtained about these users knowledge enables to investigate and predict changes within the network. So this knowledge is very important for the people or companies who make a profit from the network like telecommunication company. The second important thing is the ability to extract these users as quick as possible, i.e. developed the algorithm that will be time-effective in large social networks where number of nodes and edges equal few millions. In this master thesis the method of key user extraction, which is called social position, was analyzed. Moreover, social position measure was compared with other methods, which are used to assess the centrality of a node. Furthermore, three algorithms used to social position calculation was introduced along with results of comparison between their processing time and others centrality methods.
Multi-rate Sub-Nyquist Spectrum Sensing in Cognitive Radios
Venue: arXiv cs.IT 2013
Year: 2013

Wideband spectrum sensing is becoming increasingly important to cognitive radio (CR) systems for exploiting spectral opportunities. This paper introduces a novel multi-rate sub-Nyquist spectrum sensing (MS3) system that implements cooperative wideband spectrum sensing in a CR network. MS3 can detect the wideband spectrum using partial measurements without reconstructing the full frequency spectrum. Sub-Nyquist sampling rates are adopted in sampling channels for wrapping the frequency spectrum onto itself. This significantly reduces sensing requirements of CR. The effects of sub-Nyquist sampling are considered, and the performance of multi-channel sub-Nyquist samplings is analyzed. To improve its detection performance, sub-Nyquist sampling rates are chosen to be different such that the numbers of samples are consecutive prime numbers. Furthermore, when the received signals at CRs are faded or shadowed, the performance of MS3 is analytically evaluated. Numerical results show that the proposed system can significantly enhance the wideband spectrum sensing performance while requiring low computational and implementation complexities.
Spatially-Coupled Precoded Rateless Codes
Venue: arXiv cs.IT 2013
Year: 2013

Raptor codes are rateless codes that achieve the capacity on the binary erasure channels. However the maximum degree of optimal output degree distribution is unbounded. This leads to a computational complexity problem both at encoders and decoders. Aref and Urbanke investigated the potential advantage of universal achieving-capacity property of proposed spatially-coupled (SC) low-density generator matrix (LDGM) codes. However the decoding error probability of SC-LDGM codes is bounded away from 0. In this paper, we investigate SC-LDGM codes concatenated with SC low-density parity-check codes. The proposed codes can be regarded as SC Hsu-Anastasopoulos rateless codes. We derive a lower bound of the asymptotic overhead from stability analysis for successful decoding by density evolution. The numerical calculation reveals that the lower bound is tight. We observe that with a sufficiently large number of information bits, the asymptotic overhead and the decoding error rate approach 0 with bounded maximum degree.
A Polynomial Time Algorithm for Lossy Population Recovery
Venue: arXiv cs.DS 2013
Year: 2013

We give a polynomial time algorithm for the lossy population recovery problem. In this problem, the goal is to approximately learn an unknown distribution on binary strings of length $n$ from lossy samples: for some parameter $μ$ each coordinate of the sample is preserved with probability $μ$ and otherwise is replaced by a `?'. The running time and number of samples needed for our algorithm is polynomial in $n$ and $1/\varepsilon$ for each fixed $μ>0$. This improves on algorithm of Wigderson and Yehudayoff that runs in quasi-polynomial time for any $μ> 0$ and the polynomial time algorithm of Dvir et al which was shown to work for $μ\gtrapprox 0.30$ by Batman et al. In fact, our algorithm also works in the more general framework of Batman et al. in which there is no a priori bound on the size of the support of the distribution. The algorithm we analyze is implicit in previous work; our main contribution is to analyze the algorithm by showing (via linear programming duality and connections to complex analysis) that a certain matrix associated with the problem has a robust local inverse even though its condition number is exponentially small. A corollary of our result is the first polynomial time algorithm for learning DNFs in the restriction access model of Dvir et al.
Update Rules for Parameter Estimation in Bayesian Networks
Venue: arXiv cs.LG 2013
Year: 2013

This paper re-examines the problem of parameter estimation in Bayesian networks with missing values and hidden variables from the perspective of recent work in on-line learning [Kivinen & Warmuth, 1994]. We provide a unified framework for parameter estimation that encompasses both on-line learning, where the model is continuously adapted to new data cases as they arrive, and the more traditional batch learning, where a pre-accumulated set of samples is used in a one-time model selection process. In the batch case, our framework encompasses both the gradient projection algorithm and the EM algorithm for Bayesian networks. The framework also leads to new on-line and batch parameter update schemes, including a parameterized version of EM. We provide both empirical and theoretical results indicating that parameterized EM allows faster convergence to the maximum likelihood parameters than does standard EM.
Algorithms for Learning Decomposable Models and Chordal Graphs
Venue: arXiv cs.AI 2013
Year: 2013

Decomposable dependency models and their graphical counterparts, i.e., chordal graphs, possess a number of interesting and useful properties. On the basis of two characterizations of decomposable models in terms of independence relationships, we develop an exact algorithm for recovering the chordal graphical representation of any given decomposable model. We also propose an algorithm for learning chordal approximations of dependency models isomorphic to general undirected graphs.
Exploring Parallelism in Learning Belief Networks
Venue: arXiv cs.AI 2013
Year: 2013

It has been shown that a class of probabilistic domain models cannot be learned correctly by several existing algorithms which employ a single-link look ahead search. When a multi-link look ahead search is used, the computational complexity of the learning algorithm increases. We study how to use parallelism to tackle the increased complexity in learning such models and to speed up learning in large domains. An algorithm is proposed to decompose the learning task for parallel processing. A further task decomposition is used to balance load among processors and to increase the speed-up and efficiency. For learning from very large datasets, we present a regrouping of the available processors such that slow data access through file can be replaced by fast memory access. Our implementation in a parallel computer demonstrates the effectiveness of the algorithm.
A Standard Approach for Optimizing Belief Network Inference using Query DAGs
Venue: arXiv cs.AI 2013
Year: 2013

This paper proposes a novel, algorithm-independent approach to optimizing belief network inference. rather than designing optimizations on an algorithm by algorithm basis, we argue that one should use an unoptimized algorithm to generate a Q-DAG, a compiled graphical representation of the belief network, and then optimize the Q-DAG and its evaluator instead. We present a set of Q-DAG optimizations that supplant optimizations designed for traditional inference algorithms, including zero compression, network pruning and caching. We show that our Q-DAG optimizations require time linear in the Q-DAG size, and significantly simplify the process of designing algorithms for optimizing belief network inference.
Composition of Probability Measures on Finite Spaces
Venue: arXiv cs.AI 2013
Year: 2013

Decomposable models and Bayesian networks can be defined as sequences of oligo-dimensional probability measures connected with operators of composition. The preliminary results suggest that the probabilistic models allowing for effective computational procedures are represented by sequences possessing a special property; we shall call them perfect sequences. The paper lays down the elementary foundation necessary for further study of iterative application of operators of composition. We believe to develop a technique describing several graph models in a unifying way. We are convinced that practically all theoretical results and procedures connected with decomposable models and Bayesian networks can be translated into the terminology introduced in this paper. For example, complexity of computational procedures in these models is closely dependent on possibility to change the ordering of oligo-dimensional measures defining the model. Therefore, in this paper, lot of attention is paid to possibility to change ordering of the operators of composition.