An official website of the United States government
This paper unifies the theory of consistent-set maximization for robust outlier detection in a simultaneous localization and mapping framework. We first describe the notion of pairwise consistency before discussing how a consistency graph can be formed by evaluating pairs of measurements for consistency. Finding the largest set of consistent measurements is transformed into an instance of the maximum clique problem and can be solved relatively quickly using existing maximum-clique solvers. We then generalize our algorithm to check consistency on a group- k basis by using a generalized notion of consistency and using generalized graphs. We also present modified maximum clique algorithms that function over generalized graphs to find the set of measurements that is internally group- k consistent. We address the exponential nature of group- k consistency and present methods that can substantially decrease the number of necessary checks performed when evaluating consistency. We extend our prior work to perform data association, and to multi-agent systems in both simulation and hardware, and provide a comparison with other state-of-the-art methods.
more »
« less
Generalizations of Loday's assembly maps for Lawvere's algebraic theories
Loday’s assembly maps approximate the K-theory of group rings by the K-theory of the coefficient ring and the corresponding homology of the group. We present a generalisation that places both ingredients on the same footing. Building on Elmendorf–Mandell’s multiplicativity results and our earlier work, we show that the K-theory of Lawvere theories is lax monoidal. This result makes it possible to present our theory in a user-friendly way without using higher-categorical language. It also allows us to extend the idea to new contexts and set up a nonabelian interpolation scheme, raising novel questions. Numerous examples illustrate the scope of our extension.
more »
« less
- Award ID(s):
- 2104300
- PAR ID:
- 10469774
- Publisher / Repository:
- Cambridge University Press
- Date Published:
- Journal Name:
- Journal of the Institute of Mathematics of Jussieu
- ISSN:
- 1474-7480
- Page Range / eLocation ID:
- 1 to 27
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
For datasets exhibiting long tail phenomenon, we identify a fairness concern in existing top-k algorithms, that return a fixed set of k results for a given query. This causes a handful of popular records (products, items, etc) getting overexposed and always be returned to the user query, whereas, there exists a long tail of niche records that may be equally desirable (have similar utility). To alleviate this, we propose θ-Equiv-top-k-MMSP inside existing top-k algorithms - instead of returning a fixed top-k set, it generates all (or many) top-k sets that are equivalent in utility and creates a probability distribution over those sets. The end user will be returned one of these sets during the query time proportional to its associated probability, such that, after many draws from many end users, each record will have as equal exposure as possible (governed by uniform selection probability). θ-Equiv-top-k-MMSP is formalized with two sub-problems. (a) θ-Equiv-top-k-Sets to produce a set S of sets, each set has k records, where the sets are equivalent in utility with the top-k set; (b) MaxMinFair to produce a probability distribution over S, that is, PDF(S), such that the records in S have uniform selection probability. We formally study the hardness of θ-Equiv-top-k-MMSP. We present multiple algorithmic results - (a) An exact solution for θ-Equiv-top-k-Sets, and MaxMinFair. (b) We design highly scalable algorithms that solve θ-Equiv-top-k-Sets through a random walk and is backed by probability theory, as well as a greedy solution designed for MaxMinFair. (c) We finally present an adaptive random walk based algorithm that solves θ-Equiv-top-k-Sets and MaxMinFair at the same time. We empirically study how θ-Equiv-top-k-MMSP can alleviate a equitable exposure concerns that group fairness suffers from. We run extensive experiments using 6 datasets and design intuitive baseline algorithms that corroborate our theoretical analysis.more » « less
-
We model the societal task of redistricting political districts as a partitioning problem: Given a set of n points in the plane, each belonging to one of two parties, and a parameter k, our goal is to compute a partition P of the plane into regions so that each region contains roughly s = n/k points. P should satisfy a notion of "local" fairness, which is related to the notion of core, a well-studied concept in cooperative game theory. A region is associated with the majority party in that region, and a point is unhappy in P if it belongs to the minority party. A group D of roughly s contiguous points is called a deviating group with respect to P if majority of points in D are unhappy in P. The partition P is locally fair if there is no deviating group with respect to P.This paper focuses on a restricted case when points lie in 1D. The problem is non-trivial even in this case. We consider both adversarial and "beyond worst-case" settings for this problem. For the former, we characterize the input parameters for which a locally fair partition always exists; we also show that a locally fair partition may not exist for certain parameters. We then consider input models where there are "runs" of red and blue points. For such clustered inputs, we show that a locally fair partition may not exist for certain values of s, but an approximate locally fair partition exists if we allow some regions to have smaller sizes. We finally present a polynomial-time algorithm for computing a locally fair partition if one exists.more » « less
-
Abstract Cut-and-paste $$K$$-theory has recently emerged as an important variant of higher algebraic $$K$$-theory. However, many of the powerful tools used to study classical higher algebraic $$K$$-theory do not yet have analogues in the cut-and-paste setting. In particular, there does not yet exist a sensible notion of the Dennis trace for cut-and-paste $$K$$-theory. In this paper we address the particular case of the $$K$$-theory of polyhedra, also called scissors congruence $$K$$-theory. We introduce an explicit, computable trace map from the higher scissors congruence groups to group homology, and use this trace to prove the existence of some nonzero classes in the higher scissors congruence groups. We also show that the $$K$$-theory of polyhedra is a homotopy orbit spectrum. This fits into Thomason’s general framework of $$K$$-theory commuting with homotopy colimits, but we give a self-contained proof. We then use this result to re-interpret the trace map as a partial inverse to the map that commutes homotopy orbits with algebraic $$K$$-theory.more » « less
-
Abstract LetGbe a linear real reductive Lie group. Orbital integrals define traces on the group algebra ofG. We introduce a construction of higher orbital integrals in the direction of higher cyclic cocycles on the Harish-Chandra Schwartz algebra ofG. We analyze these higher orbital integrals via Fourier transform by expressing them as integrals on the tempered dual ofG. We obtain explicit formulas for the pairing between the higher orbital integrals and theK-theory of the reduced group$$C^{*}$$-algebra, and we discuss their application toK-theory.more » « less
