OpenRaiser/Intern-Atlas huggingface dataset:
Using Generic Summarization to Improve Music Information Retrieval Tasks
Venue: arXiv cs.IR 2016
Year: 2016

In order to satisfy processing time constraints, many MIR tasks process only a segment of the whole music signal. This practice may lead to decreasing performance, since the most important information for the tasks may not be in those processed segments. In this paper, we leverage generic summarization algorithms, previously applied to text and speech summarization, to summarize items in music datasets. These algorithms build summaries, that are both concise and diverse, by selecting appropriate segments from the input signal which makes them good candidates to summarize music as well. We evaluate the summarization process on binary and multiclass music genre classification tasks, by comparing the performance obtained using summarized datasets against the performances obtained using continuous segments (which is the traditional method used for addressing the previously mentioned time constraints) and full songs of the same original dataset. We show that GRASSHOPPER, LexRank, LSA, MMR, and a Support Sets-based Centrality model improve classification performance when compared to selected 30-second baselines. We also show that summarized datasets lead to a classification performance whose difference is not statistically significant from using full songs. Furthermore, we make an argument stating the advantages of sharing summarized datasets for future MIR research.
Convergence radius and sample complexity of ITKM algorithms for dictionary learning
Venue: arXiv cs.LG 2016
Year: 2016

In this work we show that iterative thresholding and K-means (ITKM) algorithms can recover a generating dictionary with K atoms from noisy $S$ sparse signals up to an error $\tilde \varepsilon$ as long as the initialisation is within a convergence radius, that is up to a $\log K$ factor inversely proportional to the dynamic range of the signals, and the sample size is proportional to $K \log K \tilde \varepsilon^{-2}$. The results are valid for arbitrary target errors if the sparsity level is of the order of the square root of the signal dimension $d$ and for target errors down to $K^{-\ell}$ if $S$ scales as $S \leq d/(\ell \log K)$.
Computing the partition function of a polynomial on the Boolean cube
Venue: arXiv cs.DS 2016
Year: 2016

For a polynomial f: {-1, 1}^n --> C, we define the partition function as the average of e^{lambda f(x)} over all points x in {-1, 1}^n, where lambda in C is a parameter. We present a quasi-polynomial algorithm, which, given such f, lambda and epsilon >0 approximates the partition function within a relative error of epsilon in N^{O(ln n -ln epsilon)} time provided |lambda| < 1/(2 L sqrt{deg f}), where L=L(f) is a parameter bounding the Lipschitz constant of f from above and N is the number of monomials in f. As a corollary, we obtain a quasi-polynomial algorithm, which, given such an f with coefficients +1 and -1 and such that every variable enters not more than 4 monomials, approximates the maximum of f on {-1, 1}^n within a factor of O(sqrt{deg f}/delta), provided the maximum is N delta for some 0< delta <1. If every variable enters not more than k monomials for some fixed k > 4, we are able to establish a similar result when delta > (k-1)/k.
Large-scale Biological Meta-database Management
Venue: arXiv cs.DC 2016
Year: 2016

Up-to-date meta-databases are vital for the analysis of biological data. However,the current exponential increase in biological data leads to exponentially increasing meta-database sizes. Large-scale meta-database management is therefore an important challenge for production platforms providing services for biological data analysis. In particular, there is often a need either to run an analysis with a particular version of a meta-database, or to rerun an analysis with an updated meta-database. We present our GeStore approach for biological meta-database management. It provides efficient storage and runtime generation of specific meta-database versions, and efficient incremental updates for biological data analysis tools. The approach is transparent to the tools, and we provide a framework that makes it easy to integrate GeStore with biological data analysis frameworks. We present the GeStore system, an evaluation of the performance characteristics of the system, and an evaluation of the benefits for a biological data analysis workflow.
Leader Election and Shape Formation with Self-Organizing Programmable Matter
Venue: arXiv cs.ET 2016
Year: 2016

We consider programmable matter consisting of simple computational elements, called particles, that can establish and release bonds and can actively move in a self-organized way, and we investigate the feasibility of solving fundamental problems relevant for programmable matter. As a suitable model for such self-organizing particle systems, we will use a generalization of the geometric amoebot model first proposed in SPAA 2014. Based on the geometric model, we present efficient local-control algorithms for leader election and line formation requiring only particles with constant size memory, and we also discuss the limitations of solving these problems within the general amoebot model.
A Sums-of-Squares Extension of Policy Iterations
Venue: arXiv cs.LO 2016
Year: 2016

