OpenRaiser/Intern-Atlas huggingface dataset:
Beamforming Tradeoffs for Initial UE Discovery in Millimeter-Wave MIMO Systems
Venue: arXiv cs.IT 2016
Year: 2016

Millimeter-wave MIMO systems have gained increasing traction towards the goal of meeting the high data-rate requirements in next-generation wireless systems. The focus of this work is on low-complexity beamforming approaches for initial UE discovery in such systems. Towards this goal, we first note the structure of the optimal beamformer with per-antenna gain and phase control and the structure of good beamformers with per-antenna phase-only control. Learning these beamforming structures in mmW systems is fraught with considerable complexities such as the need for a non-broadcast system design, the sensitivity of the beamformer approximants to small path length changes, etc. To overcome these issues, we establish a physical interpretation between these beamformer structures and the angles of departure/arrival of the dominant path(s). This physical interpretation provides a theoretical underpinning to the emerging interest on directional beamforming approaches that are less sensitive to small path length changes. While classical approaches for direction learning such as MUSIC have been well-understood, they suffer from many practical difficulties in a mmW context such as a non-broadcast system design and high computational complexity. A simpler broadcast solution for mmW systems is the adaptation of directional codebooks for beamforming at the two ends. We establish fundamental limits for the best beam broadening codebooks and propose a construction motivated by a virtual subarray architecture that is within a couple of dB of the best tradeoff curve at all useful beam broadening factors. We finally provide the received SNR loss-UE discovery latency tradeoff with the proposed constructions. Our results show that users with a reasonable link margin can be quickly discovered by the proposed design with a smooth roll-off in performance as the link margin deteriorates.
Submodular Optimization under Noise
Venue: arXiv cs.DS 2016
Year: 2016

We consider the problem of maximizing a monotone submodular function under noise. There has been a great deal of work on optimization of submodular functions under various constraints, resulting in algorithms that provide desirable approximation guarantees. In many applications, however, we do not have access to the submodular function we aim to optimize, but rather to some erroneous or noisy version of it. This raises the question of whether provable guarantees are obtainable in presence of error and noise. We provide initial answers, by focusing on the question of maximizing a monotone submodular function under a cardinality constraint when given access to a noisy oracle of the function. We show that: - For a cardinality constraint $k \geq 2$, there is an approximation algorithm whose approximation ratio is arbitrarily close to $1-1/e$; - For $k=1$ there is an algorithm whose approximation ratio is arbitrarily close to $1/2$. No randomized algorithm can obtain an approximation ratio better than $1/2+o(1)$; -If the noise is adversarial, no non-trivial approximation guarantee can be obtained.
Big Data Analytics = Machine Learning + Cloud Computing
Venue: arXiv cs.DC 2016
Year: 2016

Big Data can mean different things to different people. The scale and challenges of Big Data are often described using three attributes, namely Volume, Velocity and Variety (3Vs), which only reflect some of the aspects of data. In this chapter we review historical aspects of the term "Big Data" and the associated analytics. We augment 3Vs with additional attributes of Big Data to make it more comprehensive and relevant. We show that Big Data is not just 3Vs, but 32 Vs, that is, 9 Vs covering the fundamental motivation behind Big Data, which is to incorporate Business Intelligence (BI) based on different hypothesis or statistical models so that Big Data Analytics (BDA) can enable decision makers to make useful predictions for some crucial decisions or researching results. History of Big Data has demonstrated that the most cost effective way of performing BDA is to employ Machine Learning (ML) on the Cloud Computing (CC) based infrastructure or simply, ML + CC -> BDA. This chapter is devoted to help decision makers by defining BDA as a solution and opportunity to address their business needs.
Blind Image Denoising via Dependent Dirichlet Process Tree
Venue: arXiv cs.CV 2016
Year: 2016

Most existing image denoising approaches assumed the noise to be homogeneous white Gaussian distributed with known intensity. However, in real noisy images, the noise models are usually unknown beforehand and can be much more complex. This paper addresses this problem and proposes a novel blind image denoising algorithm to recover the clean image from noisy one with the unknown noise model. To model the empirical noise of an image, our method introduces the mixture of Gaussian distribution, which is flexible enough to approximate different continuous distributions. The problem of blind image denoising is reformulated as a learning problem. The procedure is to first build a two-layer structural model for noisy patches and consider the clean ones as latent variable. To control the complexity of the noisy patch model, this work proposes a novel Bayesian nonparametric prior called "Dependent Dirichlet Process Tree" to build the model. Then, this study derives a variational inference algorithm to estimate model parameters and recover clean patches. We apply our method on synthesis and real noisy images with different noise models. Comparing with previous approaches, ours achieves better performance. The experimental results indicate the efficiency of the proposed algorithm to cope with practical image denoising tasks.
Online Prediction of Dyadic Data with Heterogeneous Matrix Factorization
Venue: arXiv cs.LG 2016
Year: 2016

