Graph Tikhonov Regularization and Interpolation Via Random Spanning Forests

You are here

Top Reasons to Join SPS Today!

1. IEEE Signal Processing Magazine
2. Signal Processing Digital Library*
3. Inside Signal Processing Newsletter
4. SPS Resource Center
5. Career advancement & recognition
6. Discounts on conferences and publications
7. Professional networking
8. Communities for students, young professionals, and women
9. Volunteer opportunities
10. Coming soon! PDH/CEU credits
Click here to learn more.

Graph Tikhonov Regularization and Interpolation Via Random Spanning Forests

By: 
Yusuf Yiğit Pilavcı; Pierre-Olivier Amblard; Simon Barthelmé; Nicolas Tremblay

Novel Monte Carlo estimators are proposed to solve both the Tikhonov regularization (TR) and the interpolation problems on graphs. These estimators are based on random spanning forests (RSF), the theoretical properties of which enable to analyze the estimators’ theoretical mean and variance. We also show how to perform hyperparameter tuning for these RSF-based estimators. TR is a component in many well-known algorithms, and we show how the proposed estimators can be easily adapted to avoid expensive intermediate steps in generalized semi-supervised learning, label propagation, Newton's method and iteratively reweighted least squares. In the experiments, we illustrate the proposed methods on several problems and provide observations on their run time.

SPS on Twitter

  • New SPS Webinar! On Friday, 29 October, join Dr. Jérôme Gilles for "Empirical Wavelets," based on his original arti… https://t.co/ZuZ7qwO9Pc
  • The Brain Space Initiative Talk Series continues on Friday, 29 October when Dr. Selin Aviyente presents "Cross-Freq… https://t.co/Jxgu2soJCc
  • Join the Brain Space Initiative for another virtual mixing event on Wednesday, 27 October! Grab a coffee and meet w… https://t.co/KA3kuPUGw0
  • We're proud to sponsor a new journal, IEEE Transactions on Quantum Engineering, publishing regular, review, and tut… https://t.co/cZskrh9cvX
  • We are now seeking mentors and students for the launch of a new initiative, Mentoring Experiences for Underrepresen… https://t.co/i9SarNyKm9

SPS Videos


Signal Processing in Home Assistants

 


Multimedia Forensics


Careers in Signal Processing             

 


Under the Radar