In order to address the imprecision often introduced by widening operators in static analysis, policy iteration based on min-computations amounts to considering the characterization of reachable value set of a program as an iterative computation of policies, starting from a post-fixpoint. Computing each policy and the associated invariant relies on a sequence of numerical optimizations. While the early research efforts relied on linear programming (LP) to address linear properties of linear programs, the current state of the art is still limited to the analysis of linear programs with at most quadratic invariants, relying on semidefinite programming (SDP) solvers to compute policies, and LP solvers to refine invariants. We propose here to extend the class of programs considered through the use of Sums-of-Squares (SOS) based optimization. Our approach enables the precise analysis of switched systems with polynomial updates and guards. The analysis presented has been implemented in Matlab and applied on existing programs coming from the system control literature, improving both the range of analyzable systems and the precision of previously handled ones.
Separable projection integrals for higher-order correlators of the cosmic microwave sky: Acceleration by factors exceeding 100
Venue: arXiv cs.DC 2016
Year: 2016

We present a case study describing efforts to optimise and modernise "Modal", the simulation and analysis pipeline used by the Planck satellite experiment for constraining general non-Gaussian models of the early universe via the bispectrum (or three-point correlator) of the cosmic microwave background radiation. We focus on one particular element of the code: the projection of bispectra from the end of inflation to the spherical shell at decoupling, which defines the CMB we observe today. This code involves a three-dimensional inner product between two functions, one of which requires an integral, on a non-rectangular domain containing a sparse grid. We show that by employing separable methods this calculation can be reduced to a one-dimensional summation plus two integrations, reducing the overall dimensionality from four to three. The introduction of separable functions also solves the issue of the non-rectangular sparse grid. This separable method can become unstable in certain cases and so the slower non-separable integral must be calculated instead. We present a discussion of the optimisation of both approaches. We show significant speed-ups of ~100x, arising from a combination of algorithmic improvements and architecture-aware optimisations targeted at improving thread and vectorisation behaviour. The resulting MPI/OpenMP hybrid code is capable of executing on clusters containing processors and/or coprocessors, with strong-scaling efficiency of 98.6% on up to 16 nodes. We find that a single coprocessor outperforms two processor sockets by a factor of 1.3x and that running the same code across a combination of both microarchitectures improves performance-per-node by a factor of 3.38x. By making bispectrum calculations competitive with those for the power spectrum (or two-point correlator) we are now able to consider joint analysis for cosmological science exploitation of new data.
Generalized Categorization Axioms
Venue: arXiv cs.LG 2016
Year: 2016

Categorization axioms have been proposed to axiomatizing clustering results, which offers a hint of bridging the difference between human recognition system and machine learning through an intuitive observation: an object should be assigned to its most similar category. However, categorization axioms cannot be generalized into a general machine learning system as categorization axioms become trivial when the number of categories becomes one. In order to generalize categorization axioms into general cases, categorization input and categorization output are reinterpreted by inner and outer category representation. According to the categorization reinterpretation, two category representation axioms are presented. Category representation axioms and categorization axioms can be combined into a generalized categorization axiomatic framework, which accurately delimit the theoretical categorization constraints and overcome the shortcoming of categorization axioms. The proposed axiomatic framework not only discuses categorization test issue but also reinterprets many results in machine learning in a unified way, such as dimensionality reduction,density estimation, regression, clustering and classification.
Constant Envelope Precoding with Adaptive Receiver Constellation in MISO Fading Channel
Venue: arXiv cs.IT 2016
Year: 2016

Constant envelope (CE) precoding is an appealing transmission technique which enables the realization of high power amplifier (PA) efficiency. For CE precoding in a single-user multiple-input single-output (MISO) channel, a desired constellation is feasible at the receiver if and only if it can be scaled to lie in an annulus, whose boundaries are characterized by the instantaneous channel realization. Therefore, if a fixed receiver constellation is used for CE precoding in a fading channel, where the annulus is time-varying, there is in general a non-zero probability of encountering a channel that makes CE precoding infeasible, thereby causing a high probability of error. To tackle this problem, this paper studies the adaptive receiver constellation design for CE precoding in a single-user MISO flat-fading channel with an arbitrary number of antennas at the transmitter. We first investigate the fixed-rate adaptive receiver constellation design to minimize the symbol error rate (SER). Specifically, an efficient algorithm is proposed to find the optimal amplitude-and-phase shift keying (APSK) constellation with two rings that is both feasible and of the maximum minimum Euclidean distance (MED), for any given constellation size and instantaneous channel realization. Numerical results show that by using the optimized fixed-rate adaptive receiver constellation, our proposed scheme achieves significantly improved SER performance over CE precoding with a fixed receiver constellation. Furthermore, based on the family of optimal fixed-rate adaptive two-ring APSK constellation sets, a variable-rate CE transmission scheme is proposed and numerically examined.
Low-Latency Software Polar Decoders
Venue: arXiv cs.IT 2016
Year: 2016

