Institutional Repository [SANDBOX]
Technical University of Crete
EN  |  EL

Search

Browse

My Space

Quadratic form maximization over the binary field with polynomial complexity

Karystinos Georgios, Liavas Athanasios

Full record


URI: http://purl.tuc.gr/dl/dias/A0BD5BF6-0D2F-45D9-AEC2-853CACA60D55
Year 2008
Type of Item Conference Full Paper
License
Details
Bibliographic Citation G. N. Karystinos and A. P. Liavas, “Quadratic form maximization over the binary field with polynomial complexity,” in Proc. IEEE - Intern. Symp. Inform. Theory,(ISIT '08) pp. 2449-2453, doi: 10.1109/ISIT.2008.4595431 https://doi.org/10.1109/ISIT.2008.4595431
Appears in Collections

Summary

We consider the maximization of a quadratic form over the binary alphabet. By introducing auxiliary spherical coordinates, we show that if the rank of the form is not a function of the problem size, then (i) the multidimensional space is partitioned into a polynomial-size set of regions which are associated with distinct binary vectors and (ii) the binary vector that maximizes the rank-deficient quadratic form belongs to the polynomial-size set of candidate vectors. Thus, the size of the feasible set of candidate vectors is efficiently reduced from exponential to polynomial. We also develop an algorithm that constructs the polynomial-size feasible set in polynomial time and show that it is fully parallelizable and rank-scalable. Finally, we examine the efficiency of the proposed algorithm in the context of multiple-input multiple-output signal detection.

Services

Statistics