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

  • Registration for ICIP 2021 is now open! This hybrid event will take place 19-22 September, with the in-person compo… https://t.co/s3kiGP4EPh
  • The Brain Space Initiative Talk Series continues on Friday, 30 July when Dr. Ioulia Kovelman presents "The Bilingua… https://t.co/6EqwqmBD0Q
  • There’s still time to register your team to win the US$5,000 grand prize in the 5-Minute Video Clip Contest, “Autom… https://t.co/76kh4jeL6i
  • Join the SPS Vizag Bay, Long Island, and Finland Chapters for the Seasonal School on Signal Processing and Communic… https://t.co/l04xac8qP5
  • Calling students and graduate students! The 5-Minute Video Clip Contest returns for ICIP 2021, and there's still ti… https://t.co/4hxYYY2Va3

SPS Videos


Signal Processing in Home Assistants

 


Multimedia Forensics


Careers in Signal Processing             

 


Under the Radar