OpenRaiser/Intern-Atlas huggingface dataset:
Fast generation of complex networks with underlying hyperbolic geometry
Venue: arXiv cs.DS 2015
Year: 2015

Complex networks have become increasingly popular for modeling various real-world phenomena. Realistic generative network models are important in this context as they avoid privacy concerns of real data and simplify complex network research regarding data sharing, reproducibility, and scalability studies. \emph{Random hyperbolic graphs} are a well-analyzed family of geometric graphs. Previous work provided empirical and theoretical evidence that this generative graph model creates networks with non-vanishing clustering and other realistic features. However, the investigated networks in previous applied work were small, possibly due to the quadratic running time of a previous generator. In this work we provide the first generation algorithm for these networks with subquadratic running time. We prove a time complexity of $O((n^{3/2}+m) \log n)$ with high probability for the generation process. This running time is confirmed by experimental data with our implementation. The acceleration stems primarily from the reduction of pairwise distance computations through a polar quadtree, which we adapt to hyperbolic space for this purpose. In practice we improve the running time of a previous implementation by at least two orders of magnitude this way. Networks with billions of edges can now be generated in a few minutes. Finally, we evaluate the largest networks of this model published so far. Our empirical analysis shows that important features are retained over different graph densities and degree distributions.
On the Capacity of Symmetric Gaussian Interference Channels with Feedback
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we propose a new coding scheme for symmetric Gaussian interference channels with feedback based on the ideas of time-varying coding schemes. The proposed scheme improves the Suh-Tse and Kramer inner bounds of the channel capacity for the cases of weak and not very strong interference. This improvement is more significant when the signal-to-noise ratio (SNR) is not very high. It is shown theoretically and numerically that our coding scheme can outperform the Kramer code. In addition, the generalized degrees-of-freedom of our proposed coding scheme is equal to the Suh-Tse scheme in the strong interference case. The numerical results show that our coding scheme can attain better performance than the Suh-Tse coding scheme for all channel parameters. Furthermore, the simplicity of the encoding/decoding algorithms is another strong point of our proposed coding scheme compared with the Suh-Tse coding scheme. More importantly, our results show that an optimal coding scheme for the symmetric Gaussian interference channels with feedback can be achieved by using only marginal posterior distributions under a better cooperation strategy between transmitters.
Integral D-Finite Functions
Venue: arXiv cs.SC 2015
Year: 2015

We propose a differential analog of the notion of integral closure of algebraic function fields. We present an algorithm for computing the integral closure of the algebra defined by a linear differential operator. Our algorithm is a direct analog of van Hoeij's algorithm for computing integral bases of algebraic function fields.
The Fast Convergence of Incremental PCA
Venue: arXiv cs.LG 2015
Year: 2015

We consider a situation in which we see samples in $\mathbb{R}^d$ drawn i.i.d. from some distribution with mean zero and unknown covariance A. We wish to compute the top eigenvector of A in an incremental fashion - with an algorithm that maintains an estimate of the top eigenvector in O(d) space, and incrementally adjusts the estimate with each new data point that arrives. Two classical such schemes are due to Krasulina (1969) and Oja (1983). We give finite-sample convergence rates for both.
Phase Identification in Distribution Networks with Micro-Synchrophasors
Venue: arXiv cs.SY 2015
Year: 2015

This paper proposes a novel phase identification method for distribution networks where phases can be severely unbalanced and insufficiently labeled. The analysis approach draws on data from high-precision phasor measurement units (micro-synchrophasors or uPMUs) for distribution systems. A key fact is that time-series voltage phasors taken from a distribution network show specific patterns regarding connected phases at measurement points. The algorithm is based on analyzing crosscorrelations over voltage magnitudes along with phase angle differences on two candidate phases to be matched. If two measurement points are on the same phase, large positive voltage magnitude correlations and small voltage angle differences should be observed. The algorithm is initially validated using the IEEE 13-bus model, and subsequently with actual uPMU measurements on a 12-kV feeder.
Stochastic Local Interaction (SLI) Model: Interfacing Machine Learning and Geostatistics
Venue: arXiv cs.LG 2015
Year: 2015

Machine learning and geostatistics are powerful mathematical frameworks for modeling spatial data. Both approaches, however, suffer from poor scaling of the required computational resources for large data applications. We present the Stochastic Local Interaction (SLI) model, which employs a local representation to improve computational efficiency. SLI combines geostatistics and machine learning with ideas from statistical physics and computational geometry. It is based on a joint probability density function defined by an energy functional which involves local interactions implemented by means of kernel functions with adaptive local kernel bandwidths. SLI is expressed in terms of an explicit, typically sparse, precision (inverse covariance) matrix. This representation leads to a semi-analytical expression for interpolation (prediction), which is valid in any number of dimensions and avoids the computationally costly covariance matrix inversion.
A Fast Fractal Image Compression Algorithm Using Predefined Values for Contrast Scaling
Venue: arXiv cs.CV 2015
Year: 2015

