OpenRaiser/Intern-Atlas huggingface dataset:
Sparse Fast Fourier Transform for Exactly and Generally K-Sparse Signals by Downsampling and Sparse Recovery
Venue: arXiv cs.DS 2015
Year: 2015

Fast Fourier Transform (FFT) is one of the most important tools in digital signal processing. FFT costs O(N \log N) for transforming a signal of length N. Recently, Sparse Fourier Transform (SFT) has emerged as a critical issue addressing how to compute a compressed Fourier transform of a signal with complexity being related to the sparsity of its spectrum. In this paper, a new SFT algorithm is proposed for both exactly K-sparse signals (with K non-zero frequencies) and generally K-sparse signals (with K significant frequencies), with the assumption that the distribution of the non-zero frequencies is uniform. The nuclear idea is to downsample the input signal at the beginning; then, subsequent processing operates under downsampled signals, where signal lengths are proportional to O(K). Downsampling, however, possibly leads to "aliasing." By the shift property of DFT, we recast the aliasing problem as complex Bose-Chaudhuri-Hocquenghem (BCH) codes solved by syndrome decoding. The proposed SFT algorithm for exactly K-sparse signals recovers 1-τfrequencies with computational complexity O(K \log K) and probability at least 1-O(\frac{c}τ)^{τK} under K=O(N), where c is a user-controlled parameter. For generally K-sparse signals, due to the fact that BCH codes are sensitive to noise, we combine a part of syndrome decoding with a compressive sensing-based solver for obtaining $K$ significant frequencies. The computational complexity of our algorithm is \max \left( O(K \log K), O(N) \right), where the Big-O constant of O(N) is very small and only a simple operation involves O(N). Our simulations reveal that O(N) does not dominate the computational cost of sFFT-DT.
A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries
Venue: arXiv cs.CC 2015
Year: 2015

Conjunctive queries are basic and heavily studied database queries; in relational algebra, they are the select-project-join queries. In this article, we study the fundamental problem of counting, given a conjunctive query and a relational database, the number of answers to the query on the database. In particular, we study the complexity of this problem relative to sets of conjunctive queries. We present a trichotomy theorem, which shows essentially that this problem on a set of conjunctive queries is either tractable, equivalent to the parameterized CLIQUE problem, or as hard as the parameterized counting CLIQUE problem; the criteria describing which of these situations occurs is simply stated, in terms of graph-theoretic conditions.
A Fast and Accurate Unconstrained Face Detector
Venue: arXiv cs.CV 2015
Year: 2015

We propose a method to address challenges in unconstrained face detection, such as arbitrary pose variations and occlusions. First, a new image feature called Normalized Pixel Difference (NPD) is proposed. NPD feature is computed as the difference to sum ratio between two pixel values, inspired by the Weber Fraction in experimental psychology. The new feature is scale invariant, bounded, and is able to reconstruct the original image. Second, we propose a deep quadratic tree to learn the optimal subset of NPD features and their combinations, so that complex face manifolds can be partitioned by the learned rules. This way, only a single soft-cascade classifier is needed to handle unconstrained face detection. Furthermore, we show that the NPD features can be efficiently obtained from a look up table, and the detection template can be easily scaled, making the proposed face detector very fast. Experimental results on three public face datasets (FDDB, GENKI, and CMU-MIT) show that the proposed method achieves state-of-the-art performance in detecting unconstrained faces with arbitrary pose variations and occlusions in cluttered scenes.
Differential Game Logic
Venue: arXiv cs.LO 2015
Year: 2015

