OpenRaiser/Intern-Atlas huggingface dataset:
Source Distinguishability under Distortion-Limited Attack: an Optimal Transport Perspective
Venue: arXiv cs.SY 2014
Year: 2014

We analyze the distinguishability of two sources in a Neyman-Pearson set-up when an attacker is allowed to modify the output of one of the two sources subject to a distortion constraint. By casting the problem in a game-theoretic framework and by exploiting the parallelism between the attacker's goal and Optimal Transport Theory, we introduce the concept of Security Margin defined as the maximum average per-sample distortion introduced by the attacker for which the two sources can be distinguished ensuring arbitrarily small, yet positive, error exponents for type I and type II error probabilities. Several versions of the problem are considered according to the available knowledge about the sources and the type of distance used to define the distortion constraint. We compute the security margin for some classes of sources and derive a general upper bound assuming that the distortion is measured in terms of the mean square error between the original and the attacked sequence.
Imparo is complete by inverse subsumption
Venue: arXiv cs.AI 2014
Year: 2014

In Inverse subsumption for complete explanatory induction Yamamoto et al. investigate which inductive logic programming systems can learn a correct hypothesis $H$ by using the inverse subsumption instead of inverse entailment. We prove that inductive logic programming system Imparo is complete by inverse subsumption for learning a correct definite hypothesis $H$ wrt the definite background theory $B$ and ground atomic examples $E$, by establishing that there exists a connected theory $T$ for $B$ and $E$ such that $H$ subsumes $T$.
A New Approach to Efficient Enumeration by Push-out Amortization
Venue: arXiv cs.DS 2014
Year: 2014

Enumeration algorithms have been one of recent hot topics in theoretical computer science. Different from other problems, enumeration has many interesting aspects, such as the computation time can be shorter than the total output size, by sophisticated ordering of output solutions. One more example is that the recursion of the enumeration algorithm is often structured well, thus we can have good amortized analysis, and interesting algorithms for reducing the amortized complexity. However, there is a lack of deep studies from these points of views; there are only few results on the fundamentals of enumeration, such as a basic design of an algorithm that is applicable to many problems. In this paper, we address new approaches on the complexity analysis, and propose a new way of amortized analysis Push-Out Amortization for enumeration algorithms, where the computation time of an iteration is amortized by using all its descendant iterations. We clarify sufficient conditions on the enumeration algorithm so that the amortized analysis works. By the amortization, we show that many elimination orderings, matchings in a graph, connected vertex induced subgraphs in a graph, and spanning trees can be enumerated in O(1) time for each solution by simple algorithms with simple proofs.
Efficiency of Truthful and Symmetric Mechanisms in One-sided Matching
Venue: arXiv cs.GT 2014
Year: 2014

We study the efficiency (in terms of social welfare) of truthful and symmetric mechanisms in one-sided matching problems with {\em dichotomous preferences} and {\em normalized von Neumann-Morgenstern preferences}. We are particularly interested in the well-known {\em Random Serial Dictatorship} mechanism. For dichotomous preferences, we first show that truthful, symmetric and optimal mechanisms exist if intractable mechanisms are allowed. We then provide a connection to online bipartite matching. Using this connection, it is possible to design truthful, symmetric and tractable mechanisms that extract 0.69 of the maximum social welfare, which works under assumption that agents are not adversarial. Without this assumption, we show that Random Serial Dictatorship always returns an assignment in which the expected social welfare is at least a third of the maximum social welfare. For normalized von Neumann-Morgenstern preferences, we show that Random Serial Dictatorship always returns an assignment in which the expected social welfare is at least $\frac{1}{e}\frac{ν(\opt)^2}{n}$, where $ν(\opt)$ is the maximum social welfare and $n$ is the number of both agents and items. On the hardness side, we show that no truthful mechanism can achieve a social welfare better than $\frac{ν(\opt)^2}{n}$.
Rank weight hierarchy of some classes of cyclic codes
Venue: arXiv cs.IT 2014
Year: 2014

We study the rank weight hierarchy, thus in particular the rank metric, of cyclic codes over the finite field $\mathbb F_{q^m}$, $q$ a prime power, $m \geq 2$. We establish the rank weight hierarchy for $[n,n-1]$ cyclic codes and characterize $[n,k]$ cyclic codes of rank metric 1 when (1) $k=1$, (2) $n$ and $q$ are coprime, and (3) the characteristic $char(\mathbb F_q)$ divides $n$. Finally, for $n$ and $q$ coprime, cyclic codes of minimal $r$-rank are characterized, and a refinement of the Singleton bound for the rank weight is derived.
Image Fusion Using LEP Filtering and Bilinear Interpolation
Venue: arXiv cs.CV 2014
Year: 2014

