Recently, Mahoney and Orecchia demonstrated that popular diffusionbased procedures to compute a quick approximation to the first nontrivial eigenvector of a data graph Laplacian exactly solve certain regularized SemiDefinite 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 l2regularized or l1regularized l2 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 MahoneyOrecchia 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 diffusionbased 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.
Author Information
Patrick O Perry (NYU)
Michael W Mahoney (UC Berkeley)
More from the Same Authors

2017 Poster: Union of Intersections (UoI) for Interpretable Data Driven Discovery and Prediction »
Kristofer Bouchard · Alejandro Bujan · Farbod RoostaKhorasani · Shashanka Ubaru · Mr. Prabhat · Antoine Snijders · JianHua Mao · Edward Chang · Michael W Mahoney · Sharmodeep Bhattacharya 
2012 Poster: Semisupervised Eigenvectors for Locallybiased Learning »
Toke Jansen Hansen · Michael W Mahoney 
2011 Workshop: Sparse Representation and Lowrank Approximation »
Ameet S Talwalkar · Lester W Mackey · Mehryar Mohri · Michael W Mahoney · Francis Bach · Mike E davies · Remi Gribonval · Guillaume R Obozinski 
2010 Workshop: Lowrank Methods for Largescale Machine Learning »
Arthur Gretton · Michael W Mahoney · Mehryar Mohri · Ameet S Talwalkar 
2010 Poster: CUR from a Sparse Optimization Viewpoint »
Jacob Bien · Ya Xu · Michael W Mahoney 
2009 Poster: Unsupervised Feature Selection for the $k$means Clustering Problem »
Christos Boutsidis · Michael W Mahoney · Petros Drineas