Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 2015 | metadata_only
Book Section - Chapter

Beyond semidefinite relaxation: Basis banks and computationally enhanced guarantees


As a widely used tool in tackling general quadratic optimization problems, semidefinite relaxation (SDR) promises both a polynomial-time complexity and an a priori known sub-optimality guarantee for its approximate solutions. While attempts at improving the guarantees of SDR in a general sense have proven largely unsuccessful, it has been widely observed that the quality of solutions obtained by SDR is usually considerably better than the provided guarantees. In this paper, we propose a novel methodology that paves the way for obtaining improved data-dependent guarantees in a computational way. The derivations are dedicated to a specific quadratic optimization problem (called m-QP) which lies at the core of many communication and active sensing schemes; however, the ideas may be generalized to other quadratic optimization problems. The new guarantees are particularly useful in accuracy sensitive applications, including decision-making scenarios.

Additional Information

© 2015 IEEE.

Additional details

September 15, 2023
September 15, 2023