OpenRaiser/Intern-Atlas huggingface dataset:
Reduction of constraint systems
Venue: arXiv cs.DM 2014
Year: 2014

Geometric modeling by constraints leads to large systems of algebraic equations. This paper studies bipartite graphs underlaid by systems of equations. It shows how these graphs make possible to polynomially decompose these systems into well constrained, over-, and underconstrained subsystems. This paper also gives an efficient method to decompose well constrained systems into irreducible ones. These decompositions greatly speed up the resolution in case of reducible systems. They also allow debugging systems of constraints.
A Computational Theory of Subjective Probability
Venue: arXiv cs.AI 2014
Year: 2014

In this article we demonstrate how algorithmic probability theory is applied to situations that involve uncertainty. When people are unsure of their model of reality, then the outcome they observe will cause them to update their beliefs. We argue that classical probability cannot be applied in such cases, and that subjective probability must instead be used. In Experiment 1 we show that, when judging the probability of lottery number sequences, people apply subjective rather than classical probability. In Experiment 2 we examine the conjunction fallacy and demonstrate that the materials used by Tversky and Kahneman (1983) involve model uncertainty. We then provide a formal mathematical proof that, for every uncertain model, there exists a conjunction of outcomes which is more subjectively probable than either of its constituents in isolation.
Energy Efficient Multiuser Scheduling: Statistical Guarantees on Bursty Packet Loss
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we consider energy efficient multiuser scheduling. Packet loss tolerance of the applications is exploited to minimize average system energy. There is a constraint on average packet drop rate and maximum number of packets dropped successively (bursty loss). A finite buffer size is assumed. We propose a scheme which schedules the users opportunistically according to the channel conditions, packet loss constraints and buffer size parameters. We assume imperfect channel state information at the transmitter side and analyze the scheme in large user limit using stochastic optimization techniques. First, we optimize system energy for a fixed buffer size which results in a corresponding statistical guarantee on successive packet drop. Then, we determine the minimum buffer size to achieve a target (improved) energy efficiency for the same (or better) statistical guarantee. We show that buffer size can be traded effectively to achieve system energy efficiency for target statistical guarantees on packet loss parameters.
Fractional Repetition and Erasure Batch Codes
Venue: arXiv cs.IT 2014
Year: 2014

Batch codes are a family of codes that represent a distributed storage system (DSS) of $n$ nodes so that any batch of $t$ data symbols can be retrieved by reading at most one symbol from each node. Fractional repetition codes are a family of codes for DSS that enable efficient uncoded repairs of failed nodes. In this work these two families of codes are combined to obtain fractional repetition batch (FRB) codes which provide both uncoded repairs and parallel reads of subsets of stored symbols. In addition, new batch codes which can tolerate node failures are considered. This new family of batch codes is called erasure combinatorial batch codes (ECBCs). Some properties of FRB codes and ECBCs and examples of their constructions based on transversal designs and affine planes are presented.
Revised Version of a JCIT Paper-Comparison of Feature Point Extraction Algorithms for Vision Based Autonomous Aerial Refueling
Venue: arXiv cs.OH 2014
Year: 2014

This is a revised version of our paper published in Journal of Convergence Information Technology(JCIT): "Comparison of Feature Point Extraction Algorithms for Vision Based Autonomous Aerial Refueling". We corrected some errors including measurement unit errors, spelling errors and so on. Since the published papers in JCIT are not allowed to be modified, we submit the revised version to arXiv.org to make the paper more rigorous and not to confuse other researchers.
Real Time Speckle Image De-Noising
Venue: arXiv cs.CV 2014
Year: 2014

