A Note On Estimating the Spectral Norm of A Matrix Efficiently

2011/04/11 by Magdon-Ismail, Malik
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1104.2076

Abstract

We give an efficient algorithm which can obtain a relative error approximation to the spectral norm of a matrix, combining the power iteration method with some techniques from matrix reconstruction which use random sampling.

Related

• Fast Spectral Low Rank Matrix Approximation
• On the Upper Bounds for the Matrix Spectral Norm
• Using a Non-Commutative Bernstein Bound to Approximate Some Matrix Algorithms in the Spectral Norm
• Near-Optimal Column-Based Matrix Reconstruction
• The spectral norm error of the naive Nystrom extension