Hidden Convexity in QCQP with Toeplitz-Hermitian Quadratics

Aritra Konar; Nicholas D. Sidiropoulos

doi:10.1109/LSP.2015.2419571

Hidden Convexity in QCQP with Toeplitz-Hermitian Quadratics

Aritra Konar, Nicholas D. Sidiropoulos

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-review

20 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 language	English (US)
Article number	7079378
Pages (from-to)	1623-1627
Number of pages	5
Journal	IEEE Signal Processing Letters
Volume	22
Issue number	10
DOIs	https://doi.org/10.1109/LSP.2015.2419571
State	Published - 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

Publisher link

10.1109/LSP.2015.2419571

Find It

Find It at U of M Libraries

Cite this

@article{173a95c59d6246a0ada21b5520af2a2d,

title = "Hidden Convexity in QCQP with Toeplitz-Hermitian Quadratics",

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.",

keywords = "Circulant-Toeplitz QCQP, Toeplitz-Hermitian QCQP, distributed spectrum sensing, linear programming, moving-average processes, semi-definite relaxation, spectral factorization",

author = "Aritra Konar and Sidiropoulos, {Nicholas D.}",

note = "Publisher Copyright: {\textcopyright} 1994-2012 IEEE.",

year = "2015",

month = oct,

day = "1",

doi = "10.1109/LSP.2015.2419571",

language = "English (US)",

volume = "22",

pages = "1623--1627",

journal = "IEEE Signal Processing Letters",

issn = "1070-9908",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "10",

}

TY - JOUR

T1 - Hidden Convexity in QCQP with Toeplitz-Hermitian Quadratics

AU - Konar, Aritra

AU - Sidiropoulos, Nicholas D.

PY - 2015/10/1

Y1 - 2015/10/1

N2 - 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.

AB - 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.

KW - Circulant-Toeplitz QCQP

KW - Toeplitz-Hermitian QCQP

KW - distributed spectrum sensing

KW - linear programming

KW - moving-average processes

KW - semi-definite relaxation

KW - spectral factorization

UR - http://www.scopus.com/inward/record.url?scp=84928154852&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84928154852&partnerID=8YFLogxK

U2 - 10.1109/LSP.2015.2419571

DO - 10.1109/LSP.2015.2419571

M3 - Article

AN - SCOPUS:84928154852

SN - 1070-9908

VL - 22

SP - 1623

EP - 1627

JO - IEEE Signal Processing Letters

JF - IEEE Signal Processing Letters

IS - 10

M1 - 7079378

ER -

Hidden Convexity in QCQP with Toeplitz-Hermitian Quadratics

Abstract

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this