Analysis vs synthesis with structure -- an investigation of union of subspace models on graphs

DOI10.1016/J.ACHA.2022.03.002zbMATH Open1493.94006arXiv1811.04493OpenAlexW2899703976MaRDI QIDQ2155807FDOQ2155807

Authors: Yanyan Li 

Publication date: 15 July 2022

Published in: Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Abstract: We consider the problem of characterizing the `duality gap' between sparse synthesis- and cosparse analysis-driven signal models through the lens of spectral graph theory, in an effort to comprehend their precise equivalencies and discrepancies. By detecting and exploiting the inherent connectivity structure, and hence, distinct set of properties, of rank-deficient graph difference matrices such as the graph Laplacian, we are able to substantiate discrepancies between the cosparse analysis and sparse synthesis models, according to which the former constitutes a constrained and translated instance of the latter. In view of a general union of subspaces model, we conduct a study of the associated subspaces and their composition, which further facilitates the refinement of specialized uniqueness and recovery guarantees, and discover an underlying structured sparsity model based on the graph incidence matrix. Furthermore, for circulant graphs, we provide an exact characterization of underlying subspaces by deriving closed-form expressions as well as demonstrating transitional properties between equivalence and non-equivalence for a parametric generalization of the graph Laplacian.

Full work available at URL: https://arxiv.org/abs/1811.04493

Recommendations

• The cosparse analysis model and algorithms
• Sampling in the analysis transform domain
• Analysis versus synthesis in signal priors
• One condition for solution uniqueness and robustness of both \(\ell_1\)-synthesis and \(\ell_1\)-analysis minimizations
• A modified greedy analysis pursuit algorithm for the cosparse analysis model

zbMATH Keywords

structured sparsitygraph signal processingcosparsityGreen's functions on graphsunion of subspaces model

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Applications of graph theory (05C90) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Density (toughness, etc.) (05C42)

Cites Work

• Diffusion wavelets
• Title not available (Why is that?)
• Wavelets on graphs via spectral graph theory
• Decay Rates for Inverses of Band Matrices
• Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ ¹ minimization
• Circulants and their connectivities
• The cosparse analysis model and algorithms
• Pseudo-inverses of difference matrices and their application to sparse signal approximation
• An Optimal Circulant Preconditioner for Toeplitz Systems
• Analysis versus synthesis in signal priors
• Model-Based Compressive Sensing
• Compact Support Biorthogonal Wavelet Filterbanks for Arbitrary Undirected Graphs
• Variational splines and Paley-Wiener spaces on Combinatorial graphs
• A Simple Proof of the Fredholm Alternative and a Characterization of the Fredholm Operators
• A Theory for Sampling Signals From a Union of Subspaces
• Sampling Theorems for Signals From the Union of Finite-Dimensional Linear Subspaces
• Sampling and Reconstructing Signals From a Union of Linear Subspaces
• Title not available (Why is that?)
• Self-Similarity: Part I—Splines and Operators
• Discrete Green's functions
• Sampling and reconstruction of sparse signals on circulant graphs. An introduction to graph-FRI
• Representer Theorems for Sparsity-Promoting <inline-formula> <tex-math notation="LaTeX">$\ell _{1}$ </tex-math> </inline-formula> Regularization
• Splines and wavelets on circulant graphs

Cited In (1)

• Convergence analysis on the alternating direction method of multipliers for the cosparse optimization problem

This page was built for publication: Analysis vs synthesis with structure -- an investigation of union of subspace models on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2155807)