OpenRaiser/Intern-Atlas huggingface dataset:
Approximating the partition function of planar two-state spin systems
Venue: arXiv cs.CC 2014
Year: 2014

We consider the problem of approximating the partition function of the hard-core model on planar graphs of degree at most 4. We show that when the activity lambda is sufficiently large, there is no fully polynomial randomised approximation scheme for evaluating the partition function unless NP=RP. The result extends to a nearby region of the parameter space in a more general two-state spin system with three parameters. We also give a polynomial-time randomised approximation scheme for the logarithm of the partition function.
Sparse coding for multitask and transfer learning
Venue: arXiv cs.LG 2014
Year: 2014

We investigate the use of sparse coding and dictionary learning in the context of multitask and transfer learning. The central assumption of our learning method is that the tasks parameters are well approximated by sparse linear combinations of the atoms of a dictionary on a high or infinite dimensional space. This assumption, together with the large quantity of available data in the multitask and transfer learning settings, allows a principled choice of the dictionary. We provide bounds on the generalization error of this approach, for both settings. Numerical experiments on one synthetic and two real datasets show the advantage of our method over single task learning, a previous method based on orthogonal and dense representation of the tasks and a related method learning task grouping.
Agile Missile Controller Based on Adaptive Nonlinear Backstepping Control
Venue: arXiv cs.SY 2014
Year: 2014

This paper deals with a nonlinear adaptive autopilot design for agile missile systems. In advance of the autopilot design, an investigation of the agile turn maneuver, based on the trajectory optimization, is performed to determine state behaviors during the agile turn phase. This investigation shows that there exist highly nonlinear, rapidly changing dynamics and aerodynamic uncertainties. To handle of these difficulties, we propose a longitudinal autopilot for angle-of-attack tracking based on backstepping control methodology in conjunction with the time-delay adaptation scheme.
Lossy joint source-channel coding in the finite blocklength regime
Venue: arXiv cs.IT 2014
Year: 2014

This paper finds new tight finite-blocklength bounds for the best achievable lossy joint source-channel code rate, and demonstrates that joint source-channel code design brings considerable performance advantage over a separate one in the non-asymptotic regime. A joint source-channel code maps a block of $k$ source symbols onto a length$-n$ channel codeword, and the fidelity of reproduction at the receiver end is measured by the probability $ε$ that the distortion exceeds a given threshold $d$. For memoryless sources and channels, it is demonstrated that the parameters of the best joint source-channel code must satisfy $nC - kR(d) \approx \sqrt{nV + k \mathcal V(d)} Q(ε)$, where $C$ and $V$ are the channel capacity and channel dispersion, respectively; $R(d)$ and $\mathcal V(d)$ are the source rate-distortion and rate-dispersion functions; and $Q$ is the standard Gaussian complementary cdf. Symbol-by-symbol (uncoded) transmission is known to achieve the Shannon limit when the source and channel satisfy a certain probabilistic matching condition. In this paper we show that even when this condition is not satisfied, symbol-by-symbol transmission is, in some cases, the best known strategy in the non-asymptotic regime.
Data Processing Bounds for Scalar Lossy Source Codes with Side Information at the Decoder
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we introduce new lower bounds on the distortion of scalar fixed-rate codes for lossy compression with side information available at the receiver. These bounds are derived by presenting the relevant random variables as a Markov chain and applying generalized data processing inequalities a la Ziv and Zakai. We show that by replacing the logarithmic function with other functions, in the data processing theorem we formulate, we obtain new lower bounds on the distortion of scalar coding with side information at the decoder. The usefulness of these results is demonstrated for uniform sources and the convex function $Q(t)=t^{1-α}$, $α>1$. The bounds in this case are shown to be better than one can obtain from the Wyner-Ziv rate-distortion function.
Some Results On Point Visibility Graphs
Venue: arXiv cs.CG 2014
Year: 2014

