PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning parametric dictionaries for graph signals

Dorina Thanou, David I Shuman, Pascal Frossard

arXiv:1401.0887v1cs.LGcs.SIstat.ML

TL;DR

Sparse graph-signal dictionaries must adapt to data, remain efficient to implement, and account for graph geometry. The paper learns polynomial Laplacian dictionaries of translated local patterns; these perform comparably to or better than numerical-learning baselines and are more robust to training-set size.

  • Problem

    Graph-signal dictionary design must balance adaptation to specific data and fast implementation while incorporating the underlying graph geometry.

    Source: §I · p. 2

  • Method

    The method learns polynomial graph-Laplacian subdictionaries that represent translated overlapping local patterns in training signals.

    Source: §I · p. 3

  • Results

    The learned dictionaries outperform non-adapted graph wavelets and are comparable to or better than state-of-the-art numerical dictionaries, with greater robustness to training-data size.

    Source: §VII · pp. 24–25

  • Takeaways & Limitations

    The learned polynomial dictionaries provide localized atoms and can be stored and implemented efficiently in centralized and distributed signal-processing tasks.

    Source: §I · p. 3, §VII · p. 25

Abstract

from arXiv · show

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.

I. INTRODUCTION

Graph dictionaries must balance data adaptation and efficient implementation while representing graph signals sparsely and respecting the graph’s geometry. The paper’s polynomial Laplacian structure is designed to combine those properties with localized atoms.

I. INTRODUCTION

  • Graph dictionary design must balance adaptation to training signals with fast implementation while incorporating the graph geometry that shapes signal characteristics.The introduction frames sparse representation as constructing an overcomplete dictionary whose signals use only a few atoms.Source: §I · p. 2
  • The proposed dictionary concatenates learned polynomial graph-Laplacian subdictionaries, translating localized patterns across graph locations.The authors report that the resulting dictionaries are adapted to training data and efficient to store and apply.Source: §I · p. 3

II. RELATED WORK

  • Prior graph dictionaries either lack data adaptation or efficient implementation; the paper targets dictionaries that are adapted, structured, and efficient.The related-work discussion identifies these combined properties as the objective of the work.Source: §II · pp. 4–5

III. PRELIMINARIES

  • Graph signals assign real values to graph vertices, and Laplacian-based translation with smooth polynomial kernels yields localized atoms.The stated localization is based on shortest-path distance and ignores edge weights.Source: §III · pp. 5–6

IV. PARAMETRIC DICTIONARY LEARNING ON GRAPHS

The paper learns graph dictionaries for signal classes modeled as overlapping patterns translated across vertices. It learns polynomial generating kernels in the spectral domain to capture signal characteristics and their translations.

IV. PARAMETRIC DICTIONARY LEARNING ON GRAPHS

  • The objective is to learn a structured dictionary from weighted-graph training signals that sparsely represents the signal class.The signal model is a combination of overlapping graph patterns positioned at different vertices.Source: §IV · p. 6
  • The dictionary is designed to capture all translations of a set of patterns using generalized translation and polynomial generating kernels.The kernels are learned to capture the main characteristics of the signals in the spectral domain.Source: §IV · p. 6
  • Learning in the spectral domain enables detection of spectral components present in the training signals, including components supported on selected frequencies.Source: §IV · p. 6

A. Dictionary Structure

The dictionary is a concatenation of polynomial graph-Laplacian subdictionaries, whose translated atoms are localized. Spectral constraints bound kernel responses and promote coverage across the spectrum, while providing stability control.

A. Dictionary Structure

  • Each subdictionary is generated by a polynomial kernel translated to graph vertices, and its atoms are supported within a K-hop neighborhood.The polynomial degree K determines the localization radius in the graph topology.Source: A. Dictionary Structure · p. 7
  • Each kernel is constrained to be nonnegative and uniformly bounded by c across the Laplacian spectrum.This makes each subdictionary positive semidefinite with maximum eigenvalue at most c.Source: A. Dictionary Structure · p. 7
  • The sum of kernel responses is constrained to cover the full spectrum within tolerances ϵ1 and ϵ2.The constraints can be modified when prior information indicates that signals occupy only selected frequency regions.Source: A. Dictionary Structure · p. 7
  • The spectral constraints yield frame bounds for the dictionary and improve reconstruction stability, while avoiding the harder tight-frame learning constraint.The authors state that their constraints make the optimization easier while controlling spectral representation and reconstruction stability.Source: A. Dictionary Structure · p. 8

B. Dictionary Learning Algorithm

The learning objective seeks sparse representations while regularizing polynomial coefficients. An alternating procedure separates sparse coding from dictionary updates, but is not guaranteed to reach an optimal solution.