Dyadic Data Prediction (DDP) is an important problem in many research areas. This paper develops a novel fully Bayesian nonparametric framework which integrates two popular and complementary approaches, discrete mixed membership modeling and continuous latent factor modeling into a unified Heterogeneous Matrix Factorization~(HeMF) model, which can predict the unobserved dyadics accurately. The HeMF can determine the number of communities automatically and exploit the latent linear structure for each bicluster efficiently. We propose a Variational Bayesian method to estimate the parameters and missing data. We further develop a novel online learning approach for Variational inference and use it for the online learning of HeMF, which can efficiently cope with the important large-scale DDP problem. We evaluate the performance of our method on the EachMoive, MovieLens and Netflix Prize collaborative filtering datasets. The experiment shows that, our model outperforms state-of-the-art methods on all benchmarks. Compared with Stochastic Gradient Method (SGD), our online learning approach achieves significant improvement on the estimation accuracy and robustness.
Checking Interval Properties of Computations
Venue: arXiv cs.LO 2016
Year: 2016

Model checking is a powerful method widely explored in formal verification. Given a model of a system, e.g., a Kripke structure, and a formula specifying its expected behaviour, one can verify whether the system meets the behaviour by checking the formula against the model. Classically, system behaviour is expressed by a formula of a temporal logic, such as LTL and the like. These logics are "point-wise" interpreted, as they describe how the system evolves state-by-state. However, there are relevant properties, such as those constraining the temporal relations between pairs of temporally extended events or involving temporal aggregations, which are inherently "interval-based", and thus asking for an interval temporal logic. In this paper, we give a formalization of the model checking problem in an interval logic setting. First, we provide an interpretation of formulas of Halpern and Shoham's interval temporal logic HS over finite Kripke structures, which allows one to check interval properties of computations. Then, we prove that the model checking problem for HS against finite Kripke structures is decidable by a suitable small model theorem, and we provide a lower bound to its computational complexity.
Counting Answers to Existential Positive Queries: A Complexity Classification
Venue: arXiv cs.DB 2016
Year: 2016

Existential positive formulas form a fragment of first-order logic that includes and is semantically equivalent to unions of conjunctive queries, one of the most important and well-studied classes of queries in database theory. We consider the complexity of counting the number of answers to existential positive formulas on finite structures and give a trichotomy theorem on query classes, in the setting of bounded arity. This theorem generalizes and unifies several known results on the complexity of conjunctive queries and unions of conjunctive queries.
Localized Dictionary design for Geometrically Robust Sonar ATR
Venue: arXiv cs.CV 2016
Year: 2016