Differential game logic (dGL) is a logic for specifying and verifying properties of hybrid games, i.e. games that combine discrete, continuous, and adversarial dynamics. Unlike hybrid systems, hybrid games allow choices in the system dynamics to be resolved adversarially by different players with different objectives. The logic dGL can be used to study the existence of winning strategies for such hybrid games, i.e. ways of resolving the player's choices in some way so that he wins by achieving his objective for all choices of the opponent. Hybrid games are determined, i.e. from each state, one player has a winning strategy, yet computing their winning regions may take transfinitely many steps. The logic dGL, nevertheless, has a sound and complete axiomatization relative to any expressive logic. Separating axioms are identified that distinguish hybrid games from hybrid systems. Finally, dGL is proved to be strictly more expressive than the corresponding logic of hybrid systems by characterizing the expressiveness of both.
Massive MIMO for Wireless Sensing with a Coherent Multiple Access Channel
Venue: arXiv cs.IT 2015
Year: 2015

We consider the detection and estimation of a zero-mean Gaussian signal in a wireless sensor network with a coherent multiple access channel, when the fusion center (FC) is configured with a large number of antennas and the wireless channels between the sensor nodes and FC experience Rayleigh fading. For the detection problem, we study the Neyman-Pearson (NP) Detector and Energy Detector (ED), and find optimal values for the sensor transmission gains. For the NP detector which requires channel state information (CSI), we show that detection performance remains asymptotically constant with the number of FC antennas if the sensor transmit power decreases proportionally with the increase in the number of antennas. Performance bounds show that the benefit of multiple antennas at the FC disappears as the transmit power grows. The results of the NP detector are also generalized to the linear minimum mean squared error estimator. For the ED which does not require CSI, we derive optimal gains that maximize the deflection coefficient of the detector, and we show that a constant deflection can be asymptotically achieved if the sensor transmit power scales as the inverse square root of the number of FC antennas. Unlike the NP detector, for high sensor power the multi-antenna ED is observed to empirically have significantly better performance than the single-antenna implementation. A number of simulation results are included to validate the analysis.
Digital Filter Designs for Recursive Frequency Analysis
Venue: arXiv cs.SY 2015
Year: 2015

Digital filters for recursively computing the discrete Fourier transform (DFT) and estimating the frequency spectrum of sampled signals are examined, with an emphasis on magnitude-response and numerical stability. In this tutorial-style treatment, existing recursive techniques are reviewed, explained and compared within a coherent framework; some fresh insights are provided and new enhancements/modifications are proposed. It is shown that the replacement of resonators by (non-recursive) modulators in sliding DFT (SDFT) analyzers with either a finite impulse response (FIR), or an infinite impulse response (IIR), does improve performance somewhat; however stability is not guaranteed, as the cancellation of marginally stable poles by zeros is still involved. The FIR deadbeat observer is shown to be more reliable than the SDFT methods, an IIR variant is presented, and ways of fine-tuning its response are discussed. A novel technique for stabilizing IIR SDFT analyzers with a fading memory, so that all poles are inside the unit circle, is also derived. Slepian and sum-of-cosine windows are adapted to improve the frequency responses for the various FIR and IIR DFT methods.
Experimental Evaluation of Multi-Round Matrix Multiplication on MapReduce
Venue: arXiv cs.DC 2015
Year: 2015

A common approach in the design of MapReduce algorithms is to minimize the number of rounds. Indeed, there are many examples in the literature of monolithic MapReduce algorithms, which are algorithms requiring just one or two rounds. However, we claim that the design of monolithic algorithms may not be the best approach in cloud systems. Indeed, multi-round algorithms may exploit some features of cloud platforms by suitably setting the round number according to the execution context. In this paper we carry out an experimental study of multi-round MapReduce algorithms aiming at investigating the performance of the multi-round approach. We use matrix multiplication as a case study. We first propose a scalable Hadoop library, named M$_3$, for matrix multiplication in the dense and sparse cases which allows to tradeoff round number with the amount of data shuffled in each round and the amount of memory required by reduce functions. Then, we present an extensive study of this library on an in-house cluster and on Amazon Web Services aiming at showing its performance and at comparing monolithic and multi-round approaches. The experiments show that, even without a low level optimization, it is possible to design multi-round algorithms with a small running time overhead.
Stochastic Throughput Optimization for Two-hop Systems with Finite Relay Buffers
Venue: arXiv cs.IT 2015
Year: 2015

