In this study, we develop heuristic methods to solve unimodular quadratic programming (UQP) approximately, which is known to be NP-hard. UQP-type problems appear naturally in radar waveform design and active sensing applications. In the UQP framework, we optimize a sequence of complex variables with unit modulus by maximizing a quadratic function. To solve the UQP problem approximately, we present two heuristic methods with polynomial complexity with respect to the size of the UQP problem. The first heuristic called dominant-eigenvector-matching, where the solution is picked that matches the complex arguments of the dominant eigenvector of the Hermitian matrix in the UQP formulation. The second heuristic, a greedy strategy, is shown to provide a performance guarantee of (1 1=e) with respect to the optimal solution given that the UQP objective function possesses a property called string submodularity. We demonstrate the performance of these heuristics via numerical simulations.
Article
View HEURISTIC ALGORITHMS FOR DESIGNING UNIMODULAR CODE SEQUENCES WITH PERFORMANCE GUARANTEES