OpenRaiser/Intern-Atlas huggingface dataset:
Millimeter Wave MIMO Channel Estimation Based on Adaptive Compressed Sensing
Venue: arXiv cs.IT 2017
Year: 2017

Multiple-input multiple-output (MIMO) systems are well suited for millimeter-wave (mmWave) wireless communications where large antenna arrays can be integrated in small form factors due to tiny wavelengths, thereby providing high array gains while supporting spatial multiplexing, beamforming, or antenna diversity. It has been shown that mmWave channels exhibit sparsity due to the limited number of dominant propagation paths, thus compressed sensing techniques can be leveraged to conduct channel estimation at mmWave frequencies. This paper presents a novel approach of constructing beamforming dictionary matrices for sparse channel estimation using the continuous basis pursuit (CBP) concept, and proposes two novel low-complexity algorithms to exploit channel sparsity for adaptively estimating multipath channel parameters in mmWave channels. We verify the performance of the proposed CBP-based beamforming dictionary and the two algorithms using a simulator built upon a three-dimensional mmWave statistical spatial channel model, NYUSIM, that is based on real-world propagation measurements. Simulation results show that the CBP-based dictionary offers substantially higher estimation accuracy and greater spectral efficiency than the grid-based counterpart introduced by previous researchers, and the algorithms proposed here render better performance but require less computational effort compared with existing algorithms.
SINR and Throughput of Dense Cellular Networks with Stretched Exponential Path Loss
Venue: arXiv cs.IT 2017
Year: 2017

Distance-based attenuation is a critical aspect of wireless communications. As opposed to the ubiquitous power-law path loss model, this paper proposes a stretched exponential path loss model that is suitable for short-range communication. In this model, the signal power attenuates over a distance $r$ as $e^{-αr^β}$, where $α,β$ are tunable parameters. Using experimental propagation measurements, we show that the proposed model is accurate for short to moderate distances in the range $r \in (5,300)$ meters and so is a suitable model for dense and ultradense networks. We integrate this path loss model into a downlink cellular network with base stations modeled by a Poisson point process, and derive expressions for the coverage probability, potential throughput, and area spectral efficiency. Although the most general result for coverage probability has a double integral, several special cases are given where the coverage probability has a compact or even closed form. We then show that the potential throughput is maximized for a particular BS density and then collapses to zero for high densities, assuming a fixed SINR threshold. We next prove that the area spectral efficiency, which assumes an adaptive SINR threshold, is non-decreasing with the BS density and converges to a constant for high densities.
LRC: Dependency-Aware Cache Management for Data Analytics Clusters
Venue: arXiv cs.DC 2017
Year: 2017

Memory caches are being aggressively used in today's data-parallel systems such as Spark, Tez, and Piccolo. However, prevalent systems employ rather simple cache management policies--notably the Least Recently Used (LRU) policy--that are oblivious to the application semantics of data dependency, expressed as a directed acyclic graph (DAG). Without this knowledge, memory caching can at best be performed by "guessing" the future data access patterns based on historical information (e.g., the access recency and/or frequency), which frequently results in inefficient, erroneous caching with low hit ratio and a long response time. In this paper, we propose a novel cache replacement policy, Least Reference Count (LRC), which exploits the application-specific DAG information to optimize the cache management. LRC evicts the cached data blocks whose reference count is the smallest. The reference count is defined, for each data block, as the number of dependent child blocks that have not been computed yet. We demonstrate the efficacy of LRC through both empirical analysis and cluster deployments against popular benchmarking workloads. Our Spark implementation shows that, compared with LRU, LRC speeds up typical applications by 60%.
Diffusion L0-norm constraint improved proportionate LMS algorithm for sparse distributed estimation
Venue: arXiv cs.IT 2017
Year: 2017

To exploit the sparsity of the considered system, the diffusion proportionate-type least mean square (PtLMS) algorithms assign different gains to each tap in the convergence stage while the diffusion sparsity-constrained LMS (ScLMS) algorithms pull the components towards zeros in the steady-state stage. In this paper, by minimizing a differentiable cost function that utilizes the Riemannian distance between the updated and previous weight vectors as well as the L0 norm of the weighted updated weight vector, we propose a diffusion L0-norm constraint improved proportionate LMS (L0-IPLMS) algorithm, which combines the benefits of the diffusion PtLMS and diffusion ScLMS algorithms and performs the best performance among them. Simulations in a system identification context confirm the improvement of the proposed algorithm.
Interacting Conceptual Spaces I : Grammatical Composition of Concepts
Venue: arXiv cs.LO 2017
Year: 2017

