During the past decade, the theory of compressed sensing has drawn widespread attention to the fact that ill-posed and noisy linear systems often can be solved reliably – provided the true solution is sparse. For this reason, the sparsity level of the true solution is commonly assumed to be a known parameter in the analysis of recovery algorithms. However, the value of this parameter is typically unknown in practice. In this work we propose a new method for estimating the sparsity level without making any assumptions on the structure of the true solution. We offer a detailed analysis of our proposed estimator by deriving its rate of convergence to the true parameter, as well as its exact limiting distribution. Moreover, it is shown that the convergence rate of the estimator does not depend on the dimension of the true solution, making our method particularly well-suited for high-dimensional problems.