In this paper a new fractal image compression algorithm is proposed in which the time of encoding process is considerably reduced. The algorithm exploits a domain pool reduction approach, along with using innovative predefined values for contrast scaling factor, S, instead of scanning the parameter space [0,1]. Within this approach only domain blocks with entropies greater than a threshold are considered. As a novel point, it is assumed that in each step of the encoding process, the domain block with small enough distance shall be found only for the range blocks with low activity (equivalently low entropy). This novel point is used to find reasonable estimations of S, and use them in the encoding process as predefined values, mentioned above. The algorithm has been examined for some well-known images. This result shows that our proposed algorithm considerably reduces the encoding time producing images that are approximately the same in quality.
Design of a Transport Triggered Architecture Processor for Flexible Iterative Turbo Decoder
Venue: arXiv cs.AR 2015
Year: 2015

In order to meet the requirement of high data rates for the next generation wireless systems, the efficient implementation of receiver algorithms is essential. On the other hand, the rapid development of technology motivates the investigation of programmable implementations. This paper summarizes the design of a programmable turbo decoder as an applicationspecific instruction-set processor (ASIP) using Transport Triggered Architecture (TTA). The processor architecture is designed in such manner that it can be programmed to support other receiver algorithms, for example, decoding based on the Viterbi algorithm. Different suboptimal maximum a posteriori (MAP) algorithms are used and compared to one another for the softinput soft-output (SISO) component decoders in a single TTA processor. The max-log-MAP algorithm outperforms the other suboptimal algorithms in terms of latency. The design enables the designer to change the suboptimal algorithms according to the bit error rate (BER) performance requirement. Unlike many other programmable turbo decoder implementations, quadratic polynomial permutation (QPP) interleaver is used in this work for contention-free memory access and to make the processor 3GPP LTE compliant. Several optimization techniques to enable real time processing on programmable platforms are introduced. Using our method, with a single iteration 31.32 Mbps throughput is achieved for the max-log-MAP algorithm for a clock frequency of 200 MHz.
Maximum Entropy Models of Shortest Path and Outbreak Distributions in Networks
Venue: arXiv cs.SI 2015
Year: 2015

Properties of networks are often characterized in terms of features such as node degree distributions, average path lengths, diameters, or clustering coefficients. Here, we study shortest path length distributions. On the one hand, average as well as maximum distances can be determined therefrom; on the other hand, they are closely related to the dynamics of network spreading processes. Because of the combinatorial nature of networks, we apply maximum entropy arguments to derive a general, physically plausible model. In particular, we establish the generalized Gamma distribution as a continuous characterization of shortest path length histograms of networks or arbitrary topology. Experimental evaluations corroborate our theoretical results.
The Information-theoretic and Algorithmic Approach to Human, Animal and Artificial Cognition
Venue: arXiv cs.AI 2015
Year: 2015

We survey concepts at the frontier of research connecting artificial, animal and human cognition to computation and information processing---from the Turing test to Searle's Chinese Room argument, from Integrated Information Theory to computational and algorithmic complexity. We start by arguing that passing the Turing test is a trivial computational problem and that its pragmatic difficulty sheds light on the computational nature of the human mind more than it does on the challenge of artificial intelligence. We then review our proposed algorithmic information-theoretic measures for quantifying and characterizing cognition in various forms. These are capable of accounting for known biases in human behavior, thus vindicating a computational algorithmic view of cognition as first suggested by Turing, but this time rooted in the concept of algorithmic probability, which in turn is based on computational universality while being independent of computational model, and which has the virtue of being predictive and testable as a model theory of cognitive behavior.
Generalised Random Forest Space Overview
Venue: arXiv cs.LG 2015
Year: 2015

Assuming a view of the Random Forest as a special case of a nested ensemble of interchangeable modules, we construct a generalisation space allowing one to easily develop novel methods based on this algorithm. We discuss the role and required properties of modules at each level, especially in context of some already proposed RF generalisations.
Grouping Entities in a Fleet by Community Detection in Network of Regression Models
Venue: arXiv cs.SI 2015
Year: 2015

This paper deals with grouping of entities in a fleet based on their behavior. The behavior of each entity is characterized by its historical dataset, which comprises a dependent variable, typically a performance measure, and multiple independent variables, typically operating conditions. A regression model built using this dataset is used as a proxy for the behavior of an entity. The validation error of the model of one unit with respect to the dataset of another unit is used as a measure of the difference in behavior between two units. Grouping entities based on their behavior is posed as a graph clustering problem with nodes representing regression models and edge weights given by the validation errors. Specifically, we find communities in this graph, having dense edge connections within and sparse connections outside. A way to assess the goodness of grouping and finding the optimum number of divisions is proposed. The algorithm and measures proposed are illustrated with application to synthetic data.
WiGest: A Ubiquitous WiFi-based Gesture Recognition System
Venue: arXiv cs.HC 2015
Year: 2015