Polar codes are a new class of capacity-achieving error-correcting codes with low encoding and decoding complexity. Their low-complexity decoding algorithms rendering them attractive for use in software-defined radio applications where computational resources are limited. In this work, we present low-latency software polar decoders that exploit modern processor capabilities. We show how adapting the algorithm at various levels can lead to significant improvements in latency and throughput, yielding polar decoders that are suitable for high-performance software-defined radio applications on modern desktop processors and embedded-platform processors. These proposed decoders have an order of magnitude lower latency and memory footprint compared to state-of-the-art decoders, while maintaining comparable throughput. In addition, we present strategies and results for implementing polar decoders on graphical processing units. Finally, we show that the energy efficiency of the proposed decoders is comparable to state-of-the-art software polar decoders.
Source Coding in Networks with Covariance Distortion Constraints
Venue: arXiv cs.IT 2016
Year: 2016

We consider a source coding problem with a network scenario in mind, and formulate it as a remote vector Gaussian Wyner-Ziv problem under covariance matrix distortions. We define a notion of minimum for two positive-definite matrices based on which we derive an explicit formula for the rate-distortion function (RDF). We then study the special cases and applications of this result. We show that two well-studied source coding problems, i.e. remote vector Gaussian Wyner-Ziv problems with mean-squared error and mutual information constraints are in fact special cases of our results. Finally, we apply our results to a joint source coding and denoising problem. We consider a network with a centralized topology and a given weighted sum-rate constraint, where the received signals at the center are to be fused to maximize the output SNR while enforcing no linear distortion. We show that one can design the distortion matrices at the nodes in order to maximize the output SNR at the fusion center. We thereby bridge between denoising and source coding within this setup.
The Computational Power of Optimization in Online Learning
Venue: arXiv cs.LG 2016
Year: 2016

We consider the fundamental problem of prediction with expert advice where the experts are "optimizable": there is a black-box optimization oracle that can be used to compute, in constant time, the leading expert in retrospect at any point in time. In this setting, we give a novel online algorithm that attains vanishing regret with respect to $N$ experts in total $\widetilde{O}(\sqrt{N})$ computation time. We also give a lower bound showing that this running time cannot be improved (up to log factors) in the oracle model, thereby exhibiting a quadratic speedup as compared to the standard, oracle-free setting where the required time for vanishing regret is $\widetildeΘ(N)$. These results demonstrate an exponential gap between the power of optimization in online learning and its power in statistical learning: in the latter, an optimization oracle---i.e., an efficient empirical risk minimizer---allows to learn a finite hypothesis class of size $N$ in time $O(\log{N})$. We also study the implications of our results to learning in repeated zero-sum games, in a setting where the players have access to oracles that compute, in constant time, their best-response to any mixed strategy of their opponent. We show that the runtime required for approximating the minimax value of the game in this setting is $\widetildeΘ(\sqrt{N})$, yielding again a quadratic improvement upon the oracle-free setting, where $\widetildeΘ(N)$ is known to be tight.
Classifying Unrooted Gaussian Trees under Privacy Constraints
Venue: arXiv cs.IT 2016
Year: 2016

In this work, our objective is to find out how topological and algebraic properties of unrooted Gaussian tree models determine their security robustness, which is measured by our proposed max-min information (MaMI) metric. Such metric quantifies the amount of common randomness extractable through public discussion between two legitimate nodes under an eavesdropper attack. We show some general topological properties that the desired max-min solutions shall satisfy. Under such properties, we develop conditions under which comparable trees are put together to form partially ordered sets (posets). Each poset contains the most favorable structure as the poset leader, and the least favorable structure. Then, we compute the Tutte-like polynomial for each tree in a poset in order to assign a polynomial to any tree in a poset. Moreover, we propose a novel method, based on restricted integer partitions, to effectively enumerate all poset leaders. The results not only help us understand the security strength of different Gaussian trees, which is critical when we evaluate the information leakage issues for various jointly Gaussian distributed measurements in networks, but also provide us both an algebraic and a topological perspective in grasping some fundamental properties of such models.
A benchmark for data-based office modeling: challenges related to CO$_2$ dynamics
Venue: arXiv cs.SY 2016
Year: 2016

This paper describes a benchmark consisting of a set of synthetic measurements relative to an office environment simulated with the software IDA-ICE. The simulated environment reproduces a laboratory at the KTH-EES Smart Building, equipped with a building management system. The data set contains records collected over a period of several days. The signals to CO$_2$ concentration, mechanical ventilation airflows, air infiltrations and occupancy. Information on door and window opening is also available. This benchmark is intended for testing data-based modeling techniques. The ultimate goal is the development of models to improve the forecast and control of environmental variables. Among the numerous challenges related to this framework, we point out the problem of occupancy estimation using information on CO$_2$ concentration. This can be seen as a blind identification problem. For benchmarking purposes, we present two different identification approaches: a baseline overparametrization method and a kernel-based method.
Discovery of the $D$-basis in binary tables based on hypergraph dualization
Venue: arXiv cs.DB 2016
Year: 2016