The paper presents real time speckle de-noising based on activity computation algorithm and wavelet transform. Speckles arise in an image when laser light is reflected from an illuminated surface. The process involves detection of speckles in an image by obtaining a number of frames of the same object under different illumination or angle and comparing the frames for the granular computation and de-noising the same on presence of greater activity index. The project can be implemented in FPGA (Field Programmable Gate Array) technology. The results can be shown that the used activity computation algorithm and wavelet transform has better accuracy in the process of speckle detection and de-noising.
On LDPC Codes for Gaussian Interference Channels
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we focus on the two-user Gaussian interference channel (GIC), and study the Han-Kobayashi (HK) coding/decoding strategy with the objective of designing low-density parity-check (LDPC) codes. A code optimization algorithm is proposed which adopts a random perturbation technique via tracking the average mutual information. The degree distribution optimization and convergence threshold computation are carried out for strong and weak interference channels, employing binary phase-shift keying (BPSK). Under strong interference, it is observed that optimized codes operate close to the capacity boundary. For the case of weak interference, it is shown that via the newly designed codes, a nontrivial rate pair is achievable, which is not attainable by single user codes with time-sharing. Performance of the designed LDPC codes are also studied for finite block lengths through simulations of specific codes picked from the optimized degree distributions.
Geometric Polynomial Constraints in Higher-Order Graph Matching
Venue: arXiv cs.CV 2014
Year: 2014

Correspondence is a ubiquitous problem in computer vision and graph matching has been a natural way to formalize correspondence as an optimization problem. Recently, graph matching solvers have included higher-order terms representing affinities beyond the unary and pairwise level. Such higher-order terms have a particular appeal for geometric constraints that include three or more correspondences like the PnP 2D-3D pose problems. In this paper, we address the problem of finding correspondences in the absence of unary or pairwise constraints as it emerges in problems where unary appearance similarity like SIFT matches is not available. Current higher order matching approaches have targeted problems where higher order affinity can simply be formulated as a difference of invariances such as lengths, angles, or cross-ratios. In this paper, we present a method of how to apply geometric constraints modeled as polynomial equation systems. As opposed to RANSAC where such systems have to be solved and then tested for inlier hypotheses, our constraints are derived as a single affinity weight based on $n>2$ hypothesized correspondences without solving the polynomial system. Since the result is directly a correspondence without a transformation model, our approach supports correspondence matching in the presence of multiple geometric transforms like articulated motions.
Improvements and Experiments of a Compact Statistical Background Model
Venue: arXiv cs.CV 2014
Year: 2014

Change detection plays an important role in most video-based applications. The first stage is to build appropriate background model, which is now becoming increasingly complex as more sophisticated statistical approaches are introduced to cover challenging situations and provide reliable detection. This paper reports a simple and intuitive statistical model based on deeper learning spatial correlation among pixels: For each observed pixel, we select a group of supporting pixels with high correlation, and then use a single Gaussian to model the intensity deviations between the observed pixel and the supporting ones. In addition, a multi-channel model updating is integrated on-line and a temporal intensity constraint for each pixel is defined. Although this method is mainly designed for coping with sudden illumination changes, experimental results using all the video sequences provided on changedetection.net validate it is comparable with other recent methods under various situations.
A Sink-driven Approach to Detecting Exposed Component Vulnerabilities in Android Apps
Venue: arXiv cs.CR 2014
Year: 2014

Android apps could expose their components for cooperating with other apps. This convenience, however, makes apps susceptible to the exposed component vulnerability (ECV), in which a dangerous API (commonly known as sink) inside its component can be triggered by other (malicious) apps. In the prior works, detecting these ECVs use a set of sinks pertaining to the ECVs under detection. In this paper, we argue that a more comprehensive and effective approach should start by a systematic selection and classification of vulnerability-specific sinks (VSinks). The set of VSinks is much larger than those used in the previous works. Based on these VSinks, our sink-driven approach can detect different kinds of ECVs in an app in two steps. First, VSinks and their categories are identified through a typical forward reachability analysis. Second, based on each VSink's category, a corresponding detection method is used to identify the ECV via a customized backward dataflow analysis. We also design a semi-auto guided analysis and validation capability for system-only broadcast checking to remove some false positives. We implement our sink-driven approach in a tool called ECVDetector and evaluate it with the top 1K Android apps. Using ECVDetector we successfully identify a total of 49 vulnerable apps across all four ECV categories we have defined. To our knowledge, most of them are previously undisclosed, such as the very popular Go SMS Pro and Clean Master. Moreover, the performance of ECVDetector is high, requiring only 9.257 seconds on average to process each component.
Cross-Language Personal Name Mapping
Venue: arXiv cs.CL 2014
Year: 2014

