×

Probabilistic upper bounds for the matrix two-norm. (English) Zbl 1292.65037

Summary: We develop probabilistic upper bounds for the matrix two-norm, the largest singular value. These bounds, which are true upper bounds with a user-chosen high probability, are derived with a number of different polynomials that implicitly arise in the Lanczos bidiagonalization process. Since these polynomials are adaptively generated, the bounds typically give very good results. They can be computed efficiently. Together with an approximation that is a guaranteed lower bound, this may result in a small probabilistic interval for the matrix norm of large matrices within a fraction of a second.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15A42 Inequalities involving eigenvalues and eigenvectors
65F35 Numerical computation of matrix norms, conditioning, scaling
65F50 Computational methods for sparse matrices

Software:

MatrixMarket; na26
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Baglama, J., Reichel, L.: Augmented implicitly restarted Lanczos bidiagonalization methods. SIAM J. Sci. Comput. 27, 19-42 (2005) · Zbl 1087.65039
[2] Baglama, J., Reichel, L.: Restarted block Lanczos bidiagonalization methods. Numer. Algorithms 43, 251-272 (2007) · Zbl 1110.65027
[3] Bischof, C.H.: Incremental condition estimation. SIAM J. Matrix Anal. Appl. 11, 312-322 (1990) · Zbl 0697.65042
[4] Bischof, C.H., Lewis, J.G., Pierce, D.J.: Incremental condition estimation for sparse matrices. SIAM J. Matrix Anal. Appl. 11, 644-659 (1990) · Zbl 0726.65038
[5] Golub, G.H., Kahan, W.: Calculating the singular values and pseudo-inverse of a matrix. J. Soc. Indust Appl. Math. Ser. B Numer. Anal. 2, 205-224 (1965) · Zbl 0194.18201
[6] Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. The John Hopkins University Press, Baltimore (1996) · Zbl 0865.65009
[7] Hochstenbach, M.E.: A Jacobi-Davidson type SVD method. SIAM J. Sci. Comput. 23, 606-628 (2001) · Zbl 1002.65048
[8] Horn, R.A., Johnson, C.R.: Topics in Matrix Analysis. Cambridge University Press, Cambridge (1991) · Zbl 0729.15001
[9] Kuczyński, J., Woźniakowski, H.: Estimating the largest eigenvalue by the power and Lanczos algorithms with a random start. SIAM J. Matrix Anal. Appl. 13, 1094-1122 (1992) · Zbl 0759.65016
[10] Parlett, B.N.: The Symmetric Eigenvalue Problem. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1998) · Zbl 0885.65039
[11] Stoll, M.: A Krylov-Schur approach to the truncated SVD. Linear Algebra Appl. 436, 2795-2806 (2012) · Zbl 1241.65040
[12] The Matrix Market. http://math.nist.gov/MatrixMarket, a repository for test matrices
[13] Van Dorsselaer, J.L.M., Hochstenbach, M.E., Van der Vorst, H.A.: Computing probabilistic bounds for extreme eigenvalues of symmetric matrices with the Lanczos method. SIAM J. Matrix Anal. Appl. 22, 837-852 (2000) · Zbl 0981.65044
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.