×

Verified inclusions for a nearest matrix of specified rank deficiency via a generalization of Wedin’s \(\sin (\theta)\) theorem. (English) Zbl 1470.65088

Summary: For an \(m \times 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 \(\varDelta\) with the property that there exists a matrix within \(A-\varDelta\) 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 (\theta)\) theorem by removing its orthogonality assumption. The corresponding result is the singular vector space counterpart to Davis and Kahan’s generalized \(\sin (\theta)\) 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.

MSC:

65F99 Numerical linear algebra
15A03 Vector spaces, linear dependence, rank, lineability
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bailey, DH, A Fortran 90-based multiprecision system, ACM Trans. Math. Softw., 21, 4, 379-387 (1995) · Zbl 0883.68017 · doi:10.1145/212066.212075
[2] Davis, C.; Kahan, WM, The rotation of eigenvectors by a perturbation. III, SIAM J. Numer. Anal., 7, 1, 1-46 (1970) · Zbl 0198.47201 · doi:10.1137/0707001
[3] Demmel, J., Ahrens, P., Nguyen, H.D.: Efficient reproducible floating point summation and blas. Technical Report UCB/EECS-2016-121, EECS Department, University of California, Berkeley (2016) · Zbl 1484.65100
[4] Fousse, L.; Hanrot, G.; Lefèvre, V.; Pelissier, P.; Zimmermann, P., MPFR: a multiple-precision binary floating-point library with correct rounding, ACM Trans. Math. Softw., 33, 2, 2007 (2007) · Zbl 1365.65302 · doi:10.1145/1236463.1236468
[5] Golub, GH; Van Loan, CF, Matrix Computations (2013), Baltimore: The Johns Hopkins University Press, Baltimore · Zbl 1268.65037
[6] Hadamard, J., Sur les problèmes aux dérivées partielles et leur signification physique, Princeton Univ. Bull., 13, 49-52 (1902)
[7] Higham, NJ, Accuracy and Stability of Numerical Algorithms, Volume 80 of Other Titles in Applied Mathematics (2002), Philadelphia: Society for Industrial & Applied Mathematics (SIAM), Philadelphia · Zbl 1011.65010 · doi:10.1137/1.9780898718027
[8] Higham, NJ; Mary, T., A new approach to probabilistic rounding error analysis, SIAM J. Sci. Comput., 41, 5, A2815-A2835 (2019) · Zbl 07123205 · doi:10.1137/18M1226312
[9] Hochstenbach, ME, A Jacobi-Davidson type SVD method, SIAM J. Sci. Comput., 23, 2, 606-628 (2001) · Zbl 1002.65048 · doi:10.1137/S1064827500372973
[10] Horn, RA; Johnson, CR, Matrix Analysis (1991), New York: Cambridge University Press, New York · Zbl 0729.15001 · doi:10.1017/CBO9780511840371
[11] IEEE. IEEE standard for binary floating-point arithmetic. ANSI/IEEE Std 754-1985, pp. 1-20 (1985)
[12] IEEE. IEEE standard for floating-point arithmetic. IEEE Std 754-2019 (Revision of IEEE 754-2008), pp. 1-84 (2019)
[13] Jézéquel, F.; Chesneaux, J-M, CADNA: a library for estimating round-off error propagation, Comput. Phys. Commun., 178, 12, 933-955 (2008) · Zbl 1196.65020 · doi:10.1016/j.cpc.2008.02.003
[14] Johansson, F., Arb: A C library for ball arithmetic, ACM Commun. Comput. Algebra, 47, 3-4, 166-169 (2014) · doi:10.1145/2576802.2576828
[15] Kahan, WM; Freiman, CV; Griffith, JE; Rosenfeld, JL, A survey of error analysis, 7th IFIP Congress, Ljubljana, Amsterdam, Netherlands (1971), Amsterdam: North-Holland, Amsterdam
[16] Kanzawa, Y.; Oishi, S., Calculating bifurcation points with guaranteed accuracy, IEICE Trans. Fundam., E82-A, 6, 1055-1061 (1999)
[17] Kanzawa, Y.; Oishi, S., Imperfect singular solutions of nonlinear equations and a numerical method of proving their existence, IEICE Trans. Fundam, E82-A, 6, 1062-1069 (1999)
[18] Kearfott, RB; Nakao, MT; Neumaier, A.; Rump, SM; Shary, SP; Van Hentenryck, P., Standardized notation in interval analysis, Comput. Technol., 15, 1, 7-13 (2010) · Zbl 1196.65088
[19] Lange, M., Residual bounds for some or all singular values, Linear Algebra Appl., 464, 28-37 (2015) · Zbl 1302.15022 · doi:10.1016/j.laa.2013.06.023
[20] Li, N.; Zhi, L., Verified error bounds for isolated singular solutions of polynomial systems, SIAM J. Numer. Anal., 52, 4, 1623-1640 (2014) · Zbl 1310.65056 · doi:10.1137/120902914
[21] Mirsky, L., Symmetric gauge functions and unitarily invariant norms, Q. J. Math., 11, 1, 50-59 (1960) · Zbl 0105.01101 · doi:10.1093/qmath/11.1.50
[22] Miyajima, S.; Ogita, T.; Oishi, S.; Ganzha, VG; Mayr, EW; Vorozhtsov, EV, Fast verification for respective eigenvalues of symmetric matrix, Computer Algebra in Scientific Computing, 306-317 (2005), Berlin: Springer Berlin Heidelberg, Berlin · Zbl 1169.65312 · doi:10.1007/11555964_26
[23] Mukunoki, D.; Ogita, T.; Ozaki, K.; Wyrzykowski, R.; Deelman, E.; Dongarra, J.; Karczewski, K., Reproducible BLAS routines with tunable accuracy using Ozaki scheme for many-core architectures, Parallel Processing and Applied Mathematics, 516-527 (2020), Cham: Springer Nature, Cham · doi:10.1007/978-3-030-43229-4_44
[24] Nakatsukasa, Y., Accuracy of singular vectors obtained by projection-based svd methods, BIT Numer. Math., 57, 4, 1137-1152 (2017) · Zbl 1386.65116 · doi:10.1007/s10543-017-0665-x
[25] Neumaier, A., Rundungsfehleranalyse einiger Verfahren zur Summation endlicher Summen, Z. Angew. Math. Mech., 54, 1, 39-51 (1974) · Zbl 0273.65032 · doi:10.1002/zamm.19740540106
[26] Neumaier, A., Interval Methods for Systems of Equations. Encyclopedia of Mathematics and its Applications (1991), Cambridge: Cambridge University Press, Cambridge · Zbl 1152.65054 · doi:10.1017/CBO9780511526473
[27] Ogita, T.; Rump, SM; Oishi, S., Accurate sum and dot product, SIAM J. Sci. Comput., 26, 6, 1955-1988 (2005) · Zbl 1084.65041 · doi:10.1137/030601818
[28] Oishi, S.; Ichihara, K.; Kashiwagi, M.; Kimura, T.; Liu, X.; Masai, H.; Morikura, Y.; Ogita, T.; Ozaki, K.; Rump, SM; Sekine, K.; Takayasu, A.; Yamanaka, N., Principle of Verified Numerical Computations (2018), Tokyo: Corona, Tokyo
[29] Parlett, B.N.: The Symmetric Eigenvalue Problem, volume 20 of Classics in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, USA, unabridged, corr. republication of the work 1st publ. by Prentice-Hall edition (1998) · Zbl 0885.65039
[30] Poljak, S.; Rohn, J., Checking robust nonsingularity is NP-Hard, Math. Control Signals Syst., 6, 1-9 (1993) · Zbl 0780.93027 · doi:10.1007/BF01213466
[31] Rump, SM; Csendes, T., INTLAB-INTerval LABoratory, Developments in Reliable Computing, 77-104 (1999), Dordrecht: Springer Netherlands, Dordrecht · Zbl 0949.65046 · doi:10.1007/978-94-017-1247-7_7
[32] Rump, SM, Verification methods: rigorous results using floating-point arithmetic, Acta Numer., 19, 287-449 (2010) · Zbl 1323.65046 · doi:10.1017/S096249291000005X
[33] Rump, SM, Verified bounds for singular values, in particular for the spectral norm of a matrix and its inverse, BIT Numer. Math., 51, 2, 367-384 (2011) · Zbl 1226.65028 · doi:10.1007/s10543-010-0294-0
[34] Rump, SM, Gleitkommaarithmetik auf dem Prüfstand, Jahresber. Dtsch. Math. Ver., 118, 3, 179-226 (2016) · Zbl 1372.65140 · doi:10.1365/s13291-016-0138-1
[35] Rump, SM; Graillat, S., Verified error bounds for multiple roots of systems of nonlinear equations, Numer. Algorithms, 54, 3, 359-377 (2010) · Zbl 1201.65081 · doi:10.1007/s11075-009-9339-3
[36] Rump, SM; Ogita, T.; Oishi, S., Accurate floating-point summation part I: Faithful rounding, SIAM J. Sci. Comput., 31, 1, 189-224 (2008) · Zbl 1185.65082 · doi:10.1137/050645671
[37] Schmidt, E., Zur theorie der linearen und nichtlinearen integralgleichungen, Math. Ann., 63, 4, 433-476 (1907) · JFM 38.0377.02 · doi:10.1007/BF01449770
[38] Shewchuk, JR, Adaptive precision floating-point arithmetic and fast robust geometric predicates, Discrete Comput. Geom., 18, 3, 305-363 (1997) · Zbl 0892.68098 · doi:10.1007/PL00009321
[39] Stewart, G.W.: Perturbation theory for the singular value decomposition. Technical report, University of Maryland at College Park, USA (1990)
[40] Vignes, J., A stochastic arithmetic for reliable scientific computation, MATHCS, 35, 3, 233-261 (1993)
[41] von Neumann, J., Some matrix-inequalities and metrization of matrix-space, Tomsk Univ. Rev., 1, 286-300 (1937) · Zbl 0017.09802
[42] Weber, H.; Werner, W., On the accurate determination of nonisolated solutions of nonlinear equations, Computing, 26, 4, 315-326 (1981) · Zbl 0451.65036 · doi:10.1007/BF02237950
[43] Wedin, PÅ, Perturbation bounds in connection with singular value decomposition, BIT Numer. Math., 12, 1, 99-111 (1972) · Zbl 0239.15015 · doi:10.1007/BF01932678
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.