Regularized Laplacian Estimation and Fast Eigenvector Approximation

Details Regularized Laplacian Estimation and Fast Eigenvector Approximation Regularized Laplacian Estimation and Fast Eigenvector Approximation

2011-10-08

arxiv.org/abs/1110.1757v2

Computer Science

Data Structures and Algorithms

13 pages and 3 figures. A more detailed version of a paper appearing in the 2011 NIPS Conference

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Regularized Laplacian Estimation and Fast Eigenvector Approximation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Regularized Laplacian Estimation and Fast Eigenvector Approximation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Regularized Laplacian Estimation and Fast Eigenvector Approximation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-497819