# Very fast algorithm for single- and multi-microphone noise cancellation

## Abstract

Many applications, such as directive microphone arrays, employ linearly filtered signals from a number of sensors to enhance an audio source embedded in noise produced by other audio sources. It turns out that the noise cancellation properties are improved with the length of the filters, and filters possessing as many as 4000 taps may be used beneficially. For such filters, the techniques of adaptive filtering are inadequate resulting in poor convergence and noise cancellation properties. In this work it will be shown how to combine fast filter adaptation with accurate noise cancellation. A judicious choice of basis functions (modulated gaussians) leads to a sparse system of equations, resulting in a low computational complexity of the solver. In the first stage of the algorithm the relevant correlation functions are computed very rapidly using an FFT technique. This calculation requires about NlogN operations and produces the coefficients of a system of linear equations for the filter coefficients. In the second stage these equations are solved with a complexity of the number of equations, N, rather than in N2 operations as is the case for the usual Toeplitz solvers or in NlogN for contemporary fast Toeplitz solvers. The proposed scheme is superior to previously used schemes for filter lengths beginning from 50. The algorithm had been implemented in a single microphone noise canceller and in a directive microphone array.