Approximation algorithms for nonnegative polynomial optimization problems over unit spheres

Abstract

© 2017 Higher Education Press and Springer-Verlag Berlin Heidelberg We consider approximation algorithms for nonnegative polynomial optimization problems over unit spheres. These optimization problems have wide applications e.g., in signal and image processing, high order statistics, and computer vision. Since these problems are NP-hard, we are interested in studying on approximation algorithms. In particular, we propose some polynomial-time approximation algorithms with new approximation bounds. In addition, based on these approximation algorithms, some eFFIcient algorithms are presented and numerical results are reported to show the eFFIciency of our proposed algorithms.