OpenRaiser/Intern-Atlas huggingface dataset:
The Hilbert Space of Probability Mass Functions and Applications on Probabilistic Inference
Venue: arXiv cs.IT 2015
Year: 2015

The Hilbert space of probability mass functions (pmf) is introduced in this thesis. A factorization method for multivariate pmfs is proposed by using the tools provided by the Hilbert space of pmfs. The resulting factorization is special for two reasons. First, it reveals the algebraic relations between the involved random variables. Second, it determines the conditional independence relations between the random variables. Due to the first property of the resulting factorization, it can be shown that channel decoders can be employed in the solution of probabilistic inference problems other than decoding. This approach might lead to new probabilistic inference algorithms and new hardware options for the implementation of these algorithms. An example of new inference algorithms inspired by the idea of using channel decoder for other inference tasks is a multiple-input multiple-output (MIMO) detection algorithm which has a complexity of the square-root of the optimum MIMO detection algorithm.
Information complexity is computable
Venue: arXiv cs.IT 2015
Year: 2015

The information complexity of a function $f$ is the minimum amount of information Alice and Bob need to exchange to compute the function $f$. In this paper we provide an algorithm for approximating the information complexity of an arbitrary function $f$ to within any additive error $α> 0$, thus resolving an open question as to whether information complexity is computable. In the process, we give the first explicit upper bound on the rate of convergence of the information complexity of $f$ when restricted to $b$-bit protocols to the (unrestricted) information complexity of $f$.
A Distributed Tracking Algorithm for Reconstruction of Graph Signals
Venue: arXiv cs.IT 2015
Year: 2015

The rapid development of signal processing on graphs provides a new perspective for processing large-scale data associated with irregular domains. In many practical applications, it is necessary to handle massive data sets through complex networks, in which most nodes have limited computing power. Designing efficient distributed algorithms is critical for this task. This paper focuses on the distributed reconstruction of a time-varying bandlimited graph signal based on observations sampled at a subset of selected nodes. A distributed least square reconstruction (DLSR) algorithm is proposed to recover the unknown signal iteratively, by allowing neighboring nodes to communicate with one another and make fast updates. DLSR uses a decay scheme to annihilate the out-of-band energy occurring in the reconstruction process, which is inevitably caused by the transmission delay in distributed systems. Proof of convergence and error bounds for DLSR are provided in this paper, suggesting that the algorithm is able to track time-varying graph signals and perfectly reconstruct time-invariant signals. The DLSR algorithm is numerically experimented with synthetic data and real-world sensor network data, which verifies its ability in tracking slowly time-varying graph signals.
Implementing Randomized Matrix Algorithms in Parallel and Distributed Environments
Venue: arXiv cs.DC 2015
Year: 2015

In this era of large-scale data, distributed systems built on top of clusters of commodity hardware provide cheap and reliable storage and scalable processing of massive data. Here, we review recent work on developing and implementing randomized matrix algorithms in large-scale parallel and distributed environments. Randomized algorithms for matrix problems have received a great deal of attention in recent years, thus far typically either in theory or in machine learning applications or with implementations on a single machine. Our main focus is on the underlying theory and practical implementation of random projection and random sampling algorithms for very large very overdetermined (i.e., overconstrained) $\ell_1$ and $\ell_2$ regression problems. Randomization can be used in one of two related ways: either to construct sub-sampled problems that can be solved, exactly or approximately, with traditional numerical methods; or to construct preconditioned versions of the original full problem that are easier to solve with traditional iterative algorithms. Theoretical results demonstrate that in near input-sparsity time and with only a few passes through the data one can obtain very strong relative-error approximate solutions, with high probability. Empirical results highlight the importance of various trade-offs (e.g., between the time to construct an embedding and the conditioning quality of the embedding, between the relative importance of computation versus communication, etc.) and demonstrate that $\ell_1$ and $\ell_2$ regression problems can be solved to low, medium, or high precision in existing distributed systems on up to terabyte-sized data.
Order-Optimal Rate of Caching and Coded Multicasting with Random Demands
Venue: arXiv cs.IT 2015
Year: 2015

