Probabilistic upper bounds for the matrix two-norm

Research output: Contribution to journalArticleAcademicpeer-review

16 Citations (Scopus)

Abstract

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
Volume57
Issue number3
DOIs
Publication statusPublished - 2013

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

Cite this