A method for fast approximate computation of discrete time transforms

The fast approximated discrete transform is proposed as a method for reducing the time necessary to compute the discrete transform of a finite-length sequence. It is based on a subband decomposition and can be viewed as a link between the fast transform methods (like the fast Fourier transform), which compute all points in the transform domain, and the variety of methods to evaluate the discrete transforms at a given set of points. The method uses knowledge about the input signal to obtain an approximation to its transform by discarding the computations in bands that have little or no energy contribution. In a number of practical cases the proposed fast approximation is reasonably accurate, and in all cases the method can be iterated to yield the exact transform, if necessary