We consider the canonical {\em shared link network} formed by a source node, hosting a library of $m$ information messages (files), connected via a noiseless common link to $n$ destination nodes (users), each with a cache of size M files. Users request files at random and independently, according to a given a-priori demand distribution $\qv$. A coding scheme for this network consists of a caching placement (i.e., a mapping of the library files into the user caches) and delivery scheme (i.e., a mapping for the library files and user demands into a common multicast codeword) such that, after the codeword transmission, all users can retrieve their requested file. The rate of the scheme is defined as the {\em average} codeword length normalized with respect to the length of one file, where expectation is taken over the random user demands. For the same shared link network, in the case of deterministic demands, the optimal min-max rate has been characterized within a uniform bound, independent of the network parameters. In particular, fractional caching (i.e., storing file segments) and using linear network coding has been shown to provide a min-max rate reduction proportional to 1/M with respect to standard schemes such as unicasting or "naive" uncoded multicasting. The case of random demands was previously considered by applying the same order-optimal min-max scheme separately within groups of files requested with similar probability. However, no order-optimal guarantee was provided for random demands under the average rate performance criterion. In this paper, we consider the random demand setting and provide general achievability and converse results. In particular, we consider a family of schemes that combine random fractional caching according to a probability distribution $\pv$ that depends on the demand distribution $\qv$, with a linear coded delivery scheme based on ...
Benchmarking in Manipulation Research: The YCB Object and Model Set and Benchmarking Protocols
Venue: arXiv cs.RO 2015
Year: 2015

In this paper we present the Yale-CMU-Berkeley (YCB) Object and Model set, intended to be used to facilitate benchmarking in robotic manipulation, prosthetic design and rehabilitation research. The objects in the set are designed to cover a wide range of aspects of the manipulation problem; it includes objects of daily life with different shapes, sizes, textures, weight and rigidity, as well as some widely used manipulation tests. The associated database provides high-resolution RGBD scans, physical properties, and geometric models of the objects for easy incorporation into manipulation and planning software platforms. In addition to describing the objects and models in the set along with how they were chosen and derived, we provide a framework and a number of example task protocols, laying out how the set can be used to quantitatively evaluate a range of manipulation approaches including planning, learning, mechanical design, control, and many others. A comprehensive literature survey on existing benchmarks and object datasets is also presented and their scope and limitations are discussed. The set will be freely distributed to research groups worldwide at a series of tutorials at robotics conferences, and will be otherwise available at a reasonable purchase cost. It is our hope that the ready availability of this set along with the ground laid in terms of protocol templates will enable the community of manipulation researchers to more easily compare approaches as well as continually evolve benchmarking tests as the field matures.
The CEO Problem with Secrecy Constraints
Venue: arXiv cs.IT 2015
Year: 2015

We study a lossy source coding problem with secrecy constraints in which a remote information source should be transmitted to a single destination via multiple agents in the presence of a passive eavesdropper. The agents observe noisy versions of the source and independently encode and transmit their observations to the destination via noiseless rate-limited links. The destination should estimate the remote source based on the information received from the agents within a certain mean distortion threshold. The eavesdropper, with access to side information correlated to the source, is able to listen in on one of the links from the agents to the destination in order to obtain as much information as possible about the source. This problem can be viewed as the so-called CEO problem with additional secrecy constraints. We establish inner and outer bounds on the rate-distortion-equivocation region of this problem. We also obtain the region in special cases where the bounds are tight. Furthermore, we study the quadratic Gaussian case and provide the optimal rate-distortion-equivocation region when the eavesdropper has no side information and an achievable region for a more general setup with side information at the eavesdropper.
Necessary conditions for tractability of valued CSPs
Venue: arXiv cs.CC 2015
Year: 2015

