Discrete Signal Processing with Set Functions

• URL: http://arxiv.org/abs/2001.10290v2
• Date: Thu, 22 Oct 2020 09:10:41 GMT
• Title: Discrete Signal Processing with Set Functions
• Authors: Markus P\"uschel and Chris Wendler
• Abstract summary: We derive discrete-set signal processing (SP), a novel shift-invariant linear signal processing framework for set functions. SP considers different notions of shift obtained from set union and difference operations. We show two applications and experiments: compression in submodular function optimization and sampling for preference elicitation in auctions.
• Score: 6.548580592686076
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Set functions are functions (or signals) indexed by the powerset (set of all subsets) of a finite set N. They are fundamental and ubiquitous in many application domains and have been used, for example, to formally describe or quantify loss functions for semantic image segmentation, the informativeness of sensors in sensor networks the utility of sets of items in recommender systems, cooperative games in game theory, or bidders in combinatorial auctions. In particular, the subclass of submodular functions occurs in many optimization and machine learning problems. In this paper, we derive discrete-set signal processing (SP), a novel shift-invariant linear signal processing framework for set functions. Discrete-set SP considers different notions of shift obtained from set union and difference operations. For each shift it provides associated notions of shift-invariant filters, convolution, Fourier transform, and frequency response. We provide intuition for our framework using the concept of generalized coverage function that we define, identify multivariate mutual information as a special case of a discrete-set spectrum, and motivate frequency ordering. Our work brings a new set of tools for analyzing and processing set functions, and, in particular, for dealing with their exponential nature. We show two prototypical applications and experiments: compression in submodular function optimization and sampling for preference elicitation in combinatorial auctions.

Related papers

• Learning Submodular Sequencing from Samples [11.528995186765751]
  This paper addresses the problem of selecting and ranking items in a sequence to optimize some composite submodular function. We present an algorithm that achieves an approximation ratio dependent on the curvature of the individual submodular functions.
  arXiv  Detail & Related papers  (2024-09-09T01:33:13Z)
• FINER++: Building a Family of Variable-periodic Functions for Activating Implicit Neural Representation [39.116375158815515]
  Implicit Neural Representation (INR) is causing a revolution in the field of signal processing. INR techniques suffer from the "frequency"-specified spectral bias and capacity-convergence gap. We propose the FINER++ framework by extending existing periodic/non-periodic activation functions to variable-periodic ones.
  arXiv  Detail & Related papers  (2024-07-28T09:24:57Z)
• Basis Function Encoding of Numerical Features in Factorization Machines for Improved Accuracy [2.3022070933226217]
  We provide a systematic and theoretically-justified way to incorporate numerical features into FM variants. We show that our technique yields a model that learns segmentized functions of the numerical feature spanned by the set of functions of one's choice. Our technique preserves fast training and inference, and requires only a small modification of the computational graph of an FM model.
  arXiv  Detail & Related papers  (2023-05-23T21:10:17Z)
• Neural Estimation of Submodular Functions with Applications to Differentiable Subset Selection [50.14730810124592]
  Submodular functions and variants, through their ability to characterize diversity and coverage, have emerged as a key tool for data selection and summarization. We propose FLEXSUBNET, a family of flexible neural models for both monotone and non-monotone submodular functions.
  arXiv  Detail & Related papers  (2022-10-20T06:00:45Z)
• Multiset Signal Processing and Electronics [1.0152838128195467]
  Multisets are intuitive extensions of the traditional concept of sets that allow repetition of elements. Recent generalizations of multisets to real-valued functions have paved the way to a number of interesting implications and applications. It is proposed that effective multiset operations capable of high performance self and cross-correlation can be obtained with relative simplicity in either discrete or integrated circuits.
  arXiv  Detail & Related papers  (2021-11-13T11:50:00Z)
• A research framework for writing differentiable PDE discretizations in JAX [3.4389358108344257]
  Differentiable simulators are an emerging concept with applications in several fields, from reinforcement learning to optimal control. We propose a library of differentiable operators and discretizations, by representing operators as mappings between families of continuous functions, parametrized by finite vectors. We demonstrate the approach on an acoustic optimization problem, where the Helmholtz equation is discretized using Fourier spectral methods, and differentiability is demonstrated using gradient descent to optimize the speed of sound of an acoustic lens.
  arXiv  Detail & Related papers  (2021-11-09T15:58:44Z)
• Modulated Periodic Activations for Generalizable Local Functional Representations [113.64179351957888]
  We present a new representation that generalizes to multiple instances and achieves state-of-the-art fidelity. Our approach produces general functional representations of images, videos and shapes, and achieves higher reconstruction quality than prior works that are optimized for a single signal.
  arXiv  Detail & Related papers  (2021-04-08T17:59:04Z)
• Feature Weighted Non-negative Matrix Factorization [92.45013716097753]
  We propose the Feature weighted Non-negative Matrix Factorization (FNMF) in this paper. FNMF learns the weights of features adaptively according to their importances. It can be solved efficiently with the suggested optimization algorithm.
  arXiv  Detail & Related papers  (2021-03-24T21:17:17Z)
• Learning Set Functions that are Sparse in Non-Orthogonal Fourier Bases [73.53227696624306]
  We present a new family of algorithms for learning Fourier-sparse set functions. In contrast to other work that focused on the Walsh-Hadamard transform, our novel algorithms operate with recently introduced non-orthogonal Fourier transforms. We demonstrate effectiveness on several real-world applications.
  arXiv  Detail & Related papers  (2020-10-01T14:31:59Z)
• From Sets to Multisets: Provable Variational Inference for Probabilistic Integer Submodular Models [82.95892656532696]
  Submodular functions have been studied extensively in machine learning and data mining. In this work, we propose a continuous DR-submodular extension for integer submodular functions. We formulate a new probabilistic model which is defined through integer submodular functions.
  arXiv  Detail & Related papers  (2020-06-01T22:20:45Z)
• Invariant Feature Coding using Tensor Product Representation [75.62232699377877]
  We prove that the group-invariant feature vector contains sufficient discriminative information when learning a linear classifier. A novel feature model that explicitly consider group action is proposed for principal component analysis and k-means clustering.
  arXiv  Detail & Related papers  (2019-06-05T07:15:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.