Conditioning of leverage scores and computation by QR decomposition
From MaRDI portal
Abstract: The leverage scores of a full-column rank matrix A are the squared row norms of any orthonormal basis for range(A). We show that corresponding leverage scores of two matrices A and A + Delta A are close in the relative sense, if they have large magnitude and if all principal angles between the column spaces of A and A + Delta A are small. We also show three classes of bounds that are based on perturbation results of QR decompositions. They demonstrate that relative differences between individual leverage scores strongly depend on the particular type of perturbation Delta A. The bounds imply that the relative accuracy of an individual leverage score depends on: its magnitude and the two-norm condition of A, if Delta A is a general perturbation; the two-norm condition number of A, if Delta A is a perturbation with the same norm-wise row-scaling as A; (to first order) neither condition number nor leverage score magnitude, if Delta A is a component-wise row-scaled perturbation. Numerical experiments confirm the qualitative and quantitative accuracy of our bounds.
Recommendations
Cites work
- A Componentwise Perturbation Analysis of the QR Decomposition
- Accuracy and Stability of Numerical Algorithms
- An improved approximation algorithm for the column subset selection problem
- Componentwise perturbation analyses for the QR factorization
- Componentwise perturbation bounds for some matrix decompositions
- Computing the Polar Decomposition—with Applications
- Efficient Computing of Regression Diagnostics
- Exact matrix completion via convex optimization
- Fast approximation of matrix coherence and statistical leverage
- scientific article; zbMATH DE number 47363 (Why is no real title available?)
- scientific article; zbMATH DE number 3799843 (Why is no real title available?)
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- On perturbation bounds for the QR factorization
- On Smooth Decompositions of Matrices
- On the Perturbation of LU, Cholesky, and QR Factorizations
- On the perturbation of the Q-factor of the QR factorization.
- Perturbation Analyses for the QR Factorization
- Perturbation Bounds for the $QR$ Factorization of a Matrix
- Perturbation bounds for the Cholesky and QR factorizations
- Perturbation bounds in connection with singular value decomposition
- Randomized Algorithms for Matrices and Data
- Relative-Error CUR Matrix Decompositions
- Rigorous Perturbation Bounds of Some Matrix Factorizations
- Sampling algorithms for l₂ regression and applications
- Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods
- The effect of coherence on sampling from matrices with orthonormal columns, and preconditioned least squares problems
- The Hat Matrix in Regression and ANOVA
- Variation of the Unitary Part of a Matrix
Cited in
(5)- HOID: higher order interpolatory decomposition for tensors based on Tucker representation
- Max-Plus Algebraic Statistical Leverage Scores
- Randomized subspace iteration: analysis of canonical angles and unitarily invariant norms
- Estimating Leverage Scores via Rank Revealing Methods and Randomization
- A stochastic perturbation analysis of the QR decomposition and its applications
This page was built for publication: Conditioning of leverage scores and computation by QR decomposition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5502147)
