Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/F03B2027-A451-4A0A-8F61-132FAB741B18 | ||
| Year | 2008 | ||
| Type of Item | Conference Full Paper | ||
| License |
|
||
| 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 |
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.
Copyright © DIAS 2013