In this paper, we present three necessary conditions for recognizing point visibility graphs. We show that this recognition problem lies in PSPACE. We state new properties of point visibility graphs along with some known properties that are important in understanding point visibility graphs. For planar point visibility graphs, we present a complete characterization which leads to a linear time recognition and reconstruction algorithm.
Active Learning for Crowd-Sourced Databases
Venue: arXiv cs.LG 2014
Year: 2014

Crowd-sourcing has become a popular means of acquiring labeled data for a wide variety of tasks where humans are more accurate than computers, e.g., labeling images, matching objects, or analyzing sentiment. However, relying solely on the crowd is often impractical even for data sets with thousands of items, due to time and cost constraints of acquiring human input (which cost pennies and minutes per label). In this paper, we propose algorithms for integrating machine learning into crowd-sourced databases, with the goal of allowing crowd-sourcing applications to scale, i.e., to handle larger datasets at lower costs. The key observation is that, in many of the above tasks, humans and machine learning algorithms can be complementary, as humans are often more accurate but slow and expensive, while algorithms are usually less accurate, but faster and cheaper. Based on this observation, we present two new active learning algorithms to combine humans and algorithms together in a crowd-sourced database. Our algorithms are based on the theory of non-parametric bootstrap, which makes our results applicable to a broad class of machine learning models. Our results, on three real-life datasets collected with Amazon's Mechanical Turk, and on 15 well-known UCI data sets, show that our methods on average ask humans to label one to two orders of magnitude fewer items to achieve the same accuracy as a baseline that labels random images, and two to eight times fewer questions than previous active learning schemes.
Tight Sufficient Conditions on Exact Sparsity Pattern Recovery
Venue: arXiv cs.IT 2014
Year: 2014

A noisy underdetermined system of linear equations is considered in which a sparse vector (a vector with a few nonzero elements) is subject to measurement. The measurement matrix elements are drawn from a Gaussian distribution. We study the information-theoretic constraints on exact support recovery of a sparse vector from the measurement vector and matrix. We compute a tight, sufficient condition that is applied to ergodic wide-sense stationary sparse vectors. We compare our results with the existing bounds and recovery conditions. Finally, we extend our results to approximately sparse signals.
Offering Supplementary Network Technologies: Adoption Behavior and Offloading Benefits
Venue: arXiv cs.NI 2014
Year: 2014

To alleviate the congestion caused by rapid growth in demand for mobile data, wireless service providers (WSPs) have begun encouraging users to offload some of their traffic onto supplementary network technologies, e.g., offloading from 3G or 4G to WiFi or femtocells. With the growing popularity of such offerings, a deeper understanding of the underlying economic principles and their impact on technology adoption is necessary. To this end, we develop a model for user adoption of a base technology (e.g., 3G) and a bundle of the base plus a supplementary technology (e.g., 3G + WiFi). Users individually make their adoption decisions based on several factors, including the technologies' intrinsic qualities, negative congestion externalities from other subscribers, and the flat access rates that a WSP charges. We then show how these user-level decisions translate into aggregate adoption dynamics and prove that these converge to a unique equilibrium for a given set of exogenously determined system parameters. We fully characterize these equilibria and study adoption behaviors of interest to a WSP. We then derive analytical expressions for the revenue-maximizing prices and optimal coverage factor for the supplementary technology and examine some resulting non-intuitive user adoption behaviors. Finally, we develop a mobile app to collect empirical 3G/WiFi usage data and numerically investigate the profit-maximizing adoption levels when a WSP accounts for its cost of deploying the supplemental technology and savings from offloading traffic onto this technology.
A New Continuous-Time Equality-Constrained Optimization Method to Avoid Singularity
Venue: arXiv cs.NE 2014
Year: 2014

