  In this paper, we address the fundamental problem of line spectral estimation
in a Bayesian framework. We target model order and parameter estimation via
variational inference in a probabilistic model in which the frequencies are
continuous-valued, i.e., not restricted to a grid; and the coefficients are
governed by a Bernoulli-Gaussian prior model turning model order selection into
binary sequence detection. Unlike earlier works which retain only point
estimates of the frequencies, we undertake a more complete Bayesian treatment
by estimating the posterior probability density functions (pdfs) of the
frequencies and computing expectations over them. Thus, we additionally capture
and operate with the uncertainty of the frequency estimates. Aiming to maximize
the model evidence, variational optimization provides analytic approximations
of the posterior pdfs and also gives estimates of the additional parameters. We
propose an accurate representation of the pdfs of the frequencies by mixtures
of von Mises pdfs, which yields closed-form expectations. We define the
algorithm VALSE in which the estimates of the pdfs and parameters are
iteratively updated. VALSE is a gridless, convergent method, does not require
parameter tuning, can easily include prior knowledge about the frequencies and
provides approximate posterior pdfs based on which the uncertainty in line
spectral estimation can be quantified. Simulation results show that accounting
for the uncertainty of frequency estimates, rather than computing just point
estimates, significantly improves the performance. The performance of VALSE is
superior to that of state-of-the-art methods and closely approaches the
Cram\'er-Rao bound computed for the true model order.
