Published on Sun Jan 05 2014

Learning parametric dictionaries for graph signals

Dorina Thanou, David I Shuman, Pascal Frossard

In sparse signal representation, the choice of a dictionary often involves a tradeoff between two desirable properties -- the ability to adapt to specific signal data and a fast implementation of the dictionary. We propose a parametric dictionary learning algorithm to design data-adapted, structured dictionaries.

0
0
0
Abstract

In sparse signal representation, the choice of a dictionary often involves a tradeoff between two desirable properties -- the ability to adapt to specific signal data and a fast implementation of the dictionary. To sparsely represent signals residing on weighted graphs, an additional design challenge is to incorporate the intrinsic geometric structure of the irregular data domain into the atoms of the dictionary. In this work, we propose a parametric dictionary learning algorithm to design data-adapted, structured dictionaries that sparsely represent graph signals. In particular, we model graph signals as combinations of overlapping local patterns. We impose the constraint that each dictionary is a concatenation of subdictionaries, with each subdictionary being a polynomial of the graph Laplacian matrix, representing a single pattern translated to different areas of the graph. The learning algorithm adapts the patterns to a training set of graph signals. Experimental results on both synthetic and real datasets demonstrate that the dictionaries learned by the proposed algorithm are competitive with and often better than unstructured dictionaries learned by state-of-the-art numerical learning algorithms in terms of sparse approximation of graph signals. In contrast to the unstructured dictionaries, however, the dictionaries learned by the proposed algorithm feature localized atoms and can be implemented in a computationally efficient manner in signal processing tasks such as compression, denoising, and classification.

Tue Jul 18 2017
Machine Learning
Graph learning under sparsity priors
Graph signals offer a very generic and natural representation for data that lives on networks or irregular structures. The actual data structure is however often unknown a priori but can sometimes be estimated from the knowledge of the application domain. If this is not possible, the data structure has to beferred from the
0
0
0
Thu Jun 14 2018
Machine Learning
Finding GEMS: Multi-Scale Dictionaries for High-Dimensional Graph Signals
Modern data introduces new challenges to classic signal processing approaches. A powerful and well established model for real world signals is sparse representation over a dictionary. This model has been successfully applied to graph signals as well by integrating the underlying graph topology into the learned dictionary.
0
0
0
Mon Apr 22 2019
Machine Learning
A Unified Framework for Structured Graph Learning via Spectral Constraints
Graph learning from data represents a canonical problem that has received substantial attention in the literature. Learning a graph with a specific structure is essential for interpretability and identification of the relationships among data. In general, structured graph learning is an NP-hard combinatorial problem.
0
0
0
Fri Jun 19 2020
Machine Learning
Localized Spectral Graph Filter Frames: A Unifying Framework, Survey of Design Considerations, and Numerical Comparison (Extended Cut)
In this article, we survey a particular class of dictionaries called localized spectral graph filter frames. These atoms are created by localizing spectral patterns to different regions of the graph. We demonstrate how this class of transform methods can be used in signal processing tasks.
0
0
0
Wed Dec 16 2015
Artificial Intelligence
Signal Representations on Graphs: Tools and Applications
We present a framework for representing and modeling data on graphs. Based on this framework, we study three typical classes of graph signals. For each class, we provide an explicit definition of the graph signals and construct a corresponding graph dictionary with desirable properties.
0
0
0
Tue Sep 24 2019
Machine Learning
Structured Graph Learning Via Laplacian Spectral Constraints
Structured graph learning from observed samples is an NP-hard combinatorial problem. The proposed algorithms are provably convergent and practically amenable for large-scale graph-based learning tasks.
0
0
0