OpenRaiser/Intern-Atlas huggingface dataset:
Effective Spectral Unmixing via Robust Representation and Learning-based Sparsity
Venue: arXiv cs.CV 2017
Year: 2017

Hyperspectral unmixing (HU) plays a fundamental role in a wide range of hyperspectral applications. It is still challenging due to the common presence of outlier channels and the large solution space. To address the above two issues, we propose a novel model by emphasizing both robust representation and learning-based sparsity. Specifically, we apply the $\ell_{2,1}$-norm to measure the representation error, preventing outlier channels from dominating our objective. In this way, the side effects of outlier channels are greatly relieved. Besides, we observe that the mixed level of each pixel varies over image grids. Based on this observation, we exploit a learning-based sparsity method to simultaneously learn the HU results and a sparse guidance map. Via this guidance map, the sparsity constraint in the $\ell_{p}\!\left(\!0\!<\! p\!\leq\!1\right)$-norm is adaptively imposed according to the learnt mixed level of each pixel. Compared with state-of-the-art methods, our model is better suited to the real situation, thus expected to achieve better HU results. The resulted objective is highly non-convex and non-smooth, and so it is hard to optimize. As a profound theoretical contribution, we propose an efficient algorithm to solve it. Meanwhile, the convergence proof and the computational complexity analysis are systematically provided. Extensive evaluations verify that our method is highly promising for the HU task---it achieves very accurate guidance maps and much better HU results compared with state-of-the-art methods.
The complexity of approximating complex-valued Ising and Tutte partition functions
Venue: arXiv cs.CC 2017
Year: 2017

We study the complexity of approximately evaluating the Ising and Tutte partition functions with complex parameters. Our results are partly motivated by the study of the quantum complexity classes BQP and IQP. Recent results show how to encode quantum computations as evaluations of classical partition functions. These results rely on interesting and deep results about quantum computation in order to obtain hardness results about the difficulty of (classically) evaluating the partition functions for certain fixed parameters. The motivation for this paper is to study more comprehensively the complexity of (classically) approximating the Ising and Tutte partition functions with complex parameters. Partition functions are combinatorial in nature and quantifying their approximation complexity does not require a detailed understanding of quantum computation. Using combinatorial arguments, we give the first full classification of the complexity of multiplicatively approximating the norm and additively approximating the argument of the Ising partition function for complex edge interactions (as well as of approximating the partition function according to a natural complex metric). We also study the norm approximation problem in the presence of external fields, for which we give a complete dichotomy when the parameters are roots of unity. Previous results were known just for a few such points, and we strengthen these results from BQP-hardness to #P-hardness. Moreover, we show that computing the sign of the Tutte polynomial is #P-hard at certain points related to the simulation of BQP. Using our classifications, we then revisit the connections to quantum computation, drawing conclusions that are a little different from (and incomparable to) ones in the quantum literature, but along similar lines.
An Efficient Heuristic for Betweenness-Ordering
Venue: arXiv cs.SI 2017
Year: 2017

Centrality measures, erstwhile popular amongst the sociologists and psychologists, have seen broad and increasing applications across several disciplines of late. Amongst a plethora of application specific definitions available in the literature to rank the vertices, closeness centrality, betweenness centrality and eigenvector centrality (page-rank) have been the most important and widely applied ones. Networks where information, signal or commodities are flowing on the edges, surrounds us. Betweenness centrality comes as a handy tool to analyze such systems, but betweenness computation is a daunting task in large size networks. In this paper, we propose an efficient heuristic to determine the betweenness-ordering of $k$ vertices (where $k$ is very less than the total number of vertices) without computing their exact betweenness indices. The algorithm is based on a non-uniform node sampling model which is developed based on the analysis of Erdos-Renyi graphs. We apply our approach to find the betweenness-ordering of vertices in several synthetic and real-world graphs. The proposed heuristic results very efficient ordering even when runs for a linear time in the terms of the number of edges. We compare our method with the available techniques in the literature and show that our method produces more efficient ordering than the currently known methods.
Space-Efficient Manifest Contracts
Venue: arXiv cs.PL 2017
Year: 2017

The standard algorithm for higher-order contract checking can lead to unbounded space consumption and can destroy tail recursion, altering a program's asymptotic space complexity. While space efficiency for gradual types---contracts mediating untyped and typed code---is well studied, sound space efficiency for manifest contracts---contracts that check stronger properties than simple types, e.g., "is a natural" instead of "is an integer"---remains an open problem. We show how to achieve sound space efficiency for manifest contracts with strong predicate contracts. The essential trick is breaking the contract checking down into coercions: structured, blame-annotated lists of checks. By carefully preventing duplicate coercions from appearing, we can restore space efficiency while keeping the same observable behavior. Along the way, we define a framework for space efficiency, traversing the design space with three different space-efficient manifest calculi. We examine the diverse correctness criteria for contract semantics; we conclude with a coercion-based language whose contracts enjoy (galactically) bounded, sound space consumption---they are observationally equivalent to the standard, space-inefficient semantics.
Inter-procedural Two-Variable Herbrand Equalities
Venue: arXiv cs.LO 2017
Year: 2017

