OpenRaiser/Intern-Atlas huggingface dataset:
An Upper Bound On the Size of Locally Recoverable Codes
Venue: arXiv cs.IT 2015
Year: 2015

In a {\em locally recoverable} or {\em repairable} code, any symbol of a codeword can be recovered by reading only a small (constant) number of other symbols. The notion of local recoverability is important in the area of distributed storage where a most frequent error-event is a single storage node failure (erasure). A common objective is to repair the node by downloading data from as few other storage node as possible. In this paper, we bound the minimum distance of a code in terms of its length, size and locality. Unlike previous bounds, our bound follows from a significantly simple analysis and depends on the size of the alphabet being used. It turns out that the binary Simplex codes satisfy our bound with equality; hence the Simplex codes are the first example of a optimal binary locally repairable code family. We also provide achievability results based on random coding and concatenated codes that are numerically verified to be close to our bounds.
Graphs of Edge-Intersecting Non-Splitting Paths in a Tree: Towards Hole Representations-Part I
Venue: arXiv cs.DM 2015
Year: 2015

Given a tree and a set ${\cal P}$ of non-trivial simple paths on it, $VPT({\cal P})$ is the VPT graph (i.e. the vertex intersection graph) of the paths ${\cal P}$ of the tree $T$, and $EPT({\cal P})$ is the EPT graph (i.e. the edge intersection graph) of ${\cal P}$. These graphs have been extensively studied in the literature. Given two (edge) intersecting paths in a graph, their \emph{split vertices} is the set of vertices having degree at least $3$ in their union. A pair of (edge) intersecting paths is termed \emph{non-splitting} if they do not have split vertices (namely if their union is a path). In this work, motivated by an application in all-optical networks, we define the graph $ENPT({\cal P})$ of edge-intersecting non-splitting paths of a tree, termed the ENPT graph, as the (edge) graph having a vertex for each path in ${\cal P}$, and an edge between every pair of paths that are both edge-intersecting and non-splitting. A graph $G$ is an ENPT graph if there is a tree $T$ and a set of paths ${\cal P}$ of $T$ such that $G=ENPT({\cal P})$, and we say that $<T,{\cal P}>$ is a \emph{representation} of $G$. We first show that cycles, trees and complete graphs are ENPT graphs. Our work follows the lines of Golumbic and Jamison's research in which they defined the EPT graph class, and characterized the representations of chordless cycles (holes). It turns out that ENPT holes have a more complex structure than EPT holes. In our analysis, we assume that the EPT graph corresponding to a representation of an ENPT hole is given. We also introduce three assumptions $(P1)$, $(P2)$, $(P3)$ defined on EPT, ENPT pairs of graphs. In this Part I, using the results of Golumbic and Jamison as building blocks, we characterize (a) EPT, ENPT pairs that satisfy $(P1)$, $(P2)$, $(P3)$, and (b) the unique minimal representation of such pairs.
Path-Based Distance for Street Map Comparison
Venue: arXiv cs.CG 2015
Year: 2015

Comparing two geometric graphs embedded in space is important in the field of transportation network analysis. Given street maps of the same city collected from different sources, researchers often need to know how and where they differ. However, the majority of current graph comparison algorithms are based on structural properties of graphs, such as their degree distribution or their local connectivity properties, and do not consider their spatial embedding. This ignores a key property of road networks since similarity of travel over two road networks is intimately tied to the specific spatial embedding. Likewise, many current street map comparison algorithms focus on the spatial embeddings only and do not take structural properties into account, which makes these algorithms insensitive to local connectivity properties and shortest path similarities. We propose a new path-based distance measure to compare two planar geometric graphs embedded in the plane. Our distance measure takes structural as well as spatial properties into account by imposing a distance measure between two road networks based on the Hausdorff distance between the two sets of travel paths they represent. We show that this distance can be approximated in polynomial time and that it preserves structural and spatial properties of the graphs.
Advances in Bayesian Network Learning using Integer Programming
Venue: arXiv cs.AI 2015
Year: 2015

