On the Upper Bounds for the Matrix Spectral Norm
This addresses a computational bottleneck in linear algebra for applications like deep learning and inverse problems, though it appears incremental as it builds on existing norm estimation approaches.
The paper tackles the problem of estimating matrix spectral norms using only matrix-vector products, proposing a Counterbalance estimator that provides tighter upper bounds than standard methods like the power method, with results showing significant improvements in synthetic and real-world settings.
We consider the problem of estimating the spectral norm of a matrix using only matrix-vector products. We propose a new Counterbalance estimator that provides upper bounds on the norm and derive probabilistic guarantees on its underestimation. Compared to standard approaches such as the power method, the proposed estimator produces significantly tighter upper bounds in both synthetic and real-world settings. Our method is especially effective for matrices with fast-decaying spectra, such as those arising in deep learning and inverse problems.