  In this paper, we investigate the problem of recovering the frequency
components of a mixture of $K$ complex sinusoids from a random subset of $N$
equally-spaced time-domain samples. Because of the random subset, the samples
are effectively non-uniform. Besides, the frequency values of each of the $K$
complex sinusoids are assumed to vary continuously within a given range.
  For this problem, we propose a two-step strategy: (i) we first lift the
incomplete set of uniform samples (unavailable samples are treated as missing
data) into a structured matrix with missing entries, which is potentially
low-rank; then (ii) we complete the matrix using a weighted nuclear
minimization problem. We call the method a \emph{ weighted lifted-structured
(WLi) low-rank matrix recovery}. Our approach can be applied to a range of
matrix structures such as Hankel and double-Hankel, among others, and provides
improvement over the unweighted existing schemes such as EMaC and DEMaC. We
provide theoretical guarantees for the proposed method, as well as numerical
simulations in both noiseless and noisy settings. Both the theoretical and the
numerical results confirm the superiority of the proposed approach.
