OpenRaiser/Intern-Atlas huggingface dataset:
Extracting a shape function for a signal with intra-wave frequency modulation
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we consider signals with intra-wave frequency modulation. To handle this kind of signals effectively, we generalize our data-driven time-frequency analysis by using a shape function to describe the intra-wave frequency modulation. The idea of using a shape function in time-frequency analysis was first proposed by Wu. A shape function could be any periodic function. Based on this model, we propose to solve an optimization problem to extract the shape function. By exploring the fact that s is a periodic function, we can identify certain low rank structure of the signal. This structure enables us to extract the shape function from the signal. To test the robustness of our method, we apply our method on several synthetic and real signals. The results are very encouraging.
Computationally Efficient Sparse Bayesian Learning via Generalized Approximate Message Passing
Venue: arXiv cs.IT 2015
Year: 2015

The sparse Beyesian learning (also referred to as Bayesian compressed sensing) algorithm is one of the most popular approaches for sparse signal recovery, and has demonstrated superior performance in a series of experiments. Nevertheless, the sparse Bayesian learning algorithm has computational complexity that grows exponentially with the dimension of the signal, which hinders its application to many practical problems even with moderately large data sets. To address this issue, in this paper, we propose a computationally efficient sparse Bayesian learning method via the generalized approximate message passing (GAMP) technique. Specifically, the algorithm is developed within an expectation-maximization (EM) framework, using GAMP to efficiently compute an approximation of the posterior distribution of hidden variables. The hyperparameters associated with the hierarchical Gaussian prior are learned by iteratively maximizing the Q-function which is calculated based on the posterior approximation obtained from the GAMP. Numerical results are provided to illustrate the computational efficacy and the effectiveness of the proposed algorithm.
Optimized Uplink Transmission in Multi-Antenna C-RAN with Spatial Compression and Forward
Venue: arXiv cs.IT 2015
Year: 2015

Massive MIMO and C-RAN are two promising techniques for implementing future wireless communication systems, where a large number of antennas are deployed either being co-located at the base station (BS) or totally distributed at separate sites called remote radio heads (RRHs). In this paper, we consider a general antenna deployment design for wireless networks, termed multi-antenna C-RAN, where a flexible number of antennas can be equipped at each RRH to more effectively balance the performance and fronthaul complexity trade-off beyond the conventional massive MIMO and single-antenna C-RAN. Under the uplink communication setup, we propose a new "spatial-compression-and-forward (SCF)" scheme, where each RRH first performs a linear spatial filtering to denoise and maximally compress its received signals from multiple users to a reduced number of dimensions, then conducts uniform scalar quantization over each of the resulting dimensions in parallel, and finally sends the total quantized bits to the baseband unit (BBU) via a finite-rate fronthaul link for joint information decoding. Under this scheme, we maximize the minimum signal-to-interference-plus-noise ratio (SINR) of all users at the BBU by a joint resource allocation over the wireless transmission and fronthaul links. Specifically, each RRH determines its own spatial filtering solution in a distributed manner to reduce the signalling overhead with the BBU, while the BBU jointly optimizes the users' transmit power, the RRHs' fronthaul bits allocation, and the BBU's receive beamforming with fixed spatial filters at individual RRHs. Through numerical results, it is shown that given a total number of antennas to be deployed, multi-antenna C-RAN with the proposed SCF and joint optimization significantly outperforms both massive MIMO and single-antenna C-RAN under practical fronthaul capacity constraints.
Designing a Belief Function-Based Accessibility Indicator to Improve Web Browsing for Disabled People
Venue: arXiv cs.HC 2015
Year: 2015

