  Regularization is a powerful technique for extracting useful information from
noisy data. Typically, it is implemented by adding some sort of norm constraint
to an objective function and then exactly optimizing the modified objective
function. This procedure often leads to optimization problems that are
computationally more expensive than the original problem, a fact that is
clearly problematic if one is interested in large-scale applications. On the
other hand, a large body of empirical work has demonstrated that heuristics,
and in some cases approximation algorithms, developed to speed up computations
sometimes have the side-effect of performing regularization implicitly. Thus,
we consider the question: What is the regularized optimization objective that
an approximation algorithm is exactly optimizing?
  We address this question in the context of computing approximations to the
smallest nontrivial eigenvector of a graph Laplacian; and we consider three
random-walk-based procedures: one based on the heat kernel of the graph, one
based on computing the the PageRank vector associated with the graph, and one
based on a truncated lazy random walk. In each case, we provide a precise
characterization of the manner in which the approximation method can be viewed
as implicitly computing the exact solution to a regularized problem.
Interestingly, the regularization is not on the usual vector form of the
optimization problem, but instead it is on a related semidefinite program.
