OpenRaiser/Intern-Atlas huggingface dataset:
Low Complexity Opportunistic Interference Alignment in $K$-Transmitter MIMO Interference Channels
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we propose low complexity opportunistic methods for interference alignment in $K$-transmitter MIMO interference channels by exploiting multiuser diversity. We do not assume availability of channel state information (CSI) at the transmitters. Receivers are required to feed back analog values indicating the extent to which the received interference subspaces are aligned. The proposed opportunistic interference alignment (OIA) achieves sum-rate comparable to conventional OIA schemes but with a significantly reduced computational complexity.
A Tool for Computing and Estimating the Volume of the Solution Space of SMT(LA)
Venue: arXiv cs.AI 2015
Year: 2015

There are already quite a few tools for solving the Satisfiability Modulo Theories (SMT) problems. In this paper, we present \texttt{VolCE}, a tool for counting the solutions of SMT constraints, or in other words, for computing the volume of the solution space. Its input is essentially a set of Boolean combinations of linear constraints, where the numeric variables are either all integers or all reals, and each variable is bounded. The tool extends SMT solving with integer solution counting and volume computation/estimation for convex polytopes. Effective heuristics are adopted, which enable the tool to deal with high-dimensional problem instances efficiently and accurately.
Convergence of Laplacian spectra from random samples
Venue: arXiv cs.IT 2015
Year: 2015

Eigenvectors and eigenvalues of discrete graph Laplacians are often used for manifold learning and nonlinear dimensionality reduction. It was previously proved by Belkin and Niyogi that the eigenvectors and eigenvalues of the graph Laplacian converge to the eigenfunctions and eigenvalues of the Laplace-Beltrami operator of the manifold in the limit of infinitely many data points sampled independently from the uniform distribution over the manifold. Recently, we introduced Point Integral method (PIM) to solve elliptic equations and corresponding eigenvalue problem on point clouds. We have established a unified framework to approximate the elliptic differential operators on point clouds. In this paper, we prove that the eigenvectors and eigenvalues obtained by PIM converge in the limit of infinitely many random samples independently from a distribution (not necessarily to be uniform distribution). Moreover, one estimate of the rate of the convergence is also given.
Precoding in Multigateway Multibeam Satellite Systems
Venue: arXiv cs.IT 2015
Year: 2015

This paper considers a multigateway multibeam satellite system with multiple feeds per beam. In these systems, each gateway serves a set of beams (cluster) so that the overall data traffic is generated at different geographical areas. Full frequency reuse among beams is considered so that interference mitigation techniques are mandatory. Precisely, this paper aims at designing the precoding scheme which, in contrast to single gateway schemes, entails two main challenges. First, the precoding matrix shall be separated into feed groups assigned to each gateway. Second, complete channel state information (CSI) is required at each gateway, leading to a large communication overhead. In order to solve these problems, a design based on a regularized singular value block decomposition of the channel matrix is presented so that both inter-cluster (i.e. beams of different clusters) and intra-cluster (i.e. beams of the same cluster) interference is minimized. In addition, different gateway cooperative schemes are analysed in order to keep the inter-gateway communication low. Furthermore, the impact of the feeder link interference (i.e. interference between different feeder links) is analysed and it is shown both numerically and analytically that the system performance is reduced severally whenever this interference occurs even though precoding reverts this additional interference. Finally, numerical simulations are shown considering the latest fixed broadband communication standard DVB-S2X so that the quantized feedback effect is evaluated. The proposed precoding technique results to achieve a performance close to the single gateway operation even when the cooperation among gateways is low.
Global stabilization of classes of linear control systems with bounds on the feedback and its successive derivatives
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, we address the problem of globally stabilizing a linear time-invariant (LTI) system by means of a static feedback law whose amplitude and successive time derivatives, up to a prescribed order $p$, are bounded by arbitrary prescribed values. We solve this problem for two classes of LTI systems, namely integrator chains and skew-symmetric systems with single input. For the integrator chains, the solution we propose is based on the nested saturations introduced by A.R. Teel. We show that this construction fails for skew-symmetric systems and propose an alternative feedback law. We illustrate these findings by the stabilization of the third order integrator with prescribed bounds on the feedback and its first two derivatives, and similarly for the harmonic oscillator with prescribed bounds on the feedback and its first derivative.
Network Lasso: Clustering and Optimization in Large Graphs
Venue: arXiv cs.SI 2015
Year: 2015

