The Rotation of Eigenvectors by a Perturbation. III
1970/03/01 by Chandler Davis, W. Kahan, W. M. Kahan · 140 citations
Computer Science · Mathematics · #Matrix Theory and Algorithms #Spectral Theory in Mathematical Physics #Algebraic and Geometric Analysis
paper · doi:10.1137/0707001
Abstract
When a Hermitian linear operator is slightly perturbed, by how much can its invariant subspaces change? Given some approximations to a cluster of neighboring eigenvalues and to the corresponding eigenvectors of a real symmetric matrix, and given an estimate for the gap that separates the cluster from all other eigenvalues, how much can the subspace spanned by the eigenvectors differ from the subspace spanned by our approximations? These questions are closely related; both are investigated here. The difference between the two subspaces is characterized in terms of certain angles through which one subspace must be rotated in order most directly to reach the other. These angles unify the treatment of natural geometric, operator-theoretic and error-analytic questions concerning those subspaces. Sharp bounds upon trigonometric functions of these angles are obtained from the gap and from bounds upon either the perturbation (1st question) or a computable residual (2nd question). An example is included.
Cited by
- Semiparametric estimation of fractional cointegrating subspaces
- Operator norm consistent estimation of large-dimensional sparse covariance matrices
- An ℓp theory of PCA and spectral clustering
- Large covariance estimation through elliptical factor models
- A Structure-Adaptive Random Feature Method for High-Dimensional Elliptic PDEs
- Stability of Low-Rank Implicit Regularization in Perturbed Deep Matrix Factorization
- Single Link Removal Perturbation in Szegedy Quantum Walk: from Graph Completeness Testing to Integrity Monitoring
- No Subspace to Track: Non-Identifiability and Optimizer State in Low-Rank Training
- Quantum circuit design via dynamic Pauli constraints
- Claim-Specific Admissibility of PCA Biplot Interpretations: Target Alignment, Spectral Identifiability, and Projection Adequacy
- Scale-Aware Learning of Chaotic Dynamics on Unstructured Meshes via Binned Spectral Losses
- Mildly-Interacting Fermionic Unitaries are Efficiently Learnable
- Iterative Least Trimmed Squares for Mixed Linear Regression
- Optimal Estimation and Rank Detection for Sparse Spiked Covariance Matrices
- A Schatten-q Low-rank Matrix Perturbation Analysis via Perturbation Projection Error Bound
- On the Minimax Misclassification Ratio of Hypergraph Community Detection
- Large Covariance Estimation by Thresholding Principal Orthogonal\n Complements
- Fast Global Convergence for Low-rank Matrix Recovery via Riemannian Gradient Descent with Random Initialization
- On weakly formulated Sylvester equations and applications
- On the ℓ^∞-norms of the Singular Vectors of Arbitrary Powers of a Difference Matrix with Applications to Sigma-Delta Quantization
- Reconstruction in the Labeled Stochastic Block Model
- Unified ℓ2→∞ Eigenspace Perturbation Theory for Symmetric Random Matrices
- An ℓ∞ Eigenvector Perturbation Bound and Its Application to Robust Covariance Estimation
- Perturbation Analysis of An Eigenvector-Dependent Nonlinear Eigenvalue Problem With Applications?
- Individual-centered partial information in social networks
- Predictive Subsampling for Scalable Inference in Networks
- Fast and Robust: Computationally Efficient Covariance Estimation for Sub-Weibull Vectors
- Beyond Low Rank: Fast Low-Rank + Diagonal Decomposition with a Spectral Approach
- Sparse Principal Component Analysis with Energy Profile Dependent Sample Complexity
- Determinant-Based Error Bounds for CUR Matrix Approximation: Oversampling and Volume Sampling
- Universal entrywise eigenvector fluctuations in delocalized spiked matrix models and asymptotics of rounded spectral algorithms
- KQ-SVD: Compressing the KV Cache with Provable Guarantees on Attention Fidelity
- Composite optimization for robust blind deconvolution
- Input-Output Data-Driven Representation: Non-Minimality and Stability
- An Improved and Generalised Analysis for Spectral Clustering
- Sketched SVD: Recovering Spectral Features from Compressive Measurements
- Covariate Assisted Variable Ranking
- Sparsifying the Fisher Linear Discriminant by Rotation
- Euclidean Representation of Low-Rank Matrices and Its Statistical Applications
- How can classical multidimensional scaling go wrong?
- A Sharp Blockwise Tensor Perturbation Bound for Orthogonal Iteration
- Spectral radii of sparse random matrices
- Random perturbation of low rank matrices: Improving classical bounds
- Causal Inference with Corrupted Data: Measurement Error, Missing Values, Discretization, and Differential Privacy
- Adiabatic state preparation from general initial states
- Perturbation Bounds for Low-Rank Inverse Approximations under Noise
- Principal component analysis for high-dimensional compositional data
- Provable Low Rank Phase Retrieval
- Power spectrum signatures of graphs
- Influential Feature PCA for high dimensional clustering
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
- MRRR-based Eigensolvers for Multi-core Processors and Supercomputers
- Haplotype Assembly: An Information Theoretic View
- On Temple--Kato like inequalities and applications
- Partitioning Well-Clustered Graphs: Spectral Clustering Works!
- Finite-sample certification and operating envelopes for spectral clustering and graph centrality
- TenIPS: Inverse Propensity Sampling for Tensor Completion
- A Correctness Result for Online Robust PCA
- Enhancing Graph Classification Robustness with Singular Pooling
- Semi-supervised Vertex Hunting, with Applications in Network and Text Analysis
- Davis-Kahan Theorem under a moderate gap condition
- A Geometric Analysis of PCA
- A Sample Complexity Separation between Non-Convex and Convex\n Meta-Learning
- Strong Consistency, Graph Laplacians, and the Stochastic Block Model
- Optimal paths for symmetric actions in the unitary group
- EvoEdit: Evolving Null-space Alignment for Robust and Efficient Knowledge Editing
- On Robustness of Principal Component Regression
- Robust PCA by Manifold Optimization
- Quantum Algorithm for Low Energy Effective Hamiltonian and Quasi-Degenerate Eigenvalue Problem
- Spectral Thresholds for Identifiability and Stability:Finite-Sample Phase Transitions in High-Dimensional Learning
- On Spectral Learning for Odeco Tensors: Perturbation, Initialization, and Algorithms
- Real-Aware Residual Model Merging for Deepfake Detection
- Train Once, Reuse Everywhere: Generalizable Implicit In-Context Learning by Routing Attention
- Convexity-Driven Projection for Point Cloud Dimensionality Reduction
- A Riemannian Factor Model for Manifold-Valued Time Series
- HOMER: Huber-of-Means for Efficient and Robust Estimation in Hilbert Spaces
- Attractor Domain Theory: A Mathematical Framework for Cardiovascular Attractor Analysis with Wearable Photoplethysmography (PPG) Validation
- How Much Data is Enough? The Zeta Law of Discoverability in Biomedical Data, featuring the enigmatic Riemann zeta function
- Impact of Connectivity on Laplacian Representations in Reinforcement Learning
- Generalized Orthogonal Procrustes Problem under Arbitrary Adversaries
- Community Recovery in Graphs with Locality
- The Rotation of Eigenspaces of Perturbed Matrix Pairs
- Robust high dimensional factor models with applications to statistical machine learning
- Item Response Theory -- A Statistical Framework for Educational and Psychological Measurement
- PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements\n via Convex Programming
- Large-Scale Curve Time Series with Common Stochastic Trends
- Combined perturbation bounds for eigenstructure of Hermitian matrices and singular structure of general matrices
- Double Cross Validation for the Number of Factors in Approximate Factor Models
- State Aggregation Learning from Markov Transition Data
- Enhancing Optical Imaging via Quantum Computation
- Sequential Spectral Clustering of Data Sequences
- Unitary network: Tensor network unitaries with local unitarity
- Inference on covariance structure in high-dimensional multi-view data
- Adaptive Reduced Rank Regression
- Eigenvector Under Random Perturbation: A Nonasymptotic Rayleigh-Schrödinger Theory
- Achieving Optimal Misclassification Proportion in Stochastic Block Model
- Sufficient Forecasting Using Factor Models
- Metis: Training LLMs with FP4 Quantization
- Relative convergence estimates for the spectral asymptotic in the Large Coupling Limit
- Recovering a Hidden Community Beyond the Kesten-Stigum Threshold in O(|E| log^*|V|) Time
- Multi-sample estimation of centered log-ratio matrix in microbiome studies
- On the condition number and perturbation of matrix functions for Hermitian matrices
- Beyond Turing: Memory-Amortized Inference as a Foundation for Cognitive Computation
- Outlier Robust Online Learning
- On r-to-p norms of random matrices with nonnegative entries: Asymptotic normality and ℓ_∞-bounds for the maximizer
- Large-Scale Multiple Testing for Matrix-Valued Data under Double Dependency
- Approximate Factor Model with S-vine Copula Structure
- Learning functions varying along a central subspace
- Clustering a Mixture of Gaussians with Unknown Covariance
- Two-sample Test of Community Memberships of Weighted Stochastic Block Models
- Multiscale Dictionary Learning: Non-Asymptotic Bounds and Robustness
- An exact \sin\Θ formula for matrix perturbation analysis and its\n applications
- Angles, triangle inequalities, correlation matrices and metric-preserving and subadditive functions
- Perturbation theory for the spectral decomposition of Hermitian matrices
- Decentralized Differentially Private Power Method
- Low-Rank Structured Nonparametric Prediction of Instantaneous Volatility
- A Theoretical Analysis of Fine-tuning with Linear Teachers
- An ℓp theory of PCA and spectral clustering
- PCA in Data-Dependent Noise (Correlated-PCA): Nearly Optimal Finite Sample Guarantees
- Max vs Min: Tensor Decomposition and ICA with nearly Linear Sample Complexity
- Leave-one-out Approach for Matrix Completion: Primal and Dual Analysis
- Unique continuation and lifting of spectral band edges of Schrödinger operators on unbounded domains (With an Appendix by Albrecht Seelmann)
- Fast Landmark Subspace Clustering
- Distributed Estimation for Principal Component Analysis: An Enlarged Eigenspace Analysis
- Distributed Estimation of Principal Eigenspaces
- Graph reduction with spectral and cut guarantees
- How to Quantify Polarization in Models of Opinion Dynamics
- Phase Transitions for High Dimensional Clustering and Related Problems
- On the Downstream Performance of Compressed Word Embeddings
- Asymptotics of Empirical Eigen-structure for Ultra-high Dimensional Spiked Covariance Model
- CHIP: A Hawkes Process Model for Continuous-time Networks with Scalable and Consistent Estimation
- Generalized Topic Modeling
- A central limit theorem for an omnibus embedding of multiple random graphs and implications for multiscale network inference
- Distributed Robust Learning
- Uniform bounds for invariant subspace perturbations
- On the Existence of Solutions to the Operator Riccati Equation and the tan ? Theorem
- Certifying Global Optimality of Graph Cuts via Semidefinite Relaxation: A Performance Guarantee for Spectral Clustering
- Bayesian Nonparametric Graph Clustering
- Orthogonal symmetric non-negative matrix factorization under the stochastic block model
- Data-Driven Matrix Recovery via Optimal Shrinkage and Spatially Resolved Singular Vector Denoising under High-Dimensional Separable Noise
Related