Escaping the Krylov space during finite precision Lanczos

• URL: http://arxiv.org/abs/2505.02670v2
• Date: Tue, 22 Jul 2025 11:22:21 GMT
• Title: Escaping the Krylov space during finite precision Lanczos
• Abstract summary: We show that the numerical sequence of eigenvectors in finite precision arithmetic escapes the true vector space spanned by the exact Lanczos vectors.<n>This poses the real threat to an interpretation in view of the operator growth hypothesis.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Lanczos algorithm, introduced by Cornelius Lanczos, has been known for a long time and is widely used in computational physics. While often employed to approximate extreme eigenvalues and eigenvectores of an operator, recently interest in the sequence of basis vectors produced by the algorithm rose in the context of Krylov complexity. Although it is generally accepted and partially proven that the procedure is numerically stable for approximating the eigenvalues, there are numerical problems when investigating the Krylov basis constructed via the Lanczos procedure. In this paper, we show that loss of orthogonality and the attempt of reorthoganalization fall short of understanding and addressing the problem. Instead, the numerical sequence of eigenvectors in finite precision arithmetic escapes the true vector space spanned by the exact Lanczos vectors. This poses the real threat to an interpretation in view of the operator growth hypothesis.

Related papers

• On Kernel Eigen-alignments of KRR: Reconstruction and Generalization [3.344730946122235]
  We establish a direct connection between generalization performance in kernel methods and the estimation of eigenvectors and eigenvalues of matrices.<n>We show that strong generalization requires increasing eigenvector alignment, eigenvalue magnitude, or gaps between consecutive eigenvalues.
  arXiv  Detail & Related papers  (2026-05-14T05:46:31Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
  We derive entrywise error bounds for low-rank approximations of kernel matrices obtained using the truncated eigen-decomposition. A key technical innovation is a delocalisation result for the eigenvectors of the kernel matrix corresponding to small eigenvalues. We validate our theory with an empirical study of a collection of synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2024-05-23T12:26:25Z)
• Operator dynamics in Lindbladian SYK: a Krylov complexity perspective [0.0]
  We analytically establish the linear growth of two sets of coefficients for any generic jump operators. We find that the Krylov complexity saturates inversely with the dissipation strength, while the dissipative timescale grows logarithmically.
  arXiv  Detail & Related papers  (2023-11-01T18:00:06Z)
• Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization [48.65416821017865]
  This chapter introduces a new algorithmic approach, dubbed scaled gradient (ScaledGD) It converges linearly at a constant rate independent of the condition number of the low-rank object. It maintains the low periteration cost of gradient descent for a variety of tasks.
  arXiv  Detail & Related papers  (2023-10-09T21:16:57Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  Motivated by the problem of online correlation analysis, we propose the emphStochastic Scaled-Gradient Descent (SSD) algorithm. We bring these ideas together in an application to online correlation analysis, deriving for the first time an optimal one-time-scale algorithm with an explicit rate of local convergence to normality.
  arXiv  Detail & Related papers  (2021-12-29T18:46:52Z)
• Quantum Lattice Sieving [0.0]
  A central problem in the study of lattices is that of finding the shortest non-zero vector in the lattice. We present a quantum sieving algorithm that has memory complexity in the size of the length of the sampled vectors at the initial step of the sieve.
  arXiv  Detail & Related papers  (2021-10-26T01:50:48Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• Robust Differentiable SVD [117.35644933471401]
  Eigendecomposition of symmetric matrices is at the heart of many computer vision algorithms. Instability arises in the presence of eigenvalues that are close to each other. We show that the Taylor expansion of the SVD gradient is theoretically equivalent to the gradient obtained using PI without relying on an iterative process.
  arXiv  Detail & Related papers  (2021-04-08T15:04:15Z)
• Minimax Estimation of Linear Functions of Eigenvectors in the Face of Small Eigen-Gaps [95.62172085878132]
  Eigenvector perturbation analysis plays a vital role in various statistical data science applications. We develop a suite of statistical theory that characterizes the perturbation of arbitrary linear functions of an unknown eigenvector. In order to mitigate a non-negligible bias issue inherent to the natural "plug-in" estimator, we develop de-biased estimators.
  arXiv  Detail & Related papers  (2021-04-07T17:55:10Z)
• Analysis of Truncated Orthogonal Iteration for Sparse Eigenvector Problems [78.95866278697777]
  We propose two variants of the Truncated Orthogonal Iteration to compute multiple leading eigenvectors with sparsity constraints simultaneously. We then apply our algorithms to solve the sparse principle component analysis problem for a wide range of test datasets.
  arXiv  Detail & Related papers  (2021-03-24T23:11:32Z)
• Symmetric Boolean Factor Analysis with Applications to InstaHide [18.143740528953142]
  We show that InstaHide possesses some form of "fine-grained security" against reconstruction attacks for moderately large k. Our algorithm, based on tensor decomposition, only requires m to be at least quasi-linear in r. We complement this result with a quasipolynomial-time algorithm for a worst-case setting of the problem where the collection of k-sparse vectors is chosen arbitrarily.
  arXiv  Detail & Related papers  (2021-02-02T15:52:52Z)
• Dynamical perturbation theory for eigenvalue problems [0.0]
  We show that our algorithm outperforms the usual Rayleigh-Schr"odinger expansion on three counts. Our scheme also scales better with the size of the matrix than general-purpose eigenvalue routines.
  arXiv  Detail & Related papers  (2020-02-28T17:13:22Z)
• Entrywise convergence of iterative methods for eigenproblems [31.69089186688224]
  We address the convergence of subspace iteration when distances are measured in the $ell_2 to infty$ norm. Our results show that one can get comparable performance on downstream tasks while requiring fewer iterations, thereby saving substantial computational time.
  arXiv  Detail & Related papers  (2020-02-19T22:59:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.