A Note On Estimating the Spectral Norm of A Matrix Efficiently
  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. 
Malik Magdon-Ismail
cs.DS