We prove that all valid Herbrand equalities can be inter-procedurally inferred for programs where all assignments whose right-hand sides depend on at most one variable are taken into account. The analysis is based on procedure summaries representing the weakest pre-conditions for finitely many generic post-conditions with template variables. In order to arrive at effective representations for all occurring weakest pre-conditions, we show for almost all values possibly computed at run-time, that they can be uniquely factorized into tree patterns and a ground term. Moreover, we introduce an approximate notion of subsumption which is effectively decidable and ensures that finite conjunctions of equalities may not grow infinitely. Based on these technical results, we realize an effective fixpoint iteration to infer all inter-procedurally valid Herbrand equalities for these programs. Finally we show that an invariant candidate with a constant number of variables, can be verified in polynomial time.
Erasure/List Random Coding Error Exponents Are Not Universally Achievable
Venue: arXiv cs.IT 2017
Year: 2017

We study the problem of universal decoding for unknown discrete memoryless channels in the presence of erasure/list option at the decoder, in the random coding regime. Specifically, we harness a universal version of Forney's classical erasure/list decoder developed in earlier studies, which is based on the competitive minimax methodology, and guarantees universal achievability of a certain fraction of the optimum random coding error exponents. In this paper, we derive an exact single-letter expression for the maximum achievable fraction. Examples are given in which the maximal achievable fraction is strictly less than unity, which imply that, in general, there is no universal erasure/list decoder which achieves the same random coding error exponents as the optimal decoder for a known channel. This is in contrast to the situation in ordinary decoding (without the erasure/list option), where optimum exponents are universally achievable, as is well known. It is also demonstrated that previous lower bounds derived for the maximal achievable fraction are not tight in general. We then analyze a generalized random coding ensemble which incorporate a training sequence, in conjunction with a suboptimal practical decoder ("plug-in" decoder), which first estimates the channel using the known training sequence, and then decodes the remaining symbols of the codeword using the estimated channel. One of the implications of our results, is setting the stage for a reasonable criterion of optimal training. Finally, we compare the performance of the "plug-in" decoder and the universal decoder, in terms of the achievable error exponents, and show that the latter is noticeably better than the former.
Incorporating Hidden Costs of Annoying Ads in Display Auctions
Venue: arXiv cs.GT 2017
Year: 2017

Media publisher platforms often face an effectiveness-nuisance tradeoff: more annoying ads can be more effective for some advertisers because of their ability to attract attention, but after attracting viewers' attention, their nuisance to viewers can decrease engagement with the platform over time. With the rise of mobile technology and ad blockers, many platforms are becoming increasingly concerned about how to improve monetization through digital ads while improving viewer experience. We study an online ad auction mechanism that incorporates a charge for ad impact on user experience as a criterion for ad selection and pricing. Like a Pigovian tax, the charge causes advertisers to internalize the hidden cost of foregone future platform revenue due to ad impact on user experience. Over time, the mechanism provides an incentive for advertisers to develop ads that are effective while offering viewers a more pleasant experience. We show that adopting the mechanism can simultaneously benefit the publisher, advertisers, and viewers, even in the short term. Incorporating a charge for ad impact can increase expected advertiser profits if enough advertisers compete. A stronger effectiveness-nuisance tradeoff, meaning that ad effectiveness is more strongly associated with negative impact on user experience, increases the amount of competition required for the mechanism to benefit advertisers. The findings suggest that the mechanism can benefit the marketplace for ad slots that consistently attract many advertisers.
Proper Hamiltonian Cycles in Edge-Colored Multigraphs
Venue: arXiv cs.DM 2017
Year: 2017

A $c$-edge-colored multigraph has each edge colored with one of the $c$ available colors and no two parallel edges have the same color. A proper Hamiltonian cycle is a cycle containing all the vertices of the multigraph such that no two adjacent edges have the same color. In this work we establish sufficient conditions for a multigraph to have a proper Hamiltonian cycle, depending on several parameters such as the number of edges and the rainbow degree.
Big Learning with Bayesian Methods
Venue: arXiv cs.LG 2017
Year: 2017

