  In Graph Signal Processing (GSP), data dependencies are represented by a
graph whose nodes label the data and the edges capture dependencies among
nodes. The graph is represented by a weighted adjacency matrix $A$ that, in
GSP, generalizes the Discrete Signal Processing (DSP) shift operator $z^{-1}$.
The (right) eigenvectors of the shift $A$ (graph spectral components)
diagonalize $A$ and lead to a graph Fourier basis $F$ that provides a graph
spectral representation of the graph signal. The inverse of the (matrix of the)
graph Fourier basis $F$ is the Graph Fourier transform (GFT), $F^{-1}$. Often,
including in real world examples, this diagonalization is numerically unstable.
This paper develops an approach to compute an accurate approximation to $F$ and
$F^{-1}$, while insuring their numerical stability, by means of solving a non
convex optimization problem. To address the non-convexity, we propose an
algorithm, the stable graph Fourier basis algorithm (SGFA) that we prove to
exponentially increase the accuracy of the approximating $F$ per iteration.
Likewise, we can apply SGFA to $A^H$ and, hence, approximate the stable left
eigenvectors for the graph shift $A$ and directly compute the GFT. We evaluate
empirically the quality of SGFA by applying it to graph shifts $A$ drawn from
two real world problems, the 2004 US political blogs graph and the Manhattan
road map, carrying out a comprehensive study on tradeoffs between different
SGFA parameters. We also confirm our conclusions by applying SGFA on very
sparse and very dense directed Erd\H os-R\'enyi graphs.
