  The definition of the graph Fourier transform is a fundamental issue in graph
signal processing. Conventional graph Fourier transform is defined through the
eigenvectors of the graph Laplacian matrix, which minimize the $\ell_2$ norm
signal variation. However, the computation of Laplacian eigenvectors is
expensive when the graph is large. In this paper, we propose an alternative
definition of graph Fourier transform based on the $\ell_1$ norm variation
minimization. We obtain a necessary condition satisfied by the $\ell_1$ Fourier
basis, and provide a fast greedy algorithm to approximate the $\ell_1$ Fourier
basis. Numerical experiments show the effectiveness of the greedy algorithm.
Moreover, the Fourier transform under the greedy basis demonstrates a similar
rate of decay to that of Laplacian basis for simulated or real signals.