Image Fusion is the process in which core information from a set of component images is merged to form a single image, which is more informative and complete than the component input images in quality and appearance. This paper presents a fast and effective image fusion method for creating high quality fused images by merging component images. In the proposed method, the input image is broken down to a two-scale image representation with a base layer having large scale variations in intensity, and a detail layer containing small scale details. Here fusion of the base and detail layers is implemented by means of a Local Edge preserving filtering based technique. The proposed method is an efficient image fusion technique in which the noise component is very low and quality of the resultant image is high so that it can be used for applications like medical image processing, requiring very accurate edge preserved images. Performance is tested by calculating PSNR and SSIM of images. The benefit of the proposed method is that it removes noise without altering the underlying structures of the image. This paper also presents an image zooming technique using bilinear interpolation in which a portion of the input image is cropped and bilinear interpolation is applied. Experimental results showed that the when PSNR value is calculated, the noise is found to be very low for the resultant image portion.
Space-Time Codes from Spectral Norm: A Fresh Look
Venue: arXiv cs.IT 2014
Year: 2014

Current research proposes a natural environment for the space-time codes and in this context it is obtained a new design criterion for space-time codes in multi-antenna communication channels. The objective of this criterion is to minimize the pairwise error probability of the maximum likelihood decoder, endowed with the matrix spectrum norm. The random matrix theory is used and an approximation function for the probability density function is obtained for the largest eigenvalue of a Wishart Matrix.
Uncertainty And Evolutionary Optimization: A Novel Approach
Venue: arXiv cs.NE 2014
Year: 2014

Evolutionary algorithms (EA) have been widely accepted as efficient solvers for complex real world optimization problems, including engineering optimization. However, real world optimization problems often involve uncertain environment including noisy and/or dynamic environments, which pose major challenges to EA-based optimization. The presence of noise interferes with the evaluation and the selection process of EA, and thus adversely affects its performance. In addition, as presence of noise poses challenges to the evaluation of the fitness function, it may need to be estimated instead of being evaluated. Several existing approaches attempt to address this problem, such as introduction of diversity (hyper mutation, random immigrants, special operators) or incorporation of memory of the past (diploidy, case based memory). However, these approaches fail to adequately address the problem. In this paper we propose a Distributed Population Switching Evolutionary Algorithm (DPSEA) method that addresses optimization of functions with noisy fitness using a distributed population switching architecture, to simulate a distributed self-adaptive memory of the solution space. Local regression is used in the pseudo-populations to estimate the fitness. Successful applications to benchmark test problems ascertain the proposed method's superior performance in terms of both robustness and accuracy.
Compressive Periodogram Reconstruction Using Uniform Binning
Venue: arXiv cs.OH 2014
Year: 2014

In this paper, two problems that show great similarities are examined. The first problem is the reconstruction of the angular-domain periodogram from spatial-domain signals received at different time indices. The second one is the reconstruction of the frequency-domain periodogram from time-domain signals received at different wireless sensors. We split the entire angular or frequency band into uniform bins. The bin size is set such that the received spectra at two frequencies or angles, whose distance is equal to or larger than the size of a bin, are uncorrelated. These problems in the two different domains lead to a similar circulant structure in the so-called coset correlation matrix. This circulant structure allows for a strong compression and a simple least-squares reconstruction method. The latter is possible under the full column rank condition of the system matrix, which can be achieved by designing the spatial or temporal sampling patterns based on a circular sparse ruler. We analyze the statistical performance of the compressively reconstructed periodogram including bias and variance. We further consider the case when the bins are so small that the received spectra at two frequencies or angles, with a spacing between them larger than the size of the bin, can still be correlated. In this case, the resulting coset correlation matrix is generally not circulant and thus a special approach is required.
Hybrid Communication Architecture HCA
Venue: arXiv cs.DC 2014
Year: 2014