In equality-constrained optimization, a standard regularity assumption is often associated with feasible point methods, namely the gradients of constraints are linearly independent. In practice, the regularity assumption may be violated. To avoid such a singularity, we propose a new projection matrix, based on which a feasible point method for the continuous-time, equality-constrained optimization problem is developed. First, the equality constraint is transformed into a continuous-time dynamical system with solutions that always satisfy the equality constraint. Then, the singularity is explained in detail and a new projection matrix is proposed to avoid singularity. An update (or say a controller) is subsequently designed to decrease the objective function along the solutions of the transformed system. The invariance principle is applied to analyze the behavior of the solution. We also propose a modified approach for addressing cases in which solutions do not satisfy the equality constraint. Finally, the proposed optimization approaches are applied to two examples to demonstrate its effectiveness.
Accelerating Iterative SpMV for Discrete Logarithm Problem Using GPUs
Venue: arXiv cs.CR 2014
Year: 2014

In the context of cryptanalysis, computing discrete logarithms in large cyclic groups using index-calculus-based methods, such as the number field sieve or the function field sieve, requires solving large sparse systems of linear equations modulo the group order. Most of the fast algorithms used to solve such systems --- e.g., the conjugate gradient or the Lanczos and Wiedemann algorithms --- iterate a product of the corresponding sparse matrix with a vector (SpMV). This central operation can be accelerated on GPUs using specific computing models and addressing patterns, which increase the arithmetic intensity while reducing irregular memory accesses. In this work, we investigate the implementation of SpMV kernels on NVIDIA GPUs, for several representations of the sparse matrix in memory. We explore the use of Residue Number System (RNS) arithmetic to accelerate modular operations. We target linear systems arising when attacking the discrete logarithm problem on groups of size 100 to 1000 bits, which includes the relevant range for current cryptanalytic computations. The proposed SpMV implementation contributed to solving the discrete logarithm problem in GF($2^{619}$) and GF($2^{809}$) using the FFS algorithm.
Approximate evaluation of marginal association probabilities with belief propagation
Venue: arXiv cs.AI 2014
Year: 2014

Data association, the problem of reasoning over correspondence between targets and measurements, is a fundamental problem in tracking. This paper presents a graphical model formulation of data association and applies an approximate inference method, belief propagation (BP), to obtain estimates of marginal association probabilities. We prove that BP is guaranteed to converge, and bound the number of iterations necessary. Experiments reveal a favourable comparison to prior methods in terms of accuracy and computational complexity.
Review of Statistical Shape Spaces for 3D Data with Comparative Analysis for Human Faces
Venue: arXiv cs.CV 2014
Year: 2014

With systems for acquiring 3D surface data being evermore commonplace, it has become important to reliably extract specific shapes from the acquired data. In the presence of noise and occlusions, this can be done through the use of statistical shape models, which are learned from databases of clean examples of the shape in question. In this paper, we review, analyze and compare different statistical models: from those that analyze the variation in geometry globally to those that analyze the variation in geometry locally. We first review how different types of models have been used in the literature, then proceed to define the models and analyze them theoretically, in terms of both their statistical and computational aspects. We then perform extensive experimental comparison on the task of model fitting, and give intuition about which type of model is better for a few applications. Due to the wide availability of databases of high-quality data, we use the human face as the specific shape we wish to extract from corrupted data.
Large-Scale Distributed Internet-based Discovery Mechanism for Dynamic Spectrum Allocation
Venue: arXiv cs.NI 2014
Year: 2014

Scarcity of frequencies and the demand for more bandwidth is likely to increase the need for devices that utilize the available frequencies more efficiently. Radios must be able to dynamically find other users of the frequency bands and adapt so that they are not interfered, even if they use different radio protocols. As transmitters far away may cause as much interference as a transmitter located nearby, this mechanism can not be based on location alone. Central databases can be used for this purpose, but require expensive infrastructure and planning to scale. In this paper, we propose a decentralized protocol and architecture for discovering radio devices over the Internet. The protocol has low resource requirements, making it suitable for implementation on limited platforms. We evaluate the protocol through simulation in network topologies with up to 2.3 million nodes, including topologies generated from population patterns in Norway. The protocol has also been implemented as proof-of-concept in real Wi-Fi routers.
The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial
Venue: arXiv cs.DS 2014
Year: 2014

