Noisy Power Method with and without Spectral Gap

Wednesday, April 26, 2017, 11:00 am - 12:00 pm PDTiCal
11th floor large conference room
This event is open to the public.
AI Seminar
Seyoung Yun

The power method is a simple and efficient algorithm for finding the top $k$ singular vectors of any input matrix. In practice, a noise matrix could be added to the input matrix at each iteration of the power method, and the convergence behavior of the algorithm is not hard to guarantee. In this paper, we address problems of the noisy power method. The name noisy power method is borrowed from [hardt et al. 2014]. The convergence behavior of the noisy power method is understood only for the cases when the noise level (the spectral norm of noise matrices) is bellowing a threshold, and there are many open questions as stated in [hardt et al. 2014]  Moreover, the noisy power method cannot extract the exact top $k$ singular vectors because of the noise matrices. Our contributions are three folds: i) we provide a different approach to analyze the noisy power method that will help to understand the convergence behavior of the noisy power method, ii) we propose a simple add-on algorithm that makes the output converge to the exact top $k$ singular vectors, iii) we also provide a negative example where the noisy power method performs very badly when the noise level is equal to the spectral gap, which is a counter example for Conjecture 1.2 of [hardt et al. 2014].

Se-Young Yun is a post-doc researcher at Los Alamos National Laboratory and will join to Industrial and System Engineering Dept. of KAIST from Aug. 2017. Before joining Los Alamos National Lab., he was at Microsoft research - INRIA joint center, Paris, France and KTH, Stockholm, Sweden as a post-doc researcher. He was a visiting researcher at Microsoft research Cambridge, UK in 2015. He received the B.S. and Ph.D in electrical engineering from the KAIST, Daejeon, Republic of Korea, in 2006 and 2012, respectively. He received the best paper award in ACM MOBIHOC 2013 and outstanding reviewer award in NIPS 2016.

« Return to Upcoming Events