The beginning of the 21st century has seen many projects on distributed hash tables, both research and commercial. One of their aims has been to replace the first generation of file sharing software with scalable peer-to-peer architectures. On other fronts, the same techniques are applied, for example, to content delivery networks, streaming networks, cooperative caches, distributed file systems, and grid computing architectures for scientific use. This trend has emerged because with cooperative peers it is possible to asymptotically enhance the use of resouces in sharing of data compared to the basic client-server architecture. The need for distribution of data is wide and one could argue that it is as fundamental a building block as the message passing of the Internet. As an answer to this need a new scalable architecture is introduced: Hybrid Communication Architecture (HCA), which provides both data sharing and message passing as communication primitives for applications. HCA can be regarded as an abstraction layer for communication which is further encapsulated by a higher-level middleware. HCA is aimed at general use, and it is not designed for any particular application. One key idea is to combine data sharing with streaming since together they enable many applications not easily implementable with only one of these features. For example, a game application could share the game world state between clients and modify it by using streaming. The other distinctive feature of the system is the use of knowledge of the physical network topology in the optimization of the communication. With a feasible business model, fault-tolerance, and security features, HCA is aimed eventually for real-life adoption. This thesis presents the specification of the C++ client interface of HCA and the architecture and protocol of the distributed nodes forming the implementation.
Power Control for Sum Rate Maximization on Interference Channels Under Sum Power Constraint
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we consider the problem of power control for sum rate maximization on multiple interfering links (TX-RX pairs)under sum power constraint. We consider a single frequency network, where all pairs are operating in same frequency band,thereby creating interference for each other. We study the power allocation problem for sum rate maximization with and without QoS requirements on individual links. When the objective is only sum rate maximization without QoS guarantees, we develop an analytic solution to decide optimal power allocation for two TX-RX pair problem. We also develop a low complexity iterative algorithm for three TX-RX pair problem. For a generic N>3 TX-RX pair problem, we develop two low-complexity sub-optimal power allocation algorithms. The first algorithm is based on the idea of making clusters of two or three TX-RX pairs and then leverage the power allocation results obtained for two and three TX-RX pair problems. The second algorithm is developed by using a high SINR approximation and this algorithm can also be implemented in a distributed manner by individual TXs. We then consider the same problem but with additional QoS guarantees for individual links. We again develop an analytic solution for two TX-RX pair problem, and a distributed algorithm for N>2 TX-RX pairs.
Bridging the Research-Practice Gap in Requirements Engineering through Effective Teaching and Peer Learning
Venue: arXiv cs.SE 2014
Year: 2014

In this paper, we introduce the concept of the research practice gap as it is perceived in the field of software requirements engineering. An analysis of this gap has shown that two key causes for the research-practice gap are lack of effective communication and the relatively light coverage of requirements engineering material in University programmes. We discuss the design and delivery of a Masters course in Software Requirements Engineering (SRE) that is designed to overcome some of the issues that have caused the research-practice gap. By encouraging students to share their experiences in a peer learning environment, we aim to improve shared understanding between students (many of whom are current industry practitioners) and researchers (including academic staff members) to improve the potential for effective collaborations, whilst simultaneously developing the requirements engineering skill sets of the enrolled students. Feedback from students in the course is discussed and directions for the future development of the curriculum and learning strategies are given.
Mobile Camera Array Calibration for Light Field Acquisition
Venue: arXiv cs.CV 2014
Year: 2014

The light field camera is useful for computer graphics and vision applications. Calibration is an essential step for these applications. After calibration, we can rectify the captured image by using the calibrated camera parameters. However, the large camera array calibration method, which assumes that all cameras are on the same plane, ignores the orientation and intrinsic parameters. The multi-camera calibration technique usually assumes that the working volume and viewpoints are fixed. In this paper, we describe a calibration algorithm suitable for a mobile camera array based light field acquisition system. The algorithm performs in Zhang's style by moving a checkerboard, and computes the initial parameters in closed form. Global optimization is then applied to refine all the parameters simultaneously. Our implementation is rather flexible in that users can assign the number of viewpoints and refinement of intrinsic parameters is optional. Experiments on both simulated data and real data acquired by a commercial product show that our method yields good results. Digital refocusing application shows the calibrated light field can well focus to the target object we desired.
Some upper and lower bounds on PSD-rank
Venue: arXiv cs.CC 2014
Year: 2014

Positive semidefinite rank (PSD-rank) is a relatively new quantity with applications to combinatorial optimization and communication complexity. We first study several basic properties of PSD-rank, and then develop new techniques for showing lower bounds on the PSD-rank. All of these bounds are based on viewing a positive semidefinite factorization of a matrix $M$ as a quantum communication protocol. These lower bounds depend on the entries of the matrix and not only on its support (the zero/nonzero pattern), overcoming a limitation of some previous techniques. We compare these new lower bounds with known bounds, and give examples where the new ones are better. As an application we determine the PSD-rank of (approximations of) some common matrices.
Density Evolution for SUDOKU Codes on the Erasure Channel
Venue: arXiv cs.IT 2014
Year: 2014

