Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
The maximization of a positive (semi) definite complex quadratic form over a finite alphabet is NP-hard and achieved through exhaustive search when the form has full rank. However, if the form is rank-deficient, the optimal solution can be computed with only polynomial complexity in the length N of the maximizing vector. In this work, we consider the general case of a rank-D positive (semi) definite complex quadratic form and develop a method that maximizes the form with respect to a M-phase vector with polynomial complexity. The proposed method efficiently reduces the size of the feasible set from exponential to polynomial. We also develop an algorithm that constructs the polynomial-size candidate set in polynomial time and observe that it is fully parallelizable and rank-scalable.
Maryam Kamgarpour, Tony Alan Wood
Serge Vaudenay, Bénédikt Minh Dang Tran