Conditioning of leverage scores and computation by QR decomposition

DOI10.1137/140988541zbMATH Open1321.65070arXiv1402.0957OpenAlexW2887082150WikidataQ57439437 ScholiaQ57439437MaRDI QIDQ5502147FDOQ5502147

Authors: John T. Holodnak, Ilse C. F. Ipsen, Thomas Wentworth 

Publication date: 17 August 2015

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1402.0957

Recommendations

• Estimating Leverage Scores via Rank Revealing Methods and Randomization
• Componentwise perturbation analyses for the QR factorization
• Multiplicative perturbation analysis for QR factorizations
• On the perturbation of the Q-factor of the QR factorization.
• Perturbation Analyses for the QR Factorization

zbMATH Keywords

condition numbernumerical experimentQR decompositionstable rankprincipal anglescomponentwise perturbationsrow-scaling

Mathematics Subject Classification ID

Numerical computation of matrix norms, conditioning, scaling (65F35) Conditioning of matrices (15A12)

Cites Work

• Title not available (Why is that?)
• The Hat Matrix in Regression and ANOVA
• Title not available (Why is that?)
• Exact matrix completion via convex optimization
• Sampling algorithms for \(l_2\) regression and applications
• Relative-Error $CUR$ Matrix Decompositions
• Perturbation bounds in connection with singular value decomposition
• Randomized Algorithms for Matrices and Data
• Efficient Computing of Regression Diagnostics
• Accuracy and Stability of Numerical Algorithms
• Computing the Polar Decomposition—with Applications
• The effect of coherence on sampling from matrices with orthonormal columns, and preconditioned least squares problems
• On the Perturbation of LU, Cholesky, and QR Factorizations
• Perturbation Analyses for the QR Factorization
• On Smooth Decompositions of Matrices
• On perturbation bounds for the QR factorization
• Perturbation bounds for the Cholesky and QR factorizations
• Componentwise perturbation bounds for some matrix decompositions
• Rigorous Perturbation Bounds of Some Matrix Factorizations
• Perturbation Bounds for the $QR$ Factorization of a Matrix
• Fast approximation of matrix coherence and statistical leverage
• An improved approximation algorithm for the column subset selection problem
• A Componentwise Perturbation Analysis of the $QR$ Decomposition
• Componentwise perturbation analyses for the QR factorization
• Variation of the Unitary Part of a Matrix
• On the perturbation of the Q-factor of the QR factorization.
• Title not available (Why is that?)
• Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods

Cited In (5)

• Estimating Leverage Scores via Rank Revealing Methods and Randomization
• HOID: higher order interpolatory decomposition for tensors based on Tucker representation
• Randomized subspace iteration: analysis of canonical angles and unitarily invariant norms
• A stochastic perturbation analysis of the QR decomposition and its applications
• Max-Plus Algebraic Statistical Leverage Scores

Uses Software

• mctoolbox
• kappa_SQ

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)