Fast signal analysis and decomposition on graphs using the Sparse Matrix Transform

Recently, the Sparse Matrix Transform (SMT) has been proposed as a tool for estimating the eigen-decomposition of high dimensional data vectors. The SMT approach has two major advantages: First it can improve the accuracy of the eigendecomposition, particularly when the number of observations, n, is less the the vector dimension, p. Second, the resulting SMT eigen-decomposition is very fast to apply, i.e. O(p). In this paper, we present an SMT eigen-decomposition method suited for application to signals that live on graphs. This new SMT eigen-decomposition method has two major advantages over the more generic method presented in. First, the resulting SMT can be more accurately estimated due to the graphical constraint. Second, the computation required to design the SMT from training data is dramatically reduced from an average observed complexity of p³ to p log p.