We present WiGest: a system that leverages changes in WiFi signal strength to sense in-air hand gestures around the user's mobile device. Compared to related work, WiGest is unique in using standard WiFi equipment, with no modi-fications, and no training for gesture recognition. The system identifies different signal change primitives, from which we construct mutually independent gesture families. These families can be mapped to distinguishable application actions. We address various challenges including cleaning the noisy signals, gesture type and attributes detection, reducing false positives due to interfering humans, and adapting to changing signal polarity. We implement a proof-of-concept prototype using off-the-shelf laptops and extensively evaluate the system in both an office environment and a typical apartment with standard WiFi access points. Our results show that WiGest detects the basic primitives with an accuracy of 87.5% using a single AP only, including through-the-wall non-line-of-sight scenarios. This accuracy in-creases to 96% using three overheard APs. In addition, when evaluating the system using a multi-media player application, we achieve a classification accuracy of 96%. This accuracy is robust to the presence of other interfering humans, highlighting WiGest's ability to enable future ubiquitous hands-free gesture-based interaction with mobile devices.
On the Degrees of Freedom for Opportunistic Interference Alignment with 1-Bit Feedback: The 3 Cell Case
Venue: arXiv cs.IT 2015
Year: 2015

Opportunistic interference alignment (OIA) exploits channel randomness and multiuser diversity by user selection. For OIA the transmitter needs channel state information (CSI), which is usually measured on the receiver side and sent to the transmitter side via a feedback channel. Lee and Choi show that $d$ degrees of freedom (DoF) per transmitter are achievable in a 3-cell MIMO interference channel assuming perfect real-valued feedback. However, the feedback of a real-valued variable still requires infinite rate. In this paper, we investigate 1-bit quantization for opportunistic interference alignment (OIA) in 3-cell interference channels. We prove that 1-bit feedback is sufficient to achieve the optimal DoF $d$ in 3-cell MIMO interference channels if the number of users per cell is scaled as ${\rm SNR}^{d^2}$. Importantly, the required number of users for OIA with 1-bit feedback remains the same as with real-valued feedback. For a given system configuration, we provide an optimal choice of the 1-bit quantizer, which captures most of the capacity provided by a system with real-valued feedback. Using our new 1-bit feedback scheme for OIA, we compare OIA with IA and show that OIA has a much lower complexity and provides a better rate in the practical operation region of a cellular communication system.
Reconstruction-free action inference from compressive imagers
Venue: arXiv cs.CV 2015
Year: 2015

Persistent surveillance from camera networks, such as at parking lots, UAVs, etc., often results in large amounts of video data, resulting in significant challenges for inference in terms of storage, communication and computation. Compressive cameras have emerged as a potential solution to deal with the data deluge issues in such applications. However, inference tasks such as action recognition require high quality features which implies reconstructing the original video data. Much work in compressive sensing (CS) theory is geared towards solving the reconstruction problem, where state-of-the-art methods are computationally intensive and provide low-quality results at high compression rates. Thus, reconstruction-free methods for inference are much desired. In this paper, we propose reconstruction-free methods for action recognition from compressive cameras at high compression ratios of 100 and above. Recognizing actions directly from CS measurements requires features which are mostly nonlinear and thus not easily applicable. This leads us to search for such properties that are preserved in compressive measurements. To this end, we propose the use of spatio-temporal smashed filters, which are compressive domain versions of pixel-domain matched filters. We conduct experiments on publicly available databases and show that one can obtain recognition rates that are comparable to the oracle method in uncompressed setup, even for high compression ratios.
Band Splitting Permutations for Spatially Coupled LDPC Codes Enhancing Burst Erasure Immunity
Venue: arXiv cs.IT 2015
Year: 2015

It is well known that spatially coupled (SC) codes with erasure-BP decoding have powerful error correcting capability over memoryless erasure channels. However, the decoding performance of SC-codes significantly degrades when they are used over burst erasure channels. In this paper, we propose band splitting permutations (BSP) suitable for $(l,r,L)$ SC-codes. The BSP splits a diagonal band in a base matrix into multiple bands in order to enhance the span of the stopping sets in the base matrix. As theoretical performance guarantees, lower and upper bounds on the maximal burst correctable length of the permuted $(l,r,L)$ SC-codes are presented. Those bounds indicate that the maximal correctable burst ratio of the permuted SC-codes converges to 1/k where k=r/l. This implies the asymptotic optimality of the permuted SC-codes in terms of burst erasure correction.
Mechanism Design with Strategic Mediators
Venue: arXiv cs.GT 2015
Year: 2015

