Abstract: In spite of high computational complexity, the bilateral filter and its modifications and extensions have recently become very popular image and shape processing tools. In this paper, we propose a fast and accurate approximation of the bilateral filter. Our approach combines a dimension elevation trick with a Fast Gauss Transform. First we represent the bilateral filter as a convolution in a high dimensional space. Then the convolution is efficiently approximated by using space partitioning and Gaussian function expansions. Advantages of our approach include linear computational complexity, user-specified precision, and an ability to process high dimensional and non-uniformly sampled data. We demonstrate capabilities of the approach by considering its applications to the image and volume denoising and high-dynamic-range tone mapping problems.