The categorical compositional approach to meaning has been successfully applied in natural language processing, outperforming other models in mainstream empirical language processing tasks. We show how this approach can be generalized to conceptual space models of cognition. In order to do this, first we introduce the category of convex relations as a new setting for categorical compositional semantics, emphasizing the convex structure important to conceptual space applications. We then show how to construct conceptual spaces for various types such as nouns, adjectives and verbs. Finally we show by means of examples how concepts can be systematically combined to establish the meanings of composite phrases from the meanings of their constituent parts. This provides the mathematical underpinnings of a new compositional approach to cognition.
Metric random matchings with applications
Venue: arXiv cs.DS 2017
Year: 2017

Let $(\{1,2,\ldots,n\},d)$ be a metric space. We analyze the expected value and the variance of $\sum_{i=1}^{\lfloor n/2\rfloor}\,d({\boldsymbolπ}(2i-1),{\boldsymbolπ}(2i))$ for a uniformly random permutation ${\boldsymbolπ}$ of $\{1,2,\ldots,n\}$, leading to the following results: (I) Consider the problem of finding a point in $\{1,2,\ldots,n\}$ with the minimum sum of distances to all points. We show that this problem has a randomized algorithm that (1) always outputs a $(2+ε)$-approximate solution in expected $O(n/ε^2)$ time and that (2) inherits Indyk's~\cite{Ind99, Ind00} algorithm to output a $(1+ε)$-approximate solution in $O(n/ε^2)$ time with probability $Ω(1)$, where $ε\in(0,1)$. (II) The average distance in $(\{1,2,\ldots,n\},d)$ can be approximated in $O(n/ε)$ time to within a multiplicative factor in $[\,1/2-ε,1\,]$ with probability $1/2+Ω(1)$, where $ε>0$. (III) Assume $d$ to be a graph metric. Then the average distance in $(\{1,2,\ldots,n\},d)$ can be approximated in $O(n)$ time to within a multiplicative factor in $[\,1-ε,1+ε\,]$ with probability $1/2+Ω(1)$, where $ε=ω(1/n^{1/4})$.
Linear classifier design under heteroscedasticity in Linear Discriminant Analysis
Venue: arXiv cs.LG 2017
Year: 2017

Under normality and homoscedasticity assumptions, Linear Discriminant Analysis (LDA) is known to be optimal in terms of minimising the Bayes error for binary classification. In the heteroscedastic case, LDA is not guaranteed to minimise this error. Assuming heteroscedasticity, we derive a linear classifier, the Gaussian Linear Discriminant (GLD), that directly minimises the Bayes error for binary classification. In addition, we also propose a local neighbourhood search (LNS) algorithm to obtain a more robust classifier if the data is known to have a non-normal distribution. We evaluate the proposed classifiers on two artificial and ten real-world datasets that cut across a wide range of application areas including handwriting recognition, medical diagnosis and remote sensing, and then compare our algorithm against existing LDA approaches and other linear classifiers. The GLD is shown to outperform the original LDA procedure in terms of the classification accuracy under heteroscedasticity. While it compares favourably with other existing heteroscedastic LDA approaches, the GLD requires as much as 60 times lower training time on some datasets. Our comparison with the support vector machine (SVM) also shows that, the GLD, together with the LNS, requires as much as 150 times lower training time to achieve an equivalent classification accuracy on some of the datasets. Thus, our algorithms can provide a cheap and reliable option for classification in a lot of expert systems.
Local Deep Neural Networks for Age and Gender Classification
Venue: arXiv cs.CV 2017
Year: 2017

Local deep neural networks have been recently introduced for gender recognition. Although, they achieve very good performance they are very computationally expensive to train. In this work, we introduce a simplified version of local deep neural networks which significantly reduces the training time. Instead of using hundreds of patches per image, as suggested by the original method, we propose to use 9 overlapping patches per image which cover the entire face region. This results in a much reduced training time, since just 9 patches are extracted per image instead of hundreds, at the expense of a slightly reduced performance. We tested the proposed modified local deep neural networks approach on the LFW and Adience databases for the task of gender and age classification. For both tasks and both databases the performance is up to 1% lower compared to the original version of the algorithm. We have also investigated which patches are more discriminative for age and gender classification. It turns out that the mouth and eyes regions are useful for age classification, whereas just the eye region is useful for gender classification.
Generalized Nash Equilibrium Problem by the Alternating Direction Method of Multipliers
Venue: arXiv cs.GT 2017
Year: 2017

In this paper, the problem of finding a generalized Nash equilibrium (GNE) of a networked game is studied. Players are only able to choose their decisions from a feasible action set. The feasible set is considered to be a private linear equality constraint that is coupled through decisions of the other players. We consider that each player has his own private constraint and it has not to be shared with the other players. This general case also embodies the one with shared constraints between players and it can be also simply extended to the case with inequality constraints. Since the players don't have access to other players' actions, they need to exchange estimates of others' actions and a local copy of the Lagrangian multiplier with their neighbors over a connected communication graph. We develop a relatively fast algorithm by reformulating the conservative GNE problem within the framework of inexact-ADMM. The convergence of the algorithm is guaranteed under a few mild assumptions on cost functions. Finally, the algorithm is simulated for a wireless ad-hoc network.
Radiomics strategies for risk assessment of tumour failure in head-and-neck cancer
Venue: arXiv cs.CV 2017
Year: 2017

