OpenRaiser/Intern-Atlas huggingface dataset:
Exact Minkowski Sums of Polygons With Holes
Venue: arXiv cs.CG 2015
Year: 2015

We present an efficient algorithm that computes the Minkowski sum of two polygons, which may have holes. The new algorithm is based on the convolution approach. Its efficiency stems in part from a property for Minkowski sums of polygons with holes, which in fact holds in any dimension: Given two polygons with holes, for each input polygon we can fill up the holes that are relatively small compared to the other polygon. Specifically, we can always fill up all the holes of at least one polygon, transforming it into a simple polygon, and still obtain exactly the same Minkowski sum. Obliterating holes in the input summands speeds up the computation of Minkowski sums. We introduce a robust implementation of the new algorithm, which follows the Exact Geometric Computation paradigm and thus guarantees exact results. We also present an empirical comparison of the performance of Minkowski sum construction of various input examples, where we show that the implementation of the new algorithm exhibits better performance than several other implementations in many cases. In particular, we compared the implementation of the new algorithm, an implementation of the standard convolution algorithm, and an implementation of the decomposition approach using various convex decomposition methods, including two new methods that handle polygons with holes - one is based on vertical decomposition and the other is based on triangulation. The software has been developed as an extension of the "2D Minkowski Sums" package of CGAL (Computational Geometry Algorithms Library). Additional information and supplementary material is available at our project page http://acg.cs.tau.ac.il/projects/rc
Derivation of a low multiplicative complexity algorithm for multiplying hyperbolic octonions
Venue: arXiv cs.DS 2015
Year: 2015

We present an efficient algorithm to multiply two hyperbolic octonions. The direct multiplication of two hyperbolic octonions requires 64 real multiplications and 56 real additions. More effective solutions still do not exist. We show how to compute a product of the hyperbolic octonions with 26 real multiplications and 92 real additions. During synthesis of the discussed algorithm we use the fact that product of two hyperbolic octonions may be represented as a matrix - vector product. The matrix multiplicand that participates in the product calculating has unique structural properties that allow performing its advantageous factorization. Namely this factorization leads to significant reducing of the computational complexity of hyperbolic octonions multiplication.
The fundamental nature of the log loss function
Venue: arXiv cs.LG 2015
Year: 2015

The standard loss functions used in the literature on probabilistic prediction are the log loss function, the Brier loss function, and the spherical loss function; however, any computable proper loss function can be used for comparison of prediction algorithms. This note shows that the log loss function is most selective in that any prediction algorithm that is optimal for a given data sequence (in the sense of the algorithmic theory of randomness) under the log loss function will be optimal under any computable proper mixable loss function; on the other hand, there is a data sequence and a prediction algorithm that is optimal for that sequence under either of the two other standard loss functions but not under the log loss function.
Persistent, Global Identity for Scientists via ORCID
Venue: arXiv cs.DL 2015
Year: 2015

Scientists have an inherent interest in claiming their contributions to the scholarly record, but the fragmented state of identity management across the landscape of astronomy, physics, and other fields makes highlighting the contributions of any single individual a formidable and often frustratingly complex task. The problem is exacerbated by the expanding variety of academic research products and the growing footprints of large collaborations and interdisciplinary teams. In this essay, we outline the benefits of a unique scholarly identifier with persistent value on a global scale and we review astronomy and physics engagement with the Open Researcher and Contributor iD (ORCID) service as a solution.
Dynamic SLA Negotiation using Bandwidth Broker for Femtocell Networks
Venue: arXiv cs.NI 2015
Year: 2015

Satisfaction level of femtocell users' depends on the availability of requested bandwidth. But the xDSL line that can be used for the backhauling of femtocell traffic cannot always provide sufficient bandwidth due to the inequality between the xDSL capacity and demanded bandwidth of home applications like, IPTV, PC, WiFi, and others. A Service Level Agreement (SLA) between xDSL and femtocell operator (mobile operator) to reserve some bandwidth for the upcoming femtocell calls can increase the satisfaction level for femtocell users. In this paper we propose a SLA negotiation procedure for femtocell networks. The Bandwidth Broker controls the allocated bandwidth for femtocell users. Then we propose the dynamically reserve bandwidth scheme to increase the femtocell user's satisfaction level. Finally, we present our simulation results to validate the proposed scheme.
Hyperspectral Unmixing via Turbo Bilinear Approximate Message Passing
Venue: arXiv cs.IT 2015
Year: 2015