We consider the problem of designing mechanisms that interact with strategic agents through strategic intermediaries (or mediators), and investigate the cost to society due to the mediators' strategic behavior. Selfish agents with private information are each associated with exactly one strategic mediator, and can interact with the mechanism exclusively through that mediator. Each mediator aims to optimize the combined utility of his agents, while the mechanism aims to optimize the combined utility of all agents. We focus on the problem of facility location on a metric induced by a publicly known tree. With non-strategic mediators, there is a dominant strategy mechanism that is optimal. We show that when both agents and mediators act strategically, there is no dominant strategy mechanism that achieves any approximation. We, thus, slightly relax the incentive constraints, and define the notion of a two-sided incentive compatible mechanism. We show that the $3$-competitive deterministic mechanism suggested by Procaccia and Tennenholtz (2013) and Dekel et al. (2010) for lines extends naturally to trees, and is still $3$-competitive as well as two-sided incentive compatible. This is essentially the best possible. We then show that by allowing randomization one can construct a $2$-competitive randomized mechanism that is two-sided incentive compatible, and this is also essentially tight. This result also closes a gap left in the work of Procaccia and Tennenholtz (2013) and Lu et al. (2009) for the simpler problem of designing strategy-proof mechanisms for weighted agents with no mediators on a line, while extending to the more general model of trees. We also investigate a further generalization of the above setting where there are multiple levels of mediators.
Fragments of ML Decidable by Nested Data Class Memory Automata
Venue: arXiv cs.PL 2015
Year: 2015

The call-by-value language RML may be viewed as a canonical restriction of Standard ML to ground-type references, augmented by a "bad variable" construct in the sense of Reynolds. We consider the fragment of (finitary) RML terms of order at most 1 with free variables of order at most 2, and identify two subfragments of this for which we show observational equivalence to be decidable. The first subfragment consists of those terms in which the P-pointers in the game semantic representation are determined by the underlying sequence of moves. The second subfragment consists of terms in which the O-pointers of moves corresponding to free variables in the game semantic representation are determined by the underlying moves. These results are shown using a reduction to a form of automata over data words in which the data values have a tree-structure, reflecting the tree-structure of the threads in the game semantic plays. In addition we show that observational equivalence is undecidable at every third- or higher-order type, every second-order type which takes at least two first-order arguments, and every second-order type (of arity greater than one) that has a first-order argument which is not the final argument.
Mathematical Programs for Belief Propagation and Consensus
Venue: arXiv cs.SY 2015
Year: 2015

This paper develops methods of distributed Bayesian hypothesis tests for fault detection and diagnosis that are based on belief propagation and optimization in graphical models. The main challenges in developing distributed statistical estimation algorithms are i) difficulties in ensuring convergence and consensus for solutions of distributed inference problems, ii) increasing computational costs due to lack of scalability, and iii) communication constraints for networked multi-agent systems. To cope with those challenges, this manuscript considers i) belief propagation and optimization in graphical models of complex distributed systems, ii) decomposition methods of optimization for parallel and iterative computations, and iii) distributed decision-making protocols.
k variables are needed to define k-Clique in first-order logic
Venue: arXiv cs.LO 2015
Year: 2015

In an early paper, Immerman raised a proposal on developing model-theoretic techniques to prove lower bounds on ordered structures, which represents a long-standing challenge in finite model theory. An iconic question standing for such a challenge is how many variables are needed to define $k$-Clique in first-order logic on the class of finite ordered graphs? If $k$ variables are necessary, as widely believed, it would imply that the bounded (or finite) variable hierarchy in first-order logic is strict on the class of finite ordered graphs. In 2008, Rossman made a breakthrough by establishing an optimal average-case lower bound on the size of constant-depth unbounded fan-in circuits computing $k$-Clique. In terms of logic, this means that it needs greater than $\lfloor\frac{k} {4}\rfloor$ variables to describe the $k$-Clique problem in first-order logic on the class of finite ordered graphs, even in the presence of arbitrary arithmetic predicates. It follows, with an unpublished result of Immerman, that the bounded variable hierarchy in first-order logic is indeed strict. However, Rossman's methods come from circuit complexity and a novel notion of sensitivity by himself. And the challenge before finite model theory remains there. In this paper, we give an alternative proof for the strictness of bounded variable hierarchy in $\fo$ using pure model-theoretic toolkit, and anwser the question completely for first-order logic, i.e. $k$-variables are indeed needed to describe $k$-Clique in this logic. In contrast to Rossman's proof, our proof is purely constructive. Then we embed the main structures into a pure arithmetic structure to show a similar result where arbitrary arithmetic predicates are presented. Finally, we discuss its application in circuit complexity.