The purpose of this study is to provide an accessibility measure of web-pages, in order to draw disabled users to the pages that have been designed to be ac-cessible to them. Our approach is based on the theory of belief functions, using data which are supplied by reports produced by automatic web content assessors that test the validity of criteria defined by the WCAG 2.0 guidelines proposed by the World Wide Web Consortium (W3C) organization. These tools detect errors with gradual degrees of certainty and their results do not always converge. For these reasons, to fuse information coming from the reports, we choose to use an information fusion framework which can take into account the uncertainty and imprecision of infor-mation as well as divergences between sources. Our accessibility indicator covers four categories of deficiencies. To validate the theoretical approach in this context, we propose an evaluation completed on a corpus of 100 most visited French news websites, and 2 evaluation tools. The results obtained illustrate the interest of our accessibility indicator.
A Customized Lattice Reduction Multiprocessor for MIMO Detection
Venue: arXiv cs.IT 2015
Year: 2015

Lattice reduction (LR) is a preprocessing technique for multiple-input multiple-output (MIMO) symbol detection to achieve better bit error-rate (BER) performance. In this paper, we propose a customized homogeneous multiprocessor for LR. The processor cores are based on transport triggered architecture (TTA). We propose some modification of the popular LR algorithm, Lenstra-Lenstra-Lovasz (LLL) for high throughput. The TTA cores are programmed with high level language. Each TTA core consists of several special function units to accelerate the program code. The multiprocessor takes 187 cycles to reduce a single matrix for LR. The architecture is synthesized on 90 nm technology and takes 405 kgates at 210 MHz.
CITEX: A new citation index to measure the relative importance of authors and papers in scientific publications
Venue: arXiv cs.DL 2015
Year: 2015

Evaluating the performance of researchers and measuring the impact of papers written by scientists is the main objective of citation analysis. Various indices and metrics have been proposed for this. In this paper, we propose a new citation index CITEX, which gives normalized scores to authors and papers to determine their rankings. To the best of our knowledge, this is the first citation index which simultaneously assigns scores to both authors and papers. Using these scores, we can get an objective measure of the reputation of an author and the impact of a paper. We model this problem as an iterative computation on a publication graph, whose vertices are authors and papers, and whose edges indicate which author has written which paper. We prove that this iterative computation converges in the limit, by using a powerful theorem from linear algebra. We run this algorithm on several examples, and find that the author and paper scores match closely with what is suggested by our intuition. The algorithm is theoretically sound and runs very fast in practice. We compare this index with several existing metrics and find that CITEX gives far more accurate scores compared to the traditional metrics.
Locally recoverable codes on algebraic curves
Venue: arXiv cs.IT 2015
Year: 2015

A code over a finite alphabet is called locally recoverable (LRC code) if every symbol in the encoding is a function of a small number (at most r) other symbols. A family of linear LRC codes that generalize the classic construction of Reed-Solomon codes was constructed in a recent paper by I. Tamo and A. Barg. In this paper we extend this construction to codes on algebraic curves. We give a general construction of LRC codes on curves and compute some examples, including asymptotically good families of codes derived from the Garcia- Stichtenoth towers. The local recovery procedure is performed by polynomial interpolation over r coordinates of the codevector. We also obtain a family of Hermitian codes with two disjoint recovering sets for every symbol of the codeword.
Navigability is a Robust Property
Venue: arXiv cs.SI 2015
Year: 2015

The Small World phenomenon has inspired researchers across a number of fields. A breakthrough in its understanding was made by Kleinberg who introduced Rank Based Augmentation (RBA): add to each vertex independently an arc to a random destination selected from a carefully crafted probability distribution. Kleinberg proved that RBA makes many networks navigable, i.e., it allows greedy routing to successfully deliver messages between any two vertices in a polylogarithmic number of steps. We prove that navigability is an inherent property of many random networks, arising without coordination, or even independence assumptions.
Maximin Safety: When Failing to Lose is Preferable to Trying to Win
Venue: arXiv cs.AI 2015
Year: 2015

We present a new decision rule, \emph{maximin safety}, that seeks to maintain a large margin from the worst outcome, in much the same way minimax regret seeks to minimize distance from the best. We argue that maximin safety is valuable both descriptively and normatively. Descriptively, maximin safety explains the well-known \emph{decoy effect}, in which the introduction of a dominated option changes preferences among the other options. Normatively, we provide an axiomatization that characterizes preferences induced by maximin safety, and show that maximin safety shares much of the same behavioral basis with minimax regret.
Taming Multirelations
Venue: arXiv cs.LO 2015
Year: 2015

