Inferring causality between randomly observed stochastic processes is inherentily a difficult task and few statistical guarantees are available for practitioners in this setting. As such data sets are now very common (stock market, mobile sensing, medical data), we want to provide a statistically sound and scalable approach to infer relationships between continuous stochastic processes observed discretely and randomly. We show how spectral domain random projections can mitigate statistical and scalability related issues provided a careful design of the frequency domain basis is used. After having provided theorems giving strong statistical guarantees, we show through numerical experiments on surrogate and actual data that our method is reliable and scalable.