Name matching between multiple natural languages is an important step in cross-enterprise integration applications and data mining. It is difficult to decide whether or not two syntactic values (names) from two heterogeneous data sources are alternative designation of the same semantic entity (person), this process becomes more difficult with Arabic language due to several factors including spelling and pronunciation variation, dialects and special vowel and consonant distinction and other linguistic characteristics. This paper proposes a new framework for name matching between the Arabic language and other languages. The framework uses a dictionary based on a new proposed version of the Soundex algorithm to encapsulate the recognition of special features of Arabic names. The framework proposes a new proximity matching algorithm to suit the high importance of order sensitivity in Arabic name matching. New performance evaluation metrics are proposed as well. The framework is implemented and verified empirically in several case studies demonstrating substantial improvements compared to other well-known techniques found in literature.
A Parallel Two-Pass MDL Context Tree Algorithm for Universal Source Coding
Venue: arXiv cs.IT 2014
Year: 2014

We present a novel lossless universal source coding algorithm that uses parallel computational units to increase the throughput. The length-$N$ input sequence is partitioned into $B$ blocks. Processing each block independently of the other blocks can accelerate the computation by a factor of $B$, but degrades the compression quality. Instead, our approach is to first estimate the minimum description length (MDL) source underlying the entire input, and then encode each of the $B$ blocks in parallel based on the MDL source. With this two-pass approach, the compression loss incurred by using more parallel units is insignificant. Our algorithm is work-efficient, i.e., its computational complexity is $O(N/B)$. Its redundancy is approximately $B\log(N/B)$ bits above Rissanen's lower bound on universal coding performance, with respect to any tree source whose maximal depth is at most $\log(N/B)$.
Exact values for the Grundy number of some graphs
Venue: arXiv cs.DM 2014
Year: 2014

The Grundy number of a graph G is the maximum number k of colors used to color the vertices of G such that the coloring is proper and every vertex x colored with color i, is adjacent to (i - 1) vertices colored with each color j, In this paper we give bounds for the Grundy number of some graphs and Cartesian products of graphs. In particular, we determine an exact value of this parameter for n-dimensional meshes and some n-dimensional toroidal meshes. Finally, we present an algorithm to generate all graphs for a given Grundy number
A PTAS for the continuous 1.5D Terrain Guarding Problem
Venue: arXiv cs.CG 2014
Year: 2014

In the continuous 1.5-dimensional terrain guarding problem we are given an $x$-monotone chain (the \emph{terrain} $T$) and ask for the minimum number of point guards (located anywhere on $T$), such that all points of $T$ are covered by at least one guard. It has been shown that the 1.5-dimensional terrain guarding problem is \NP-hard. The currently best known approximation algorithm achieves a factor of $4$. For the discrete problem version with a finite set of guard candidates and a finite set of points on the terrain that need to be monitored, a polynomial time approximation scheme (PTAS) has been presented [10]. We show that for the general problem we can construct finite guard and witness sets, $G$ and $W$, such that there exists an optimal guard cover $G^* \subseteq G$ that covers $T$, and when these guards monitor all points in $W$ the entire terrain is guarded. This leads to a PTAS as well as an (exact) IP formulation for the continuous terrain guarding problem.
Cognitive-mapping and contextual pyramid based Digital Elevation Model Registration and its effective storage using fractal based compression
Venue: arXiv cs.AI 2014
Year: 2014

