Options
Verified inclusions for a nearest matrix of specified rank deficiency via a generalization of Wedin’s sin (θ) theorem
Publikationstyp
Journal Article
Date Issued
2021-03
Sprache
English
Author(s)
Institut
TORE-URI
Journal
Volume
61
Issue
1
Start Page
361
End Page
380
Citation
BIT Numerical Mathematics 61 (1): 361-380 (2021-03)
Publisher DOI
Scopus ID
Publisher
Springer Science + Business Media B.V
For an m× n matrix A, the mathematical property that the rank of A is equal to r for 0 < r< min (m, n) is an ill-posed problem. In this note we show that, regardless of this circumstance, it is possible to solve the strongly related problem of computing a nearby matrix with at least rank deficiency k in a mathematically rigorous way and using only floating-point arithmetic. Given an integer k and a real or complex matrix A, square or rectangular, we first present a verification algorithm to compute a narrow interval matrix Δ with the property that there exists a matrix within A- Δ with at least rank deficiency k. Subsequently, we extend this algorithm for computing an inclusion for a specific perturbation E with that property but also a minimal distance with respect to any unitarily invariant norm. For this purpose, we generalize Wedin’s sin (θ) theorem by removing its orthogonality assumption. The corresponding result is the singular vector space counterpart to Davis and Kahan’s generalized sin (θ) theorem for eigenspaces. The presented verification methods use only standard floating-point operations and are completely rigorous including all possible rounding errors and/or data dependencies.
Subjects
Distance to rank deficiency
Ill-posedness
INTLAB
Separation of singular vector subspaces
sin (Θ) theorem
Unitarily invariant norms
Verified error bounds
DDC Class
004: Informatik
510: Mathematik
More Funding Information
This research was partially supported by CREST, Japan Science and Technology Agency (JST), and by Université Paris Sorbonne.