Explosive growth in data and availability of cheap computing resources have sparked increasing interest in Big learning, an emerging subfield that studies scalable machine learning algorithms, systems, and applications with Big Data. Bayesian methods represent one important class of statistic methods for machine learning, with substantial recent developments on adaptive, flexible and scalable Bayesian learning. This article provides a survey of the recent advances in Big learning with Bayesian methods, termed Big Bayesian Learning, including nonparametric Bayesian methods for adaptively inferring model complexity, regularized Bayesian inference for improving the flexibility via posterior regularization, and scalable algorithms and systems based on stochastic subsampling and distributed computing for dealing with large-scale applications.
Efficient storage of Pareto points in biobjective mixed integer programming
Venue: arXiv cs.DS 2017
Year: 2017

In biobjective mixed integer linear programs (BOMILPs), two linear objectives are minimized over a polyhedron while restricting some of the variables to be integer. Since many of the techniques for finding or approximating the Pareto set of a BOMILP use and update a subset of nondominated solutions, it is highly desirable to efficiently store this subset. We present a new data structure, a variant of a binary tree that takes as input points and line segments in $\R^2$ and stores the nondominated subset of this input. When used within an exact solution procedure, such as branch-and-bound (BB), at termination this structure contains the set of Pareto optimal solutions. We compare the efficiency of our structure in storing solutions to that of a dynamic list which updates via pairwise comparison. Then we use our data structure in two biobjective BB techniques available in the literature and solve three classes of instances of BOMILP, one of which is generated by us. The first experiment shows that our data structure handles up to $10^7$ points or segments much more efficiently than a dynamic list. The second experiment shows that our data structure handles points and segments much more efficiently than a list when used in a BB.
Elections with Few Voters: Candidate Control Can Be Easy
Venue: arXiv cs.AI 2017
Year: 2017

We study the computational complexity of candidate control in elections with few voters, that is, we consider the parameterized complexity of candidate control in elections with respect to the number of voters as a parameter. We consider both the standard scenario of adding and deleting candidates, where one asks whether a given candidate can become a winner (or, in the destructive case, can be precluded from winning) by adding or deleting few candidates, as well as a combinatorial scenario where adding/deleting a candidate automatically means adding or deleting a whole group of candidates. Considering several fundamental voting rules, our results show that the parameterized complexity of candidate control, with the number of voters as the parameter, is much more varied than in the setting with many voters.
FairCache: Introducing Fairness to ICN Caching - Technical Report
Venue: arXiv cs.NI 2017
Year: 2017

Information-centric networking extensively uses universal in-network caching. However, developing an efficient and fair collaborative caching algorithm for selfish caches is still an open question. In addition, the communication overhead induced by collaboration is especially poorly understood in a general network setting such as realistic ISP and Autonomous System networks. In this paper, we address these two problems by modeling the in-network caching problem as a Nash bargaining game. We show that the game is a convex optimization problem and further derive the corresponding distributed algorithm. We analytically investigate the collaboration overhead on general graph topologies, and theoretically show that collaboration has to be constrained within a small neighborhood due to its cost growing exponentially. Our proposed algorithm achieves at least 16% performance gain over its competitors on different network topologies in the evaluation, and guarantees provable convergence, Pareto efficiency and proportional fairness.
List-decoding algorithms for lifted codes
Venue: arXiv cs.IT 2017
Year: 2017

Lifted Reed-Solomon codes are a natural affine-invariant family of error-correcting codes which generalize Reed-Muller codes. They were known to have efficient local-testing and local-decoding algorithms (comparable to the known algorithms for Reed-Muller codes), but with significantly better rate. We give efficient algorithms for list-decoding and local list-decoding of lifted codes. Our algorithms are based on a new technical lemma, which says that codewords of lifted codes are low degree polynomials when viewed as univariate polynomials over a big field (even though they may be very high degree when viewed as multivariate polynomials over a small field).
Batched Point Location in SINR Diagrams via Algebraic Tools
Venue: arXiv cs.CG 2017
Year: 2017

The SINR model for wireless networks has been extensively studied recently. It tries to model whether a particular transmitter is heard at a specific location, with $n$ transmitting simultaneously. The SINR diagram consists of $n$ regions where each transmitter can be heard and the remaining space where no one can be heard. Efficient point location in the SINR diagram, i.e., building a data structure to determine, for a query point, whether any transmitter is heard there, and if so, which one, has been recently investigated. Previous such planar data structures are constructed in time at least quadratic in $n$ and support logarithmic-time approximate queries. Moreover, the performance of these depends not only on the number $n$ of transmitters and on the approximation parameter $\varepsilon$, but also on some geometric parameters that cannot be bounded a priori as a function of $n$ or $\varepsilon$. We address the question of batched point location queries, i.e., answering many queries simultaneously. Specifically, in one dimension, we can answer $n$ queries exactly in amortized polylogarithmic time per query, while in the plane we can do it approximately. All these results can handle arbitrary power assignments to the transmitters. Moreover, the amortized query time in these results depends only on $n$ and $\varepsilon$. We also show how to speed up the preprocessing in a previously proposed point-location structure in SINR diagram for uniform-power sites, by almost a full order of magnitude. For this we obtain results on the sensitivity of the reception regions to slight changes in the reception threshold, which are of independent interest. Finally, these results demonstrate the (so far underutilized) power of combining algebraic tools with those of computational geometry and other fields.
A Portfolio Approach to Algorithm Selection for Discrete Time-Cost Trade-off Problem
Venue: arXiv cs.AI 2017
Year: 2017

