OpenRaiser/Intern-Atlas huggingface dataset:
Orthogonal AMP
Venue: arXiv cs.IT 2017
Year: 2017

Approximate message passing (AMP) is a low-cost iterative signal recovery algorithm for linear system models. When the system transform matrix has independent identically distributed (IID) Gaussian entries, the performance of AMP can be asymptotically characterized by a simple scalar recursion called state evolution (SE). However, SE may become unreliable for other matrix ensembles, especially for ill-conditioned ones. This imposes limits on the applications of AMP. In this paper, we propose an orthogonal AMP (OAMP) algorithm based on de-correlated linear estimation (LE) and divergence-free non-linear estimation (NLE). The Onsager term in standard AMP vanishes as a result of the divergence-free constraint on NLE. We develop an SE procedure for OAMP and show numerically that the SE for OAMP is accurate for general unitarily-invariant matrices, including IID Gaussian matrices and partial orthogonal matrices. We further derive optimized options for OAMP and show that the corresponding SE fixed point coincides with the optimal performance obtained via the replica method. Our numerical results demonstrate that OAMP can be advantageous over AMP, especially for ill-conditioned matrices
Modelling homogeneous generative meta-programming
Venue: arXiv cs.PL 2017
Year: 2017

Homogeneous generative meta-programming (HGMP) enables the generation of program fragments at compile-time or run-time. We present the first foundational calculus which can model powerful HGMP languages such as Template Haskell. The calculus is designed such that we can gradually enhance it with the features needed to model many of the advanced features of real languages. As a demonstration of the flexibility of our approach, we also provide a simple type system for the calculus.
Non-preemptive Scheduling in a Smart Grid Model and its Implications on Machine Minimization
Venue: arXiv cs.DS 2017
Year: 2017

We study a scheduling problem arising in demand response management in smart grid. Consumers send in power requests with a flexible feasible time interval during which their requests can be served. The grid controller, upon receiving power requests, schedules each request within the specified interval. The electricity cost is measured by a convex function of the load in each timeslot. The objective is to schedule all requests with the minimum total electricity cost. Previous work has studied cases where jobs have unit power requirement and unit duration. We extend the study to arbitrary power requirement and duration, which has been shown to be NP-hard. We give the first online algorithm for the general problem, and prove that the problem is fixed parameter tractable. We also show that the online algorithm is asymptotically optimal when the objective is to minimize the peak load. In addition, we observe that the classical non-preemptive machine minimization problem is a special case of the smart grid problem with min-peak objective, and show that we can solve the non-preemptive machine minimization problem asymptotically optimally.
Semi-supervised Clustering for Short Text via Deep Representation Learning
Venue: arXiv cs.CL 2017
Year: 2017

In this work, we propose a semi-supervised method for short text clustering, where we represent texts as distributed vectors with neural networks, and use a small amount of labeled data to specify our intention for clustering. We design a novel objective to combine the representation learning process and the k-means clustering process together, and optimize the objective with both labeled data and unlabeled data iteratively until convergence through three steps: (1) assign each short text to its nearest centroid based on its representation from the current neural networks; (2) re-estimate the cluster centroids based on cluster assignments from step (1); (3) update neural networks according to the objective by keeping centroids and cluster assignments fixed. Experimental results on four datasets show that our method works significantly better than several other text clustering methods.
Sentence Similarity Learning by Lexical Decomposition and Composition
Venue: arXiv cs.CL 2017
Year: 2017

Most conventional sentence similarity methods only focus on similar parts of two input sentences, and simply ignore the dissimilar parts, which usually give us some clues and semantic meanings about the sentences. In this work, we propose a model to take into account both the similarities and dissimilarities by decomposing and composing lexical semantics over sentences. The model represents each word as a vector, and calculates a semantic matching vector for each word based on all words in the other sentence. Then, each word vector is decomposed into a similar component and a dissimilar component based on the semantic matching vector. After this, a two-channel CNN model is employed to capture features by composing the similar and dissimilar components. Finally, a similarity score is estimated over the composed feature vectors. Experimental results show that our model gets the state-of-the-art performance on the answer sentence selection task, and achieves a comparable result on the paraphrase identification task.
Experimental Performance Evaluation of Cloud-Based Analytics-as-a-Service
Venue: arXiv cs.DC 2017
Year: 2017

