Signal Recovery on Graphs: Variation Minimization
arXiv:1411.7414 · doi:10.1109/TSP.2015.2441042
Abstract
We consider the problem of signal recovery on graphs as graphs model data with complex structure as signals on a graph. Graph signal recovery implies recovery of one or multiple smooth graph signals from noisy, corrupted, or incomplete measurements. We propose a graph signal model and formulate signal recovery as a corresponding optimization problem. We provide a general solution by using the alternating direction methods of multipliers. We next show how signal inpainting, matrix completion, robust principal component analysis, and anomaly detection all relate to graph signal recovery, and provide corresponding specific solutions and theoretical analysis. Finally, we validate the proposed methods on real-world recovery problems, including online blog classification, bridge condition identification, temperature estimation, recommender system, and expert opinion combination of online blog classification.
To appear on IEEE Transactions on Signal Processing
References in corpus (4)
Cited by in corpus (73)
- Discrete Signal Processing on Graphs: Sampling Theory
- Signal Recovery on Graphs: Variation Minimization
- Sampling of graph signals with successive local aggregations
- Kernel-based Reconstruction of Graph Signals
- Adaptive Least Mean Squares Estimation of Graph Signals
- Reconstruction of Graph Signals through Percolation from Seeding Nodes
- Graph Unrolling Networks: Interpretable Neural Networks for Graph Signal Denoising
- Deep Unsupervised Learning of 3D Point Clouds via Graph Topology Inference and Filtering
- Distributed Adaptive Learning of Graph Signals
- Spectral Projector-Based Graph Fourier Transforms
- Reconstruction of Time-varying Graph Signals via Sobolev Smoothness
- A Directed Graph Fourier Transform with Spread Frequency Components
- Graph Fourier Transform: A Stable Approximation
- Convergence Analysis of Distributed Inference with Vector-Valued Gaussian Belief Propagation
- Personalized Graph Signal Processing for Collaborative Filtering
- Semi-supervised Learning in Network-Structured Data via Total Variation Minimization
- Vector-Valued Graph Trend Filtering with Non-Convex Penalties
- Bayesian Estimation of Graph Signals
- Graph Spatio-Spectral Total Variation Model for Hyperspectral Image Denoising
- Signal Representations on Graphs: Tools and Applications
- Sampling and Reconstruction of Sparse Signals on Circulant Graphs - An Introduction to Graph-FRI
- Gegenbauer Graph Neural Networks for Time-varying Signal Reconstruction
- Iterative reconstruction of signals on graph
- Graph Signal Restoration Using Nested Deep Algorithm Unrolling
- Graph Signal Processing: Dualizing GSP Sampling in the Vertex and Spectral Domains
- Graph-signal Reconstruction and Blind Deconvolution for Structured Inputs
- MC2G: An Efficient Algorithm for Matrix Completion with Social and Item Similarity Graphs
- Bayesian Graph Neural Networks with Adaptive Connection Sampling
- Mumford-Shah functionals on graphs and their asymptotics
- Non-Bayesian Estimation Framework for Signal Recovery on Graphs
- Matrix completion and extrapolation via kernel regression
- Widely-Linear MMSE Estimation of Complex-Valued Graph Signals
- 3D Point Cloud Denoising via Bipartite Graph Approximation and Reweighted Graph Laplacian
- Phase Transitions and a Model Order Selection Criterion for Spectral Graph Clustering
- Understanding Graph Neural Networks from Graph Signal Denoising Perspectives
- Graph Signal Processing -- Part II: Processing and Analyzing Signals on Graphs
- Preconditioned Gradient Descent Algorithm for Inverse Filtering on Spatially Distributed Networks
- A Review of Graph-Powered Data Quality Applications for IoT Monitoring Sensor Networks
- Generalization error bounds for kernel matrix completion and extrapolation
- Detecting Localized Categorical Attributes on Graphs
- Localization, Decomposition, and Dictionary Learning of Piecewise-Constant Signals on Graphs
- Signal Recovery on Graphs: Fundamental Limits of Sampling Strategies
- Polynomial graph filter of multiple shifts and distributed implementation of inverse filtering
- Graph Fourier Transform based on Directed Laplacian
- Hilbert Transform, Analytic Signal, and Modulation Analysis for Graph Signal Processing
- A Markov Variation Approach to Smooth Graph Signal Interpolation
- Learning Product Graphs Underlying Smooth Graph Signals
- Graph Signal Processing: Overview, Challenges and Applications
- Fast Path Localization on Graphs via Multiscale Viterbi Decoding
- Sampling and Recovery of Graph Signals based on Graph Neural Networks
- Agile Inexact Methods for Spectral Projector-Based Graph Fourier Transforms
- Signal Processing on Directed Graphs
- Filter Design for Autoregressive Moving Average Graph Filters
- AMOS: An Automated Model Order Selection Algorithm for Spectral Graph Clustering
- On the Supermodularity of Active Graph-based Semi-supervised Learning with Stieltjes Matrix Regularization
- Graph Equivalence Classes for Spectral Projector-Based Graph Fourier Transforms
- Folded Graph Signals: Sensing with Unlimited Dynamic Range
- Learning Optimal Graph Filters for Clustering of Attributed Graphs
- Spectral Statistics of Lattice Graph Structured, Non-uniform Percolations
- A Bayesian Perspective on Uncertainty Quantification for Estimated Graph Signals
- Scalable -Channel Critically Sampled Filter Banks for Graph Signals
- Proactive Doppler Shift Compensation in Vehicular Cyber-Physical Systems
- Graphmax for Text Generation
- The Logistic Network Lasso
- Dual Geometric Graph Network (DG2N) -- Iterative network for deformable shape alignment
- The Power of Side-information in Subgraph Detection
- Extreme Learning Machine for Graph Signal Processing
- DPC: Unsupervised Deep Point Correspondence via Cross and Self Construction
- Multi-dimensional graph fractional Fourier transform and its application
- Recursive Prediction of Graph Signals with Incoming Nodes
- Community Detection and Matrix Completion with Social and Item Similarity Graphs
- A statistical perspective of sampling scores for linear regression
- Robust Semi-Supervised Graph Classifier Learning with Negative Edge Weights