B. Dictionary Learning Algorithm

  • The objective learns polynomial parameters so training signals are represented using few dictionary atoms, while penalizing coefficient norms for kernel smoothness and numerical stability.The sparsity level T0 constrains the number of coefficients used for each signal.Source: B. Dictionary Learning Algorithm · p. 9
  • The nonconvex learning problem alternates sparse coding with dictionary updates, using OMP for coding and a convex quadratic program for updates.OMP is applied after atom normalization; the update step fixes the sparse coefficients while optimizing dictionary parameters.Source: B. Dictionary Learning Algorithm · pp. 9–10
  • Alternating optimization is not guaranteed to reach an optimal solution, although it converged to a local optimum in all experiments.The algorithm’s complexity is dominated by precomputing Laplacian eigenvalues for the spectral constraints; the update quadratic program can use interior-point or operator-splitting methods.Source: B. Dictionary Learning Algorithm · p. 10

V. EXPERIMENTAL RESULTS

The experiments compare graph-based transforms, unstructured numerical learning, and graph-structured learning on synthetic and real graph signals. Testing uses a common sparse-coding procedure and average approximation error.

V. EXPERIMENTAL RESULTS

  • Testing compares the proposed method with SGWT, K-SVD, and the graph-based dictionary learning algorithm [19].The experiments cover approximation of both synthetic and real data.Source: §V · p. 10
  • Learning runs for 25 iterations and uses the sdpt3 solver in the yalmip toolbox to solve optimization problem (12).The stated defaults include c = 1 and ϵ1 = ϵ2 = 0.01.Source: §V · p. 11
  • Orthogonal matching pursuit (OMP) provides the sparse-coding step for every tested dictionary, with atoms normalized to unit norm.The reported average approximation error is ∥Ytest − DXtest∥2_F / |Ytest|.Source: §V · p. 11

A. Synthetic Signals

The synthetic-signal experiments use a connected random geometric graph with 100 vertices and thresholded Gaussian edge weights.

A. Synthetic Signals

  • The graph has N = 100 vertices placed randomly in the unit square.Source: A. Synthetic Signals · p. 11
  • Edge weights use a thresholded Gaussian kernel, with nonzero weights for vertex pairs within distance κ.The supplied passage gives the kernel form as W(i, j) = e−[dist(i,j)]2, with threshold κ.Source: A. Synthetic Signals · p. 11
  • The experiments set θ = 0.9 and κ = 0.5 and ensure that the graph is connected.Source: A. Synthetic Signals · p. 11

1) Polynomial Generating Dictionary:

On synthetic signals generated from localized graph patterns, the experiments assess kernel recovery, sparse approximation, sensitivity to training-set size, and noise resilience. The learned polynomial dictionary recovers kernel shapes, outperforms SGWT in approximation, and is less sensitive to training noise than K-SVD and the structured graph dictionary.

1) Polynomial Generating Dictionary:

  • Synthetic signals combine at most four random atoms from four fifth-order polynomial-Laplacian subdictionaries, each representing a constitutive pattern.The learned dictionary uses degree K = 20 in the training-set-size experiment.Source: 1) Polynomial Generating Dictionary · p. 12
  • With polynomial dictionary learning (S = 4 subdictionaries, K = 20), recovery accuracy improves as training-set size increases; reported SNR values are 4.9, 5.3, and 14.9 for M = 400, 600, and 2000, respectively.The algorithm recovers the generating-kernel shape even with a very small number of training signals.Source: 1) Polynomial Generating Dictionary · p. 12
  • Polynomial-dictionary approximation is always better than SGWT across the tested training-set sizes.The authors attribute the improvement to learning kernel shapes from data rather than using SGWT's a priori kernels.Source: 1) Polynomial Generating Dictionary · p. 12, Figure 3 · p. 14
  • K-SVD performance deteriorates as training data shrink, while the polynomial dictionary remains more stable by including translated patterns across graph locations.K-SVD tends to learn global-support atoms and may learn a localized pattern only in the area where it appears in training.Source: 1) Polynomial Generating Dictionary · pp. 13–14
  • The graph-structured dictionary can learn nonsmooth generating kernels more flexibly when those kernels do not match the polynomial model.Its learned atoms are not guaranteed to be well localized, and its unstructured kernels lead to more complex implementations.Source: 1) Polynomial Generating Dictionary · p. 14
  • With noisy training signals at SNR = 4dB, the learned kernels preserve the noiseless kernel shape, and the polynomial dictionary is less noise-sensitive than K-SVD and the structured graph dictionary.The noise has zero mean and variance σ = 0.015; testing uses 2000 signals.Source: 1) Polynomial Generating Dictionary · p. 15

2) Non-Polynomial Generating Dictionary:

The experiments test polynomial dictionary learning when synthetic signals come from a non-polynomial generating dictionary. The learned dictionary is competitive, and its approximation improves with polynomial degree.

