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

DOI10.1137/0613066zbMATH Open0759.65016OpenAlexW2040466831MaRDI QIDQ4021609FDOQ4021609

Authors:

Publication date: 16 January 1993

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0613066

Recommendations

• Estimating a largest eigenvector by Lanczos and polynomial algorithms with a random start
• Error bounds on the power method for determining the largest eigenvalue of a symmetric, positive definite matrix
• Probabilistic Bounds on the Extremal Eigenvalues and Condition Number by the Lanczos Algorithm
• Randomized error estimation for eigenvalue approximation
• On the randomized error of polynomial methods for eigenvector and eigenvalue estimates

zbMATH Keywords

power methodrandom startLanczos algorithmsKrylov chainlarge symmetric positive definite \(n\times n\) matrixlarges eigenvalue

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15)

Cited In (83)

• A Riemannian dimension-reduced second-order method with application in sensor network localization
• A deterministic algorithm for the Frieze-Kannan regularity lemma
• Lanczos, Householder transformations, and implicit deflation for fast and reliable dominant singular subspace computation
• Worst-Case Complexity of TRACE with Inexact Subproblem Solutions for Nonconvex Smooth Optimization
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization
• Geodesic convexity of the symmetric eigenvalue problem and convergence of steepest descent
• Efficient bounds and estimates for canonical angles in randomized subspace approximations
• Nonsmooth projection-free optimization with functional constraints
• Randomized Nyström Preconditioning
• SketchySGD: reliable stochastic optimization via randomized curvature estimates
• A Newton-CG Based Barrier Method for Finding a Second-Order Stationary Point of Nonconvex Conic Optimization with Complexity Guarantees
• Memory-efficient structured convex optimization via extreme point sampling
• A Newton-CG Based Augmented Lagrangian Method for Finding a Second-Order Stationary Point of Nonconvex Equality Constrained Optimization with Complexity Guarantees
• An optimal-storage approach to semidefinite programming using approximate complementarity
• Improved estimation of relaxation time in nonreversible Markov chains
• Probabilistic bounds for the matrix condition number with extended Lanczos bidiagonalization
• Perspectives on information-based complexity
• Randomized algorithms for the low-rank approximation of matrices
• Randomized block Krylov methods for approximating extreme eigenvalues
• Evaluation of spectral zeta-functions with the renormalization group
• Implicit Regularity and Linear Convergence Rates for the Generalized Trust-Region Subproblem
• Sparse Approximate Solutions to Semidefinite Programs
• A linear-time algorithm for globally maximizing the sum of a generalized Rayleigh quotient and a quadratic form on the unit sphere
• Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization
• Generalized conditional gradient for sparse estimation
• Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces
• The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection
• First-Order Methods for Nonconvex Quadratic Minimization
• Error Bounds for Lanczos-Based Matrix Function Approximation
• Convex relaxations for permutation problems
• Globally maximizing the sum of squares of quadratic forms over the unit sphere
• First-order methods for convex optimization
• Randomized numerical linear algebra: Foundations and algorithms
• Symbolic and numeric methods for exploiting structure in constructing resultant matrices
• Statistical Condition Estimation for Linear Systems
• Spectrally-truncated kernel ridge regression and its free lunch
• A fast randomized algorithm for the approximation of matrices
• A distributed Frank-Wolfe framework for learning low-rank matrices with the trace norm
• A recursive skeletonization factorization based on strong admissibility
• On the randomized error of polynomial methods for eigenvector and eigenvalue estimates
• Estimating a largest eigenvector by Lanczos and polynomial algorithms with a random start
• Hierarchical interpolative factorization for elliptic operators: differential equations
• Accelerated methods for nonconvex optimization
• Hierarchical interpolative factorization for elliptic operators: integral equations
• A linear-time algorithm for minimizing the ratio of quadratic functions with a quadratic constraint
• Approximate inversion of discrete Fourier integral operators
• A second-order cone based approach for solving the trust-region subproblem and its variants
• Gradient descent finds the cubic-regularized nonconvex Newton step
• Computing the field of values and pseudospectra using the Lanczos method with continuation
• A linear-time algorithm for trust region problems
• Sublinear time algorithms for approximate semidefinite programming
• Newton-type methods for non-convex optimization under inexact Hessian information
• Randomization and the parallel solution of linear algebra problems
• Subspace Iteration Randomization and Singular Value Problems
• Hierarchical interpolative factorization preconditioner for parabolic equations
• Trust-region Newton-CG with strong second-order complexity guarantees for nonconvex optimization
• Uniform Error Estimates for the Lanczos Method
• An accelerated first-order method with complexity analysis for solving cubic regularization subproblems
• A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization
• A linear-time algorithm for generalized trust region subproblems
• PCA Sparsified
• The generalized trust region subproblem: solution complexity and convex hull results
• A note on probably certifiably correct algorithms
• Combining stochastic adaptive cubic regularization with negative curvature for nonconvex optimization
• On norm compression inequalities for partitioned block tensors
• Cubic regularization methods with second-order complexity guarantee based on a new subproblem reformulation
• Norm and trace estimation with random rank-one vectors
• Smallest eigenvalue of large Hankel matrices at critical point: comparing conjecture with parallelised computation
• Complexity of linear minimization and projection on some sets
• Fast quantum subroutines for the simplex method
• Bounding the spectrum of large Hermitian matrices
• Subsampling algorithms for semidefinite programming
• A linear-time algorithm for the trust region subproblem based on hidden convexity
• Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
• Optimal information dissemination strategy to promote preventive behaviors in multilayer epidemic networks
• Scalable semidefinite programming
• Conditional gradient sliding for convex optimization
• Randomized error estimation for eigenvalue approximation
• Probabilistic upper bounds for the matrix two-norm
• The Monte Carlo Algorithm with a Pseudorandom Generator
• Convergence rate of block-coordinate maximization Burer-Monteiro method for solving large SDPs
• Spectral norm of a symmetric tensor and its computation
• Near-optimal stochastic approximation for online principal component estimation

Uses Software

• EISPACK

This page was built for publication: Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4021609)