Optimal queueing control of multi-hop networks remains a challenging problem even in the simplest scenarios. In this paper, we consider a two-hop half-duplex relaying system with random channel connectivity. The relay is equipped with a finite buffer. We focus on stochastic link selection and transmission rate control to maximize the average system throughput subject to a half-duplex constraint. We formulate this stochastic optimization problem as an infinite horizon average cost Markov decision process (MDP), which is well-known to be a difficult problem. By using sample-path analysis and exploiting the specific problem structure, we first obtain an \emph{equivalent Bellman equation} with reduced state and action spaces. By using \emph{relative value iteration algorithm}, we analyze the properties of the value function of the MDP. Then, we show that the optimal policy has a threshold-based structure by characterizing the \emph{supermodularity} in the optimal control. Based on the threshold-based structure and Markov chain theory, we further simplify the original complex stochastic optimization problem to a static optimization problem over a small discrete feasible set and propose a low-complexity algorithm to solve the simplified static optimization problem by making use of its special structure. Furthermore, we obtain the closed-form optimal threshold for the symmetric case. The analytical results obtained in this paper also provide design insights for two-hop relaying systems with multiple relays equipped with finite relay buffers.
A New Approach to Customization of Collision Warning Systems to Individual Drivers
Venue: arXiv cs.OH 2015
Year: 2015

This paper discusses the need for individualizing safety systems and proposes an approach including the Real-Time estimation of the distribution of brake response times for an individual driver. While maintaining high level of safety, the collision warning system should send "tailored" responses to the driver. This method could be the first step to show that safety applications would potentially benefit from customizing to individual drivers' characteristics using VANET. Our simulation results show that, as one of the imminent and preliminary outcomes of the new improved system, the number of false alarms will be reduced by more than 40%. We think this tactic can reach to even beyond the safety applications for designing the future innovative systems.
Bi-l0-l2-Norm Regularization for Blind Motion Deblurring
Venue: arXiv cs.CV 2015
Year: 2015

In blind motion deblurring, leading methods today tend towards highly non-convex approximations of the l0-norm, especially in the image regularization term. In this paper, we propose a simple, effective and fast approach for the estimation of the motion blur-kernel, through a bi-l0-l2-norm regularization imposed on both the intermediate sharp image and the blur-kernel. Compared with existing methods, the proposed regularization is shown to be more effective and robust, leading to a more accurate motion blur-kernel and a better final restored image. A fast numerical scheme is deployed for alternatingly computing the sharp image and the blur-kernel, by coupling the operator splitting and augmented Lagrangian methods. Experimental results on both a benchmark image dataset and real-world motion blurred images show that the proposed approach is highly competitive with state-of-the- art methods in both deblurring effectiveness and computational efficiency.
Solving Hard Control Problems in Voting Systems via Integer Programming
Venue: arXiv cs.GT 2015
Year: 2015

Voting problems are central in the area of social choice. In this article, we investigate various voting systems and types of control of elections. We present integer linear programming (ILP) formulations for a wide range of NP-hard control problems. Our ILP formulations are flexible in the sense that they can work with an arbitrary number of candidates and voters. Using the off-the-shelf solver Cplex, we show that our approaches can manipulate elections with a large number of voters and candidates efficiently.
Large Scale Purchase Prediction with Historical User Actions on B2C Online Retail Platform
Venue: arXiv cs.LG 2015
Year: 2015