Convex optimization is an essential tool for modern data analysis, as it provides a framework to formulate and solve many problems in machine learning and data mining. However, general convex optimization solvers do not scale well, and scalable solvers are often specialized to only work on a narrow class of problems. Therefore, there is a need for simple, scalable algorithms that can solve many common optimization problems. In this paper, we introduce the \emph{network lasso}, a generalization of the group lasso to a network setting that allows for simultaneous clustering and optimization on graphs. We develop an algorithm based on the Alternating Direction Method of Multipliers (ADMM) to solve this problem in a distributed and scalable manner, which allows for guaranteed global convergence even on large graphs. We also examine a non-convex extension of this approach. We then demonstrate that many types of problems can be expressed in our framework. We focus on three in particular - binary classification, predicting housing prices, and event detection in time series data - comparing the network lasso to baseline approaches and showing that it is both a fast and accurate method of solving large optimization problems.
Using Fisher Information In Big Data
Venue: arXiv cs.IT 2015
Year: 2015

In this era of Big Data, proficient use of data mining is the key to capture useful information from any dataset. As numerous data mining techniques make use of information theory concepts, in this paper, we discuss how Fisher information (FI) can be applied to analyze patterns in Big Data. The main advantage of FI is its ability to combine multiple variables together to inform us on the overall trends and stability of a system. It can therefore detect whether a system is losing dynamic order and stability, which may serve as a signal of an impending regime shift. In this work, we first provide a brief overview of Fisher information theory, followed by a simple step-by-step numerical example on how to compute FI. Finally, as a numerical demonstration, we calculate the evolution of FI for GDP per capita (current US Dollar) and total population of the USA from 1960 to 2013.
Fast Blocked Clause Decomposition with High Quality
Venue: arXiv cs.LO 2015
Year: 2015

Any CNF formula can be decomposed two blocked subsets such that both can be solved by BCE (Blocked Clause Elimination). To make the decomposition more useful, one hopes to have the decomposition as unbalanced as possible. It is often time consuming to achieve this goal. So far there have been several decomposition and post-processing algorithms such as PureDecompose, QuickDecompose, EagerMover etc. We found that these existing algorithms are often either inefficient or low-quality decomposition. This paper aims at improving the decomposition quality, while keeping the runtime of algorithms under control. To achieve this goal, we improve the existing BCE, and present two new variants of PureDecompose, a new heuristic decomposition called LessInterfereDecompose, and a new post-processing algorithm called RsetGuidedDecompose. Combining these new techniques results in a new algorithm called MixDecompose. In our experiments, there is no application formula where the quality of PureDecompose+EagerMover is better than MixDecompose. In terms of speed, MixDecompose is also very fast. Our average runtime is a little longer, but the worst-case runtime is shorter. In theory, our two variants of PureDecompose requires linear time in the number of clauses. By limiting the size of the touch list used by BCE, we can guarantee always that MixDecompose runs in linear time.
Non-convex Regularizations for Feature Selection in Ranking With Sparse SVM
Venue: arXiv cs.LG 2015
Year: 2015

Feature selection in learning to rank has recently emerged as a crucial issue. Whereas several preprocessing approaches have been proposed, only a few works have been focused on integrating the feature selection into the learning process. In this work, we propose a general framework for feature selection in learning to rank using SVM with a sparse regularization term. We investigate both classical convex regularizations such as $\ell\_1$ or weighted $\ell\_1$ and non-convex regularization terms such as log penalty, Minimax Concave Penalty (MCP) or $\ell\_p$ pseudo norm with $p\textless{}1$. Two algorithms are proposed, first an accelerated proximal approach for solving the convex problems, second a reweighted $\ell\_1$ scheme to address the non-convex regularizations. We conduct intensive experiments on nine datasets from Letor 3.0 and Letor 4.0 corpora. Numerical results show that the use of non-convex regularizations we propose leads to more sparsity in the resulting models while prediction performance is preserved. The number of features is decreased by up to a factor of six compared to the $\ell\_1$ regularization. In addition, the software is publicly available on the web.
Embedding rationally independent languages into maximal ones
Venue: arXiv cs.FL 2015
Year: 2015

We consider the embedding problem in coding theory: given an independence (a code-related property) and an independent language $L$, find a maximal independent language containing $L$. We consider the case where the code-related property is defined via a rational binary relation that is decreasing with respect to any fixed total order on the set of words. Our method works by iterating a max-min operator that has been used before for the embedding problem for properties defined by length-increasing-and-transitive binary relations. By going to order-decreasing rational relations, represented by input-decreasing transducers, we are able to include many known properties from both the noiseless and noisy domains of coding theory, as well as any combination of such properties. Moreover, in many cases the desired maximal embedding is effectively computable.
Assume-Admissible Synthesis
Venue: arXiv cs.LO 2015
Year: 2015