2) Non-Polynomial Generating Dictionary:

  • At K = 20 and 25, learned kernels approximate the generating dictionary's spectral bands, while higher polynomial degrees yield greater spectral localization.The generating atoms use randomly chosen spectral coefficients and are not guaranteed to be localized in the vertex domain.Source: 2) Non-Polynomial Generating Dictionary · p. 16, Figure 6 · p. 17
  • Learned atoms adapt their supports to graph topology, ranging from localized to smoother patterns; the smoothest corresponds to the low-frequency kernel.Low-frequency Laplacian eigenvectors are smoother with respect to graph topology.Source: 2) Non-Polynomial Generating Dictionary · pp. 16–17, Figure 7 · p. 18
  • Approximation performance on 2,000 test signals improves as polynomial degree increases, allowing more flexibility; small K also yields narrower supports and requires more atoms across graph regions.The test signals are generated in the same way as the training signals.Source: 2) Non-Polynomial Generating Dictionary · pp. 17–18, Figure 8 · p. 19
  • The learned dictionary is competitive, especially with smaller training sets, while structured graph learning generally approximates better; our dictionary outperforms its polynomial approximation.The comparison fixes K = 20; the learned dictionary is also more computationally efficient to implement.Source: 2) Non-Polynomial Generating Dictionary · pp. 18–19, Figure 9 · p. 19

3) Generating Dictionary Focused on Specific Frequency Bands:

This experiment tests whether the algorithm can learn kernels for signals concentrated in two frequency bands not specified in advance. The learned kernels concentrate on those bands.

3) Generating Dictionary Focused on Specific Frequency Bands:

  • Training signals combine at most four atoms, each concentrated in one of two graph-spectral bands, [λ0 : λ9] or [λ89 : λ99].The experiment uses 600 training signals, K = 20, and ϵ1 = c to permit kernels supported on specific bands.Source: 3) Generating Dictionary Focused on… · pp. 19–20
  • The two bands are defined by graph eigenvalues [λ0 : λ9] and [λ89 : λ99], corresponding to [0 : 0.275] and [1.174 : 1.256].The frequency bands are not known a priori in this experiment.Source: 3) Generating Dictionary Focused on… · pp. 19–20
  • The learned kernels concentrate on the two frequency regions containing the generating dictionary's atoms, detecting spectral components present in the training signals.Fig. 10 shows kernels learned from training signals supported only in those two bands.Source: 3) Generating Dictionary Focused on… · p. 20, Figure 10 · p. 20

B. Approximation of Real Graph Signals

On three real graph-signal datasets, the learned dictionaries outperform SGWT in test approximation error, with localized atoms representing real signals. The paper also describes compact storage and efficient centralized and distributed computations enabled by the polynomial structure.

B. Approximation of Real Graph Signals

VI. COMPUTATIONAL EFFICIENCY OF THE LEARNED POLYNOMIAL DICTIONARY

  • The dictionary has (K+1)S parameters, and its forward and adjoint operators can be applied efficiently when the graph is sparse.The stated parameter count depends on the number of subdictionaries S and polynomial degree K.Source: §VI · pp. 22–23
  • Polynomial structure also enables distributed computation of quantities including D^T y and D^T D x when communication between graph nodes is costly.The paper identifies sensor networks as an example setting.Source: §VI · p. 24

VII. CONCLUSION

The paper learns structured dictionaries formed from polynomial functions of the graph Laplacian, with patterns translated across graph locations. These dictionaries perform competitively in sparse approximation while retaining efficient storage and implementation.

VII. CONCLUSION

  • Each dictionary is a union of polynomial matrix functions of the graph Laplacian, whose learned kernels correspond to localized graph patterns when translated to vertices.The algorithm learns the parameters from training signals on the graph.Source: §VII · p. 24
  • The learned dictionaries outperform non-adapted graph wavelet dictionaries such as the SGWT and match or outperform K-SVD in sparse approximation.The reported comparison concerns sparse approximation performance.Source: §VII · pp. 24–25
  • The learned dictionaries are more robust to training-data size and can be efficiently stored and implemented in centralized and distributed signal processing tasks.Source: §VII · p. 25

APPENDIX A

Appendix A expresses the optimization objective as a quadratic program with affine constraints. It rewrites terms using stacked vectors built from Laplacian powers and subdictionary coefficients.

APPENDIX A

  • Optimization problem (12) is a quadratic program because its objective is quadratic and its constraints are affine.Source: Appendix A · pp. 25–26
  • For each subdictionary, the derivation stacks products of Laplacian-power rows and coefficient columns into vectors used to rewrite the objective.The vectors are indexed by signal and atom; the Laplacian-power row and coefficient-column meanings are stated in the appendix.Source: Appendix A · p. 25
  • The resulting objective is quadratic, and the constraints can be expressed as affine functions, allowing the optimization problem to be solved efficiently.Source: Appendix A · p. 26

Related papers

Loading 1401.0887v1…