Advancements in Sonar image capture have opened the door to powerful classification schemes for automatic target recognition (ATR. Recent work has particularly seen the application of sparse reconstruction-based classification (SRC) to sonar ATR, which provides compelling accuracy rates even in the presence of noise and blur. Existing sparsity based sonar ATR techniques however assume that the test images exhibit geometric pose that is consistent with respect to the training set. This work addresses the outstanding open challenge of handling inconsistently posed test sonar images relative to training. We develop a new localized block-based dictionary design that can enable geometric, i.e. pose robustness. Further, a dictionary learning method is incorporated to increase performance and efficiency. The proposed SRC with Localized Pose Management (LPM), is shown to outperform the state of the art SIFT feature and SVM approach, due to its power to discern background clutter in Sonar images.
Energy Harvesting in Secure MIMO Systems
Venue: arXiv cs.IT 2016
Year: 2016

The problems of energy harvesting in wireless com- munication systems have recently drawn much attention. In this paper, we focus on the investigation of energy harvesting maximization (EHM) in the important secrecy multi-input multi- output (MIMO) systems where little research has been done due to their complexity. Particularly, this paper studies the resource allocation strategies in MIMO wiretap channels, wherein we attempt to maximize the harvested energy by one or multiple multi-antenna energy receivers (ERs) (potential eavesdropper) while guaranteeing the secure communication for the multi- antenna information receiver (IR). Two types of IR, with and without the capability to cancel the interference from energy signals, are taken into account. In the scenario of single energy receiver (ER), we consider the joint design of the transmis- sion information and energy covariances for EHM. Both of the optimization problems for the two types of IR are non- convex, and appear to be difficult. To circumvent them, the combination of first order Taylor approximation and sequential convex optimization approach is proposed. Then, we extend our attention to the scenario with multiple ERs, where the artificial noise (AN) aided weighted sum-energy harvesting maximization (WS-EHM) problem is considered. Other than the approaches adopted in solving the EHM problems, an algorithm conducts in an alternating fashion is proposed to handle this problem. In particular, we first perform a judicious transformation of the WS- EHM problem. Then, a block Gauss-Seidel (GS) algorithm based on logarithmic barrier method and gradient projection (GP) is derived to obtain the optimal solution of the reformulation by solving convex problems alternately. Furthermore, the resulting block GS method is proven to converge to a Karush-Kuhn-Tucker (KKT) point of the original WS-EHM problem...
Protection of flows under targeted attacks
Venue: arXiv cs.DM 2016
Year: 2016

Due to the importance of robustness in many real-world optimization problems, the field of robust optimization has gained a lot of attention over the past decade. We concentrate on maximum flow problems and introduce a novel robust optimization model which, compared to known models from the literature, features several advantageous properties: (i) We consider a general class of path-based flow problems which can be used to model a large variety of network routing problems (and other packing problems). (ii) We aim at solutions that are robust against targeted attacks by a potent adversary who may attack any flow path of his choice on any edge of the network. (iii) In contrast to previous robust maximum flow models, for which no efficient algorithms are known, optimal robust flows for the most important basic variants of our model can be found in polynomial time. We also consider generalizations where the flow player can spend a budget to protect the network against the interdictor. Here, we show that the problem can be solved efficiently when the interdiction costs are determined by the flow player from scratch. However, the problem becomes hard to approximate when the flow player has to improve an initial protection infrastructure.
Creativity in Machine Learning
Venue: arXiv cs.CV 2016
Year: 2016

Recent machine learning techniques can be modified to produce creative results. Those results did not exist before; it is not a trivial combination of the data which was fed into the machine learning system. The obtained results come in multiple forms: As images, as text and as audio. This paper gives a high level overview of how they are created and gives some examples. It is meant to be a summary of the current work and give people who are new to machine learning some starting points.
Supervised Learning in Spiking Neural Networks for Precise Temporal Encoding
Venue: arXiv cs.NE 2016
Year: 2016

Precise spike timing as a means to encode information in neural networks is biologically supported, and is advantageous over frequency-based codes by processing input features on a much shorter time-scale. For these reasons, much recent attention has been focused on the development of supervised learning rules for spiking neural networks that utilise a temporal coding scheme. However, despite significant progress in this area, there still lack rules that have a theoretical basis, and yet can be considered biologically relevant. Here we examine the general conditions under which synaptic plasticity most effectively takes place to support the supervised learning of a precise temporal code. As part of our analysis we examine two spike-based learning methods: one of which relies on an instantaneous error signal to modify synaptic weights in a network (INST rule), and the other one on a filtered error signal for smoother synaptic weight modifications (FILT rule). We test the accuracy of the solutions provided by each rule with respect to their temporal encoding precision, and then measure the maximum number of input patterns they can learn to memorise using the precise timings of individual spikes as an indication of their storage capacity. Our results demonstrate the high performance of FILT in most cases, underpinned by the rule's error-filtering mechanism, which is predicted to provide smooth convergence towards a desired solution during learning. We also find FILT to be most efficient at performing input pattern memorisations, and most noticeably when patterns are identified using spikes with sub-millisecond temporal precision. In comparison with existing work, we determine the performance of FILT to be consistent with that of the highly efficient E-learning Chronotron, but with the distinct advantage that FILT is also implementable as an online method for increased biological realism.
Properties of Space MIMO Communication Channels
Venue: arXiv cs.IT 2016
Year: 2016

This paper discusses the characteristics of a space-to-space multiple-input, multiple-output (MIMO) communication channel that distinguish it from more common terrestrial MIMO communication channels. These characteristics imply that the channel matrices for space communication channels have a particularly simple structure that leads to statistical characteristics that are both predictable and readily controllable using clusters of satellites as distributed communication nodes. Furthermore, the extremely high cost of launching mass into space introduces a constraint into the channel capacity equation that leads to a spectral-efficiency vs. energy-efficiency tradeoff for space MIMO communication that is fundamentally different from the tradeoff that is generally considered applicable to terrestrial MIMO communication systems.
Formally Proving and Enhancing a Self-Stabilising Distributed Algorithm
Venue: arXiv cs.DC 2016
Year: 2016

This paper presents the benefits of formal modelling and verification techniques for self-stabilising distributed algorithms. An algorithm is studied, that takes a set of processes connected by a tree topology and converts it to a ring configuration. The Coloured Petri net model not only facilitates the proof that the algorithm is correct and self-stabilising but also easily shows that it enjoys new properties of termination and silentness. Further, the formal results show how the algorithm can be simplified without loss of generality.
A Class of Non-Linearly Solvable Networks
Venue: arXiv cs.IT 2016
Year: 2016

For each integer $m \geq 2$, a network is constructed which is solvable over an alphabet of size $m$ but is not solvable over any smaller alphabets. If $m$ is composite, then the network has no vector linear solution over any $R$-module alphabet and is not asymptotically linear solvable over any finite-field alphabet. The network's capacity is shown to equal one, and when $m$ is composite, its linear capacity is shown to be bounded away from one for all finite-field alphabets.
Streaming Big Data meets Backpressure in Distributed Network Computation
Venue: arXiv cs.NI 2016
Year: 2016

We study network response to queries that require computation of remotely located data and seek to characterize the performance limits in terms of maximum sustainable query rate that can be satisfied. The available resources include (i) a communication network graph with links over which data is routed, (ii) computation nodes, over which computation load is balanced, and (iii) network nodes that need to schedule raw and processed data transmissions. Our aim is to design a universal methodology and distributed algorithm to adaptively allocate resources in order to support maximum query rate. The proposed algorithms extend in a nontrivial way the backpressure (BP) algorithm to take into account computations operated over query streams. They contribute to the fundamental understanding of network computation performance limits when the query rate is limited by both the communication bandwidth and the computation capacity, a classical setting that arises in streaming big data applications in network clouds and fogs.
Placing Dynamic Content in Caches with Small Population
Venue: arXiv cs.NI 2016
Year: 2016

This paper addresses a fundamental limitation for the adoption of caching for wireless access networks due to small population sizes. This shortcoming is due to two main challenges: (i) making timely estimates of varying content popularity and (ii) inferring popular content from small samples. We propose a framework which alleviates such limitations. To timely estimate varying popularity in a context of a single cache we propose an Age-Based Threshold (ABT) policy which caches all contents requested more times than a threshold $\widetilde N(τ)$, where $τ$ is the content age. We show that ABT is asymptotically hit rate optimal in the many contents regime, which allows us to obtain the first characterization of the optimal performance of a caching system in a dynamic context. We then address small sample sizes focusing on $L$ local caches and one global cache. On the one hand we show that the global cache learns L times faster by aggregating all requests from local caches, which improves hit rates. On the other hand, aggregation washes out local characteristics of correlated traffic which penalizes hit rate. This motivates coordination mechanisms which combine global learning of popularity scores in clusters and LRU with prefetching.
Improved graph-based SFA: Information preservation complements the slowness principle
Venue: arXiv cs.CV 2016
Year: 2016

Slow feature analysis (SFA) is an unsupervised-learning algorithm that extracts slowly varying features from a multi-dimensional time series. A supervised extension to SFA for classification and regression is graph-based SFA (GSFA). GSFA is based on the preservation of similarities, which are specified by a graph structure derived from the labels. It has been shown that hierarchical GSFA (HGSFA) allows learning from images and other high-dimensional data. The feature space spanned by HGSFA is complex due to the composition of the nonlinearities of the nodes in the network. However, we show that the network discards useful information prematurely before it reaches higher nodes, resulting in suboptimal global slowness and an under-exploited feature space. To counteract these problems, we propose an extension called hierarchical information-preserving GSFA (HiGSFA), where information preservation complements the slowness-maximization goal. We build a 10-layer HiGSFA network to estimate human age from facial photographs of the MORPH-II database, achieving a mean absolute error of 3.50 years, improving the state-of-the-art performance. HiGSFA and HGSFA support multiple-labels and offer a rich feature space, feed-forward training, and linear complexity in the number of samples and dimensions. Furthermore, HiGSFA outperforms HGSFA in terms of feature slowness, estimation accuracy and input reconstruction, giving rise to a promising hierarchical supervised-learning approach.
Learning the Semantics of Structured Data Sources
Venue: arXiv cs.AI 2016
Year: 2016

Information sources such as relational databases, spreadsheets, XML, JSON, and Web APIs contain a tremendous amount of structured data that can be leveraged to build and augment knowledge graphs. However, they rarely provide a semantic model to describe their contents. Semantic models of data sources represent the implicit meaning of the data by specifying the concepts and the relationships within the data. Such models are the key ingredients to automatically publish the data into knowledge graphs. Manually modeling the semantics of data sources requires significant effort and expertise, and although desirable, building these models automatically is a challenging problem. Most of the related work focuses on semantic annotation of the data fields (source attributes). However, constructing a semantic model that explicitly describes the relationships between the attributes in addition to their semantic types is critical. We present a novel approach that exploits the knowledge from a domain ontology and the semantic models of previously modeled sources to automatically learn a rich semantic model for a new source. This model represents the semantics of the new source in terms of the concepts and relationships defined by the domain ontology. Given some sample data from the new source, we leverage the knowledge in the domain ontology and the known semantic models to construct a weighted graph that represents the space of plausible semantic models for the new source. Then, we compute the top k candidate semantic models and suggest to the user a ranked list of the semantic models for the new source. The approach takes into account user corrections to learn more accurate semantic models on future data sources. Our evaluation shows that our method generates expressive semantic models for data sources and services with minimal user input. ...