Please join us in welcoming Minh Tang, assistant professor from the NC State’s Statistics Department, as he discusses deviation analysis of randomized singular value decomposition (SVD) and its applications to high-dimensional statistics.
OR PRO TIP: All OR 601/801 students must attend in person. Others are welcome to join in person or can join by Zoom.
https://ncsu.zoom.us/j/93958805097?pwd=azltMmloZlp6dzRLWjBtOUtUdU1pdz09
Meeting ID: 939 5880 5097
Passcode: 547206
Randomized singular value decomposition (RSVD) is a class of computationally efficient algorithms for computing the truncated SVD of large data matrices. Given a symmetric matrix M, the prototypical RSVD algorithm approximates the k leading singular vectors of M by computing the SVD of M g G Insert Formula M^{g} G; here g is a positive integer and G is a Gaussian sketching matrix. In this talk, we present statistical properties of RSVD under a general "signal-plus-noise" framework, i.e., the observed matrix is assumed to be an additive perturbation of some true but unknown signal matrix. We first derive upper bounds for the spectral norm and two-to-infinity norm between the approximate singular vectors of the observed matrix and the true singular vectors of the signal matrix. These upper bounds depend on the signal-to-noise ratio (SNR) and the number of power iterations g. A phase transition phenomenon is observed in which a smaller SNR requires larger values of g to guarantee convergence of the spectral and two-to-infinity norms. Finally, we derive normal approximations for the row-wise fluctuations of the approximate singular vectors and entrywise fluctuations of the observed matrix when projected onto these vectors. We illustrate our results by deriving nearly-optimal performance guarantees for RSVD when applied to three statistical inference problems, namely, community detection in networks, matrix completion, and PCA with missing data.
Minh Tang received a BS degree from Assumption University (Thailand) in 2001, an MS degree from the University of Wisconsin Milwaukee in 2004 and a Ph.D. degree from Indiana University Bloomington in 2010, all in computer science. He was a postdoctoral fellow and subsequently research faculty in the Department of Applied Mathematics and Statistics at Johns Hopkins University. He is currently an assistant professor in the Department of Statistics at North Carolina State University. His research interests include dimensionality reduction and statistical inference for high-dimensional and graph-valued data.
