Blind Identification of Graph Filters

DOI10.1109/TSP.2016.2628343MaRDI QIDQ4620631zbMATH OpenOpenAlexFDO

Authors Santiago Segarra, Gonzalo Mateos, Antonio G. Marques, Alejandro Ribeiro

Publication date 8 February 2019

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Applications of graph theory (05C90) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: Network processes are often represented as signals defined on the vertices of a graph. To untangle the latent structure of such signals, one can view them as outputs of linear graph filters modeling underlying network dynamics. This paper deals with the problem of joint identification of a graph filter and its input signal, thus broadening the scope of classical blind deconvolution of temporal and spatial signals to the less-structured graph domain. Given a graph signal $mathbfy$ modeled as the output of a graph filter, the goal is to recover the vector of filter coefficients $mathbfh$, and the input signal $mathbfx$ which is assumed to be sparse. While $mathbfy$ is a bilinear function of $mathbfx$ and $mathbfh$, the filtered graph signal is also a linear combination of the entries of the lifted rank-one, row-sparse matrix $mathbfxmathbf{h}^T$. The blind graph-filter identification problem can thus be tackled via rank and sparsity minimization subject to linear constraints, an inverse problem amenable to convex relaxations offering provable recovery guarantees under simplifying assumptions. Numerical tests using both synthetic and real-world networks illustrate the merits of the proposed algorithms, as well as the benefits of leveraging multiple signals to aid the blind identification task.

Cited in

(4)

• Blind identification of fully observed linear time-varying systems via sparse recovery
• Signal processing on the permutahedron: tight spectral frames for ranked data analysis
• Robust Hierarchical Clustering for Directed Networks: An Axiomatic Approach
• Graph Fourier transform based on singular value decomposition of the directed Laplacian

This page was built for publication: Blind Identification of Graph Filters

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