Using least squares to extract a Fourier approximation

Question

I am faced with the following problem. I have signal $x_t:\{0,1,N-1\} \rightarrow \mathbb{C}$ where $N$ is very large. I want to compute a few of the Fourier coefficients say for example:$\hat{x}_0, \hat{x}_1, \hat{x}_2$. Since $N$ is prohibitively large I don't want to use the Fourier analysis equation and I don't want to look at the whole signal. I take the following approach, I vectorize $x$ and $\hat{x}$ and I let $\mathcal{F} \in \mathbb{C}^{N \times N}$ denote the matrix that holds the Fourier basis as its columns. It holds that: $$x = \mathcal{F} \hat{x}, \;\;\;\ \hat{x} = \mathcal{F}^{-1} x $$ One thing I could do now is compute the least square solution to get these three coefficients: $$\hat{x}_{0:3} = \arg\min_{\theta \in \mathbb{C^3}}\|x-F_{:,0:3} \theta\|$$ Where the equality above is exact. But again this would require me to read the whole signal. I am now wondering what happens if I subsample some rows of the vector $x$ and rows of the Fourier matrix uniformly at random, say I subsample 10 rows and solve the corresponding (still overdetermined), least squares system. What kind of theoretical guarantees could I give?