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

  • CALL FOR PAPERS: The IEEE/ACM Transactions on Audio, Speech, and Language Processing is now accepting submissions f… https://t.co/wkoVBKfE5j
  • DEADLINE EXTENDED: The IEEE Journal of Selected Topics in Signal Processing is now accepting submissions for a Spec… https://t.co/qoRbzFeMLL
  • Our Information Forensics and Security Webinar Series continues on Tuesday, 23 August when Dr. Anderson Rocha prese… https://t.co/q48hnIMfan
  • There is still time to submit your proposal to host the 2023 IEEE Workshop on Automatic Speech Recognition and Unde… https://t.co/y1VxOKiEwb
  • DEADLINE EXTENDED: The IEEE Transactions on Multimedia is now accepting submissions for a Special Issue on Perceivi… https://t.co/2PvWLwoclK

SPS Videos


Signal Processing in Home Assistants

 


Multimedia Forensics


Careers in Signal Processing             

 


Under the Radar