In this paper, we introduce a novel rule for synthesis of reactive systems, applicable to systems made of n components which have each their own objectives. It is based on the notion of admissible strategies. We compare our novel rule with previous rules defined in the literature, and we show that contrary to the previous proposals, our rule defines sets of solutions which are rectangular. This property leads to solutions which are robust and resilient. We provide algorithms with optimal complexity and also an abstraction framework.
Analytical Derivation of the Inverse Moments of One-sided Correlated Gram Matrices with Applications
Venue: arXiv cs.IT 2015
Year: 2015

This paper addresses the development of analytical tools for the computation of the moments of random Gram matrices with one side correlation. Such a question is mainly driven by applications in signal processing and wireless communications wherein such matrices naturally arise. In particular, we derive closed-form expressions for the inverse moments and show that the obtained results can help approximate several performance metrics such as the average estimation error corresponding to the Best Linear Unbiased Estimator (BLUE) and the Linear Minimum Mean Square Error LMMSE or also other loss functions used to measure the accuracy of covariance matrix estimates.
Approximation Algorithms for Connected Maximum Cut and Related Problems
Venue: arXiv cs.DS 2015
Year: 2015

An instance of the Connected Maximum Cut problem consists of an undirected graph G = (V, E) and the goal is to find a subset of vertices S $\subseteq$ V that maximizes the number of edges in the cut δ(S) such that the induced graph G[S] is connected. We present the first non-trivial Ω(1/log n) approximation algorithm for the connected maximum cut problem in general graphs using novel techniques. We then extend our algorithm to an edge weighted case and obtain a poly-logarithmic approximation algorithm. Interestingly, in stark contrast to the classical max-cut problem, we show that the connected maximum cut problem remains NP-hard even on unweighted, planar graphs. On the positive side, we obtain a polynomial time approximation scheme for the connected maximum cut problem on planar graphs and more generally on graphs with bounded genus.
A note on the substructural hierarchy
Venue: arXiv cs.LO 2015
Year: 2015

We prove that all axiomatic extensions of the full Lambek calculus with exchange can be axiomatized by formulas on the $\mathcal N_3$ level of the substructural hierarchy.
Theory of Programs
Venue: arXiv cs.PL 2015
Year: 2015

A general theory of programs, programming and programming languages built up from a few concepts of elementary set theory. Derives, as theorems, properties treated as axioms by classic approaches to programming. Covers sequential and concurrent computation.
Incentivizing Exploration In Reinforcement Learning With Deep Predictive Models
Venue: arXiv cs.AI 2015
Year: 2015

Achieving efficient and scalable exploration in complex domains poses a major challenge in reinforcement learning. While Bayesian and PAC-MDP approaches to the exploration problem offer strong formal guarantees, they are often impractical in higher dimensions due to their reliance on enumerating the state-action space. Hence, exploration in complex domains is often performed with simple epsilon-greedy methods. In this paper, we consider the challenging Atari games domain, which requires processing raw pixel inputs and delayed rewards. We evaluate several more sophisticated exploration strategies, including Thompson sampling and Boltzman exploration, and propose a new exploration method based on assigning exploration bonuses from a concurrently learned model of the system dynamics. By parameterizing our learned model with a neural network, we are able to develop a scalable and efficient approach to exploration bonuses that can be applied to tasks with complex, high-dimensional state spaces. In the Atari domain, our method provides the most consistent improvement across a range of games that pose a major challenge for prior methods. In addition to raw game-scores, we also develop an AUC-100 metric for the Atari Learning domain to evaluate the impact of exploration on this benchmark.
Ridge Regression, Hubness, and Zero-Shot Learning
Venue: arXiv cs.LG 2015
Year: 2015

This paper discusses the effect of hubness in zero-shot learning, when ridge regression is used to find a mapping between the example space to the label space. Contrary to the existing approach, which attempts to find a mapping from the example space to the label space, we show that mapping labels into the example space is desirable to suppress the emergence of hubs in the subsequent nearest neighbor search step. Assuming a simple data model, we prove that the proposed approach indeed reduces hubness. This was verified empirically on the tasks of bilingual lexicon extraction and image labeling: hubness was reduced with both of these tasks and the accuracy was improved accordingly.
Logic as a complex network
Venue: arXiv cs.SI 2015
Year: 2015

When we represent logical, connective implications by directed edges, the resulting set of directed edges can be regarded as a complex network. In this article, we compose a network model that represents a deductive-logic-like structure composed solely of implications. The proposed network model grows like the BA model reported by Barabasi and Albert [Science 286, 509 (1999)]. Though the BA model references the whole of the existing network when a node is added, our model references only part of the existing network. In this view, our model is more realistic than the BA model. However, it also exhibits power law characteristics.
Describing Multimedia Content using Attention-based Encoder--Decoder Networks
Venue: arXiv cs.NE 2015
Year: 2015