Binary multirelations generalise binary relations by associating elements of a set to its subsets. We study the structure and algebra of multirelations under the operations of union, intersection, sequential and parallel composition, as well as finite and infinite iteration. Starting from a set-theoretic investigation, we propose axiom systems for multirelations in contexts ranging from bi-monoids to bi-quantales.
Recursive Bayesian Filtering in Circular State Spaces
Venue: arXiv cs.SY 2015
Year: 2015

For recursive circular filtering based on circular statistics, we introduce a general framework for estimation of a circular state based on different circular distributions, specifically the wrapped normal distribution and the von Mises distribution. We propose an estimation method for circular systems with nonlinear system and measurement functions. This is achieved by relying on efficient deterministic sampling techniques. Furthermore, we show how the calculations can be simplified in a variety of important special cases, such as systems with additive noise as well as identity system or measurement functions. We introduce several novel key components, particularly a distribution-free prediction algorithm, a new and superior formula for the multiplication of wrapped normal densities, and the ability to deal with non-additive system noise. All proposed methods are thoroughly evaluated and compared to several state-of-the-art solutions.
The weighted 2-metric dimension of trees in the non-landmarks model
Venue: arXiv cs.DS 2015
Year: 2015

Let T=(V,E) be a tree graph with non-negative weights defined on the vertices. A vertex z is called a separating vertex for u and v if the distances of z to u and v are not equal. A set of vertices L\subseteq V is a feasible solution for the non-landmarks model (NL), if for every pair of distinct vertices, u,v \in V\setminus L, there are at least two vertices of L separating them. Such a feasible solution is called a "landmark set". We analyze the structure of landmark sets for trees and design a linear time algorithm for finding a minimum cost landmark set for a given tree graph.
A Direct Symbolic Execution of SQL Code for Testing of Data-Oriented Applications
Venue: arXiv cs.SE 2015
Year: 2015

Symbolic execution is a technique which enables automatically generating test inputs (and outputs) exercising a set of execution paths within a program to be tested. If the paths cover a sufficient part of the code under test, the test data offer a representative view of the program's actual behaviour, which notably enables detecting errors and correcting faults. Relational databases are ubiquitous in software, but symbolic execution of pieces of code that manipulate them remains a non-trivial problem, particularly because of the complex structure of such databases and the complex behaviour of SQL statements. In this work, we define a direct symbolic execution for database manipulation code and integrate it with a more traditional symbolic execution of normal program code. The database tables are represented by relational symbols and the SQL statements by relational constraints over these symbols and the symbols representing the normal variables of the program. An algorithm based on these principles is presented for the symbolic execution of Java methods that implement business use cases by reading and writing in a relational database, the latter subject to data integrity constraints. The algorithm is integrated in a test generation tool and experimented over sample code. The target language for the constraints produced by the tool is the SMT-Lib standard and the used solver is Microsoft Z3. The results show that the proposed approach enables generating meaningful test data, including valid database content, in reasonable time. In particular, the Z3 solver is shown to be more scalable than the Alloy solver, used in our previous work, for solving relational constraints.
Trolls Identification within an Uncertain Framework
Venue: arXiv cs.AI 2015
Year: 2015