It is a known fact that the performance of optimization algorithms for NP-Hard problems vary from instance to instance. We observed the same trend when we comprehensively studied multi-objective evolutionary algorithms (MOEAs) on a six benchmark instances of discrete time-cost trade-off problem (DTCTP) in a construction project. In this paper, instead of using a single algorithm to solve DTCTP, we use a portfolio approach that takes multiple algorithms as its constituent. We proposed portfolio comprising of four MOEAs, Non-dominated Sorting Genetic Algorithm II (NSGA-II), the strength Pareto Evolutionary Algorithm II (SPEA-II), Pareto archive evolutionary strategy (PAES) and Niched Pareto Genetic Algorithm II (NPGA-II) to solve DTCTP. The result shows that the portfolio approach is computationally fast and qualitatively superior to its constituent algorithms for all benchmark instances. Moreover, portfolio approach provides an insight in selecting the best algorithm for all benchmark instances of DTCTP.
Irreversible 2-conversion set in graphs of bounded degree
Venue: arXiv cs.DM 2017
Year: 2017

An irreversible $k$-threshold process (also a $k$-neighbor bootstrap percolation) is a dynamic process on a graph where vertices change color from white to black if they have at least $k$ black neighbors. An irreversible $k$-conversion set of a graph $G$ is a subset $S$ of vertices of $G$ such that the irreversible $k$-threshold process starting with $S$ black eventually changes all vertices of $G$ to black. We show that deciding the existence of an irreversible 2-conversion set of a given size is NP-complete, even for graphs of maximum degree 4, which answers a question of Dreyer and Roberts. Conversely, we show that for graphs of maximum degree 3, the minimum size of an irreversible 2-conversion set can be computed in polynomial time. Moreover, we find an optimal irreversible 3-conversion set for the toroidal grid, simplifying constructions of Pike and Zou.
Adam: A Method for Stochastic Optimization
Venue: arXiv cs.LG 2017
Year: 2017

We introduce Adam, an algorithm for first-order gradient-based optimization of stochastic objective functions, based on adaptive estimates of lower-order moments. The method is straightforward to implement, is computationally efficient, has little memory requirements, is invariant to diagonal rescaling of the gradients, and is well suited for problems that are large in terms of data and/or parameters. The method is also appropriate for non-stationary objectives and problems with very noisy and/or sparse gradients. The hyper-parameters have intuitive interpretations and typically require little tuning. Some connections to related algorithms, on which Adam was inspired, are discussed. We also analyze the theoretical convergence properties of the algorithm and provide a regret bound on the convergence rate that is comparable to the best known results under the online convex optimization framework. Empirical results demonstrate that Adam works well in practice and compares favorably to other stochastic optimization methods. Finally, we discuss AdaMax, a variant of Adam based on the infinity norm.
From Clarity to Efficiency for Distributed Algorithms
Venue: arXiv cs.PL 2017
Year: 2017

This article describes a very high-level language for clear description of distributed algorithms and optimizations necessary for generating efficient implementations. The language supports high-level control flows where complex synchronization conditions can be expressed using high-level queries, especially logic quantifications, over message history sequences. Unfortunately, the programs would be extremely inefficient, including consuming unbounded memory, if executed straightforwardly. We present new optimizations that automatically transform complex synchronization conditions into incremental updates of necessary auxiliary values as messages are sent and received. The core of the optimizations is the first general method for efficient implementation of logic quantifications. We have developed an operational semantics of the language, implemented a prototype of the compiler and the optimizations, and successfully used the language and implementation on a variety of important distributed algorithms.
Micro-location for Internet of Things equipped Smart Buildings
Venue: arXiv cs.OH 2017
Year: 2017

Micro-location is the process of locating any entity with high accuracy (possibly in centimeters), while geofencing is the process of creating a virtual fence around a so-called Point of Interest (PoI). In this paper, we present an insight into various micro-location enabling technologies and services. We also discuss how these can accelerate the incorporation of Internet of Things (IoT) in smart buildings. We argue that micro-location based location-aware solutions can play a significant role in facilitating the tenants of an IoT equipped smart building. Also, such advanced technologies will enable the smart building control system through minimal actions performed by the tenants. We also highlight the existing and envisioned services to be provided by using micro-location enabling technologies. We describe the challenges and propose some potential solutions such that micro-location enabling technologies and services are thoroughly integrated with IoT equipped smart building.