An increasing number of Analytics-as-a-Service solutions has recently seen the light, in the landscape of cloud-based services. These services allow flexible composition of compute and storage components, that create powerful data ingestion and processing pipelines. This work is a first attempt at an experimental evaluation of analytic application performance executed using a wide range of storage service configurations. We present an intuitive notion of data locality, that we use as a proxy to rank different service compositions in terms of expected performance. Through an empirical analysis, we dissect the performance achieved by analytic workloads and unveil problems due to the impedance mismatch that arise in some configurations. Our work paves the way to a better understanding of modern cloud-based analytic services and their performance, both for its end-users and their providers.
Shape-aware Surface Reconstruction from Sparse 3D Point-Clouds
Venue: arXiv cs.CV 2017
Year: 2017

The reconstruction of an object's shape or surface from a set of 3D points plays an important role in medical image analysis, e.g. in anatomy reconstruction from tomographic measurements or in the process of aligning intra-operative navigation and preoperative planning data. In such scenarios, one usually has to deal with sparse data, which significantly aggravates the problem of reconstruction. However, medical applications often provide contextual information about the 3D point data that allow to incorporate prior knowledge about the shape that is to be reconstructed. To this end, we propose the use of a statistical shape model (SSM) as a prior for surface reconstruction. The SSM is represented by a point distribution model (PDM), which is associated with a surface mesh. Using the shape distribution that is modelled by the PDM, we formulate the problem of surface reconstruction from a probabilistic perspective based on a Gaussian Mixture Model (GMM). In order to do so, the given points are interpreted as samples of the GMM. By using mixture components with anisotropic covariances that are "oriented" according to the surface normals at the PDM points, a surface-based fitting is accomplished. Estimating the parameters of the GMM in a maximum a posteriori manner yields the reconstruction of the surface from the given data points. We compare our method to the extensively used Iterative Closest Points method on several different anatomical datasets/SSMs (brain, femur, tibia, hip, liver) and demonstrate superior accuracy and robustness on sparse data.
Optimizing Power and User Association for Energy Saving in Load-Coupled Cooperative LTE
Venue: arXiv cs.IT 2017
Year: 2017

We consider an energy minimization problem for cooperative LTE networks. To reduce energy consumption, we investigate how to jointly optimize the transmit power and the association between cells and user equipments (UEs), by taking into consideration joint transmission (JT), one of the coordinated multipoint (CoMP) techniques. We formulate the optimization problem mathematically. For solving the problem, a dynamic power allocation algorithm that adjusts the transmit power of all cells, and an algorithm for optimizing the cell-UE association, are proposed. The two algorithms are iteratively used in an algorithmic framework to enhance the energy performance. Numerically, the proposed algorithms can lead to lower energy consumption than the optimal energy setting in the non-JT case. In comparison to fixed power allocation in JT, the proposed dynamic power allocation algorithm is able to significantly reduce the energy consumption.
MPAR: A Movement Pattern-Aware Optimal Routing for Social Delay Tolerant Networks
Venue: arXiv cs.IT 2017
Year: 2017