We consider the problem of learning Bayesian networks (BNs) from complete discrete data. This problem of discrete optimisation is formulated as an integer program (IP). We describe the various steps we have taken to allow efficient solving of this IP. These are (i) efficient search for cutting planes, (ii) a fast greedy algorithm to find high-scoring (perhaps not optimal) BNs and (iii) tightening the linear relaxation of the IP. After relating this BN learning problem to set covering and the multidimensional 0-1 knapsack problem, we present our empirical results. These show improvements, sometimes dramatic, over earlier results.
Exact and Stable Covariance Estimation from Quadratic Sampling via Convex Programming
Venue: arXiv cs.IT 2015
Year: 2015

Statistical inference and information processing of high-dimensional data often require efficient and accurate estimation of their second-order statistics. With rapidly changing data, limited processing power and storage at the acquisition devices, it is desirable to extract the covariance structure from a single pass over the data and a small number of stored measurements. In this paper, we explore a quadratic (or rank-one) measurement model which imposes minimal memory requirements and low computational complexity during the sampling process, and is shown to be optimal in preserving various low-dimensional covariance structures. Specifically, four popular structural assumptions of covariance matrices, namely low rank, Toeplitz low rank, sparsity, jointly rank-one and sparse structure, are investigated, while recovery is achieved via convex relaxation paradigms for the respective structure. The proposed quadratic sampling framework has a variety of potential applications including streaming data processing, high-frequency wireless communication, phase space tomography and phase retrieval in optics, and non-coherent subspace detection. Our method admits universally accurate covariance estimation in the absence of noise, as soon as the number of measurements exceeds the information theoretic limits. We also demonstrate the robustness of this approach against noise and imperfect structural assumptions. Our analysis is established upon a novel notion called the mixed-norm restricted isometry property (RIP-$\ell_{2}/\ell_{1}$), as well as the conventional RIP-$\ell_{2}/\ell_{2}$ for near-isotropic and bounded measurements. In addition, our results improve upon the best-known phase retrieval (including both dense and sparse signals) guarantees using PhaseLift with a significantly simpler approach.
Complexity of linear circuits and geometry
Venue: arXiv cs.CC 2015
Year: 2015

We use algebraic geometry to study matrix rigidity, and more generally, the complexity of computing a matrix-vector product, continuing a study initiated by Kumar, et. al. We (i) exhibit many non-obvious equations testing for (border) rigidity, (ii) compute degrees of varieties associated to rigidity, (iii) describe algebraic varieties associated to families of matrices that are expected to have super-linear rigidity, and (iv) prove results about the ideals and degrees of cones that are of interest in their own right.
Robust and highly performant ring detection algorithm for 3d particle tracking using 2d microscope imaging
Venue: arXiv cs.CV 2015
Year: 2015

Three-dimensional particle tracking is an essential tool in studying dynamics under the microscope, namely, fluid dynamics in microfluidic devices, bacteria taxis, cellular trafficking. The 3d position can be determined using 2d imaging alone by measuring the diffraction rings generated by an out-of-focus fluorescent particle, imaged on a single camera. Here I present a ring detection algorithm exhibiting a high detection rate, which is robust to the challenges arising from ring occlusion, inclusions and overlaps, and allows resolving particles even when near to each other. It is capable of real time analysis thanks to its high performance and low memory footprint. The proposed algorithm, an offspring of the circle Hough transform, addresses the need to efficiently trace the trajectories of many particles concurrently, when their number in not necessarily fixed, by solving a classification problem, and overcomes the challenges of finding local maxima in the complex parameter space which results from ring clusters and noise. Several algorithmic concepts introduced here can be advantageous in other cases, particularly when dealing with noisy and sparse data. The implementation is based on open-source and cross-platform software packages only, making it easy to distribute and modify. It is implemented in a microfluidic experiment allowing real-time multi-particle tracking at 70 Hz, achieving a detection rate which exceeds 94% and only 1% false-detection.
Low-Complexity Interactive Algorithms for Synchronization from Deletions, Insertions, and Substitutions
Venue: arXiv cs.IT 2015
Year: 2015

