Is there a method to identify location of non-zero Fourier coefficients of a signal (just locations, not values) with minimum computational cost (less that computations of FFT)?
So, first of all, computation of FFT:
Remember, the $10N$-point FFT, which you need for the resolution you demand:
Suppose my signal is a vector of length $N$ associated with some white noise.Suppose the demanded frequency accuracy is
$$\frac{f_\text{sample}}{10N}$$
has complexity of $\mathcal O\left(10N\log(10N)\right)$.
You've got a sparsity of ca. $\frac1{20}$:
comment clarify I give an example, imagin we have signal with lengh of 1000 or 2000. We take its DFT and there are less than 50 coefficient non-zero.
which means that it's not that sparse, and all algorithms exploiting sparsity by throwing linear algebra at the problem can't really benefit much from the situation; a $K$/$L$-rank matrix/matrix operation typically has best-case complexity $K\cdot L$, so considering $K=N$ this can only work out¹ in the favour of the sparse operation if $L<10\log(10N)$. Now you gave $N\approx 1000$, and let's chose a very modest logarithm base here – $\log_{10}$ – so, you'd end up with the condition $L < 10\log_{10} 10000 = 40$, and as you can see, with $L\approx 50$, this is not generally the case – this can really only work out if your sparsity-exploiting "tone finder" is very, very, very efficient.
But, you'll say, there's superefficient parametric estimators such as ESPRIT, that can get a much higher resolution with less samples!
Yes, that's what I'd have suggested in your situation, in general, too, but you've got to realize that these subspace/Eigenvalue based approaches work on a autocorrelation signal model – i.e. they need an estimate of the auto-correlation-matrix, which you typically get by calculating the dyadic product of the $N$-sample vector – a operation with complexity $\frac 12 N^2$, i.e. much much more than the complexity of the FFT.
So, to answer your question: No, there's to my knowledge no estimator with lower computational cost, but there's more mathematically efficient estimators than the DFT; however, you might actually get a $\frac1{10}$ resolution with less than $N$ samples, but really, you need to have a rank of your matrix estimate sufficiently higher than the number of tones you're looking for, so I'm afraid this won't change that much.
¹ I'm well aware that's not really how Landau symbols work. However, FFT implementations are
really highly optimized, and so is LAPack, and thus, my gut feeling says I can really use the complexity limits as "constants".