Social Delay Tolerant Networks (SDTNs) are a special kind of Delay Tolerant Network (DTN) that consists of a number of mobile devices with social characteristics. The current research achievements on routing algorithms tend to separately evaluate the available profit for each prospective relay node and cannot achieve the global optimal performance in an overall perspective. In this paper, we propose a Movement Pattern-Aware optimal Routing (MPAR) for SDTNs, by choosing the optimal relay node(s) set for each message, which eventually based on running a search algorithm on a hyper-cube solution space. Concretely, the movement pattern of a group of node(s) can be extracted from the movement records of nodes. Then the set of commonly visited locations for the relay node(s) set and the destination node is obtained, by which we can further evaluate the co-delivery probability of the relay node(s) set. Both local search scheme and tabu-search scheme are utilized in finding the optimal set, and the tabu-search based routing Tabu-MPAR is proved able to guide the relay node(s) set in evolving to the optimal one. We demonstrate how the MPAR algorithm significantly outperforms the previous ones through extensive simulations, based on the synthetic SDTN mobility model.
Online Tree Caching
Venue: arXiv cs.DS 2017
Year: 2017

We initiate the study of a natural and practically relevant new variant of online caching where the to-be-cached items can have dependencies. We assume that the universe is a tree T and items are tree nodes; we require that if a node v is cached then the whole subtree T(v) rooted at v is cached as well. This theoretical problem finds an immediate application in the context of forwarding table optimization in IP routing and software-defined networks. We present an elegant online deterministic algorithm TC for this problem, and rigorously prove that its competitive ratio is O(height(T) * k_ALG/(k_ALG-k_OPT+1)), where k_ALG and k_OPT denote the cache sizes of an online and the optimal offline algorithm, respectively. The result is optimal up to a factor of O(height(T)).
REEL-BF Design: Achieving the SDP Bound for Downlink Beamforming with Arbitrary Shaping Constraints
Venue: arXiv cs.IT 2017
Year: 2017

This paper considers the beamforming design for a multiuser multiple-input single-output (MISO) downlink with an arbitrary number of (context-specific) shaping constraints. In this setup, the state-of-the-art beamforming schemes cannot attain the well-known performance bound promised by the semidefinite program (SDP) relaxation technique. To close the gap, we propose a redundant-signal embedded linear beamforming (REEL-BF) scheme, where each user is assigned with one information beamformer and several shaping beamformers. It is shown that the proposed REEL-BF scheme can perform general rank-$K$ beamforming for user symbols in a low-complexity and structured manner. In addition, sufficient conditions are derived to guarantee that the REEL-BF scheme always achieves the SDP bound for linear beamforming schemes. Based on such conditions, an efficient algorithm is then developed to obtain the optimal REEL-BF solution in polynomial time. Numerical results demonstrate that the proposed scheme enjoys substantial performance gains over the existing alternatives.
Walrasian Pricing in Multi-unit Auctions
Venue: arXiv cs.GT 2017
Year: 2017

Multi-unit auctions are a paradigmatic model, where a seller brings multiple units of a good, while several buyers bring monetary endowments. It is well known that Walrasian equilibria do not always exist in this model, however compelling relaxations such as (Walrasian) envy-free pricing do. In this paper we design an optimal envy-free mechanism for multi-unit auctions with budgets. When the market is even mildly competitive, the approximation ratios of this mechanism are small constants for both the revenue and welfare objectives, and in fact for welfare the approximation converges to 1 as the market becomes fully competitive. We also give an impossibility theorem, showing that truthfulness requires discarding resources and, in particular, is incompatible with (Pareto) efficiency.
Bioinformatics and Classical Literary Study
Venue: arXiv cs.CL 2017
Year: 2017

This paper describes the Quantitative Criticism Lab, a collaborative initiative between classicists, quantitative biologists, and computer scientists to apply ideas and methods drawn from the sciences to the study of literature. A core goal of the project is the use of computational biology, natural language processing, and machine learning techniques to investigate authorial style, intertextuality, and related phenomena of literary significance. As a case study in our approach, here we review the use of sequence alignment, a common technique in genomics and computational linguistics, to detect intertextuality in Latin literature. Sequence alignment is distinguished by its ability to find inexact verbal similarities, which makes it ideal for identifying phonetic echoes in large corpora of Latin texts. Although especially suited to Latin, sequence alignment in principle can be extended to many other languages.
The parameterized space complexity of embedding along a path
Venue: arXiv cs.CC 2017
Year: 2017