Consider two remote nodes having binary sequences $X$ and $Y$, respectively. $Y$ is an edited version of ${X}$, where the editing involves random deletions, insertions, and substitutions, possibly in bursts. The goal is for the node with $Y$ to reconstruct $X$ with minimal exchange of information over a noiseless link. The communication is measured in terms of both the total number of bits exchanged and the number of interactive rounds of communication. This paper focuses on the setting where the number of edits is $o(\tfrac{n}{\log n})$, where $n$ is the length of $X$. We first consider the case where the edits are a mixture of insertions and deletions (indels), and propose an interactive synchronization algorithm with near-optimal communication rate and average computational complexity of $O(n)$ arithmetic operations. The algorithm uses interaction to efficiently split the source sequence into substrings containing exactly one deletion or insertion. Each of these substrings is then synchronized using an optimal one-way synchronization code based on the single-deletion correcting channel codes of Varshamov and Tenengolts (VT codes). We then build on this synchronization algorithm in three different ways. First, it is modified to work with a single round of interaction. The reduction in the number of rounds comes at the expense of higher communication, which is quantified. Next, we present an extension to the practically important case where the insertions and deletions may occur in (potentially large) bursts. Finally, we show how to synchronize the sources to within a target Hamming distance. This feature can be used to differentiate between substitution and indel edits. In addition to theoretical performance bounds, we provide several validating simulation results for the proposed algorithms.
Multi-Armed Bandits for Intelligent Tutoring Systems
Venue: arXiv cs.AI 2015
Year: 2015

We present an approach to Intelligent Tutoring Systems which adaptively personalizes sequences of learning activities to maximize skills acquired by students, taking into account the limited time and motivational resources. At a given point in time, the system proposes to the students the activity which makes them progress faster. We introduce two algorithms that rely on the empirical estimation of the learning progress, RiARiT that uses information about the difficulty of each exercise and ZPDES that uses much less knowledge about the problem. The system is based on the combination of three approaches. First, it leverages recent models of intrinsically motivated learning by transposing them to active teaching, relying on empirical estimation of learning progress provided by specific activities to particular students. Second, it uses state-of-the-art Multi-Arm Bandit (MAB) techniques to efficiently manage the exploration/exploitation challenge of this optimization process. Third, it leverages expert knowledge to constrain and bootstrap initial exploration of the MAB, while requiring only coarse guidance information of the expert and allowing the system to deal with didactic gaps in its knowledge. The system is evaluated in a scenario where 7-8 year old schoolchildren learn how to decompose numbers while manipulating money. Systematic experiments are presented with simulated students, followed by results of a user study across a population of 400 school children.
Scalable Synchronization and Reciprocity Calibration for Distributed Multiuser MIMO
Venue: arXiv cs.NI 2015
Year: 2015

Large-scale distributed Multiuser MIMO (MU-MIMO) is a promising wireless network architecture that combines the advantages of "massive MIMO" and "small cells." It consists of several Access Points (APs) connected to a central server via a wired backhaul network and acting as a large distributed antenna system. We focus on the downlink, which is both more demanding in terms of traffic and more challenging in terms of implementation than the uplink. In order to enable multiuser joint precoding of the downlink signals, channel state information at the transmitter side is required. We consider Time Division Duplex (TDD), where the {\em downlink} channels can be learned from the user uplink pilot signals, thanks to channel reciprocity. Furthermore, coherent multiuser joint precoding is possible only if the APs maintain a sufficiently accurate relative timing and phase synchronization. AP synchronization and TDD reciprocity calibration are two key problems to be solved in order to enable distributed MU-MIMO downlink. In this paper, we propose novel over-the-air synchronization and calibration protocols that scale well with the network size. The proposed schemes can be applied to networks formed by a large number of APs, each of which is driven by an inexpensive 802.11-grade clock and has a standard RF front-end, not explicitly designed to be reciprocal. Our protocols can incorporate, as a building block, any suitable timing and frequency estimator. Here we revisit the problem of joint ML timing and frequency estimation and use the corresponding Cramer-Rao bound to evaluate the performance of the synchronization protocol. Overall, the proposed synchronization and calibration schemes are shown to achieve sufficient accuracy for satisfactory distributed MU-MIMO performance.
On the extraction of instantaneous frequencies from ridges in time-frequency representations of signals
Venue: arXiv cs.CE 2015
Year: 2015

