Regularized Laplacian Estimation and Fast Eigenvector Approximation
P. Perry, and M. Mahoney. (2011)cite arxiv:1110.1757Comment: 13 pages and 3 figures. A more detailed version of a paper appearing in the 2011 NIPS Conference.
Abstract
Recently, Mahoney and Orecchia demonstrated that popular diffusion-based
procedures to compute a quick approximation to the first nontrivial
eigenvector of a data graph Laplacian exactly solve certain regularized
Semi-Definite Programs (SDPs). In this paper, we extend that result by
providing a statistical interpretation of their approximation procedure. Our
interpretation will be analogous to the manner in which $\ell_2$-regularized or
$\ell_1$-regularized $\ell_2$-regression (often called Ridge regression and
Lasso regression, respectively) can be interpreted in terms of a Gaussian prior
or a Laplace prior, respectively, on the coefficient vector of the regression
problem. Our framework will imply that the solutions to the Mahoney-Orecchia
regularized SDP can be interpreted as regularized estimates of the
pseudoinverse of the graph Laplacian. Conversely, it will imply that the
solution to this regularized estimation problem can be computed very quickly by
running, e.g., the fast diffusion-based PageRank procedure for computing an
approximation to the first nontrivial eigenvector of the graph Laplacian.
Empirical results are also provided to illustrate the manner in which
approximate eigenvector computation implicitly performs statistical
regularization, relative to running the corresponding exact algorithm.
Description
[1110.1757] Regularized Laplacian Estimation and Fast Eigenvector Approximation
%0 Generic
%1 perry2011regularized
%A Perry, Patrick O.
%A Mahoney, Michael W.
%D 2011
%K computation eigenvectors ill-posed_problems regularization
%T Regularized Laplacian Estimation and Fast Eigenvector Approximation
%U http://arxiv.org/abs/1110.1757
%X Recently, Mahoney and Orecchia demonstrated that popular diffusion-based
procedures to compute a quick approximation to the first nontrivial
eigenvector of a data graph Laplacian exactly solve certain regularized
Semi-Definite Programs (SDPs). In this paper, we extend that result by
providing a statistical interpretation of their approximation procedure. Our
interpretation will be analogous to the manner in which $\ell_2$-regularized or
$\ell_1$-regularized $\ell_2$-regression (often called Ridge regression and
Lasso regression, respectively) can be interpreted in terms of a Gaussian prior
or a Laplace prior, respectively, on the coefficient vector of the regression
problem. Our framework will imply that the solutions to the Mahoney-Orecchia
regularized SDP can be interpreted as regularized estimates of the
pseudoinverse of the graph Laplacian. Conversely, it will imply that the
solution to this regularized estimation problem can be computed very quickly by
running, e.g., the fast diffusion-based PageRank procedure for computing an
approximation to the first nontrivial eigenvector of the graph Laplacian.
Empirical results are also provided to illustrate the manner in which
approximate eigenvector computation implicitly performs statistical
regularization, relative to running the corresponding exact algorithm.
@misc{perry2011regularized,
abstract = {Recently, Mahoney and Orecchia demonstrated that popular diffusion-based
procedures to compute a quick \emph{approximation} to the first nontrivial
eigenvector of a data graph Laplacian \emph{exactly} solve certain regularized
Semi-Definite Programs (SDPs). In this paper, we extend that result by
providing a statistical interpretation of their approximation procedure. Our
interpretation will be analogous to the manner in which $\ell_2$-regularized or
$\ell_1$-regularized $\ell_2$-regression (often called Ridge regression and
Lasso regression, respectively) can be interpreted in terms of a Gaussian prior
or a Laplace prior, respectively, on the coefficient vector of the regression
problem. Our framework will imply that the solutions to the Mahoney-Orecchia
regularized SDP can be interpreted as regularized estimates of the
pseudoinverse of the graph Laplacian. Conversely, it will imply that the
solution to this regularized estimation problem can be computed very quickly by
running, e.g., the fast diffusion-based PageRank procedure for computing an
approximation to the first nontrivial eigenvector of the graph Laplacian.
Empirical results are also provided to illustrate the manner in which
approximate eigenvector computation \emph{implicitly} performs statistical
regularization, relative to running the corresponding exact algorithm.},
added-at = {2012-08-05T01:45:06.000+0200},
author = {Perry, Patrick O. and Mahoney, Michael W.},
biburl = {https://www.bibsonomy.org/bibtex/209a9f3f500d1bd4712221cd068d9fab4/peter.ralph},
description = {[1110.1757] Regularized Laplacian Estimation and Fast Eigenvector Approximation},
interhash = {d65965282cc7e4d69f1cc2aa8df65c9a},
intrahash = {09a9f3f500d1bd4712221cd068d9fab4},
keywords = {computation eigenvectors ill-posed_problems regularization},
note = {cite arxiv:1110.1757Comment: 13 pages and 3 figures. A more detailed version of a paper appearing in the 2011 NIPS Conference},
timestamp = {2012-08-05T01:45:06.000+0200},
title = {Regularized Laplacian Estimation and Fast Eigenvector Approximation},
url = {http://arxiv.org/abs/1110.1757},
year = 2011
}