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

Search

Browse

My Space

Efficient computation of the binary vector that maximizesa rank-deficient quadratic form

Liavas Athanasios, Karystinos,G.N

Full record


URI: http://purl.tuc.gr/dl/dias/F03B2027-A451-4A0A-8F61-132FAB741B18
Year 2008
Type of Item Conference Full Paper
License
Details
Bibliographic Citation G. N. Karystinos and A. P. Liavas.(2008).Efficient computation of the binary vector that maximizes a rank-deficient quadratic form.Presented at IEEE International Conference on Acoustics, Speech, and Signal Processing.[online].Available:http://www.telecom.tuc.gr/~karystinos/paper_TIT3.pdf
Appears in Collections

Summary

The maximization of a full-rank quadratic form overthe binary alphabet can be performed through exponential-complexityexhaustive search. However, if the rank of the form is not afunction of the problem size, then it can be maximized in polynomialtime. By introducing auxiliary spherical coordinates, we showthat the rank-deficient quadratic-form maximization problem isconverted into a double maximization of a linear form over a multidimensionalcontinuous set, the multidimensional set is partitionedinto a polynomial-size set of regions which are associated with distinctcandidate binary vectors, and the optimal binary vector belongsto the polynomial-size set of candidate vectors. Thus, the sizeof the candidate set is reduced from exponential to polynomial. Wealso develop an algorithm that constructs the polynomial-size candidateset in polynomial time and show that it is fully parallelizableand rank-scalable. Finally, we demonstrate the efficiency ofthe proposed algorithm in the context of adaptive spreading codedesign.

Services

Statistics