Digital Elevation models (DEM) are images having terrain information embedded into them. Using cognitive mapping concepts for DEM registration, has evolved from this basic idea of using the mapping between the space to objects and defining their relationships to form the basic landmarks that need to be marked, stored and manipulated in and about the environment or other candidate environments, namely, in our case, the DEMs. The progressive two-level encapsulation of methods of geo-spatial cognition includes landmark knowledge and layout knowledge and can be useful for DEM registration. Space-based approach, that emphasizes on explicit extent of the environment under consideration, and object-based approach, that emphasizes on the relationships between objects in the local environment being the two paradigms of cognitive mapping can be methodically integrated in this three-architecture for DEM registration. Initially, P-model based segmentation is performed followed by landmark formation for contextual mapping that uses contextual pyramid formation. Apart from landmarks being used for registration key-point finding, Euclidean distance based deformation calculation has been used for transformation and change detection. Landmarks have been categorized to belong to either being flat-plain areas without much variation in the land heights; peaks that can be found when there is gradual increase in height as compared to the flat areas; valleys, marked with gradual decrease in the height seen in DEM; and finally, ripple areas with very shallow crests and nadirs. Fractal based compression was used for storage of co-registered DEMs. This method may further be extended for DEM-topographic map and DEM-to-remote sensed image registration. Experimental results further cement the fact that DEM registration may be effectively done using the proposed method.
On the Computational Intractability of Exact and Approximate Dictionary Learning
Venue: arXiv cs.IT 2014
Year: 2014

The efficient sparse coding and reconstruction of signal vectors via linear observations has received a tremendous amount of attention over the last decade. In this context, the automated learning of a suitable basis or overcomplete dictionary from training data sets of certain signal classes for use in sparse representations has turned out to be of particular importance regarding practical signal processing applications. Most popular dictionary learning algorithms involve NP-hard sparse recovery problems in each iteration, which may give some indication about the complexity of dictionary learning but does not constitute an actual proof of computational intractability. In this technical note, we show that learning a dictionary with which a given set of training signals can be represented as sparsely as possible is indeed NP-hard. Moreover, we also establish hardness of approximating the solution to within large factors of the optimal sparsity level. Furthermore, we give NP-hardness and non-approximability results for a recent dictionary learning variation called the sensor permutation problem. Along the way, we also obtain a new non-approximability result for the classical sparse recovery problem from compressed sensing.
Load Balancing in Two-Tier Cellular Networks with Open and Hybrid Access Femtocells
Venue: arXiv cs.NI 2014
Year: 2014

Femtocell base station (BS) is a low-power, low-price BS based on cellular communication technology. It is expected to become a cost-effective solution for improving the communication performance of indoor users, whose traffic demands are large in general. There are mainly three access strategies for femtocell, i.e., closed access, open access and hybrid access strategies. While it has been generally known that open/hybrid access femtocells contribute more to enhancing the system-wide performance than closed access femtocells, the operating parameters of both macro and femtocells should be carefully chosen according to the mobile operator's policy, consumer's requirements, and so on. We propose long-term parameter optimization schemes, which maximize the average throughput of macrocell users while guaranteeing some degree of benefits to femtocell owners. To achieve this goal, we jointly optimize the ratio of dedicated resources for femtocells as well as the femtocell service area in open access femtocell networks through the numerical analysis. It is proved that the optimal parameter selection of open access femtocell is a convex optimization problem in typical environments. Then, we extend our algorithm to hybrid access femtocells where some intra-femtocell resources are dedicated only for femtocell owners while remaining resources are shared with foreign macrocell users. Our evaluation results show that the proposed parameter optimization schemes significantly enhance the performance of macrocell users thanks to the large offloading gain. The benefits provided to femtocell users are also adaptively maintained according to the femtocell users' requirements. The results in this paper provide insights about the situations where femtocell deployment on dedicated channels is preferred to the co-channel deployment.
Exact Algorithms for 0-1 Integer Programs with Linear Equality Constraints
Venue: arXiv cs.DS 2014
Year: 2014

