Search

Browse

• Communities
• Authors
• Year
• Titles
• Subjects

My Space

• Login

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

Liavas Athanasios, Karystinos,G.N

Full record

---

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