Entrywise convergence of iterative methods for eigenproblems
- URL: http://arxiv.org/abs/2002.08491v2
- Date: Sat, 31 Oct 2020 02:06:19 GMT
- Title: Entrywise convergence of iterative methods for eigenproblems
- Abstract summary: 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.
- Score: 31.69089186688224
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Several problems in machine learning, statistics, and other fields rely on
computing eigenvectors. For large scale problems, the computation of these
eigenvectors is typically performed via iterative schemes such as subspace
iteration or Krylov methods. While there is classical and comprehensive
analysis for subspace convergence guarantees with respect to the spectral norm,
in many modern applications other notions of subspace distance are more
appropriate. Recent theoretical work has focused on perturbations of subspaces
measured in the $\ell_{2 \to \infty}$ norm, but does not consider the actual
computation of eigenvectors. Here we address the convergence of subspace
iteration when distances are measured in the $\ell_{2 \to \infty}$ norm and
provide deterministic bounds. We complement our analysis with a practical
stopping criterion and demonstrate its applicability via numerical experiments.
Our results show that one can get comparable performance on downstream tasks
while requiring fewer iterations, thereby saving substantial computational
time.
Related papers
- Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
arXiv Detail & Related papers (2026-04-09T16:38:14Z) - Escaping the Krylov space during finite precision Lanczos [0.0]
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.
arXiv Detail & Related papers (2025-05-05T14:19:04Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
We convert high-dimensional $ell_infty$-approachability problems to low-dimensional pseudonorm approachability problems.
We develop an algorithmic theory of pseudonorm approachability, analogous to previous work on approachability for $ell$ and other norms.
arXiv Detail & Related papers (2023-02-03T03:19:14Z) - Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
We present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space.
We generalize the "XY"-mixer designed to preserve the subspace of "one-hot" states to the general case of subspaces given by a number of computational basis states.
Our analysis also leads to valid Trotterizations for "XY"-mixer with fewer CX gates than is known to date.
arXiv Detail & Related papers (2022-03-11T17:19:26Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process.
We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator.
We prove minimax lower bounds over sub-classes of MRPs.
arXiv Detail & Related papers (2021-09-24T14:48:20Z) - Weighting vectors for machine learning: numerical harmonic analysis
applied to boundary detection [3.8848561367220276]
We show that when the metric space is Euclidean, the weighting vector serves as an effective tool for boundary detection.
We demonstrate performance that is competitive or exceeds performance of state-of-the-art techniques on benchmark data sets.
arXiv Detail & Related papers (2021-06-01T22:14:22Z) - 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) - Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space.
We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation.
arXiv Detail & Related papers (2020-12-09T20:19:32Z) - Distributed Estimation for Principal Component Analysis: an Enlarged
Eigenspace Analysis [45.829683377074524]
This paper studies distributed estimation for a fundamental statistical machine learning problem, principal component analysis (PCA)
We propose a novel multi-round algorithm for constructing top-$L$-dim eigenspace for distributed data.
Our algorithm takes advantage of shift-and-invert preconditioning and convex optimization.
arXiv Detail & Related papers (2020-04-05T22:28:08Z) - Linear-time inference for Gaussian Processes on one dimension [17.77516394591124]
We investigate data sampled on one dimension for which state-space models are popular due to their linearly-scaling computational costs.
We provide the first general proof of conjecture that state-space models are general, able to approximate any one-dimensional Gaussian Processes.
We develop parallelized algorithms for performing inference and learning in the LEG model, test the algorithm on real and synthetic data, and demonstrate scaling to datasets with billions of samples.
arXiv Detail & Related papers (2020-03-11T23:20:13Z) - 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)
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.