The extraction of oscillatory components and their properties from different time-frequency representations, such as windowed Fourier transform and wavelet transform, is an important topic in signal processing. The first step in this procedure is to find an appropriate ridge curve: a sequence of amplitude peak positions (ridge points), corresponding to the component of interest. This is not a trivial issue, and the optimal method for extraction is still not settled or agreed. We discuss and develop procedures that can be used for this task and compare their performance on both simulated and real data. In particular, we propose a method which, in contrast to many other approaches, is highly adaptive so that it does not need any parameter adjustment for the signal to be analysed. Being based on dynamic path optimization and fixed point iteration, the method is very fast, and its superior accuracy is also demonstrated. In addition, we investigate the advantages and drawbacks that synchrosqueezing offers in relation to curve extraction. The codes used in this work are freely available for download.
A Preadapted Universal Switch Distribution for Testing Hilberg's Conjecture
Venue: arXiv cs.IT 2015
Year: 2015

Hilberg's conjecture about natural language states that the mutual information between two adjacent long blocks of text grows like a power of the block length. The exponent in this statement can be upper bounded using the pointwise mutual information estimate computed for a carefully chosen code. The bound is the better, the lower the compression rate is but there is a requirement that the code be universal. So as to improve a received upper bound for Hilberg's exponent, in this paper, we introduce two novel universal codes, called the plain switch distribution and the preadapted switch distribution. Generally speaking, switch distributions are certain mixtures of adaptive Markov chains of varying orders with some additional communication to avoid so called catch-up phenomenon. The advantage of these distributions is that they both achieve a low compression rate and are guaranteed to be universal. Using the switch distributions we obtain that a sample of a text in English is non-Markovian with Hilberg's exponent being $\le 0.83$, which improves over the previous bound $\le 0.94$ obtained using the Lempel-Ziv code.
Information Compression, Intelligence, Computing, and Mathematics
Venue: arXiv cs.AI 2015
Year: 2015

This paper presents evidence for the idea that much of artificial intelligence, human perception and cognition, mainstream computing, and mathematics, may be understood as compression of information via the matching and unification of patterns. This is the basis for the "SP theory of intelligence", outlined in the paper and fully described elsewhere. Relevant evidence may be seen: in empirical support for the SP theory; in some advantages of information compression (IC) in terms of biology and engineering; in our use of shorthands and ordinary words in language; in how we merge successive views of any one thing; in visual recognition; in binocular vision; in visual adaptation; in how we learn lexical and grammatical structures in language; and in perceptual constancies. IC via the matching and unification of patterns may be seen in both computing and mathematics: in IC via equations; in the matching and unification of names; in the reduction or removal of redundancy from unary numbers; in the workings of Post's Canonical System and the transition function in the Universal Turing Machine; in the way computers retrieve information from memory; in systems like Prolog; and in the query-by-example technique for information retrieval. The chunking-with-codes technique for IC may be seen in the use of named functions to avoid repetition of computer code. The schema-plus-correction technique may be seen in functions with parameters and in the use of classes in object-oriented programming. And the run-length coding technique may be seen in multiplication, in division, and in several other devices in mathematics and computing. The SP theory resolves the apparent paradox of "decompression by compression". And computing and cognition as IC is compatible with the uses of redundancy in such things as backup copies to safeguard data and understanding speech in a noisy environment.
Failure dynamics of the global risk network
Venue: arXiv cs.CY 2015
Year: 2015