The goal of hyperspectral unmixing is to decompose an electromagnetic spectral dataset measured over M spectral bands and T pixels into N constituent material spectra (or "end-members") with corresponding spatial abundances. In this paper, we propose a novel approach to hyperspectral unmixing based on loopy belief propagation (BP) that enables the exploitation of spectral coherence in the endmembers and spatial coherence in the abundances. In particular, we partition the factor graph into spectral coherence, spatial coherence, and bilinear subgraphs, and pass messages between them using a "turbo" approach. To perform message passing within the bilinear subgraph, we employ the bilinear generalized approximate message passing algorithm (BiG-AMP), a recently proposed belief-propagation-based approach to matrix factorization. Furthermore, we propose an expectation-maximization (EM) strategy to tune the prior parameters and a model-order selection strategy to select the number of materials N. Numerical experiments conducted with both synthetic and real-world data show favorable unmixing performance relative to existing methods.
Rectified Factor Networks
Venue: arXiv cs.LG 2015
Year: 2015

We propose rectified factor networks (RFNs) to efficiently construct very sparse, non-linear, high-dimensional representations of the input. RFN models identify rare and small events in the input, have a low interference between code units, have a small reconstruction error, and explain the data covariance structure. RFN learning is a generalized alternating minimization algorithm derived from the posterior regularization method which enforces non-negative and normalized posterior means. We proof convergence and correctness of the RFN learning algorithm. On benchmarks, RFNs are compared to other unsupervised methods like autoencoders, RBMs, factor analysis, ICA, and PCA. In contrast to previous sparse coding methods, RFNs yield sparser codes, capture the data's covariance structure more precisely, and have a significantly smaller reconstruction error. We test RFNs as pretraining technique for deep networks on different vision datasets, where RFNs were superior to RBMs and autoencoders. On gene expression data from two pharmaceutical drug discovery studies, RFNs detected small and rare gene modules that revealed highly relevant new biological insights which were so far missed by other unsupervised methods.
Greedy Minimization of Weakly Supermodular Set Functions
Venue: arXiv cs.DS 2015
Year: 2015

This paper defines weak-$α$-supermodularity for set functions. Many optimization objectives in machine learning and data mining seek to minimize such functions under cardinality constrains. We prove that such problems benefit from a greedy extension phase. Explicitly, let $S^*$ be the optimal set of cardinality $k$ that minimizes $f$ and let $S_0$ be an initial solution such that $f(S_0)/f(S^*) \le ρ$. Then, a greedy extension $S \supset S_0$ of size $|S| \le |S_0| + \lceil αk \ln(ρ/\varepsilon) \rceil$ yields $f(S)/f(S^*) \le 1+\varepsilon$. As example usages of this framework we give new bicriteria results for $k$-means, sparse regression, and columns subset selection.
Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems
Venue: arXiv cs.CC 2015
Year: 2015

Given a large data matrix $A\in\mathbb{R}^{n\times n}$, we consider the problem of determining whether its entries are i.i.d. with some known marginal distribution $A_{ij}\sim P_0$, or instead $A$ contains a principal submatrix $A_{{\sf Q},{\sf Q}}$ whose entries have marginal distribution $A_{ij}\sim P_1\neq P_0$. As a special case, the hidden (or planted) clique problem requires to find a planted clique in an otherwise uniformly random graph. Assuming unbounded computational resources, this hypothesis testing problem is statistically solvable provided $|{\sf Q}|\ge C \log n$ for a suitable constant $C$. However, despite substantial effort, no polynomial time algorithm is known that succeeds with high probability when $|{\sf Q}| = o(\sqrt{n})$. Recently Meka and Wigderson \cite{meka2013association}, proposed a method to establish lower bounds within the Sum of Squares (SOS) semidefinite hierarchy. Here we consider the degree-$4$ SOS relaxation, and study the construction of \cite{meka2013association} to prove that SOS fails unless $k\ge C\, n^{1/3}/\log n$. An argument presented by Barak implies that this lower bound cannot be substantially improved unless the witness construction is changed in the proof. Our proof uses the moments method to bound the spectrum of a certain random association scheme, i.e. a symmetric random matrix whose rows and columns are indexed by the edges of an Erdös-Renyi random graph.
Optimization-Based Linear Network Coding for General Connections of Continuous Flows
Venue: arXiv cs.IT 2015
Year: 2015

For general connections, the problem of finding network codes and optimizing resources for those codes is intrinsically difficult and little is known about its complexity. Most of the existing solutions rely on very restricted classes of network codes in terms of the number of flows allowed to be coded together, and are not entirely distributed. In this paper, we consider a new method for constructing linear network codes for general connections of continuous flows to minimize the total cost of edge use based on mixing. We first formulate the minimumcost network coding design problem. To solve the optimization problem, we propose two equivalent alternative formulations with discrete mixing and continuous mixing, respectively, and develop distributed algorithms to solve them. Our approach allows fairly general coding across flows and guarantees no greater cost than any solution without network coding.
Load-aware Dynamic Spectrum Access for Small Cell Networks: A Graphical Game Approach
Venue: arXiv cs.IT 2015
Year: 2015

