  We consider the problem of state estimation from a few linear measurements,
where the state to recover is an element of the manifold $\mathcal{M}$ of
solutions of a parameter-dependent equation. The state is estimated using prior
knowledge on $\mathcal{M}$ coming from model order reduction. Variational
approaches based on linear approximation of $\mathcal{M}$, such as PBDW, yields
a recovery error limited by the Kolmogorov width of $\mathcal{M}$. To overcome
this issue, piecewise-affine approximations of $\mathcal{M}$ have also been
considered, that consist in using a library of linear spaces among which one is
selected by minimizing some distance to $\mathcal{M}$. In this paper, we
propose a state estimation method relying on dictionary-based model reduction,
where a space is selected from a library generated by a dictionary of
snapshots, using a distance to the manifold. The selection is performed among a
set of candidate spaces obtained from a set of $\ell_1$-regularized
least-squares problems. Then, in the framework of parameter-dependent operator
equations (or PDEs) with affine parametrizations, we provide an efficient
offline-online decomposition based on randomized linear algebra, that ensures
efficient and stable computations while preserving theoretical guarantees.
