Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start

By J. Kuczy, H. Wo. 1992

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Optimization & Training

Citations in the corpus

Frank-Wolfe Splitting via Augmented Lagrangian Method (2018, methodology): “(34) can be computed efficiently by the Lanczos algorithm (Paige, 1971; Kuczyński and Woźniakowski, 1992) whereas the forward backward splitting which is the standard splitting method to solve (33) needs to compute projections over the trace norm ball via a complete diagonalization which is O(d(3)).”
Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions (2009, methodology): “Woźniakowski and coauthors have analyzed the performance of the power method and the Lanczos iteration given a random starting vector [80, 86].”
Local Saddle Point Optimization: A Curvature Exploitation Approach (2018, unknown): “The results of [21] provide a bound on the number of required iterations to extract the extreme curvature: for the case λmin(∇(2)xf(z)) ≤ −γ, 1 γ log(k/δ (2))Lx iterations suffice to find a vector v̂ such that v̂∇(2)xf(z)v̂ ≤ − γ 2 with probability 1− δ (cf.”
Fast and Simple PCA via Convex Optimization (2015, unknown): “Method Complexity Comments Power method [17] λ1 ǫ N Lanczos [17] √”
An Algorithm for the Principal Component Analysis of Large Data Sets (2010, unknown): “The denoising is clearly satisfactory.”
Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition (2015, methodology): “For analyzing block methods, results like Lemma 4 can effect iv ly serve as a replacement for earlier random initialization analysis that applies to single vect or power and Krylov methods [44].”
Accelerated Methods for Non-Convex Optimization (2016, methodology): “A number of methods compute such (approximate) leading eigenvectors, including the Lanczos method [17].”
First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time (2017, unknown): “Following the results in [13], it can be shown that if λmin(∇(2)f(x)) ≤ −γ, then with at most log(d/δ(2))L1 γ HVPs, the Power method finds a vector v̂t = vt/‖vt‖ such that v̂ > t ∇(2)f(x)v̂t ≤ − γ 2 holds with high probability 1− δ.”
Improved Approximation Algorithms for Large Matrices via Random Projections (2006, methodology): “Similarly, approximate SVD schemes based on the Lánczos or power method requireΩ(log m) passes [44, 37].”