Hidden Convexity in QCQP with Toeplitz-Hermitian Quadratics

Aritra Konar, Nicholas D. Sidiropoulos

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

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.

Original languageEnglish (US)
Article number7079378
Pages (from-to)1623-1627
Number of pages5
JournalIEEE Signal Processing Letters
Volume22
Issue number10
DOIs
StatePublished - Oct 1 2015

Bibliographical note

Publisher Copyright:
© 1994-2012 IEEE.

Keywords

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

Fingerprint

Dive into the research topics of 'Hidden Convexity in QCQP with Toeplitz-Hermitian Quadratics'. Together they form a unique fingerprint.

Cite this