Rank-Deficient Quadratic-Form Maximization Over M-Phase Alphabet: Polynomial-Complexity Solvability And Algorithmic Developments

The maximization of a positive (semi) definite complex quadratic form over a finite alphabet is NP-hard and achieved through exhaustive search when the form has full rank. However, if the form is rank-deficient, the optimal solution can be computed with only polynomial complexity in the length N of the maximizing vector. In this work, we consider the general case of a rank-D positive (semi) definite complex quadratic form and develop a method that maximizes the form with respect to a M-phase vector with polynomial complexity. The proposed method efficiently reduces the size of the feasible set from exponential to polynomial. We also develop an algorithm that constructs the polynomial-size candidate set in polynomial time and observe that it is fully parallelizable and rank-scalable.

Published in:
2011 IEEE International Conference On Acoustics, Speech, And Signal Processing, 3856-3859
Presented at:
IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Prague, Czech Republic, May 22-27, 2011

 Record created 2011-12-29, last modified 2018-09-13

Rate this document:

Rate this document:
(Not yet reviewed)