Features are disclosed for performing acoustic echo cancellation using random noise. The output may be used to perform speech recognition. Random noise may be introduced into a reference signal path and into a microphone signal path. The random noise introduced into the microphone signal path may be transformed based on an estimated echo path and then combined with microphone output. The random noise introduced into the reference signal path may be combined with a reference signal and then transformed. In some embodiments, the random noise in the reference signal path may be used in the absence of another reference signal, allowing the acoustic echo canceler to be continuously trained.