Discovery of (strong) association rules, or implications, is an important task in data management, and it finds application in artificial intelligence, data mining and the semantic web. We introduce a novel approach for the discovery of a specific set of implications, called the $D$-basis, that provides a representation for a reduced binary table, based on the structure of its Galois lattice. At the core of the method are the $D$-relation defined in the lattice theory framework, and the hypergraph dualization algorithm that allows us to effectively produce the set of transversals for a given Sperner hypergraph. The latter algorithm, first developed by specialists from Rutgers Center for Operations Research, has already found numerous applications in solving optimization problems in data base theory, artificial intelligence and game theory. One application of the method is for analysis of gene expression data related to a particular phenotypic variable, and some initial testing is done for the data provided by the University of Hawaii Cancer Center.
Network-Coded Multiple Access with High-order Modulations
Venue: arXiv cs.IT 2016
Year: 2016

This paper presents the first network-coded multiple access (NCMA) system prototype operated on high-order modulations up to 16-QAM. NCMA jointly exploits physical-layer network coding (PNC) and multiuser decoding (MUD) to boost throughput of multipacket reception systems. Direct generalization of the existing NCMA decoding algorithm, originally designed for BPSK, to high-order modulations, will lead to huge performance degradation. The throughput degradation is caused by the relative phase offset between received signals from different nodes. To circumvent the phase offset problem, this paper investigates an NCMA system with multiple receive antennas at the access point (AP), referred to as MIMO-NCMA. We put forth a low-complexity symbol-level NCMA decoder that, together with MIMO, can substantially alleviate the performance degradation induced by relative phase offset. To demonstrate the feasibility and advantage of MIMO-NCMA for high-order modulations, we implemented our designs on software-defined radio. Our experimental results show that the throughput of QPSK MIMO-NCMA is double that of both BPSK NCMA and QPSK MUD at SNR=10dB. For higher SNRs at which 16-QAM can be supported, the throughput of MIMO-NCMA can be as high as 3.5 times that of BPSK NCMA. Overall, this paper provides an implementable framework for high-order modulated NCMA.
Backhaul-Aware User Association and Resource Allocation for Energy-Constrained HetNets
Venue: arXiv cs.NI 2016
Year: 2016

Growing attentions have been paid to renewable energy or hybrid energy powered heterogeneous networks (HetNets). In this paper, focusing on backhaul-aware joint user association and resource allocation for this type of HetNets, we formulate an online optimization problem to maximize the network utility reflecting proportional fairness. Since user association and resource allocation are tightly coupled not only on resource consumption of the base stations (BSs), but also in the constraints of their available energy and backhaul, the closed-form solution is quite difficult to obtain. Thus, we solve the problem distributively via employing some decomposition methods. Specifically, at first, by adopting primal decomposition method, we decompose the original problem into a lower-level resource allocation problem for each BS, and a higher-level user association problem. For the optimal resource allocation, we prove that a BS either assigns equal normalized resources or provides equal long-term service rate to its served users. Then, the user association problem is solved by Lagrange dual decomposition method, and a completely distributed algorithm is developed. Moreover, applying results of the subgradient method, we demonstrate the convergence of the proposed distributed algorithm. Furthermore, in order to efficiently and reliably apply the proposed algorithm to the future wireless networks with an extremely dense BS deployment, we design a virtual user association and resource allocation scheme based on the software-defined networking architecture. Lastly, numerical results validate the convergence of the proposed algorithm and the significant improvement on network utility, load balancing and user fairness.
A Survey on Applications of Model-Free Strategy Learning in Cognitive Wireless Networks
Venue: arXiv cs.NI 2016
Year: 2016

Model-free learning has been considered as an efficient tool for designing control mechanisms when the model of the system environment or the interaction between the decision-making entities is not available as a-priori knowledge. With model-free learning, the decision-making entities adapt their behaviors based on the reinforcement from their interaction with the environment and are able to (implicitly) build the understanding of the system through trial-and-error mechanisms. Such characteristics of model-free learning is highly in accordance with the requirement of cognition-based intelligence for devices in cognitive wireless networks. Recently, model-free learning has been considered as one key implementation approach to adaptive, self-organized network control in cognitive wireless networks. In this paper, we provide a comprehensive survey on the applications of the state-of-the-art model-free learning mechanisms in cognitive wireless networks. According to the system models that those applications are based on, a systematic overview of the learning algorithms in the domains of single-agent system, multi-agent systems and multi-player games is provided. Furthermore, the applications of model-free learning to various problems in cognitive wireless networks are discussed with the focus on how the learning mechanisms help to provide the solutions to these problems and improve the network performance over the existing model-based, non-adaptive methods. Finally, a broad