The embedding problem is to decide, given an ordered pair of structures, whether or not there is an injective homomorphism from the first structure to the second. We study this problem using an established perspective in parameterized complexity theory: the universe size of the first structure is taken to be the parameter, and we define the embedding problem relative to a class ${\cl A}$ of structures to be the restricted version of the general problem where the first structure must come from ${\cl A}$. We initiate a systematic complexity study of this problem family, by considering classes whose structures are what we call rooted path structures; these structures have paths as Gaifman graphs. Our main theorem is a dichotomy theorem on classes of rooted path structures.
The Capacity of Private Information Retrieval
Venue: arXiv cs.IT 2017
Year: 2017

In the private information retrieval (PIR) problem a user wishes to retrieve, as efficiently as possible, one out of $K$ messages from $N$ non-communicating databases (each holds all $K$ messages) while revealing nothing about the identity of the desired message index to any individual database. The information theoretic capacity of PIR is the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. For $K$ messages and $N$ databases, we show that the PIR capacity is $(1+1/N+1/N^2+\cdots+1/N^{K-1})^{-1}$. A remarkable feature of the capacity achieving scheme is that if we eliminate any subset of messages (by setting the message symbols to zero), the resulting scheme also achieves the PIR capacity for the remaining subset of messages.
Pareto optimal matchings of students to courses in the presence of prerequisites
Venue: arXiv cs.DS 2017
Year: 2017

We consider the problem of allocating applicants to courses, where each applicant has a subset of acceptable courses that she ranks in strict order of preference. Each applicant and course has a capacity, indicating the maximum number of courses and applicants they can be assigned to, respectively. We thus essentially have a many-to-many bipartite matching problem with one-sided preferences, which has applications to the assignment of students to optional courses at a university. We consider additive preferences and lexicographic preferences as two means of extending preferences over individual courses to preferences over bundles of courses. We additionally focus on the cases that courses have prerequisite constraints and where courses may be corequisites. For these extensions to the basic problem, we present the following algorithmic results, which are mainly concerned with the computation of Pareto optimal matchings (POMs). Firstly, we consider compulsory prerequisites. For additive preferences, we show that the problem of finding a POM is NP-hard. On the other hand, in the case of lexicographic preferences we give a polynomial-time algorithm for finding a POM, based on the well-known sequential mechanism. However we show that the problem of deciding whether a given matching is Pareto optimal is co-NP-complete. We further prove that finding a maximum cardinality (Pareto optimal) matching is NP-hard. Under alternative prerequisites, we show that finding a POM is NP-hard for either additive or lexicographic preferences. Finally we consider corequisites. We prove that, as in the case of compulsory prerequisites, finding a POM is NP-hard for additive preferences, though solvable in polynomial time for lexicographic preferences. In the latter case, the problem of finding a maximum cardinality POM is NP-hard and very difficult to approximate
A fixed-parameter algorithm for a routing open shop problem: unit processing times, few machines and locations
Venue: arXiv cs.DM 2017
Year: 2017

The open shop problem is to find a minimum makespan schedule to process each job $J_i$ on each machine $M_q$ for $p_{iq}$ time such that, at any time, each machine processes at most one job and each job is processed by at most one machine. We study a problem variant in which the jobs are located in the vertices of an edge-weighted graph. The weights determine the time needed for the machines to travel between jobs in different vertices. We show that the problem with $m$ machines and $n$ unit-time jobs in $g$ vertices is solvable in $2^{O(gm^2\log gm)}+O(mn\log n)$ time.
Inferential Privacy Guarantees for Differentially Private Mechanisms
Venue: arXiv cs.DS 2017
Year: 2017

