Low Complexity and High-Resolution Line Spectral Estimation Using Cyclic Minimization

The line spectral estimation problem has applications in radar, wireless communications, spectroscopy, and power electronics, among others. The signal is modeled as a sparse linear combination of complex sinusoids and the problem target is to estimate the number of sinusoids in the mixture, and respective parameters of each individual sinusoid, such as magnitude, phase, and frequency. In this work, we first introduce a novel formulation of the rank function, which involves the solution of a multi-convex optimization problem. Using the multi-convex reformulation of the rank function an over-parameterization of the line estimation problem is proposed together with a cyclic minimization procedure to obtain a solution. The cyclic method iterates between the optimization of the signal subspace and null-space and stops when the two are orthogonal. Every limit point of the sequence of iterates is shown to be a stationary point of the original problem. Numerical experiments show that only a small number of iterations is required for convergence. The signal subspace optimization is a semidefinite program (SDP) and the null-space optimization has a closed-form solution. The cost per iteration of a general-purpose interior point method (IPM) to solve the SDP is a quartic function of the problem dimension. It is shown that by exploiting the problem structure the cost per iteration of the IPM may be reduced to a cubic function of the problem dimension, comparable to the cost of the alternating direction method of multipliers (ADMM). However, contrarily to the latter, the former achieves the precision necessary for fine frequency localization. A large set of numerical experiments show the effectiveness of the proposed approach.