The Experts below are selected from a list of 327 Experts worldwide ranked by ideXlab platform
Markus Puschel - One of the best experts on this subject based on the ideXlab platform.
-
Discrete Signal processing with set functions
arXiv: Information Theory, 2020Co-Authors: Markus Puschel, Chris WendlerAbstract:Set functions are functions (or Signals) indexed by the power set (set of all subsets) of a finite set $N$. They are ubiquitous in many application domains. For example, they are equivalent to node- or edge-weighted hypergraphs and to cooperative games in game theory. Further, the subclass of submodular functions occurs in many optimization and machine learning problems. In this paper, we derive Discrete-set Signal processing (SP), a shift-invariant linear Signal processing framework for set functions. Discrete-set SP provides suitable definitions of shift, shift-invariant systems, convolution, Fourier transform, frequency response, and other SP concepts. Different variants are possible due to different possible shifts. Discrete-set SP is inherently different from graph SP as it distinguishes the neighbors of an index $A\subseteq N$, i.e., those with one elements more or less by providing $n = |N|$ shifts. Finally, we show three prototypical applications and experiments with Discrete-set SP including compression in submodular function optimization, sampling for preference elicitation in auctions, and novel power set neural networks.
-
Discrete Signal processing with set functions
arXiv: Information Theory, 2020Co-Authors: Markus Puschel, Chris WendlerAbstract: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.
-
a Discrete Signal processing framework for meet join lattices with applications to hypergraphs and trees
International Conference on Acoustics Speech and Signal Processing, 2019Co-Authors: Markus PuschelAbstract:We introduce a novel Discrete Signal processing framework, called Discrete-lattice SP, for Signals indexed by a finite lattice. A lattice is a partially ordered set that supports a meet (or join) operation that returns the greatest element below two given elements. Discrete-lattice SP chooses the meet as shift operation and derives associated notion of (meet-invariant) convolution, Fourier transform, frequency response, and a convolution theorem. Examples of lattices include sets of sets that are closed under intersection and trees. Thus our framework is applicable to certain sparse set functions, Signals on sparse hypergraphs, and Signals on trees. Another view on Discrete-lattice SP is as an SP framework for a certain class of directed graphs. However, it is fundamentally different from the prior graph SP as it is based on more than one basic shift and all shifts are always simultaneously diagonalizable.
-
a Discrete Signal processing framework for set functions
International Conference on Acoustics Speech and Signal Processing, 2018Co-Authors: Markus PuschelAbstract:A set function associates a real (or complex) value with every subset of a given finite set $S$ . In this paper, we derive a novel Discrete Signal processing (DSP) framework for such functions. This means we define and derive suitable notions of basic DSP concepts including shift, filtering, frequency response, Fourier transform, and convolution theorems. At the heart is the definition of the shift on subsets for which we consider the two most natural choices, i.e., those most analogous to the time shift in standard DSP. Set functions naturally occur in many contexts associated with probability distributions, graph cuts, sensor placements, mutual information, entropy of sets of random variables, and others. Our work offers a new set of tools for their processing.
-
automatic generation of fast Discrete Signal transforms
IEEE Transactions on Signal Processing, 2001Co-Authors: Sebastian Egner, Markus PuschelAbstract:This paper presents an algorithm that derives fast versions for a broad class of Discrete Signal transforms symbolically. The class includes but is not limited to the Discrete Fourier and the Discrete trigonometric transforms. This is achieved by finding fast sparse matrix factorizations for the matrix representations of these transforms. Unlike previous methods, the algorithm is entirely automatic and uses the defining matrix as its sole input. The sparse matrix factorization algorithm consists of two steps: first, the "symmetry" of the matrix is computed in the form of a pair of group representations; second, the representations are stepwise decomposed, giving rise to a sparse factorization of the original transform matrix. We have successfully demonstrated the method by computing automatically efficient transforms in several important cases: for the DFT, we obtain the Cooley-Tukey (1965) FFT; for a class of transforms including the DCT, type II, the number of arithmetic operations for our fast transforms is the same as for the best-known algorithms. Our approach provides new insights and interpretations for the structure of these Signal transforms and the question of why fast algorithms exist. The sparse matrix factorization algorithm is implemented within the software package AREP.
Aliaksei Sandryhaila - One of the best experts on this subject based on the ideXlab platform.
-
Discrete Signal processing on graphs sampling theory
IEEE Transactions on Signal Processing, 2015Co-Authors: Siheng Chen, Aliaksei Sandryhaila, Rohan Varma, Jelena KovačevićAbstract:We propose a sampling theory for Signals that are supported on either directed or undirected graphs. The theory follows the same paradigm as classical sampling theory. We show that perfect recovery is possible for graph Signals bandlimited under the graph Fourier transform. The sampled Signal coefficients form a new graph Signal, whose corresponding graph structure preserves the first-order difference of the original graph Signal. For general graphs, an optimal sampling operator based on experimentally designed sampling is proposed to guarantee perfect recovery and robustness to noise; for graphs whose graph Fourier transforms are frames with maximal robustness to erasures as well as for Erdős-Renyi graphs, random sampling leads to perfect recovery with high probability. We further establish the connection to the sampling theory of finite Discrete-time Signal processing and previous work on Signal recovery on graphs. To handle full-band graph Signals, we propose a graph filter bank based on sampling theory on graphs. Finally, we apply the proposed sampling theory to semi-supervised classification of online blogs and digit images, where we achieve similar or better performance with fewer labeled samples compared to previous work.
-
Signal Processing on Weighted Line Graphs
Excursions in Harmonic Analysis Volume 4, 2015Co-Authors: Aliaksei Sandryhaila, Jelena KovačevićAbstract:This chapter describes a Signal processing framework for Signals that are represented, or indexed, by weighted line graphs, which are a generalization of directed line graphs used for representation of time Signals in classical Signal processing theory. The presented framework is based on the theory of Discrete Signal processing on graphs and on algebraic Signal processing theory. It defines fundamental Signal processing concepts, such as Signals and filters, z-transform, frequency and spectrum, Fourier transform and others, in a principled way. The framework also illustrates a strong connection between Signal processing on weighted line graphs and Signal representation based on orthogonal polynomials.
-
Discrete Signal processing on graphs frequency analysis
arXiv: Social and Information Networks, 2013Co-Authors: Aliaksei Sandryhaila, Jose M. F. MouraAbstract:Signals and datasets that arise in physical and engineering applications, as well as social, genetics, biomolecular, and many other domains, are becoming increasingly larger and more complex. In contrast to traditional time and image Signals, data in these domains are supported by arbitrary graphs. Signal processing on graphs extends concepts and techniques from traditional Signal processing to data indexed by generic graphs. This paper studies the concepts of low and high frequencies on graphs, and low-, high-, and band-pass graph filters. In traditional Signal processing, there concepts are easily defined because of a natural frequency ordering that has a physical interpretation. For Signals residing on graphs, in general, there is no obvious frequency ordering. We propose a definition of total variation for graph Signals that naturally leads to a frequency ordering on graphs and defines low-, high-, and band-pass graph Signals and filters. We study the design of graph filters with specified frequency response, and illustrate our approach with applications to sensor malfunction detection and data classification.
-
Discrete Signal processing on graphs graph filters
International Conference on Acoustics Speech and Signal Processing, 2013Co-Authors: Aliaksei Sandryhaila, Jose M. F. MouraAbstract:We propose a novel Discrete Signal processing framework for structured datasets that arise from social, economic, biological, and physical networks. Our framework extends traditional Discrete Signal processing theory to datasets with complex structure that can be represented by graphs, so that data elements are indexed by graph nodes and relations between elements are represented by weighted graph edges. We interpret such datasets as Signals on graphs, introduce the concept of graph filters for processing such Signals, and discuss important properties of graph filters, including linearity, shift-invariance, and invertibility. We then demonstrate the application of graph filters to data classification by demonstrating that a classifier can be interpreted as an adaptive graph filter. Our experiments demonstrate that the proposed approach achieves high classification accuracy.
-
Discrete Signal processing on graphs graph fourier transform
International Conference on Acoustics Speech and Signal Processing, 2013Co-Authors: Aliaksei Sandryhaila, Jose M. F. MouraAbstract:We propose a novel Discrete Signal processing framework for the representation and analysis of datasets with complex structure. Such datasets arise in many social, economic, biological, and physical networks. Our framework extends traditional Discrete Signal processing theory to structured datasets by viewing them as Signals represented by graphs, so that Signal coefficients are indexed by graph nodes and relations between them are represented by weighted graph edges. We discuss the notions of Signals and filters on graphs, and define the concepts of the spectrum and Fourier transform for graph Signals. We demonstrate their relation to the generalized eigenvector basis of the graph adjacency matrix and study their properties. As a potential application of the graph Fourier transform, we consider the efficient representation of structured data that utilizes the sparseness of graph Signals in the frequency domain.
Jose M. F. Moura - One of the best experts on this subject based on the ideXlab platform.
-
Discrete Signal processing on graphs frequency analysis
arXiv: Social and Information Networks, 2013Co-Authors: Aliaksei Sandryhaila, Jose M. F. MouraAbstract:Signals and datasets that arise in physical and engineering applications, as well as social, genetics, biomolecular, and many other domains, are becoming increasingly larger and more complex. In contrast to traditional time and image Signals, data in these domains are supported by arbitrary graphs. Signal processing on graphs extends concepts and techniques from traditional Signal processing to data indexed by generic graphs. This paper studies the concepts of low and high frequencies on graphs, and low-, high-, and band-pass graph filters. In traditional Signal processing, there concepts are easily defined because of a natural frequency ordering that has a physical interpretation. For Signals residing on graphs, in general, there is no obvious frequency ordering. We propose a definition of total variation for graph Signals that naturally leads to a frequency ordering on graphs and defines low-, high-, and band-pass graph Signals and filters. We study the design of graph filters with specified frequency response, and illustrate our approach with applications to sensor malfunction detection and data classification.
-
Discrete Signal processing on graphs graph fourier transform
International Conference on Acoustics Speech and Signal Processing, 2013Co-Authors: Aliaksei Sandryhaila, Jose M. F. MouraAbstract:We propose a novel Discrete Signal processing framework for the representation and analysis of datasets with complex structure. Such datasets arise in many social, economic, biological, and physical networks. Our framework extends traditional Discrete Signal processing theory to structured datasets by viewing them as Signals represented by graphs, so that Signal coefficients are indexed by graph nodes and relations between them are represented by weighted graph edges. We discuss the notions of Signals and filters on graphs, and define the concepts of the spectrum and Fourier transform for graph Signals. We demonstrate their relation to the generalized eigenvector basis of the graph adjacency matrix and study their properties. As a potential application of the graph Fourier transform, we consider the efficient representation of structured data that utilizes the sparseness of graph Signals in the frequency domain.
-
Discrete Signal processing on graphs graph filters
International Conference on Acoustics Speech and Signal Processing, 2013Co-Authors: Aliaksei Sandryhaila, Jose M. F. MouraAbstract:We propose a novel Discrete Signal processing framework for structured datasets that arise from social, economic, biological, and physical networks. Our framework extends traditional Discrete Signal processing theory to datasets with complex structure that can be represented by graphs, so that data elements are indexed by graph nodes and relations between elements are represented by weighted graph edges. We interpret such datasets as Signals on graphs, introduce the concept of graph filters for processing such Signals, and discuss important properties of graph filters, including linearity, shift-invariance, and invertibility. We then demonstrate the application of graph filters to data classification by demonstrating that a classifier can be interpreted as an adaptive graph filter. Our experiments demonstrate that the proposed approach achieves high classification accuracy.
-
Discrete Signal processing on graphs
IEEE Transactions on Signal Processing, 2013Co-Authors: Aliaksei Sandryhaila, Jose M. F. MouraAbstract:In social settings, individuals interact through webs of relationships. Each individual is a node in a complex network (or graph) of interdependencies and generates data, lots of data. We label the data by its source, or formally stated, we index the data by the nodes of the graph. The resulting Signals (data indexed by the nodes) are far removed from time or image Signals indexed by well ordered time samples or pixels. DSP, Discrete Signal processing, provides a comprehensive, elegant, and efficient methodology to describe, represent, transform, analyze, process, or synthesize these well ordered time or image Signals. This paper extends to Signals on graphs DSP and its basic tenets, including filters, convolution, z-transform, impulse response, spectral representation, Fourier transform, frequency response, and illustrates DSP on graphs by classifying blogs, linear predicting and compressing data from irregularly located weather stations, or predicting behavior of customers of a mobile service provider.
-
ICASSP - Discrete Signal processing on graphs: Graph fourier transform
2013 IEEE International Conference on Acoustics Speech and Signal Processing, 2013Co-Authors: Aliaksei Sandryhaila, Jose M. F. MouraAbstract:We propose a novel Discrete Signal processing framework for the representation and analysis of datasets with complex structure. Such datasets arise in many social, economic, biological, and physical networks. Our framework extends traditional Discrete Signal processing theory to structured datasets by viewing them as Signals represented by graphs, so that Signal coefficients are indexed by graph nodes and relations between them are represented by weighted graph edges. We discuss the notions of Signals and filters on graphs, and define the concepts of the spectrum and Fourier transform for graph Signals. We demonstrate their relation to the generalized eigenvector basis of the graph adjacency matrix and study their properties. As a potential application of the graph Fourier transform, we consider the efficient representation of structured data that utilizes the sparseness of graph Signals in the frequency domain.
Jelena Kovačević - One of the best experts on this subject based on the ideXlab platform.
-
Discrete Signal processing on graphs sampling theory
IEEE Transactions on Signal Processing, 2015Co-Authors: Siheng Chen, Aliaksei Sandryhaila, Rohan Varma, Jelena KovačevićAbstract:We propose a sampling theory for Signals that are supported on either directed or undirected graphs. The theory follows the same paradigm as classical sampling theory. We show that perfect recovery is possible for graph Signals bandlimited under the graph Fourier transform. The sampled Signal coefficients form a new graph Signal, whose corresponding graph structure preserves the first-order difference of the original graph Signal. For general graphs, an optimal sampling operator based on experimentally designed sampling is proposed to guarantee perfect recovery and robustness to noise; for graphs whose graph Fourier transforms are frames with maximal robustness to erasures as well as for Erdős-Renyi graphs, random sampling leads to perfect recovery with high probability. We further establish the connection to the sampling theory of finite Discrete-time Signal processing and previous work on Signal recovery on graphs. To handle full-band graph Signals, we propose a graph filter bank based on sampling theory on graphs. Finally, we apply the proposed sampling theory to semi-supervised classification of online blogs and digit images, where we achieve similar or better performance with fewer labeled samples compared to previous work.
-
Signal Processing on Weighted Line Graphs
Excursions in Harmonic Analysis Volume 4, 2015Co-Authors: Aliaksei Sandryhaila, Jelena KovačevićAbstract:This chapter describes a Signal processing framework for Signals that are represented, or indexed, by weighted line graphs, which are a generalization of directed line graphs used for representation of time Signals in classical Signal processing theory. The presented framework is based on the theory of Discrete Signal processing on graphs and on algebraic Signal processing theory. It defines fundamental Signal processing concepts, such as Signals and filters, z-transform, frequency and spectrum, Fourier transform and others, in a principled way. The framework also illustrates a strong connection between Signal processing on weighted line graphs and Signal representation based on orthogonal polynomials.
Y V Venkatesh - One of the best experts on this subject based on the ideXlab platform.
-
gini index as sparsity measure for Signal reconstruction from compressive samples
IEEE Journal of Selected Topics in Signal Processing, 2011Co-Authors: Dornoosh Zonoobi, Ashraf A Kassim, Y V VenkateshAbstract:Sparsity is a fundamental concept in compressive sampling of Signals/images, which is commonly measured using the l0 norm, even though, in practice, the l1 or the lp ( 0 <; p <; 1) (pseudo-) norm is preferred. In this paper, we explore the use of the Gini index (GI), of a Discrete Signal, as a more effective measure of its sparsity for a significantly improved performance in its reconstruction from compressive samples. We also successfully incorporate the GI into a stochastic optimization algorithm for Signal reconstruction from compressive samples and illustrate our approach with both synthetic and real Signals/images.