A graph laplacian matrix learning method for fast implementation of graph fourier transform
In this paper, we propose an efficient graph learning approach for fast graph Fourier transform. We consider a maximum likelihood problem with additional constraints based on a matrix factorization of the graph Laplacian matrix, such that its eigenmatrix is a product of a block diagonal matrix and a butterfly-like matrix. We show that a special case of this problem reduces to a learning problem with constraints enforcing certain graph symmetries. Then, we provide an efficient approximation approach for the general problem without enforcing any symmetry constraint. We use this approach to design a fast nonseparable transform for intra predictive residual blocks in video compression. The resulting transform achieves a better rate-distortion performance than the 2D DCT and the hybrid DCT/ADST transform.