In this letter, we investigate the problem of dynamic spectrum access for small cell networks, using a graphical game approach. Compared with existing studies, we take the features of different cell loads and local interference relationship into account. It is proved that the formulated spectrum access game is an exact potential game with the aggregate interference level as the potential function, and Nash equilibrium (NE) of the game corresponds to the global or local optima of the original optimization problem. A lower bound of the achievable aggregate interference level is rigorously derived. Finally, we propose an autonomous best response learning algorithm to converge towards its NE. It is shown that the proposed game-theoretic solution converges rapidly and its achievable performance is close to the optimum solution.
Ecosystem: A Characteristic Of Crowdsourced Environments
Venue: arXiv cs.CY 2015
Year: 2015

The phenomenal success of certain crowdsourced online platforms, such as Wikipedia, is accredited to their ability to tap the crowd's potential to collaboratively build knowledge. While it is well known that the crowd's collective wisdom surpasses the cumulative individual expertise, little is understood on the dynamics of knowledge building in a crowdsourced environment. A proper understanding of the dynamics of knowledge building in a crowdsourced environment would enable one in the better designing of such environments to solicit knowledge from the crowd. Our experiment on crowdsourced systems based on annotations shows that an important reason for the rapid knowledge building in such environments is due to variance in expertise. First, we used as our test bed, a customized Crowdsourced Annotation System (CAS) which provides a group of users the facility to annotate a given document while trying to understand it. Our results showed the presence of different genres of proficiency amongst the users of an annotation system. We observed that the ecosystem in crowdsourced annotation system comprised of mainly four categories of contributors, namely: Probers, Solvers, Articulators and Explorers. We inferred from our experiment that the knowledge garnering mainly happens due to the synergetic interaction across these categories. Further, we conducted an analysis on the dataset of Wikipedia and Stack Overflow and noticed the ecosystem presence in these portals as well. From this study, we claim that the ecosystem is a universal characteristic of all crowdsourced portals.
Optimal Linear and Cyclic Locally Repairable Codes over Small Fields
Venue: arXiv cs.IT 2015
Year: 2015

We consider locally repairable codes over small fields and propose constructions of optimal cyclic and linear codes in terms of the dimension for a given distance and length. Four new constructions of optimal linear codes over small fields with locality properties are developed. The first two approaches give binary cyclic codes with locality two. While the first construction has availability one, the second binary code is characterized by multiple available repair sets based on a binary Simplex code. The third approach extends the first one to q-ary cyclic codes including (binary) extension fields, where the locality property is determined by the properties of a shortened first-order Reed-Muller code. Non-cyclic optimal binary linear codes with locality greater than two are obtained by the fourth construction.
Personalized Security Indicators to Detect Application Phishing Attacks in Mobile Platforms
Venue: arXiv cs.CR 2015
Year: 2015

Phishing in mobile applications is a relevant threat with successful attacks reported in the wild. In such attacks, malicious mobile applications masquerade as legitimate ones to steal user credentials. In this paper we categorize application phishing attacks in mobile platforms and possible countermeasures. We show that personalized security indicators can help users to detect phishing attacks and have very little deployment cost. Personalized security indicators, however, rely on the user alertness to detect phishing attacks. Previous work in the context of website phishing has shown that users tend to ignore the absence of security indicators and fall victim of the attacker. Consequently, the research community has deemed personalized security indicators as an ineffective phishing detection mechanism. We evaluate personalized security indicators as a phishing detection solution in the context of mobile applications. We conducted a large-scale user study where a significant amount of participants that used personalized security indicators were able to detect phishing. All participants that did not use indicators could not detect the attack and entered their credentials to a phishing application. We found the difference in the attack detection ratio to be statistically significant. Personalized security indicators can, therefore, help phishing detection in mobile applications and their reputation as an anti-phishing mechanism should be reconsidered. We also propose a novel protocol to setup personalized security indicators under a strong adversarial model and provide details on its performance and usability.
Transformation of basic probability assignments to probabilities based on a new entropy measure
Venue: arXiv cs.AI 2015
Year: 2015

Dempster-Shafer evidence theory is an efficient mathematical tool to deal with uncertain information. In that theory, basic probability assignment (BPA) is the basic element for the expression and inference of uncertainty. Decision-making based on BPA is still an open issue in Dempster-Shafer evidence theory. In this paper, a novel approach of transforming basic probability assignments to probabilities is proposed based on Deng entropy which is a new measure for the uncertainty of BPA. The principle of the proposed method is to minimize the difference of uncertainties involving in the given BPA and obtained probability distribution. Numerical examples are given to show the proposed approach.
Privacy preserving distributed profile matching in mobile social network
Venue: arXiv cs.CR 2015
Year: 2015