Quantitative extraction of high-dimensional mineable data from medical images is a process known as radiomics. Radiomics is foreseen as an essential prognostic tool for cancer risk assessment and the quantification of intratumoural heterogeneity. In this work, 1615 radiomic features (quantifying tumour image intensity, shape, texture) extracted from pre-treatment FDG-PET and CT images of 300 patients from four different cohorts were analyzed for the risk assessment of locoregional recurrences (LR) and distant metastases (DM) in head-and-neck cancer. Prediction models combining radiomic and clinical variables were constructed via random forests and imbalance-adjustment strategies using two of the four cohorts. Independent validation of the prediction and prognostic performance of the models was carried out on the other two cohorts (LR: AUC = 0.69 and CI = 0.67; DM: AUC = 0.86 and CI = 0.88). Furthermore, the results obtained via Kaplan-Meier analysis demonstrated the potential of radiomics for assessing the risk of specific tumour outcomes using multiple stratification groups. This could have important clinical impact, notably by allowing for a better personalization of chemo-radiation treatments for head-and-neck cancer patients from different risk groups.
Channel Impulse Response-based Distributed Physical Layer Authentication
Venue: arXiv cs.IT 2017
Year: 2017

In this preliminary work, we study the problem of {\it distributed} authentication in wireless networks. Specifically, we consider a system where multiple Bob (sensor) nodes listen to a channel and report their {\it correlated} measurements to a Fusion Center (FC) which makes the ultimate authentication decision. For the feature-based authentication at the FC, channel impulse response has been utilized as the device fingerprint. Additionally, the {\it correlated} measurements by the Bob nodes allow us to invoke Compressed sensing to significantly reduce the reporting overhead to the FC. Numerical results show that: i) the detection performance of the FC is superior to that of a single Bob-node, ii) compressed sensing leads to at least $20\%$ overhead reduction on the reporting channel at the expense of a small ($<1$ dB) SNR margin to achieve the same detection performance.
Informational Substitutes
Venue: arXiv cs.GT 2017
Year: 2017

We propose definitions of substitutes and complements for pieces of information ("signals") in the context of a decision or optimization problem, with game-theoretic and algorithmic applications. In a game-theoretic context, substitutes capture diminishing marginal value of information to a rational decision maker. We use the definitions to address the question of how and when information is aggregated in prediction markets. Substitutes characterize "best-possible" equilibria with immediate information aggregation, while complements characterize "worst-possible", delayed aggregation. Game-theoretic applications also include settings such as crowdsourcing contests and Q\&A forums. In an algorithmic context, where substitutes capture diminishing marginal improvement of information to an optimization problem, substitutes imply efficient approximation algorithms for a very general class of (adaptive) information acquisition problems. In tandem with these broad applications, we examine the structure and design of informational substitutes and complements. They have equivalent, intuitive definitions from disparate perspectives: submodularity, geometry, and information theory. We also consider the design of scoring rules or optimization problems so as to encourage substitutability or complementarity, with positive and negative results. Taken as a whole, the results give some evidence that, in parallel with substitutable items, informational substitutes play a natural conceptual and formal role in game theory and algorithms.
Maximizing the area of intersection of rectangles
Venue: arXiv cs.DS 2017
Year: 2017

This paper attacks the following problem. We are given a large number $N$ of rectangles in the plane, each with horizontal and vertical sides, and also a number $r<N$. The given list of $N$ rectangles may contain duplicates. The problem is to find $r$ of these rectangles, such that, if they are discarded, then the intersection of the remaining $(N-r)$ rectangles has an intersection with as large an area as possible. We will find an upper bound, depending only on $N$ and $r$, and not on the particular data presented, for the number of steps needed to run the algorithm on (a mathematical model of) a computer. In fact our algorithm is able to determine, for each $s\le r$, $s$ rectangles from the given list of $N$ rectangles, such that the remaining $(N-s)$ rectangles have as large an area as possible, and this takes hardly any more time than taking care only of the case $s=r$. Our algorithm extends to $d$-dimensional rectangles. Our method is to exhaustively examine all possible intersections---this is much faster than it sounds, because we do not need to examine all $\binom Ns$ subsets in order to find all possible intersection rectangles. For an extreme example, suppose the rectangles are nested, for example concentric squares of distinct sizes, then the only intersections examined are the smallest $s+1$ rectangles.
Applied Type System: An Approach to Practical Programming with Theorem-Proving
Venue: arXiv cs.PL 2017
Year: 2017