Whereas deep neural networks were first mostly used for classification tasks, they are rapidly expanding in the realm of structured output problems, where the observed target is composed of multiple random variables that have a rich joint distribution, given the input. We focus in this paper on the case where the input also has a rich structure and the input and output structures are somehow related. We describe systems that learn to attend to different places in the input, for each element of the output, for a variety of tasks: machine translation, image caption generation, video clip description and speech recognition. All these systems are based on a shared set of building blocks: gated recurrent neural networks and convolutional neural networks, along with trained attention mechanisms. We report on experimental results with these systems, showing impressively good performance and the advantage of the attention mechanism.
A Diffusion-Neuron Hybrid System for Molecular Communication
Venue: arXiv cs.ET 2015
Year: 2015

Diffusion-based and neural communication are two interesting domains in molecular communication. Both of them have distinct advantages and are exploited separately in many works. However, in some cases, neural and diffusion-based ways have to work together for a communication. Therefore, in this paper, we propose a hybrid communication system, in which the diffusion-based and neural communication channels are contained. Multiple connection nano-devices (CND) are used to connect the two channels. We define the practice function of the CNDs and develop the mechanism of exchanging information from diffusion-based to neural channel, based on the biological characteristics of the both channels. In addition, we establish a brief mathematical model to present the complete communication process of the hybrid system. The information exchange process at the CNDs is shown in the simulation. The bit error rate (BER) indicator is used to verify the reliability of communication. The result reveals that based on the biological channels, optimizing some parameters of nano-devices could improve the reliability performance.
On Web-grid Implementation Using Single System Image
Venue: arXiv cs.DC 2015
Year: 2015

With the latest innovations and trend towards personalizing users' web browsing experience, the web has been increasingly dominated by dynamic contents. However, delivering dynamic content remains a challenge due to the many dependencies involved in compiling the content, specifically personalized ones. This paper presents the use of Single System Image (SSI) clustering systems for a cheap, off-the-shelf, local lightweight distributed web-grid composed of desktop PCs. The three clustering systems considered in the study are Kerrighed, OpenSSI and openMosix. Through an online simulation technique, the performance savings achieved by the clustering systems were measured. Results showed that Kerrighed has the least number of missed requests while the response time is comparable with the rest.
Preferential Attachment in an Internet-mediated Human Network
Venue: arXiv cs.SI 2015
Year: 2015

In the advent of the Internet, web-mediated social networking has become of great influence to Filipinos. Networking sites such as Friendster, YouTube, FaceBook and MySpace are among the most well known sites on the Internet. These sites provide a wide range of services to users from different parts of the world, such as connecting and finding people, as well as, sharing and organizing contents. The popularity and accessibility of these sites enable information to be available. These allow people to analyze and study the characteristics of the population of online social networks. In this study, we developed a computer program to analyze the structural dynamics of a locally popular social networking site: The Friendster Network. Understanding the structural dynamics of a virtual community has many implications, such as finding an improvement on the current networking system, among others. Based on our analysis, we found out that users of the site exhibit preferential attachment to users with high number of friends.
PanoSwarm: Collaborative and Synchronized Multi-Device Panoramic Photography
Venue: arXiv cs.HC 2015
Year: 2015

Taking a picture has been traditionally a one-persons task. In this paper we present a novel system that allows multiple mobile devices to work collaboratively in a synchronized fashion to capture a panorama of a highly dynamic scene, creating an entirely new photography experience that encourages social interactions and teamwork. Our system contains two components: a client app that runs on all participating devices, and a server program that monitors and communicates with each device. In a capturing session, the server collects in realtime the viewfinder images of all devices and stitches them on-the-fly to create a panorama preview, which is then streamed to all devices as visual guidance. The system also allows one camera to be the host and to send direct visual instructions to others to guide camera adjustment. When ready, all devices take pictures at the same time for panorama stitching. Our preliminary study suggests that the proposed system can help users capture high quality panoramas with an enjoyable teamwork experience. A demo video of the system in action is provided at http://youtu.be/PwQ6k_ZEQSs.
Kernel Based Sequential Data Anomaly Detection in Business Process Event Logs
Venue: arXiv cs.SE 2015
Year: 2015

Business Process Management Systems (BPMS) log events and traces of activities during the execution of a process. Anomalies are defined as deviation or departure from the normal or common order. Anomaly detection in business process logs has several applications such as fraud detection and understanding the causes of process errors. In this paper, we present a novel approach for anomaly detection in business process logs. We model the event logs as a sequential data and apply kernel based anomaly detection techniques to identify outliers and discordant observations. Our technique is unsupervised (does not require a pre-annotated training dataset), employs kNN (k-nearest neighbor) kernel based technique and normalized longest common subsequence (LCS) similarity measure. We conduct experiments on a recent, large and real-world incident management data of an enterprise and demonstrate that our approach is effective.