Abstract

We consider the problem of estimating the spectral norm of a matrix usingonly matrix-vector products. We propose a new Counterbalance estimator thatprovides upper bounds on the norm and derive probabilistic guarantees on itsunderestimation. Compared to standard approaches such as the power method, theproposed estimator produces significantly tighter upper bounds in bothsynthetic and real-world settings. Our method is especially effective formatrices with fast-decaying spectra, such as those arising in deep learning andinverse problems.

 

Quick Read (beta)