Probabilistic upper bounds for the matrix two-norm

Research output: Contribution to journalArticleAcademicpeer-review

19 Citations (Scopus)


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. Keywords: Matrix two-norm · Probabilistic bound · SVD · Singular value problem · Singular value decomposition · Subspace method · Lanczos bidiagonalization · Lanczos polynomial · Ritz polynomial · Condition number· Large (sparse) matrix
Original languageEnglish
Pages (from-to)464-476
JournalJournal of Scientific Computing
Issue number3
Publication statusPublished - 2013


Dive into the research topics of 'Probabilistic upper bounds for the matrix two-norm'. Together they form a unique fingerprint.

Cite this