The web plays an important role in people's social lives since the emergence of Web 2.0. It facilitates the interaction between users, gives them the possibility to freely interact, share and collaborate through social networks, online communities forums, blogs, wikis and other online collaborative media. However, an other side of the web is negatively taken such as posting inflammatory messages. Thus, when dealing with the online communities forums, the managers seek to always enhance the performance of such platforms. In fact, to keep the serenity and prohibit the disturbance of the normal atmosphere, managers always try to novice users against these malicious persons by posting such message (DO NOT FEED TROLLS). But, this kind of warning is not enough to reduce this phenomenon. In this context we propose a new approach for detecting malicious people also called 'Trolls' in order to allow community managers to take their ability to post online. To be more realistic, our proposal is defined within an uncertain framework. Based on the assumption consisting on the trolls' integration in the successful discussion threads, we try to detect the presence of such malicious users. Indeed, this method is based on a conflict measure of the belief function theory applied between the different messages of the thread. In order to show the feasibility and the result of our approach, we test it in different simulated data.
Output-sensitive algorithms for sumset and sparse polynomial multiplication
Venue: arXiv cs.SC 2015
Year: 2015

We present randomized algorithms to compute the sumset (Minkowski sum) of two integer sets, and to multiply two univariate integer polynomials given by sparse representations. Our algorithm for sumset has cost softly linear in the combined size of the inputs and output. This is used as part of our sparse multiplication algorithm, whose cost is softly linear in the combined size of the inputs, output, and the sumset of the supports of the inputs. As a subroutine, we present a new method for computing the coefficients of a sparse polynomial, given a set containing its support. Our multiplication algorithm extends to multivariate Laurent polynomials over finite fields and rational numbers. Our techniques are based on sparse interpolation algorithms and results from analytic number theory.
Communication Theoretic Data Analytics
Venue: arXiv cs.IT 2015
Year: 2015

Widespread use of the Internet and social networks invokes the generation of big data, which is proving to be useful in a number of applications. To deal with explosively growing amounts of data, data analytics has emerged as a critical technology related to computing, signal processing, and information networking. In this paper, a formalism is considered in which data is modeled as a generalized social network and communication theory and information theory are thereby extended to data analytics. First, the creation of an equalizer to optimize information transfer between two data variables is considered, and financial data is used to demonstrate the advantages. Then, an information coupling approach based on information geometry is applied for dimensionality reduction, with a pattern recognition example to illustrate the effectiveness. These initial trials suggest the potential of communication theoretic data analytics for a wide range of applications.
Stable matchings of teachers to schools
Venue: arXiv cs.DS 2015
Year: 2015

Several countries successfully use centralized matching schemes for school or higher education assignment, or for entry-level labour markets. In this paper we explore the computational aspects of a possible similar scheme for assigning teachers to schools. Our model is motivated by a particular characteristic of the education system in many countries where each teacher specializes in two subjects. We seek stable matchings, which ensure that no teacher and school have the incentive to deviate from their assignments. Indeed we propose two stability definitions depending on the precise format of schools' preferences. If the schools' ranking of applicants is independent of their subjects of specialism, we show that the problem of deciding whether a stable matching exists is NP-complete, even if there are only three subjects, unless there are master lists of applicants or of schools. By contrast, if the schools may order applicants differently in each of their specialization subjects, the problem of deciding whether a stable matching exists is NP-complete even in the presence of subject-specific master lists plus a master list of schools. Finally, we prove a strong inapproximability result for the problem of finding a matching with the minimum number of blocking pairs with respect to both stability definitions.
Efficient Web-Based SCADA System
Venue: arXiv cs.SY 2015
Year: 2015

Computer-based supervisory control and data acquisition (SCADA) systems have evolved over the past four decades, from standalone, compartmentalized operations into networked architectures that communicate across large distances. There is an emerging trend comprising SCADA and conventional IT units toward consolidating some overlapping activities. This trend is motivated by cost savings achieved by consolidating disparate platforms, networks, software, and maintenance tools. For reasons of efficiency, maintenance, economics, data acquisition, control platforms have migrated from isolated in-plant networks using proprietary hardware and software to PC-based systems using standard software, network protocols, and the Internet. In this thesis, we present an approach for web-based SCADA systems that adapt to the behavior of the target application. In addition, we take into account the real time constraints that imposed by the nature of the problem. We show that our approach is more efficient than other approaches in terms of consuming as little as possible of the available resources (computational power and network bandwidth).
Hybrid Millimeter-Wave Systems: A Novel Paradigm for HetNets
Venue: arXiv cs.NI 2015
Year: 2015