Codes based on SUDOKU puzzles are discussed, and belief propagation decoding introduced for the erasure channel. Despite the non-linearity of the code constraints, it is argued that density evolution can be used to analyse code performance due to the invariance of the code under alphabet permutation. The belief propagation decoder for erasure channels operates by exchanging messages containing sets of possible values. Accordingly, density evolution tracks the probability mass functions of the set cardinalities. The equations governing the mapping of those probability mass functions are derived and calculated for variable and constraint nodes, and decoding thresholds are computed for long SUDOKU codes with random interleavers.
Faults in Linux 2.6
Venue: arXiv cs.SE 2014
Year: 2014

In August 2011, Linux entered its third decade. Ten years before, Chou et al. published a study of faults found by applying a static analyzer to Linux versions 1.0 through 2.4.1. A major result of their work was that the drivers directory contained up to 7 times more of certain kinds of faults than other directories. This result inspired numerous efforts on improving the reliability of driver code. Today, Linux is used in a wider range of environments, provides a wider range of services, and has adopted a new development and release model. What has been the impact of these changes on code quality? To answer this question, we have transported Chou et al.'s experiments to all versions of Linux 2.6; released between 2003 and 2011. We find that Linux has more than doubled in size during this period, but the number of faults per line of code has been decreasing. Moreover, the fault rate of drivers is now below that of other directories, such as arch. These results can guide further development and research efforts for the decade to come. To allow updating these results as Linux evolves, we define our experimental protocol and make our checkers available.
PaPy: Parallel and Distributed Data-processing Pipelines in Python
Venue: arXiv cs.PL 2014
Year: 2014

PaPy, which stands for parallel pipelines in Python, is a highly flexible framework that enables the construction of robust, scalable workflows for either generating or processing voluminous datasets. A workflow is created from user-written Python functions (nodes) connected by 'pipes' (edges) into a directed acyclic graph. These functions are arbitrarily definable, and can make use of any Python modules or external binaries. Given a user-defined topology and collection of input data, functions are composed into nested higher-order maps, which are transparently and robustly evaluated in parallel on a single computer or on remote hosts. Local and remote computational resources can be flexibly pooled and assigned to functional nodes, thereby allowing facile load-balancing and pipeline optimization to maximize computational throughput. Input items are processed by nodes in parallel, and traverse the graph in batches of adjustable size -- a trade-off between lazy-evaluation, parallelism, and memory consumption. The processing of a single item can be parallelized in a scatter/gather scheme. The simplicity and flexibility of distributed workflows using PaPy bridges the gap between desktop -> grid, enabling this new computing paradigm to be leveraged in the processing of large scientific datasets.
PresenceSense: Zero-training Algorithm for Individual Presence Detection based on Power Monitoring
Venue: arXiv cs.HC 2014
Year: 2014

Non-intrusive presence detection of individuals in commercial buildings is much easier to implement than intrusive methods such as passive infrared, acoustic sensors, and camera. Individual power consumption, while providing useful feedback and motivation for energy saving, can be used as a valuable source for presence detection. We conduct pilot experiments in an office setting to collect individual presence data by ultrasonic sensors, acceleration sensors, and WiFi access points, in addition to the individual power monitoring data. PresenceSense (PS), a semi-supervised learning algorithm based on power measurement that trains itself with only unlabeled data, is proposed, analyzed and evaluated in the study. Without any labeling efforts, which are usually tedious and time consuming, PresenceSense outperforms popular models whose parameters are optimized over a large training set. The results are interpreted and potential applications of PresenceSense on other data sources are discussed. The significance of this study attaches to space security, occupancy behavior modeling, and energy saving of plug loads.
SoundLoc: Acoustic Method for Indoor Localization without Infrastructure
Venue: arXiv cs.HC 2014
Year: 2014

Identifying locations of occupants is beneficial to energy management in buildings. A key observation in indoor environment is that distinct functional areas are typically controlled by separate HVAC and lighting systems and room level localization is sufficient to provide a powerful tool for energy usage reduction by occupancy-based actuation of the building facilities. Based upon this observation, this paper focuses on identifying the room where a person or a mobile device is physically present. Existing room localization methods, however, require special infrastructure to annotate rooms. SoundLoc is a room-level localization system that exploits the intrinsic acoustic properties of individual rooms and obviates the needs for infrastructures. As we show in the study, rooms' acoustic properties can be characterized by Room Impulse Response (RIR). Nevertheless, obtaining precise RIRs is a time-consuming and expensive process. The main contributions of our work are the following. First, a cost-effective RIR measurement system is implemented and the Noise Adaptive Extraction of Reverberation (NAER) algorithm is developed to estimate room acoustic parameters in noisy conditions. Second, a comprehensive physical and statistical analysis of features extracted from RIRs is performed. Also, SoundLoc is evaluated using the dataset consisting of ten (10) different rooms. The overall accuracy of 97.8% achieved demonstrates the potential to be integrated into automatic mapping of building space.