Risks threatening modern societies form an intricately interconnected network that often underlies crisis situations. Yet, little is known about how risk materializations in distinct domains influence each other. Here we present an approach in which expert assessments of risks likelihoods and influence underlie a quantitative model of the global risk network dynamics. The modeled risks range from environmental to economic and technological and include difficult to quantify risks, such as geo-political or social. Using the maximum likelihood estimation, we find the optimal model parameters and demonstrate that the model including network effects significantly outperforms the others, uncovering full value of the expert collected data. We analyze the model dynamics and study its resilience and stability. Our findings include such risk properties as contagion potential, persistence, roles in cascades of failures and the identity of risks most detrimental to system stability. The model provides quantitative means for measuring the adverse effects of risk interdependence and the materialization of risks in the network.
Losing Weight by Gaining Edges
Venue: arXiv cs.CC 2015
Year: 2015

We present a new way to encode weighted sums into unweighted pairwise constraints, obtaining the following results. - Define the k-SUM problem to be: given n integers in [-n^2k, n^2k] are there k which sum to zero? (It is well known that the same problem over arbitrary integers is equivalent to the above definition, by linear-time randomized reductions.) We prove that this definition of k-SUM remains W[1]-hard, and is in fact W[1]-complete: k-SUM can be reduced to f(k) * n^o(1) instances of k-Clique. - The maximum node-weighted k-Clique and node-weighted k-dominating set problems can be reduced to n^o(1) instances of the unweighted k-Clique and k-dominating set problems, respectively. This implies a strong equivalence between the time complexities of the node weighted problems and the unweighted problems: any polynomial improvement on one would imply an improvement for the other. - A triangle of weight 0 in a node weighted graph with m edges can be deterministically found in m^1.41 time.
Cloud Compute-and-Forward with Relay Cooperation
Venue: arXiv cs.IT 2015
Year: 2015

We study a cloud network with M distributed receiving antennas and L users, which transmit their messages towards a centralized decoder (CD), where M>=L. We consider that the cloud network applies the Compute-and-Forward (C&F) protocol, where L antennas/relays are selected to decode integer equations of the transmitted messages. In this work, we focus on the best relay selection and the optimization of the Physical-Layer Network Coding (PNC) at the relays, aiming at the throughput maximization of the network. Existing literature optimizes PNC with respect to the maximization of the minimum rate among users. The proposed strategy maximizes the sum rate of the users allowing nonsymmetric rates, while the optimal solution is explored with the aid of the Pareto frontier. The problem of relay selection is matched to a coalition formation game, where the relays and the CD cooperate in order to maximize their profit. Efficient coalition formation algorithms are proposed, which perform joint relay selection and PNC optimization. Simulation results show that a considerable improvement is achieved compared to existing results, both in terms of the network sum rate and the players' profits.
Automated identification and characterization of parcels (AICP) with OpenStreetMap and Points of Interest
Venue: arXiv cs.CY 2015
Year: 2015

Against the paucity of urban parcels in China, this paper proposes a method to automatically identify and characterize parcels (AICP) with OpenStreetMap (OSM) and Points of Interest (POI) data. Parcels are the basic spatial units for fine-scale urban modeling, urban studies, as well as spatial planning. Conventional ways of identification and characterization of parcels rely on remote sensing and field surveys, which are labor intensive and resource-consuming. Poorly developed digital infrastructure, limited resources, and institutional barriers have all hampered the gathering and application of parcel data in developing countries. Against this backdrop, we employ OSM road networks to identify parcel geometries and POI data to infer parcel characteristics. A vector-based CA model is adopted to select urban parcels. The method is applied to the entire state of China and identifies 82,645 urban parcels in 297 cities. Notwithstanding all the caveats of open and/or crowd-sourced data, our approach could produce reasonably good approximation of parcels identified from conventional methods, thus having the potential to become a useful supplement.