Regularized Laplacian Estimation and Fast Eigenvector Approximation Michael W. Mahoney Information, Operations, and Management Sciences Department of Mathematics NYU Stern School of Business

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.