In this document, a privacy-preserving distributed profile matching protocol is proposed in a particular network context called \emph{mobile social network}. Such networks are often deployed in more or less hostile environments, requiring rigorous security mechanisms. In the same time, energy and computational resources are limited as these heterogeneous networks are frequently constituted by wireless components like tablets or mobile phones. This is why a new encryption algorithm having an high level of security while preserving resources is proposed in this paper. The approach is based on elliptic curve cryptography, more specifically on an almost completely homomorphic cryptosystem over a supersingular elliptic curve, leading to a secure and efficient preservation of privacy in distributed profile matching.
A framework to discover potential ideas of new product development from crowdsourcing application
Venue: arXiv cs.IR 2015
Year: 2015

In this paper, we study idea mining from crowdsourcing applications which encourage a group of people, who are usually undefined and very large sized, to generate ideas for new product development (NPD). In order to isolate the relatively small number of potential ones among ideas from crowd, decision makers not only have to identify the key textual information representing the ideas, but they also need to consider online opinions of people who gave comments and votes on the ideas. Due to the extremely large size of text data generated by people on the Internet, identifying textual information has been carried out in manual ways, and has been considered very time consuming and costly. To overcome the ineffectiveness, this paper introduces a novel framework that can help decision makers discover ideas having the potential to be used in an NPD process. To achieve this, a semi-automatic text mining technique that retrieves useful text patterns from ideas posted on crowdsourcing application is proposed. Then, we provide an online learning algorithm to evaluate whether the idea is potential or not. Finally to verify the effectiveness of our algorithm, we conducted experiments on the data, which are collected from an existing crowd sourcing website.
Describing Colors, Textures and Shapes for Content Based Image Retrieval - A Survey
Venue: arXiv cs.IR 2015
Year: 2015

Visual media has always been the most enjoyed way of communication. From the advent of television to the modern day hand held computers, we have witnessed the exponential growth of images around us. Undoubtedly it's a fact that they carry a lot of information in them which needs be utilized in an effective manner. Hence intense need has been felt to efficiently index and store large image collections for effective and on- demand retrieval. For this purpose low-level features extracted from the image contents like color, texture and shape has been used. Content based image retrieval systems employing these features has proven very successful. Image retrieval has promising applications in numerous fields and hence has motivated researchers all over the world. New and improved ways to represent visual content are being developed each day. Tremendous amount of research has been carried out in the last decade. In this paper we will present a detailed overview of some of the powerful color, texture and shape descriptors for content based image retrieval. A comparative analysis will also be carried out for providing an insight into outstanding challenges in this field.
Exploiting a comparability mapping to improve bi-lingual data categorization: a three-mode data analysis perspective
Venue: arXiv cs.IR 2015
Year: 2015

We address in this paper the co-clustering and co-classification of bilingual data laying in two linguistic similarity spaces when a comparability measure defining a mapping between these two spaces is available. A new approach that we can characterized as a three-mode analysis scheme, is proposed to mix the comparability measure with the two similarity measures. Our aim is to improve jointly the accuracy of classification and clustering tasks performed in each of the two linguistic spaces, as well as the quality of the final alignment of comparable clusters that can be obtained. We used first some purely synthetic random data sets to assess our formal similarity-comparability mixing model. We then propose two variants of the comparability measure that has been defined by (Li and Gaussier 2010) in the context of bilingual lexicon extraction to adapt it to clustering or categorizing tasks. These two variant measures are subsequently used to evaluate our similarity-comparability mixing model in the context of the co-classification and co-clustering of comparable textual data sets collected from Wikipedia categories for the English and French languages. Our experiments show clear improvements in clustering and classification accuracies when mixing comparability with similarity measures, with, as expected, a higher robustness obtained when the two comparability variant measures that we propose are used. We believe that this approach is particularly well suited for the construction of thematic comparable corpora of controllable quality.
A Survey of Millimeter Wave (mmWave) Communications for 5G: Opportunities and Challenges
Venue: arXiv cs.NI 2015
Year: 2015

With the explosive growth of mobile data demand, the fifth generation (5G) mobile network would exploit the enormous amount of spectrum in the millimeter wave (mmWave) bands to greatly increase communication capacity. There are fundamental differences between mmWave communications and existing other communication systems, in terms of high propagation loss, directivity, and sensitivity to blockage. These characteristics of mmWave communications pose several challenges to fully exploit the potential of mmWave communications, including integrated circuits and system design, interference management, spatial reuse, anti-blockage, and dynamics control. To address these challenges, we carry out a survey of existing solutions and standards, and propose design guidelines in architectures and protocols for mmWave communications. We also discuss the potential applications of mmWave communications in the 5G network, including the small cell access, the cellular access, and the wireless backhaul. Finally, we discuss relevant open research issues including the new physical layer technology, software-defined network architecture, measurements of network state information, efficient control mechanisms, and heterogeneous networking, which should be further investigated to facilitate the deployment of mmWave communication systems in the future 5G networks.