Hidden Convexity in QCQP with Toeplitz-Hermitian Quadratics

作者：Konar Aritra^*; Sidiropoulos Nicholas D

来源：IEEE Signal Processing Letters, 2015, 22(10): 1623-1627.

DOI：10.1109/LSP.2015.2419571

• Circulant-Toeplitz QCQP
• distributed spectrum sensing
• linear programming
• moving-average processes
• Toeplitz-Hermitian QCQP
• semi-definite relaxation
• spectral factorization

Quadratically Constrained Quadratic Programming (QCQP) has a broad spectrum of applications in engineering. The general QCQP problem is NP-Hard. This article considers QCQP with Toeplitz-Hermitian quadratics, and shows that it possesses hidden convexity: it can always be solved in polynomial-time via Semidefinite Relaxation followed by spectral factorization. Furthermore, if the matrices are circulant, then the QCQP can be equivalently reformulated as a linear program, which can be solved very efficiently. An application to parametric power spectrum sensing from binary measurements is included to illustrate the results.

• 出版日期2015-10