OpenRaiser/Intern-Atlas huggingface dataset:
Subdivision into i-packings and S-packing chromatic number of some lattices
Venue: arXiv cs.DM 2015
Year: 2015

An $i$-packing in a graph $G$ is a set of vertices at pairwise distance greater than $i$. For a nondecreasing sequence of integers $S=(s\_{1},s\_{2},\ldots)$, the $S$-packing chromatic number of a graph $G$ is the least integer $k$ such that there exists a coloring of $G$ into $k$ colors where each set of vertices colored $i$, $i=1,\ldots, k$, is an $s\_i$-packing. This paper describes various subdivisions of an $i$-packing into $j$-packings ($j\textgreater{}i$) for the hexagonal, square and triangular lattices. These results allow us to bound the $S$-packing chromatic number for these graphs, with more precise bounds and exact values for sequences $S=(s\_{i}, i\in\mathbb{N}^{*})$, $s\_{i}=d+ \lfloor (i-1)/n \rfloor$.
Core-competitive Auctions
Venue: arXiv cs.GT 2015
Year: 2015

One of the major drawbacks of the celebrated VCG auction is its low (or zero) revenue even when the agents have high value for the goods and a {\em competitive} outcome could have generated a significant revenue. A competitive outcome is one for which it is impossible for the seller and a subset of buyers to `block' the auction by defecting and negotiating an outcome with higher payoffs for themselves. This corresponds to the well-known concept of {\em core} in cooperative game theory. In particular, VCG revenue is known to be not competitive when the goods being sold have complementarities. A bottleneck here is an impossibility result showing that there is no auction that simultaneously achieves competitive prices (a core outcome) and incentive-compatibility. In this paper we try to overcome the above impossibility result by asking the following natural question: is it possible to design an incentive-compatible auction whose revenue is comparable (even if less) to a competitive outcome? Towards this, we define a notion of {\em core-competitive} auctions. We say that an incentive-compatible auction is $α$-core-competitive if its revenue is at least $1/α$ fraction of the minimum revenue of a core-outcome. We study the Text-and-Image setting. In this setting, there is an ad slot which can be filled with either a single image ad or $k$ text ads. We design an $O(\ln \ln k)$ core-competitive randomized auction and an $O(\sqrt{\ln(k)})$ competitive deterministic auction for the Text-and-Image setting. We also show that both factors are tight.
Word-level Symbolic Trajectory Evaluation
Venue: arXiv cs.LO 2015
Year: 2015

Symbolic trajectory evaluation (STE) is a model checking technique that has been successfully used to verify industrial designs. Existing implementations of STE, however, reason at the level of bits, allowing signals to take values in {0, 1, X}. This limits the amount of abstraction that can be achieved, and presents inherent limitations to scaling. The main contribution of this paper is to show how much more abstract lattices can be derived automatically from RTL descriptions, and how a model checker for the general theory of STE instantiated with such abstract lattices can be implemented in practice. This gives us the first practical word-level STE engine, called STEWord. Experiments on a set of designs similar to those used in industry show that STEWord scales better than word-level BMC and also bit-level STE.
Geometry of Graph Edit Distance Spaces
Venue: arXiv cs.CV 2015
Year: 2015

In this paper we study the geometry of graph spaces endowed with a special class of graph edit distances. The focus is on geometrical results useful for statistical pattern recognition. The main result is the Graph Representation Theorem. It states that a graph is a point in some geometrical space, called orbit space. Orbit spaces are well investigated and easier to explore than the original graph space. We derive a number of geometrical results from the orbit space representation, translate them to the graph space, and indicate their significance and usefulness in statistical pattern recognition.
CURL: Co-trained Unsupervised Representation Learning for Image Classification
Venue: arXiv cs.LG 2015
Year: 2015

In this paper we propose a strategy for semi-supervised image classification that leverages unsupervised representation learning and co-training. The strategy, that is called CURL from Co-trained Unsupervised Representation Learning, iteratively builds two classifiers on two different views of the data. The two views correspond to different representations learned from both labeled and unlabeled data and differ in the fusion scheme used to combine the image features. To assess the performance of our proposal, we conducted several experiments on widely used data sets for scene and object recognition. We considered three scenarios (inductive, transductive and self-taught learning) that differ in the strategy followed to exploit the unlabeled data. As image features we considered a combination of GIST, PHOG, and LBP as well as features extracted from a Convolutional Neural Network. Moreover, two embodiments of CURL are investigated: one using Ensemble Projection as unsupervised representation learning coupled with Logistic Regression, and one based on LapSVM. The results show that CURL clearly outperforms other supervised and semi-supervised learning methods in the state of the art.
Improving Time Estimation by Blind Deconvolution: with Applications to TOFD and Backscatter Sizing
Venue: arXiv cs.OH 2015
Year: 2015

In this paper we present a blind deconvolution scheme based on statistical wavelet estimation. We assume no prior knowledge of the wavelet, and do not select a reflector from the signal. Instead, the wavelet (ultrasound pulse) is statistically estimated from the signal itself by a kurtosis-based metric. This wavelet is then used to deconvolve the RF (radiofrequency) signal through Wiener filtering, and the resultant zero phase trace is subjected to spectral broadening by Autoregressive Spectral Extrapolation (ASE). These steps increase the time resolution of diffraction techniques. Results on synthetic and real cases show the robustness of the proposed method.
Feature Representation for Online Signature Verification
Venue: arXiv cs.CV 2015
Year: 2015

Biometrics systems have been used in a wide range of applications and have improved people authentication. Signature verification is one of the most common biometric methods with techniques that employ various specifications of a signature. Recently, deep learning has achieved great success in many fields, such as image, sounds and text processing. In this paper, deep learning method has been used for feature extraction and feature selection.
Performance Evaluation and Optimization of Math-Similarity Search
Venue: arXiv cs.IR 2015
Year: 2015

Similarity search in math is to find mathematical expressions that are similar to a user's query. We conceptualized the similarity factors between mathematical expressions, and proposed an approach to math similarity search (MSS) by defining metrics based on those similarity factors [11]. Our preliminary implementation indicated the advantage of MSS compared to non-similarity based search. In order to more effectively and efficiently search similar math expressions, MSS is further optimized. This paper focuses on performance evaluation and optimization of MSS. Our results show that the proposed optimization process significantly improved the performance of MSS with respect to both relevance ranking and recall.
A complexity dichotomy for the dominating set problem
Venue: arXiv cs.DM 2015
Year: 2015

We completely determine the complexity status of the dominating set problem for hereditary graph classes defined by forbidden induced subgraphs with at most five vertices.
Privacy for the Protected (Only)
Venue: arXiv cs.DS 2015
Year: 2015

Motivated by tensions between data privacy for individual citizens, and societal priorities such as counterterrorism and the containment of infectious disease, we introduce a computational model that distinguishes between parties for whom privacy is explicitly protected, and those for whom it is not (the targeted subpopulation). The goal is the development of algorithms that can effectively identify and take action upon members of the targeted subpopulation in a way that minimally compromises the privacy of the protected, while simultaneously limiting the expense of distinguishing members of the two groups via costly mechanisms such as surveillance, background checks, or medical testing. Within this framework, we provide provably privacy-preserving algorithms for targeted search in social networks. These algorithms are natural variants of common graph search methods, and ensure privacy for the protected by the careful injection of noise in the prioritization of potential targets. We validate the utility of our algorithms with extensive computational experiments on two large-scale social network datasets.
Signaling Design of Two-Way MIMO Full-Duplex Channel: Optimality Under Imperfect Transmit Front-End Chain
Venue: arXiv cs.IT 2015
Year: 2015

We derive the optimal signaling for a multiple input multiple output (MIMO) full-duplex two-way channel under the imperfect transmit front-end chain. We characterize the two-way rates of the channel by using a game-theoretical approach, where we focus on the Pareto boundary of the achievable rate region and Nash equilibia (NE). For a MISO full-duplex two-way channel, we prove that beamforming is an optimal transmission strategy which can achieve any point on the Pareto boundary. Furthermore, we present a closed-form expression for the optimal beamforming weights. In our numerical examples we quantify gains in the achievable rates of the proposed beamforming over the zero-forcing beamforming. For a general MIMO full-duplex channel, we establish the existence of NE and present a condition for the uniqueness of NE. We then propose an iterative water-filling algorithm which is capable of reaching NE. Through simulations the threshold of the self-interference level is found, below which the full-duplex NE outperforms the half-duplex TDMA.
RBIR using Interest Regions and Binary Signatures
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we introduce an approach to overcome the low accuracy of the Content-Based Image Retrieval (CBIR) (when using the global features). To increase the accuracy, we use Harris-Laplace detector to identify the interest regions of image. Then, we build the Region-Based Image Retrieval (RBIR). For the efficient image storage and retrieval, we encode images into binary signatures. The binary signature of a image is created from its interest regions. Furthermore, this paper also provides an algorithm for image retrieval on S-tree by comparing the images' signatures on a metric similarly to EMD (earth mover's distance). Finally, we evaluate the created models on COREL's images.
Hierarchical structure-and-motion recovery from uncalibrated images
Venue: arXiv cs.CV 2015
Year: 2015

This paper addresses the structure-and-motion problem, that requires to find camera motion and 3D struc- ture from point matches. A new pipeline, dubbed Samantha, is presented, that departs from the prevailing sequential paradigm and embraces instead a hierarchical approach. This method has several advantages, like a provably lower computational complexity, which is necessary to achieve true scalability, and better error containment, leading to more stability and less drift. Moreover, a practical autocalibration procedure allows to process images without ancillary information. Experiments with real data assess the accuracy and the computational efficiency of the method.
Robust Face Recognition with Structural Binary Gradient Patterns
Venue: arXiv cs.CV 2015
Year: 2015

This paper presents a computationally efficient yet powerful binary framework for robust facial representation based on image gradients. It is termed as structural binary gradient patterns (SBGP). To discover underlying local structures in the gradient domain, we compute image gradients from multiple directions and simplify them into a set of binary strings. The SBGP is derived from certain types of these binary strings that have meaningful local structures and are capable of resembling fundamental textural information. They detect micro orientational edges and possess strong orientation and locality capabilities, thus enabling great discrimination. The SBGP also benefits from the advantages of the gradient domain and exhibits profound robustness against illumination variations. The binary strategy realized by pixel correlations in a small neighborhood substantially simplifies the computational complexity and achieves extremely efficient processing with only 0.0032s in Matlab for a typical face image. Furthermore, the discrimination power of the SBGP can be enhanced on a set of defined orientational image gradient magnitudes, further enforcing locality and orientation. Results of extensive experiments on various benchmark databases illustrate significant improvements of the SBGP based representations over the existing state-of-the-art local descriptors in the terms of discrimination, robustness and complexity. Codes for the SBGP methods will be available at http://www.eee.manchester.ac.uk/research/groups/sisp/software/.
Optimal Communication of States of Dynamical Systems over Gaussian Channels with Noisy Feedback: The Scalar Case
Venue: arXiv cs.IT 2015
Year: 2015

We consider the problem of communicating the state of a dynamical system via a Shannon Gaussian channel. The receiver, which acts as both a decoder and estimator, observes the noisy measurement of the channel output and makes an optimal estimate of the state of the dynamical system in the minimum mean square sense. Noisy feedback from the receiver to the transmitter is present. The transmitter observes the noise-corrupted feedback message from the receiver together with a possibly noisy measurement of the state the dynamical system. These measurements are then used to encode the message to be transmitted over a noisy Gaussian channel, where a per symbol power constraint is imposed on the transmitted message. Thus, we get a mixed problem of Shannon's source-channel coding problem and a sort of Kalman filtering problem. In particular, we consider two feedback instances, one being feedback of receiver measurements and the second being the receiver's state estimates. We show that optimal encoders and decoders are linear filters with a finite memory and we give explicitly the state space realizations of the optimal filters. For the case where the transmitter has access to noisy measurements of the state, we derive a separation principle for the optimal communication scheme. Furthermore, we investigate the presence of noiseless feedback or no feedback from the receiver to the transmitter. Necessary and sufficient conditions for the existence of a stationary solution are also given for the feedback cases considered.
User Preferences Modeling and Learning for Pleasing Photo Collage Generation
Venue: arXiv cs.MM 2015
Year: 2015

In this paper we consider how to automatically create pleasing photo collages created by placing a set of images on a limited canvas area. The task is formulated as an optimization problem. Differently from existing state-of-the-art approaches, we here exploit subjective experiments to model and learn pleasantness from user preferences. To this end, we design an experimental framework for the identification of the criteria that need to be taken into account to generate a pleasing photo collage. Five different thematic photo datasets are used to create collages using state-of-the-art criteria. A first subjective experiment where several subjects evaluated the collages, emphasizes that different criteria are involved in the subjective definition of pleasantness. We then identify new global and local criteria and design algorithms to quantify them. The relative importance of these criteria are automatically learned by exploiting the user preferences, and new collages are generated. To validate our framework, we performed several psycho-visual experiments involving different users. The results shows that the proposed framework allows to learn a novel computational model which effectively encodes an inter-user definition of pleasantness. The learned definition of pleasantness generalizes well to new photo datasets of different themes and sizes not used in the learning. Moreover, compared with two state of the art approaches, the collages created using our framework are preferred by the majority of the users.
On Quantum Generalizations of Information-Theoretic Measures and their Contribution to Distributional Semantics
Venue: arXiv cs.IT 2015
Year: 2015

Information-theoretic measures such as relative entropy and correlation are extremely useful when modeling or analyzing the interaction of probabilistic systems. We survey the quantum generalization of 5 such measures and point out some of their commonalities and interpretations. In particular we find the application of information theory to distributional semantics useful. By modeling the distributional meaning of words as density operators rather than vectors, more of their semantic structure may be exploited. Furthermore, properties of and interactions between words such as ambiguity, similarity and entailment can be simulated more richly and intuitively when using methods from quantum information theory.
Sample-Optimal Density Estimation in Nearly-Linear Time
Venue: arXiv cs.DS 2015
Year: 2015

We design a new, fast algorithm for agnostically learning univariate probability distributions whose densities are well approximated by piecewise polynomial functions. Let $f$ be the density function of an arbitrary univariate distribution, and suppose that $f$ is $\mathrm{OPT}$-close in $L_1$-distance to an unknown piecewise polynomial function with $t$ interval pieces and degree $d$. Our algorithm draws $n = O(t(d+1)/ε^2)$ samples from $f$, runs in time $\tilde{O}(n \cdot \mathrm{poly}(d))$, and with probability at least $9/10$ outputs an $O(t)$-piecewise degree-$d$ hypothesis $h$ that is $4 \cdot \mathrm{OPT} +ε$ close to $f$. Our general algorithm yields (nearly) sample-optimal and nearly-linear time estimators for a wide range of structured distribution families over both continuous and discrete domains in a unified way. For most of our applications, these are the first sample-optimal and nearly-linear time estimators in the literature. As a consequence, our work resolves the sample and computational complexities of a broad class of inference tasks via a single "meta-algorithm". Moreover, we experimentally demonstrate that our algorithm performs very well in practice. Our algorithm consists of three "levels": (i) At the top level, we employ an iterative greedy algorithm for finding a good partition of the real line into the pieces of a piecewise polynomial. (ii) For each piece, we show that the sub-problem of finding a good polynomial fit on the current interval can be solved efficiently with a separation oracle method. (iii) We reduce the task of finding a separating hyperplane to a combinatorial problem and give an efficient algorithm for this problem. Combining these three procedures gives a density estimation algorithm with the claimed guarantees.
Large-Scale Convex Optimization for Dense Wireless Cooperative Networks
Venue: arXiv cs.IT 2015
Year: 2015

Convex optimization is a powerful tool for resource allocation and signal processing in wireless networks. As the network density is expected to drastically increase in order to accommodate the exponentially growing mobile data traffic, performance optimization problems are entering a new era characterized by a high dimension and/or a large number of constraints, which poses significant design and computational challenges. In this paper, we present a novel two-stage approach to solve large-scale convex optimization problems for dense wireless cooperative networks, which can effectively detect infeasibility and enjoy modeling flexibility. In the proposed approach, the original large-scale convex problem is transformed into a standard cone programming form in the first stage via matrix stuffing, which only needs to copy the problem parameters such as channel state information (CSI) and quality-of-service (QoS) requirements to the pre-stored structure of the standard form. The capability of yielding infeasibility certificates and enabling parallel computing is achieved by solving the homogeneous self-dual embedding of the primal-dual pair of the standard form. In the solving stage, the operator splitting method, namely, the alternating direction method of multipliers (ADMM), is adopted to solve the large-scale homogeneous self-dual embedding. Compared with second-order methods, ADMM can solve large-scale problems in parallel with modest accuracy within a reasonable amount of time. Simulation results will demonstrate the speedup, scalability, and reliability of the proposed framework compared with the state-of-the-art modeling frameworks and solvers.
Distributed Massive MIMO in Cellular Networks: Impact of Imperfect Hardware and Number of Oscillators
Venue: arXiv cs.IT 2015
Year: 2015

Distributed massive multiple-input multiple-output (MIMO) combines the array gain of coherent MIMO processing with the proximity gains of distributed antenna setups. In this paper, we analyze how transceiver hardware impairments affect the downlink with maximum ratio transmission. We derive closed-form spectral efficiencies expressions and study their asymptotic behavior as the number of the antennas increases. We prove a scaling law on the hardware quality, which reveals that massive MIMO is resilient to additive distortions, while multiplicative phase noise is a limiting factor. It is also better to have separate oscillators at each antenna than one per BS.
Quizz: Targeted crowdsourcing with a billion (potential) users
Venue: arXiv cs.AI 2015
Year: 2015

We describe Quizz, a gamified crowdsourcing system that simultaneously assesses the knowledge of users and acquires new knowledge from them. Quizz operates by asking users to complete short quizzes on specific topics; as a user answers the quiz questions, Quizz estimates the user's competence. To acquire new knowledge, Quizz also incorporates questions for which we do not have a known answer; the answers given by competent users provide useful signals for selecting the correct answers for these questions. Quizz actively tries to identify knowledgeable users on the Internet by running advertising campaigns, effectively leveraging the targeting capabilities of existing, publicly available, ad placement services. Quizz quantifies the contributions of the users using information theory and sends feedback to the advertisingsystem about each user. The feedback allows the ad targeting mechanism to further optimize ad placement. Our experiments, which involve over ten thousand users, confirm that we can crowdsource knowledge curation for niche and specialized topics, as the advertising network can automatically identify users with the desired expertise and interest in the given topic. We present controlled experiments that examine the effect of various incentive mechanisms, highlighting the need for having short-term rewards as goals, which incentivize the users to contribute. Finally, our cost-quality analysis indicates that the cost of our approach is below that of hiring workers through paid-crowdsourcing platforms, while offering the additional advantage of giving access to billions of potential users all over the planet, and being able to reach users with specialized expertise that is not typically available through existing labor marketplaces.