In this paper, we show $O(1.415^n)$-time and $O(1.190^n)$-space exact algorithms for 0-1 integer programs where constraints are linear equalities and coefficients are arbitrary real numbers. Our algorithms are quadratically faster than exhaustive search and almost quadratically faster than an algorithm for an inequality version of the problem by Impagliazzo, Lovett, Paturi and Schneider (arXiv:1401.5512), which motivated our work. Rather than improving the time and space complexity, we advance to a simple direction as inclusion of many NP-hard problems in terms of exact exponential algorithms. Specifically, we extend our algorithms to linear optimization problems.
Low Complexity Decoding for Higher Order Punctured Trellis-Coded Modulation Over Intersymbol Interference Channels
Venue: arXiv cs.IT 2014
Year: 2014

Trellis-coded modulation (TCM) is a power and bandwidth efficient digital transmission scheme which offers very low structural delay of the data stream. Classical TCM uses a signal constellation of twice the cardinality compared to an uncoded transmission with one bit of redundancy per PAM symbol, i.e., application of codes with rates $\frac{n-1}{n}$ when $2^{n}$ denotes the cardinality of the signal constellation. Recently published work allows rate adjustment for TCM by means of puncturing the convolutional code (CC) on which a TCM scheme is based on. In this paper it is shown how punctured TCM-signals transmitted over intersymbol interference (ISI) channels can favorably be decoded. Significant complexity reductions at only minor performance loss can be achieved by means of reduced state sequence estimation.
A Topic Model Approach to Multi-Modal Similarity
Venue: arXiv cs.IR 2014
Year: 2014

Calculating similarities between objects defined by many heterogeneous data modalities is an important challenge in many multimedia applications. We use a multi-modal topic model as a basis for defining such a similarity between objects. We propose to compare the resulting similarities from different model realizations using the non-parametric Mantel test. The approach is evaluated on a music dataset.
Supervised Dictionary Learning by a Variational Bayesian Group Sparse Nonnegative Matrix Factorization
Venue: arXiv cs.CV 2014
Year: 2014

Nonnegative matrix factorization (NMF) with group sparsity constraints is formulated as a probabilistic graphical model and, assuming some observed data have been generated by the model, a feasible variational Bayesian algorithm is derived for learning model parameters. When used in a supervised learning scenario, NMF is most often utilized as an unsupervised feature extractor followed by classification in the obtained feature subspace. Having mapped the class labels to a more general concept of groups which underlie sparsity of the coefficients, what the proposed group sparse NMF model allows is incorporating class label information to find low dimensional label-driven dictionaries which not only aim to represent the data faithfully, but are also suitable for class discrimination. Experiments performed in face recognition and facial expression recognition domains point to advantages of classification in such label-driven feature subspaces over classification in feature subspaces obtained in an unsupervised manner.
Weakly Equivalent Arrays
Venue: arXiv cs.LO 2014
Year: 2014

The (extensional) theory of arrays is widely used to model systems. Hence, efficient decision procedures are needed to model check such systems. Current decision procedures for the theory of arrays saturate the read-over-write and extensionality axioms originally proposed by McCarthy. Various filters are used to limit the number of axiom instantiations while preserving completeness. We present an algorithm that lazily instantiates lemmas based on weak equivalence classes. These lemmas are easier to interpolate as they only contain existing terms. We formally define weak equivalence and show correctness of the resulting decision procedure.
Finding a closest point in a lattice of Voronoi's first kind
Venue: arXiv cs.IT 2014
Year: 2014

We show that for those lattices of Voronoi's first kind with known obtuse superbasis, a closest lattice point can be computed in $O(n^4)$ operations where $n$ is the dimension of the lattice. To achieve this a series of relevant lattice vectors that converges to a closest lattice point is found. We show that the series converges after at most $n$ terms. Each vector in the series can be efficiently computed in $O(n^3)$ operations using an algorithm to compute a minimum cut in an undirected flow network.