Heterogeneous Networks (HetNets) are known to enhance the bandwidth efficiency and throughput of wireless networks by more effectively utilizing the network resources. However, the higher density of users and access points in HetNets introduces significant inter-user interference that needs to be mitigated through complex and sophisticated interference cancellation schemes. Moreover, due to significant channel attenuation and presence of hardware impairments, e.g., phase noise and amplifier nonlinearities, the vast bandwidth in the millimeter-wave band has not been fully utilized to date. In order to enable the development of multi-Gigabit per second wireless networks, we introduce a novel millimeter-wave HetNet paradigm, termed hybrid HetNet, which exploits the vast bandwidth and propagation characteristics in the 60 GHz and 70-80 GHz bands to reduce the impact of interference in HetNets. Simulation results are presented to illustrate the performance advantage of hybrid HetNets with respect to traditional networks. Next, two specific transceiver structures that enable hand-offs from the 60 GHz band, i.e., the V-band to the 70-80 GHz band, i.e., the E-band, and vice versa are proposed. Finally, the practical and regulatory challenges for establishing a hybrid HetNet are outlined.
An ${\cal O}(m\log n)$ algorithm for the weighted stable set problem in claw-free graphs with $α({G}) \le 3$
Venue: arXiv cs.DM 2015
Year: 2015

In this paper we show how to solve the \emph{Maximum Weight Stable Set Problem} in a claw-free graph $G(V, E)$ with $α(G) \le 3$ in time ${\cal O}(|E|\log|V|)$. More precisely, in time ${\cal O}(|E|)$ we check whether $α(G) \le 3$ or produce a stable set with cardinality at least $4$; moreover, if $α(G) \le 3$ we produce in time ${\cal O}(|E|\log|V|)$ a maximum stable set of $G$. This improves the bound of ${\cal O}(|E||V|)$ due to Faenza et al.
CRDSA, CRDSA++ and IRSA: Stability and Performance Evaluation
Venue: arXiv cs.IT 2015
Year: 2015

In the recent past, new enhancements based on the well established Aloha technique (CRDSA, CRDSA++, IRSA) have demonstrated the capability to reach higher throughput than traditional SA, in bursty traffic conditions and without any need of coordination among terminals. In this paper, retransmissions and related stability for these new techniques are discussed. A model is also formulated in order to provide a basis for the analysis of the stability and the performance both for finite and infinite users population. This model can be used as a framework for the design of such a communication system.
Ultrascale Simulations of Non-smooth Granular Dynamics
Venue: arXiv cs.CE 2015
Year: 2015

This article presents new algorithms for massively parallel granular dynamics simulations on distributed memory architectures using a domain partitioning approach. Collisions are modelled with hard contacts in order to hide their micro-dynamics and thus to extend the time and length scales that can be simulated. The multi-contact problem is solved using a non-linear block Gauss-Seidel method that is conforming to the subdomain structure. The parallel algorithms employ a sophisticated protocol between processors that delegate algorithmic tasks such as contact treatment and position integration uniquely and robustly to the processors. Communication overhead is minimized through aggressive message aggregation, leading to excellent strong and weak scaling. The robustness and scalability is assessed on three clusters including two peta-scale supercomputers with up to 458752 processor cores. The simulations can reach unprecedented resolution of up to ten billion non-spherical particles and contacts.
A Generalized Framework for Virtual Substitution
Venue: arXiv cs.SC 2015
Year: 2015

We generalize the framework of virtual substitution for real quantifier elimination to arbitrary but bounded degrees. We make explicit the representation of test points in elimination sets using roots of parametric univariate polynomials described by Thom codes. Our approach follows an early suggestion by Weispfenning, which has never been carried out explicitly. Inspired by virtual substitution for linear formulas, we show how to systematically construct elimination sets containing only test points representing lower bounds.