Dynamical perturbation theory for eigenvalue problems

• URL: http://arxiv.org/abs/2002.12872v3
• Date: Wed, 11 Mar 2020 15:39:46 GMT
• Title: Dynamical perturbation theory for eigenvalue problems
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many problems in physics, chemistry and other fields are perturbative in nature, i.e. differ only slightly from related problems with known solutions. Prominent among these is the eigenvalue perturbation problem, wherein one seeks the eigenvectors and eigenvalues of a matrix with small off-diagonal elements. Here we introduce a novel iterative algorithm to compute these eigenpairs based on fixed-point iteration for an algebraic equation in complex projective space. We show from explicit and numerical examples that our algorithm outperforms the usual Rayleigh-Schr\"odinger expansion on three counts. First, since it is not defined as a power series, its domain of convergence is not a priori confined to a disk in the complex plane; we find that it indeed usually extends beyond the standard perturbative radius of convergence. Second, it converges at a faster rate than the Rayleigh-Schr\"odinger expansion, i.e. fewer iterations are required to reach a given precision. Third, the (time- and space-) algorithmic complexity of each iteration does not increase with the order of the approximation, allowing for higher precision computations. Because this complexity is merely that of matrix multiplication, our dynamical scheme also scales better with the size of the matrix than general-purpose eigenvalue routines such as the shifted QR or divide-and-conquer algorithms. Whether they are dense, sparse, symmetric or unsymmetric, we confirm that dynamical diagonalization quickly outpaces LAPACK drivers as the size of matrices grows; for the computation of just the dominant eigenvector, our method converges order of magnitudes faster than the Arnoldi algorithm implemented in ARPACK.

Related papers

• The Structural Complexity of Matrix-Vector Multiplication [0.10485739694839669]
  We show that the matrix-vector multiplication problem can be solved with $tildeO(n2)$ preprocessing and $tilde O(n2-1/d)$ query time. Our results yield the first non-trivial upper bounds for many applications.
  arXiv  Detail & Related papers  (2025-02-28T17:11:36Z)
• Improving Algorithmic Efficiency using Cryptography [11.496343300483904]
  We show how to use cryptography to improve the time complexity of solving computational problems. We show that under standard cryptographic assumptions, we can design algorithms that are determinantally faster than existing ones.
  arXiv  Detail & Related papers  (2025-02-18T17:08:59Z)
• A fixed-point algorithm for matrix projections with applications in quantum information [7.988085110283119]
  We show that our algorithm converges exponentially fast to the optimal solution in the number of iterations. We discuss several applications of our algorithm in quantum resource theories and quantum Shannon theory.
  arXiv  Detail & Related papers  (2023-12-22T11:16:11Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  Trust-region (TR) and adaptive regularization using cubics have proven to have some very appealing theoretical properties. We show that TR and ARC methods can simultaneously provide inexact computations of the Hessian, gradient, and function values.
  arXiv  Detail & Related papers  (2023-10-18T10:29:58Z)
• On algorithmically boosting fixed-point computations [0.9790236766474201]
  Algorithmic boosting is the principle of computing fixed points by taking (long-run) averages of iterated maps. We show that our algorithmic boosting method can set in motion em exponential speedups in the convergence rate.
  arXiv  Detail & Related papers  (2023-04-04T07:26:50Z)
• Low-Rank Updates of Matrix Square Roots [7.832944895330117]
  We consider the matrix square root and inverse square root operations. Given a low rank perturbation to a matrix, we argue that a low-rank approximate correction to the (inverse) square root exists. We then discuss how a low-rank solution to that equation can be computed.
  arXiv  Detail & Related papers  (2022-01-31T12:05:33Z)
• Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors [54.936314353063494]
  We provide recovery guarantees for a correlation-based optimization algorithm for robust 1-bit compressive sensing. We make use of a practical iterative algorithm, and perform numerical experiments on image datasets to corroborate our results.
  arXiv  Detail & Related papers  (2021-08-08T05:28:06Z)
• 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)
• Fast and accurate optimization on the orthogonal manifold without retraction [7.887285735878797]
  We propose a landing algorithm which does not involve retractions. The algorithm is not constrained to stay on the manifold but its evolution is driven by a potential energy. One of the landing algorithm only involves matrix multiplications, which makes it cheap compared to its retraction counterparts.
  arXiv  Detail & Related papers  (2021-02-15T10:12:05Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• Non-Sparse PCA in High Dimensions via Cone Projected Power Iteration [4.162663632560141]
  We propose a cone projected power algorithm to recover the first principal eigenvector from a noisy positive semidefinite matrix. Our numerical experiments on simulated and real data, show that our method achieves shorter run time and smaller error in comparison to the ordinary power and some sparse principal component analysis algorithms.
  arXiv  Detail & Related papers  (2020-05-15T15:02:24Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems. We focus on two classical embeddings, namely, Gaussian projections and subsampled Hadamard transforms. Our resulting algorithm yields the best complexity known for solving least-squares problems with no condition number dependence.
  arXiv  Detail & Related papers  (2020-02-21T17:45:32Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  We study the performance of iterative sketching for least-squares problems. We show that the convergence rate for Haar and randomized Hadamard matrices are identical, andally improve upon random projections. These techniques may be applied to other algorithms that employ randomized dimension reduction.
  arXiv  Detail & Related papers  (2020-02-03T16:17:50Z)

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.