The framework Pure Type System (PTS) offers a simple and general approach to designing and formalizing type systems. However, in the presence of dependent types, there often exist certain acute problems that make it difficult for PTS to directly accommodate many common realistic programming features such as general recursion, recursive types, effects (e.g., exceptions, references, input/output), etc. In this paper, Applied Type System (ATS) is presented as a framework for designing and formalizing type systems in support of practical programming with advanced types (including dependent types). In particular, it is demonstrated that ATS can readily accommodate a paradigm referred to as programming with theorem-proving (PwTP) in which programs and proofs are constructed in a syntactically intertwined manner, yielding a practical approach to internalizing constraint-solving needed during type-checking. The key salient feature of ATS lies in a complete separation between statics, where types are formed and reasoned about, and dynamics, where programs are constructed and evaluated. With this separation, it is no longer possible for a program to occur in a type as is otherwise allowed in PTS. The paper contains not only a formal development of ATS but also some examples taken from ats-lang.org, a programming language with a type system rooted in ATS, in support of employing ATS as a framework to formulate advanced type systems for practical programming.
A New Paradigm for Robotic Dust Collection: Theorems, User Studies, and a Field Study
Venue: arXiv cs.RO 2017
Year: 2017

We pioneer a new future in robotic dust collection by introducing passive dust-collecting robots that, unlike their predecessors, do not require locomotion to collect dust. While previous research has exclusively focused on active dust-collecting robots, we show that these robots fail with respect to practical and theoretical aspects, as well as human factors. By contrast, passive robots, through their unconstrained versatility, shine brilliantly in all three metrics. We present a mathematical formalism of both paradigms followed by a user study and field study.
Proof Verification Can Be Hard!
Venue: arXiv cs.LO 2017
Year: 2017

The generally accepted wisdom in computational circles is that pure proof verification is a solved problem and that the computationally hard elements and fertile areas of study lie in proof discovery. This wisdom presumably does hold for conventional proof systems such as first-order logic with a standard proof calculus such as natural deduction or resolution. But this folk belief breaks down when we consider more user-friendly/powerful inference rules. One such rule is the restricted ω-rule, which is not even semi-decidable when added to a standard proof calculus of a nice theory. While presumably not a novel result, we feel that the hardness of proof verification is under-appreciated in most communities that deal with proofs. A proof-sketch follows.
Team Formation for Scheduling Educational Material in Massive Online Classes
Venue: arXiv cs.AI 2017
Year: 2017

Whether teaching in a classroom or a Massive Online Open Course it is crucial to present the material in a way that benefits the audience as a whole. We identify two important tasks to solve towards this objective, 1 group students so that they can maximally benefit from peer interaction and 2 find an optimal schedule of the educational material for each group. Thus, in this paper, we solve the problem of team formation and content scheduling for education. Given a time frame d, a set of students S with their required need to learn different activities T and given k as the number of desired groups, we study the problem of finding k group of students. The goal is to teach students within time frame d such that their potential for learning is maximized and find the best schedule for each group. We show this problem to be NP-hard and develop a polynomial algorithm for it. We show our algorithm to be effective both on synthetic as well as a real data set. For our experiments, we use real data on students' grades in a Computer Science department. As part of our contribution, we release a semi-synthetic dataset that mimics the properties of the real data.
Assortative Mixing Equilibria in Social Network Games
Venue: arXiv cs.SI 2017
Year: 2017

It is known that individuals in social networks tend to exhibit homophily (a.k.a. assortative mixing) in their social ties, which implies that they prefer bonding with others of their own kind. But what are the reasons for this phenomenon? Is it that such relations are more convenient and easier to maintain? Or are there also some more tangible benefits to be gained from this collective behaviour? The current work takes a game-theoretic perspective on this phenomenon, and studies the conditions under which different assortative mixing strategies lead to equilibrium in an evolving social network. We focus on a biased preferential attachment model where the strategy of each group (e.g., political or social minority) determines the level of bias of its members toward other group members and non-members. Our first result is that if the utility function that the group attempts to maximize is the degree centrality of the group, interpreted as the sum of degrees of the group members in the network, then the only strategy achieving Nash equilibrium is a perfect homophily, which implies that cooperation with other groups is harmful to this utility function. A second, and perhaps more surprising, result is that if a reward for inter-group cooperation is added to the utility function (e.g., externally enforced by an authority as a regulation), then there are only two possible equilibria, namely, perfect homophily or perfect heterophily, and it is possible to characterize their feasibility spaces. Interestingly, these results hold regardless of the minority-majority ratio in the population. We believe that these results, as well as the game-theoretic perspective presented herein, may contribute to a better understanding of the forces that shape the groups and communities of our society.