The correlations and network structure amongst individuals in datasets today---whether explicitly articulated, or deduced from biological or behavioral connections---pose new issues around privacy guarantees, because of inferences that can be made about one individual from another's data. This motivates quantifying privacy in networked contexts in terms of "inferential privacy"---which measures the change in beliefs about an individual's data from the result of a computation---as originally proposed by Dalenius in the 1970's. Inferential privacy is implied by differential privacy when data are independent, but can be much worse when data are correlated; indeed, simple examples, as well as a general impossibility theorem of Dwork and Naor, preclude the possibility of achieving non-trivial inferential privacy when the adversary can have arbitrary auxiliary information. In this paper, we ask how differential privacy guarantees translate to guarantees on inferential privacy in networked contexts: specifically, under what limitations on the adversary's information about correlations, modeled as a prior distribution over datasets, can we deduce an inferential guarantee from a differential one? We prove two main results. The first result pertains to distributions that satisfy a natural positive-affiliation condition, and gives an upper bound on the inferential privacy guarantee for any differentially private mechanism. This upper bound is matched by a simple mechanism that adds Laplace noise to the sum of the data. The second result pertains to distributions that have weak correlations, defined in terms of a suitable "influence matrix". The result provides an upper bound for inferential privacy in terms of the differential privacy parameter and the spectral norm of this matrix.
A Data-Scalable Randomized Misfit Approach for Solving Large-Scale PDE-Constrained Inverse Problems
Venue: arXiv cs.NA 2017
Year: 2017

A randomized misfit approach is presented for the efficient solution of large-scale PDE-constrained inverse problems with high-dimensional data. The purpose of this paper is to offer a theory-based framework for random projections in this inverse problem setting. The stochastic approximation to the misfit is analyzed using random projection theory. By expanding beyond mean estimator convergence, a practical characterization of randomized misfit convergence can be achieved. The theoretical results developed hold with any valid random projection in the literature. The class of feasible distributions is broad yet simple to characterize compared to previous stochastic misfit methods. This class includes very sparse random projections which provide additional computational benefit. A different proof for a variant of the Johnson-Lindenstrauss lemma is also provided. This leads to a different intuition for the $O(ε^{-2})$ factor in bounds for Johnson-Lindenstrauss results. The main contribution of this paper is a theoretical result showing the method guarantees a valid solution for small reduced misfit dimensions. The interplay between Johnson-Lindenstrauss theory and Morozov's discrepancy principle is shown to be essential to the result. The computational cost savings for large-scale PDE-constrained problems with high- dimensional data is discussed. Numerical verification of the developed theory is presented for model problems of estimating a distributed parameter in an elliptic partial differential equation. Results with different random projections are presented to demonstrate the viability and accuracy of the proposed approach.
Identifiability of an X-rank decomposition of polynomial maps
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we study a polynomial decomposition model that arises in problems of system identification, signal processing and machine learning. We show that this decomposition is a special case of the X-rank decomposition --- a powerful novel concept in algebraic geometry that generalizes the tensor CP decomposition. We prove new results on generic/maximal rank and on identifiability of a particular polynomial decomposition model. In the paper, we try to make results and basic tools accessible for general audience (assuming no knowledge of algebraic geometry or its prerequisites).
Carrier Phase Estimation in Dispersion-Unmanaged Optical Transmission Systems
Venue: arXiv cs.IT 2017
Year: 2017

The study on carrier phase estimation (CPE) approaches, involving a one-tap normalized least-mean-square (NLMS) algorithm, a block-wise average algorithm, and a Viterbi-Viterbi algorithm has been carried out in the long-haul high-capacity dispersion-unmanaged coherent optical systems. The close-form expressions and analytical predictions for bit-error-rate behaviors in these CPE methods have been analyzed by considering both the laser phase noise and the equalization enhanced phase noise. It is found that the Viterbi-Viterbi algorithm outperforms the one-tap NLMS and the block-wise average algorithms for a small phase noise variance (or effective phase noise variance), while the three CPE methods converge to a similar performance for a large phase noise variance (or effective phase noise variance). In addition, the differences between the three CPE approaches become smaller for higher-level modulation formats.