This paper describes the solution of Bazinga Team for Tmall Recommendation Prize 2014. With real-world user action data provided by Tmall, one of the largest B2C online retail platforms in China, this competition requires to predict future user purchases on Tmall website. Predictions are judged on F1Score, which considers both precision and recall for fair evaluation. The data set provided by Tmall contains more than half billion action records from over ten million distinct users. Such massive data volume poses a big challenge, and drives competitors to write every single program in MapReduce fashion and run it on distributed cluster. We model the purchase prediction problem as standard machine learning problem, and mainly employ regression and classification methods as single models. Individual models are then aggregated in a two-stage approach, using linear regression for blending, and finally a linear ensemble of blended models. The competition is approaching the end but still in running during writing this paper. In the end, our team achieves F1Score 6.11 and ranks 7th (out of 7,276 teams in total).
Bearing Rigidity and Almost Global Bearing-Only Formation Stabilization
Venue: arXiv cs.SY 2015
Year: 2015

A fundamental problem that the bearing rigidity theory studies is to determine when a framework can be uniquely determined up to a translation and a scaling factor by its inter-neighbor bearings. While many previous works focused on the bearing rigidity of two-dimensional frameworks, a first contribution of this paper is to extend these results to arbitrary dimensions. It is shown that a framework in an arbitrary dimension can be uniquely determined up to a translation and a scaling factor by the bearings if and only if the framework is infinitesimally bearing rigid. In this paper, the proposed bearing rigidity theory is further applied to the bearing-only formation stabilization problem where the target formation is defined by inter-neighbor bearings and the feedback control uses only bearing measurements. Nonlinear distributed bearing-only formation control laws are proposed for the cases with and without a global orientation. It is proved that the control laws can almost globally stabilize infinitesimally bearing rigid formations. Numerical simulations are provided to support the analysis.
Equilibrium States in Numerical Argumentation Networks
Venue: arXiv cs.AI 2015
Year: 2015

Given an argumentation network with initial values to the arguments, we look for algorithms which can yield extensions compatible with such initial values. We find that the best way of tackling this problem is to offer an iteration formula that takes the initial values and the attack relation and iterates a sequence of intermediate values that eventually converges leading to an extension. The properties surrounding the application of the iteration formula and its connection with other numerical and non-numerical techniques proposed by others are thoroughly investigated in this paper.
Energy-Aware Competitive Power Allocation for Heterogeneous Networks Under QoS Constraints
Venue: arXiv cs.IT 2015
Year: 2015

