  In this paper, we introduce a new, spectral notion of approximation between
directed graphs, which we call singular value (SV) approximation.
SV-approximation is stronger than previous notions of spectral approximation
considered in the literature, including spectral approximation of Laplacians
for undirected graphs (Spielman Teng STOC 2004), standard approximation for
directed graphs (Cohen et. al. STOC 2017), and unit-circle approximation for
directed graphs (Ahmadinejad et. al. FOCS 2020). Further, SV approximation
enjoys several useful properties not possessed by previous notions of
approximation, e.g., it is preserved under products of random-walk matrices and
bounded matrices.
  We provide a nearly linear-time algorithm for SV-sparsifying (and hence
UC-sparsifying) Eulerian directed graphs, as well as $\ell$-step random walks
on such graphs, for any $\ell\leq \text{poly}(n)$. Combined with the Eulerian
scaling algorithms of (Cohen et. al. FOCS 2018), given an arbitrary (not
necessarily Eulerian) directed graph and a set $S$ of vertices, we can
approximate the stationary probability mass of the $(S,S^c)$ cut in an
$\ell$-step random walk to within a multiplicative error of
$1/\text{polylog}(n)$ and an additive error of $1/\text{poly}(n)$ in nearly
linear time. As a starting point for these results, we provide a simple
black-box reduction from SV-sparsifying Eulerian directed graphs to
SV-sparsifying undirected graphs; such a directed-to-undirected reduction was
not known for previous notions of spectral approximation.
