Ιδρυματικό Αποθετήριο [SANDBOX]
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

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

Liavas Athanasios, Karystinos,G.N

Πλήρης Εγγραφή


URI: http://purl.tuc.gr/dl/dias/F03B2027-A451-4A0A-8F61-132FAB741B18
Έτος 2008
Τύπος Πλήρης Δημοσίευση σε Συνέδριο
Άδεια Χρήσης
Λεπτομέρειες
Βιβλιογραφική Αναφορά 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
Εμφανίζεται στις Συλλογές

Περίληψη

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.

Υπηρεσίες

Στατιστικά