Intersection graphs of geometric objects have been extensively studied, both due to their interesting structure and their numerous applications; prominent examples include interval graphs and permutation graphs. In this paper we study a natural graph class that generalizes both interval and permutation graphs, namely \emph{simple-triangle} graphs. Simple-triangle graphs - also known as \emph{PI} graphs (for Point-Interval) - are the intersection graphs of triangles that are defined by a point on a line $L_{1}$ and an interval on a parallel line $L_{2}$. They lie naturally between permutation and trapezoid graphs, which are the intersection graphs of line segments between $L_{1}$ and $L_{2}$ and of trapezoids between $L_{1}$ and $L_{2}$, respectively. Although various efficient recognition algorithms for permutation and trapezoid graphs are well known to exist, the recognition of simple-triangle graphs has remained an open problem since their introduction by Corneil and Kamula three decades ago. In this paper we resolve this problem by proving that simple-triangle graphs can be recognized in polynomial time. As a consequence, our algorithm also solves a longstanding open problem in the area of partial orders, namely the recognition of \emph{linear-interval orders}, i.e. of partial orders $P=P_{1}\cap P_{2}$, where $P_{1}$ is a linear order and $P_{2}$ is an interval order. This is one of the first results on recognizing partial orders $P$ that are the intersection of orders from two different classes $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$. In complete contrast to this, partial orders $P$ which are the intersection of orders from the same class $\mathcal{P}$ have been extensively investigated, and in most cases the complexity status of these recognition problems has been already established.
Approximating Source Location and Star Survivable Network Problems
Venue: arXiv cs.DS 2014
Year: 2014

In Source Location (SL) problems the goal is to select a mini-mum cost source set $S \subseteq V$ such that the connectivity (or flow) $ψ(S,v)$ from $S$ to any node $v$ is at least the demand $d_v$ of $v$. In many SL problems $ψ(S,v)=d_v$ if $v \in S$, namely, the demand of nodes selected to $S$ is completely satisfied. In a node-connectivity variant suggested recently by Fukunaga, every node $v$ gets a "bonus" $p_v \leq d_v$ if it is selected to $S$. Fukunaga showed that for undirected graphs one can achieve ratio $O(k \ln k)$ for his variant, where $k=\max_{v \in V}d_v$ is the maximum demand. We improve this by achieving ratio $\min\{p^*\lnk,k\}\cdot O(\ln (k/q^*))$ for a more general version with node capacities, where $p^*=\max_{v \in V} p_v$ is the maximum bonus and $q^*=\min_{v \in V} q_v$ is the minimum capacity. In particular, for the most natural case $p^*=1$ considered by Fukunaga, we improve the ratio from $O(k \ln k)$ to $O(\ln^2k)$. We also get ratio $O(k)$ for the edge-connectivity version, for which no ratio that depends on $k$ only was known before. To derive these results, we consider a particular case of the Survivable Network (SN) problem when all edges of positive cost form a star. We give ratio $O(\min\{\ln n,\ln^2 k\})$ for this variant, improving over the best ratio known for the general case $O(k^3 \ln n)$ of Chuzhoy and Khanna.
Diffusion of Lexical Change in Social Media
Venue: arXiv cs.CL 2014
Year: 2014

Computer-mediated communication is driving fundamental changes in the nature of written language. We investigate these changes by statistical analysis of a dataset comprising 107 million Twitter messages (authored by 2.7 million unique user accounts). Using a latent vector autoregressive model to aggregate across thousands of words, we identify high-level patterns in diffusion of linguistic change over the United States. Our model is robust to unpredictable changes in Twitter's sampling rate, and provides a probabilistic characterization of the relationship of macro-scale linguistic influence to a set of demographic and geographic predictors. The results of this analysis offer support for prior arguments that focus on geographical proximity and population size. However, demographic similarity -- especially with regard to race -- plays an even more central role, as cities with similar racial demographics are far more likely to share linguistic influence. Rather than moving towards a single unified "netspeak" dialect, language evolution in computer-mediated communication reproduces existing fault lines in spoken American English.
Image Encryption Using Fibonacci-Lucas Transformation
Venue: arXiv cs.CR 2014
Year: 2014