This work proposes a distributed power allocation scheme for maximizing energy efficiency in the uplink of orthogonal frequency-division multiple access (OFDMA)-based heterogeneous networks (HetNets). The user equipment (UEs) in the network are modeled as rational agents that engage in a non-cooperative game where each UE allocates its available transmit power over the set of assigned subcarriers so as to maximize its individual utility (defined as the user's throughput per Watt of transmit power) subject to minimum-rate constraints. In this framework, the relevant solution concept is that of Debreu equilibrium, a generalization of Nash equilibrium which accounts for the case where an agent's set of possible actions depends on the actions of its opponents. Since the problem at hand might not be feasible, Debreu equilibria do not always exist. However, using techniques from fractional programming, we provide a characterization of equilibrial power allocation profiles when they do exist. In particular, Debreu equilibria are found to be the fixed points of a water-filling best response operator whose water level is a function of minimum rate constraints and circuit power. Moreover, we also describe a set of sufficient conditions for the existence and uniqueness of Debreu equilibria exploiting the contraction properties of the best response operator. This analysis provides the necessary tools to derive a power allocation scheme that steers the network to equilibrium in an iterative and distributed manner without the need for any centralized processing. Numerical simulations are then used to validate the analysis and assess the performance of the proposed algorithm as a function of the system parameters.
Show Me the Money: Dynamic Recommendations for Revenue Maximization
Venue: arXiv cs.DB 2015
Year: 2015

Recommender Systems (RS) play a vital role in applications such as e-commerce and on-demand content streaming. Research on RS has mainly focused on the customer perspective, i.e., accurate prediction of user preferences and maximization of user utilities. As a result, most existing techniques are not explicitly built for revenue maximization, the primary business goal of enterprises. In this work, we explore and exploit a novel connection between RS and the profitability of a business. As recommendations can be seen as an information channel between a business and its customers, it is interesting and important to investigate how to make strategic dynamic recommendations leading to maximum possible revenue. To this end, we propose a novel \model that takes into account a variety of factors including prices, valuations, saturation effects, and competition amongst products. Under this model, we study the problem of finding revenue-maximizing recommendation strategies over a finite time horizon. We show that this problem is NP-hard, but approximation guarantees can be obtained for a slightly relaxed version, by establishing an elegant connection to matroid theory. Given the prohibitively high complexity of the approximation algorithm, we also design intelligent heuristics for the original problem. Finally, we conduct extensive experiments on two real and synthetic datasets and demonstrate the efficiency, scalability, and effectiveness our algorithms, and that they significantly outperform several intuitive baselines.
Resource Allocation for Outdoor-to-Indoor Multicarrier Transmission with Shared UE-side Distributed Antenna Systems
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we study the resource allocation algorithm design for downlink multicarrier transmission with a shared user equipment (UE)-side distributed antenna system (SUDAS) which utilizes both licensed and unlicensed frequency bands for improving the system throughput. The joint UE selection and transceiver processing matrix design is formulated as a non-convex optimization problem for the maximization of the end-to-end system throughput (bits/s). In order to obtain a tractable resource allocation algorithm, we first show that the optimal transmitter precoding and receiver post-processing matrices jointly diagonalize the end-to-end communication channel. Subsequently, the optimization problem is converted to a scalar optimization problem for multiple parallel channels, which is solved by using an asymptotically optimal iterative algorithm. Simulation results illustrate that the proposed resource allocation algorithm for the SUDAS achieves an excellent system performance and provides a spatial multiplexing gain for single-antenna UEs.
Abelian networks II. Halting on all inputs
Venue: arXiv cs.FL 2015
Year: 2015

Abelian networks are systems of communicating automata satisfying a local commutativity condition. We show that a finite irreducible abelian network halts on all inputs if and only if all eigenvalues of its production matrix lie in the open unit disk.
A lattice framework for pricing display advertisement options with the stochastic volatility underlying model
Venue: arXiv cs.GT 2015
Year: 2015

Advertisement (abbreviated ad) options are a recent development in online advertising. Simply, an ad option is a first look contract in which a publisher or search engine grants an advertiser a right but not obligation to enter into transactions to purchase impressions or clicks from a specific ad slot at a pre-specified price on a specific delivery date. Such a structure provides advertisers with more flexibility of their guaranteed deliveries. The valuation of ad options is an important topic and previous studies on ad options pricing have been mostly restricted to the situations where the underlying prices follow a geometric Brownian motion (GBM). This assumption is reasonable for sponsored search; however, some studies have also indicated that it is not valid for display advertising. In this paper, we address this issue by employing a stochastic volatility (SV) model and discuss a lattice framework to approximate the proposed SV model in option pricing. Our developments are validated by experiments with real advertising data: (i) we find that the SV model has a better fitness over the GBM model; (ii) we validate the proposed lattice model via two sequential Monte Carlo simulation methods; (iii) we demonstrate that advertisers are able to flexibly manage their guaranteed deliveries by using the proposed options, and publishers can have an increased revenue when some of their inventories are sold via ad options.
On computable abstractions (a conceptual introduction)
Venue: arXiv cs.AI 2015
Year: 2015

This paper introduces abstractions that are meaningful for computers and that can be built and used according to computers' own criteria, i.e., computable abstractions. It is analyzed how abstractions can be seen to serve as the building blocks for the creation of one own's understanding of things, which is essential in performing intellectual tasks. Thus, abstractional machines are defined, which following a mechanical process can, based on computable abstractions, build and use their own understanding of things. Abstractional machines are illustrated through an example that outlines their application to the task of natural language processing.