The connection between constraint languages and clone theory has been a fruitful line of research on the complexity of constraint satisfaction problems. In a recent result, Cohen et al. [SICOMP'13] have characterised a Galois connection between valued constraint languages and so-called weighted clones. In this paper, we study the structure of weighted clones. We extend the results of Creed and Zivny from [CP'11/SICOMP'13] on types of weightings necessarily contained in every nontrivial weighted clone. This result has immediate computational complexity consequences as it provides necessary conditions for tractability of weighted clones and thus valued constraint languages. We demonstrate that some of the necessary conditions are also sufficient for tractability, while others are provably not.
Spectral Sparsification of Random-Walk Matrix Polynomials
Venue: arXiv cs.DS 2015
Year: 2015

We consider a fundamental algorithmic question in spectral graph theory: Compute a spectral sparsifier of random-walk matrix-polynomial $$L_α(G)=D-\sum_{r=1}^dα_rD(D^{-1}A)^r$$ where $A$ is the adjacency matrix of a weighted, undirected graph, $D$ is the diagonal matrix of weighted degrees, and $α=(α_1...α_d)$ are nonnegative coefficients with $\sum_{r=1}^dα_r=1$. Recall that $D^{-1}A$ is the transition matrix of random walks on the graph. The sparsification of $L_α(G)$ appears to be algorithmically challenging as the matrix power $(D^{-1}A)^r$ is defined by all paths of length $r$, whose precise calculation would be prohibitively expensive. In this paper, we develop the first nearly linear time algorithm for this sparsification problem: For any $G$ with $n$ vertices and $m$ edges, $d$ coefficients $α$, and $ε> 0$, our algorithm runs in time $O(d^2m\log^2n/ε^{2})$ to construct a Laplacian matrix $\tilde{L}=D-\tilde{A}$ with $O(n\log n/ε^{2})$ non-zeros such that $\tilde{L}\approx_εL_α(G)$. Matrix polynomials arise in mathematical analysis of matrix functions as well as numerical solutions of matrix equations. Our work is particularly motivated by the algorithmic problems for speeding up the classic Newton's method in applications such as computing the inverse square-root of the precision matrix of a Gaussian random field, as well as computing the $q$th-root transition (for $q\geq1$) in a time-reversible Markov model. The key algorithmic step for both applications is the construction of a spectral sparsifier of a constant degree random-walk matrix-polynomials introduced by Newton's method. Our algorithm can also be used to build efficient data structures for effective resistances for multi-step time-reversible Markov models, and we anticipate that it could be useful for other tasks in network analysis.
Supervised LogEuclidean Metric Learning for Symmetric Positive Definite Matrices
Venue: arXiv cs.LG 2015
Year: 2015

Metric learning has been shown to be highly effective to improve the performance of nearest neighbor classification. In this paper, we address the problem of metric learning for Symmetric Positive Definite (SPD) matrices such as covariance matrices, which arise in many real-world applications. Naively using standard Mahalanobis metric learning methods under the Euclidean geometry for SPD matrices is not appropriate, because the difference of SPD matrices can be a non-SPD matrix and thus the obtained solution can be uninterpretable. To cope with this problem, we propose to use a properly parameterized LogEuclidean distance and optimize the metric with respect to kernel-target alignment, which is a supervised criterion for kernel learning. Then the resulting non-trivial optimization problem is solved by utilizing the Riemannian geometry. Finally, we experimentally demonstrate the usefulness of our LogEuclidean metric learning algorithm on real-world classification tasks for EEG signals and texture patches.
Estimating Minimum Sum-rate for Cooperative Data Exchange
Venue: arXiv cs.IT 2015
Year: 2015

This paper considers how to accurately estimate the minimum sum-rate so as to reduce the complexity of solving cooperative data exchange (CDE) problems. The CDE system contains a number of geographically close clients who send packets to help the others recover an entire packet set. The minimum sum-rate is the minimum value of total number of transmissions that achieves universal recovery (the situation when all the clients recover the whole packet set). Based on a necessary and sufficient condition for a supermodular base polyhedron to be nonempty, we show that the minimum sum-rate for a CDE system can be determined by a maximization over all possible partitions of the client set. Due to the high complexity of solving this maximization problem, we propose a deterministic algorithm to approximate a lower bound on the minimum sum-rate. We show by experiments that this lower bound is much tighter than those lower bounds derived in the existing literature. We also show that the deterministic algorithm prevents from repetitively running the existing algorithms for solving CDE problems so that the overall complexity can be reduced accordingly.
A Method of Evaluating Effect of QoS Degradation on Multidimensional QoE of Web Service with ISO - based Usability
Venue: arXiv cs.NI 2015
Year: 2015

This paper studies a method of investigating effect of IP performance (QoS) degradation on quality of experience (QoE) for a Web service; it considers the usability based on the ISO 9241-11 as multidimensional QoE of a Web service (QoE-Web) and the QoS parameters standardized by the IETF. Moreover, the paper tackles clarification of the relationship between ISO-based QoE-Web and IETF-based QoS by the multiple regression analysis. The experiment is intended for the two actual Japanese online shopping services and utilizes 35 subjects. From the results, the paper quantitatively discusses how the QoE-Web deteriorates owing to the QoS degradation and shows that it is appropriate to evaluate the proposed method.
Multiresolution Division Multiplex (MRDM): A New Wavelet-based Multiplex System
Venue: arXiv cs.IT 2015
Year: 2015

An original multiplex scheme is introduced, which is based on Mallat's multiresolution formulation of wavelet systems. This system is adaptable and its implementation is well matched to digital signal processors and computers. The approach termed multiresolution division multiplex (MRDM) is intensive in signal processing (SP) tools, extremely flexible and can combine a variety of tributaries at different bit rates. A broad variety of orthogonal wavelet systems can endow with MRDM and the channel waveforms, and consequently the spectral shape and system performance depend upon the selected wavelets. Demultiplex can be done efficiently, since the number of floating multiplications and additions increase only linearly with the length of signals. A Haar-based MRDM scheme is presented to illustrate the versatility of this new multiplex approach.
Separation of sinusoidal and chirp components using Compressive sensing approach
Venue: arXiv cs.IT 2015
Year: 2015

In this paper we deal with the linear frequency modulated signals and radar signals that are affected by disturbance which is the inevitable phenomenon in everyday communications. The considered cases represent the cases when the signals of interest overlap with other signals or with noise. In order to successfully separate these signals we propose the compressive sensing method, which states that the useful signal part can be separated successfully from a small amount of measurements as long as the acquired signal can be presented as sparse in a certain transformation domain. The effectiveness of our approach is proven experimentally through examples.
Regularized ZF in Cooperative Broadcast Channels under Distributed CSIT: A Large System Analysis
Venue: arXiv cs.IT 2015
Year: 2015

Obtaining accurate Channel State Information (CSI) at the transmitters (TX) is critical to many cooperation schemes such as Network MIMO, Interference Alignment etc. Practical CSI feedback and limited backhaul-based sharing inevitably creates degradations of CSI which are specific to each TX, giving rise to a distributed form of CSI. In the Distributed CSI (D-CSI) broadcast channel setting, the various TXs design elements of the precoder based on their individual estimates of the global multiuser channel matrix, which intuitively degrades performance when compared with the commonly used centralized CSI assumption. This paper tackles this challenging scenario and presents a first analysis of the rate performance for the distributed CSI multi-TX broadcast channel setting, in the large number of antenna regime. Using Random Matrix Theory (RMT) tools, we derive deterministic equivalents of the Signal to Interference plus Noise Ratio (SINR) for the popular regularized Zero-Forcing (ZF) precoder, allowing to unveil the price of distributedness for such cooperation methods.
assistME: A Platform for Assisting Engineers in Maintaining the Factory Pipeline
Venue: arXiv cs.HC 2015
Year: 2015

In this position paper, we present our approach of utilizing mobile devices (i.e., mobile phones and tablets) for assisting engineers and experts in understanding and maintaining the factory pipelines. For this, we present a platform, called assistME, that is composed of three main components: the assistME Server, the assistME mobile infrastructure, and the co-assistME collaborative environment. In order to get full utilization of the assistME platform, we assume that an initial setup is made in the factory in such a way that it is equipped with different sensors to collect data about specific events in the factory pipeline together with the corresponding locations of these events. The assistME Server works as a central control unit in the platform and collects data from the installed sensors in the factory pipeline. In the case of any unexpected behavior or any critical situation in the factory pipeline, notification and other details are sent to the related group of engineers and experts through the assistME mobile app. Further, the co-assistME collaborative environment, equipped with a large shared screen and multiple mobile devices, helps the engineers and experts to collaborate with to understand and analyze the current situation in the factory pipeline in order to maintain it accurately.
Applying deep learning techniques on medical corpora from the World Wide Web: a prototypical system and evaluation
Venue: arXiv cs.CL 2015
Year: 2015

BACKGROUND: The amount of biomedical literature is rapidly growing and it is becoming increasingly difficult to keep manually curated knowledge bases and ontologies up-to-date. In this study we applied the word2vec deep learning toolkit to medical corpora to test its potential for identifying relationships from unstructured text. We evaluated the efficiency of word2vec in identifying properties of pharmaceuticals based on mid-sized, unstructured medical text corpora available on the web. Properties included relationships to diseases ('may treat') or physiological processes ('has physiological effect'). We compared the relationships identified by word2vec with manually curated information from the National Drug File - Reference Terminology (NDF-RT) ontology as a gold standard. RESULTS: Our results revealed a maximum accuracy of 49.28% which suggests a limited ability of word2vec to capture linguistic regularities on the collected medical corpora compared with other published results. We were able to document the influence of different parameter settings on result accuracy and found and unexpected trade-off between ranking quality and accuracy. Pre-processing corpora to reduce syntactic variability proved to be a good strategy for increasing the utility of the trained vector models. CONCLUSIONS: Word2vec is a very efficient implementation for computing vector representations and for its ability to identify relationships in textual data without any prior domain knowledge. We found that the ranking and retrieved results generated by word2vec were not of sufficient quality for automatic population of knowledge bases and ontologies, but could serve as a starting point for further manual curation.
On Galois-Division Multiple Access Systems: Figures of Merit and Performance Evaluation
Venue: arXiv cs.IT 2015
Year: 2015

A new approach to multiple access based on finite field transforms is investigated. These schemes, termed Galois-Division Multiple Access (GDMA), offer compact bandwidth requirements. A new digital transform, the Finite Field Hartley Transform (FFHT) requires to deal with fields of characteristic p, p \neq 2. A binary-to-p-ary (p \neq 2) mapping based on the opportunistic secondary channel is introduced. This allows the use of GDMA in conjunction with available digital systems. The performance of GDMA is also evaluated.
An Open-Source Monitoring System for Remote Solar Power Applications
Venue: arXiv cs.CY 2015
Year: 2015

Renewable energy systems are an increasingly popular way to generate electricity. As with any new technological paradigm, new challenges have emerged which are unique to the utilization of renewable energy systems. One of these challenges in particular is the development of effective monitoring technologies to compensate for the decentralized nature of remote power generation. This project details the development of an open-source monitoring system for remote solar power systems. The problem space that this project is specifically concerned with deals with the reduction of cost and the use of open platforms to make solar monitoring viable in developing countries where both the resources and general knowledge required to undertake such efforts are particularly scarce. Currently, solar monitoring technologies are expensive, limited in their application, and for the most part proprietary. It is arguable that such systems can be developed using non-customized hardware and open-source software that can be obtained and run anywhere in the world. This project is one such argument. This proof of concept is sufficient to show that solar remote monitoring is neither expensive nor particularly cumbersome to implement and thus warrants further investigation and development by the open source community.