Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
From MaRDI portal
Publication:4021609
DOI10.1137/0613066zbMath0759.65016OpenAlexW2040466831MaRDI QIDQ4021609
No author found.
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
power methodrandom startLanczos algorithmsKrylov chainlarge symmetric positive definite \(n\times n\) matrixlarges eigenvalue
Related Items (75)
Randomized numerical linear algebra: Foundations and algorithms ⋮ Approximate inversion of discrete Fourier integral operators ⋮ A distributed Frank-Wolfe framework for learning low-rank matrices with the trace norm ⋮ Probabilistic Bounds for the Matrix Condition Number with Extended Lanczos Bidiagonalization ⋮ Sublinear time algorithms for approximate semidefinite programming ⋮ A linear-time algorithm for trust region problems ⋮ Convex Relaxations for Permutation Problems ⋮ Hierarchical Interpolative Factorization for Elliptic Operators: Differential Equations ⋮ Lanczos, Householder transformations, and implicit deflation for fast and reliable dominant singular subspace computation ⋮ Perspectives on information-based complexity ⋮ Randomization and the parallel solution of linear algebra problems ⋮ Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness ⋮ Accelerated Methods for NonConvex Optimization ⋮ On norm compression inequalities for partitioned block tensors ⋮ Computing the field of values and pseudospectra using the Lanczos method with continuation ⋮ On the randomized error of polynomial methods for eigenvector and eigenvalue estimates ⋮ A Second-Order Cone Based Approach for Solving the Trust-Region Subproblem and Its Variants ⋮ Cubic regularization methods with second-order complexity guarantee based on a new subproblem reformulation ⋮ Worst-Case Complexity of TRACE with Inexact Subproblem Solutions for Nonconvex Smooth Optimization ⋮ A linear-time algorithm for the trust region subproblem based on hidden convexity ⋮ A Newton-CG Based Barrier Method for Finding a Second-Order Stationary Point of Nonconvex Conic Optimization with Complexity Guarantees ⋮ Implicit Regularity and Linear Convergence Rates for the Generalized Trust-Region Subproblem ⋮ A Newton-CG Based Augmented Lagrangian Method for Finding a Second-Order Stationary Point of Nonconvex Equality Constrained Optimization with Complexity Guarantees ⋮ Improved estimation of relaxation time in nonreversible Markov chains ⋮ A note on probably certifiably correct algorithms ⋮ The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection ⋮ Randomized Nyström Preconditioning ⋮ First-order methods for convex optimization ⋮ PCA Sparsified ⋮ First-Order Methods for Nonconvex Quadratic Minimization ⋮ Spectral norm of a symmetric tensor and its computation ⋮ Newton-type methods for non-convex optimization under inexact Hessian information ⋮ Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces ⋮ Probabilistic upper bounds for the matrix two-norm ⋮ Evaluation of spectral zeta-functions with the renormalization group ⋮ Hierarchical interpolative factorization preconditioner for parabolic equations ⋮ Globally maximizing the sum of squares of quadratic forms over the unit sphere ⋮ Spectrally-truncated kernel ridge regression and its free lunch ⋮ Norm and Trace Estimation with Random Rank-one Vectors ⋮ Complexity Analysis of Second-Order Line-Search Algorithms for Smooth Nonconvex Optimization ⋮ Randomized algorithms for the low-rank approximation of matrices ⋮ Memory-Efficient Structured Convex Optimization via Extreme Point Sampling ⋮ Uniform Error Estimates for the Lanczos Method ⋮ Near-optimal stochastic approximation for online principal component estimation ⋮ A fast randomized algorithm for the approximation of matrices ⋮ A linear-time algorithm for minimizing the ratio of quadratic functions with a quadratic constraint ⋮ An Optimal-Storage Approach to Semidefinite Programming Using Approximate Complementarity ⋮ The Monte Carlo Algorithm with a Pseudorandom Generator ⋮ Statistical Condition Estimation for Linear Systems ⋮ A Recursive Skeletonization Factorization Based on Strong Admissibility ⋮ Bounding the spectrum of large Hermitian matrices ⋮ Smallest eigenvalue of large Hankel matrices at critical point: comparing conjecture with parallelised computation ⋮ Sparse Approximate Solutions to Semidefinite Programs ⋮ An accelerated first-order method with complexity analysis for solving cubic regularization subproblems ⋮ A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization ⋮ Hierarchical Interpolative Factorization for Elliptic Operators: Integral Equations ⋮ Conditional Gradient Sliding for Convex Optimization ⋮ Combining stochastic adaptive cubic regularization with negative curvature for nonconvex optimization ⋮ A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma ⋮ Complexity of linear minimization and projection on some sets ⋮ Fast quantum subroutines for the simplex method ⋮ A Linear-Time Algorithm for Globally Maximizing the Sum of a Generalized Rayleigh Quotient and a Quadratic Form on the Unit Sphere ⋮ Randomized block Krylov methods for approximating extreme eigenvalues ⋮ Gradient Descent Finds the Cubic-Regularized Nonconvex Newton Step ⋮ Generalized Conditional Gradient for Sparse Estimation ⋮ Subsampling Algorithms for Semidefinite Programming ⋮ Scalable Semidefinite Programming ⋮ Convergence rate of block-coordinate maximization Burer-Monteiro method for solving large SDPs ⋮ Trust-Region Newton-CG with Strong Second-Order Complexity Guarantees for Nonconvex Optimization ⋮ A Linear-Time Algorithm for Generalized Trust Region Subproblems ⋮ Subspace Iteration Randomization and Singular Value Problems ⋮ Optimal information dissemination strategy to promote preventive behaviors in multilayer epidemic networks ⋮ Error Bounds for Lanczos-Based Matrix Function Approximation ⋮ Symbolic and numeric methods for exploiting structure in constructing resultant matrices ⋮ The generalized trust region subproblem: solution complexity and convex hull results
Uses Software
This page was built for publication: Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
