# Matrix-Free Two-to-Infinity and One-to-Two Norms Estimation

arXiv: https://arxiv.org/abs/2508.04444 · HTML: https://mlsanity.com/paper/2508.04444/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 44 references that are in the map.
- First posted on arXiv 6 Aug 2025.

## Builds on (most cited first, 18 of 18)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Wide Residual Networks](https://mlsanity.com/paper/1605.07146/) (2016)
- [Automatic differentiation in machine learning: a survey](https://mlsanity.com/paper/1502.05767/) (2015)
- [Robust Learning with Jacobian Regularization](https://mlsanity.com/paper/1908.02729/) (2019)
- [UltraGCN: Ultra Simplification of Graph Convolutional Networks for Recommendation](https://mlsanity.com/paper/2110.15114/) (2021)
- [Hutch++: Optimal Stochastic Trace Estimation](https://mlsanity.com/paper/2010.09649/) (2020)
- [Adversarial Personalized Ranking for Recommendation](https://mlsanity.com/paper/1808.03908/) (2018)
- [Optimal Sketching for Trace Estimation](https://mlsanity.com/paper/2111.00664/) (2021)
- [Projection-Cost-Preserving Sketches: Proof Strategies and Constructions](https://mlsanity.com/paper/2004.08434/) (2020)
- [Dynamic Trace Estimation](https://mlsanity.com/paper/2110.13752/) (2021)
- [Stochastic diagonal estimation: probabilistic bounds and an improved algorithm](https://mlsanity.com/paper/2201.10684/) (2022)
- [Optimal Query Complexities for Dynamic Trace Estimation](https://mlsanity.com/paper/2209.15219/) (2022)
- [Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery](https://mlsanity.com/paper/2402.15739/) (2024)
- [A Tight Analysis of Hutchinson's Diagonal Estimator](https://mlsanity.com/paper/2208.03268/) (2022)
- [Davis-Kahan Theorem in the two-to-infinity norm and its application to perfect clustering](https://mlsanity.com/paper/2411.11728/) (2024)
- [Stochastic diagonal estimation with adaptive parameter selection](https://mlsanity.com/paper/2410.11613/) (2024)
- [On the Upper Bounds for the Matrix Spectral Norm](https://mlsanity.com/paper/2506.15660/) (2025)

## Built on by (most cited first, 1 of 1)

- [Bradley-Terry Rankings for Recommender Systems Across Dataset Taxonomies](https://mlsanity.com/paper/2606.07492/) (2026)

## Abstract (arXiv)

In this paper, we propose new randomized algorithms for estimating the two-to-infinity and one-to-two norms in a matrix-free setting, using only matrix-vector multiplications. Our methods are based on appropriate modifications of Hutchinson's diagonal estimator and its Hutch++ version. We provide oracle complexity bounds for both modifications. We further illustrate the practical utility of our algorithms for Jacobian-based regularization in deep neural network training on image classification tasks. We also demonstrate that our methodology can be applied to mitigate the effect of adversarial attacks in the domain of recommender systems.