Secret communication techniques are of great demand since last 3000 years due to the need of information security and confidentiality at various levels of communication such as while communicating confidential personal data, medical data of patients, defence and intelligence information of countries, data related to examinations etc. With advancements in image processing research, Image encryption and Steganographic techniques have gained popularity over other forms of hidden communication techniques during the last few decades and a number of image encryption models are suggested by various researchers from time to time. In this paper, we are suggesting a new image encryption model based on Fibonacci and Lucas series.
Extending the Concept of Analog Butterworth Filter for Fractional Order Systems
Venue: arXiv cs.SY 2014
Year: 2014

This paper proposes the design of Fractional Order (FO) Butterworth filter in complex w-plane (w=sq; q being any real number) considering the presence of under-damped, hyper-damped, ultra-damped poles. This is the first attempt to design such fractional Butterworth filters in complex w-plane instead of complex s-plane, as conventionally done for integer order filters. Firstly, the concept of fractional derivatives and w-plane stability of linear fractional order systems are discussed. Detailed mathematical formulation for the design of fractional Butterworth-like filter (FBWF) in w-plane is then presented. Simulation examples are given along with a practical example to design the FO Butterworth filter with given specifications in frequency domain to show the practicability of the proposed formulation.
Attention Competition with Advertisement
Venue: arXiv cs.SI 2014
Year: 2014

In the new digital age, information is available in large quantities. Since information consumes primarily the attention of its recipients, the scarcity of attention is becoming the main limiting factor. In this study, we investigate the impact of advertisement pressure on a cultural market where consumers have a limited attention capacity. A model of competition for attention is developed and investigated analytically and by simulation. Advertisement is found to be much more effective when attention capacity of agents is extremely scarce. We have observed that the market share of the advertised item improves if dummy items are introduced to the market while the strength of the advertisement is kept constant.
New results on stabbing segments with a polygon
Venue: arXiv cs.CC 2014
Year: 2014

We consider a natural variation of the concept of stabbing a segment by a simple polygon: a segment is stabbed by a simple polygon $\mathcal{P}$ if at least one of its two endpoints is contained in $\mathcal{P}$. A segment set $S$ is stabbed by $\mathcal{P}$ if every segment of $S$ is stabbed by $\mathcal{P}$. We show that if $S$ is a set of pairwise disjoint segments, the problem of computing the minimum perimeter polygon stabbing $S$ can be solved in polynomial time. We also prove that for general segments the problem is NP-hard. Further, an adaptation of our polynomial-time algorithm solves an open problem posed by Löffler and van Kreveld [Algorithmica 56(2), 236--269 (2010)] about finding a maximum perimeter convex hull for a set of imprecise points modeled as line segments.
Measures of Entropy from Data Using Infinitely Divisible Kernels
Venue: arXiv cs.LG 2014
Year: 2014

Information theory provides principled ways to analyze different inference and learning problems such as hypothesis testing, clustering, dimensionality reduction, classification, among others. However, the use of information theoretic quantities as test statistics, that is, as quantities obtained from empirical data, poses a challenging estimation problem that often leads to strong simplifications such as Gaussian models, or the use of plug in density estimators that are restricted to certain representation of the data. In this paper, a framework to non-parametrically obtain measures of entropy directly from data using operators in reproducing kernel Hilbert spaces defined by infinitely divisible kernels is presented. The entropy functionals, which bear resemblance with quantum entropies, are defined on positive definite matrices and satisfy similar axioms to those of Renyi's definition of entropy. Convergence of the proposed estimators follows from concentration results on the difference between the ordered spectrum of the Gram matrices and the integral operators associated to the population quantities. In this way, capitalizing on both the axiomatic definition of entropy and on the representation power of positive definite kernels, the proposed measure of entropy avoids the estimation of the probability distribution underlying the data. Moreover, estimators of kernel-based conditional entropy and mutual information are also defined. Numerical experiments on independence tests compare favourably with state of the art.