CS Paper Radar

Hutch#: Optimal non-adaptive Frobenius norm estimation

Tyler Chen, Diana Halikias, Christopher Musco, David Persson

cs.DS math.NA ·submitted 2026-09-23 17:59 UTC · v2
theory

Abstract

The Girard--Hutchinson estimator provides an extremely simple randomized estimate of the Frobenius norm of a matrix $A$ that can only be accessed implicitly via matrix-vector products. In particular, if $Ω$ is a random Gaussian matrix with $r = O(1/\varepsilon^2)$ columns, than $\frac{1}{r}\|AΩ\|_F^2$ provides a $(1\pm \varepsilon)$ multiplicative approximation to $\|A\|_F^2$ with high probability. In this work, we introduce a closely related estimator, given by \begin{align*} {\frac{1}{r}\|AΩ\|_F^2 + \frac{1}{r}\|Ψ^T A\|_F^2 - \frac{1}{r^2}\|Ψ^T AΩ\|_F^2}, \end{align*} where $Ψ$ is a second, independent random Gaussian matrix with $r$ columns. We prove that this estimator yields a $(1\pm\varepsilon)$ multiplicative approximation to $\|A\|_F^2$ when $r = O(1/\varepsilon)$, a quadratic improvement over Girard--Hutchinson. This dependence on $\varepsilon$ is optimal. Our method, which we call Hutch# (pronounced ``Hutch sharp''), matches the complexity of the Hutch++ algorithm [Meyer, Musco, Musco, Woodruff, 2021]. However, unlike Hutch++, Hutch# uses only \textit{non-adaptive} matrix-vector products with $A$ and $A^T$ and requires no orthogonalization or other advanced linear algebra steps. Thus, Hutch# combines the simplicity of the Girard--Hutchinson estimator and the optimal query complexity of Hutch++.

Closest papers

Nearest neighbours by meaning across the whole index.

Hadamard Flattening and Gaussian Pooling Sketch for Least Squares with Coordinate-wise Guarantee

cs.DS cs.LGstat.ML ·2026-08-27 ·Zhao Song, Lichen Zhang
similarity 0.63
Abstract · Improve presentation and add more discussions on prior work. Abstract shortened to meet arxiv requirement

Randomized sketch-and-solve algorithms accelerate overconstrained $\ell_2$ regression by replacing the input with a much smaller, randomly projected problem. While standard subspace embeddings nearly preserve the regression cost, coordinate-wise accuracy is more delicate: rather than the objective value, we want the solution vector itself to be close to the optimum in $\ell_\infty$ norm. Specifically, we seek $x'\in\mathbb{R}^d$ with $\|x'-x^\star\|_\infty\leq\fracε{\sqrt d}\|Ax^\star-b\|_2\|A^\dagger\|_{\mathrm{op}}$, where $A\in\mathbb{R}^{n\times d}$ is the design matrix, $b\in\mathbb{R}^n$ the label vector, $x^\star$ the optimal solution and $A^\dagger$ the pseudo-inverse of $A$. Price, Song and Woodruff introduced this problem and claimed that the subsampled randomized Hadamard transform (SRHT) with $O(ε^{-2}d^{1+Θ(\sqrt{\log\log n/\log d})})$ rows achieves this guarantee; we point out a gap in the proof. Song, Ye, Yin and Zhang later claimed $O(ε^{-2}d\log^3 n)$ rows, but their proof relies on an independence assumption that does not hold in general, and we exhibit an explicit instance on which it fails. To achieve a truly nearly-linear-in-$d$ row count, we introduce a new fast, dense randomized transform combining a randomized Hadamard flattening, a random permutation, and balanced, disjoint Gaussian pooling. Conditioned on the Hadamard-and-permutation stage, the sketched problem becomes an exact Gaussian regression whose noise is independent of the entire sketched design, exactly what Song, Ye, Yin and Zhang's argument was missing. Our sketch yields the $\ell_\infty$ guarantee with $m=O(ε^{-2}d\log d)$ rows, using one Hadamard pass with padded internal dimension $N=\widetilde{O}(n+ε^{-2}d^3)$. It is also efficient to apply: $(SA,Sb)$ can be computed in $O(Nd\log N)=\widetilde{O}(nd+ε^{-2}d^4)$ time.

0.19

Stable and Online Algorithms for Random Matrix Discrepancy

cs.DS cs.CCcs.DMmath.CO+1 ·2026-10-01 ·Eren C. Kızıldağ, Shuangping Li
theoryhighly cited similarity 0.62
Abstract

We study the average-case matrix discrepancy problem: given independent normalized $d\times d$ Gaussian orthogonal ensemble matrices $A_1,\dots,A_N$ and a fixed margin $κ>0$, find signs $σ_1,\dots,σ_N\in\{-1,1\}$ such that the operator norm of $\sum_{i=1}^N σ_i A_i$ is at most $κ\sqrt{N}$. Focusing on the proportional regime $N/d^2\to τ\in(0,\infty)$ as $d\to\infty$ followed by the small-margin limit $κ\downarrow 0$, we characterize the density required by stable offline algorithms and by online algorithms. In the offline setting, we construct a polynomial-time \emph{recenter-and-round} algorithm that is noise-stable and succeeds whenever $τ=Ω(\frac{1}{κ^2\log(1/κ)})$, along with a matching lower bound for all stable algorithms. In the online setting where each sign must be chosen irrevocably upon observing the corresponding matrix, we determine the exact limiting performance of the \emph{Frobenius-greedy} algorithm, establishing that it succeeds when $τ>τ_{\rm FG}(κ)\sim \fracπ{4κ^2}$, as well as a matching lower bound for all online algorithms by conditioning on a revealed prefix. At the core of our algorithms lies rotational symmetry, which enables us to transfer Frobenius norm control into operator norm guarantees. Together, our results identify the algorithmic phase transition points for random matrix discrepancy: $Θ(\frac{1}{κ^2\log(1/κ)})$ for stable offline algorithms and $Θ(\frac{1}{κ^2})$ for online algorithms. Both thresholds lie far above the satisfiability scale $Θ(\log(1/κ))$, as shown by Maillard~\cite{maillard2025}.

0.31

Accurate Trace Estimation with Fewer Random Bits via Recursive TensorSketch

cs.LG cs.DS ·2026-09-16 ·Mohammad Azhar Khan, Rameshwar Pratap, Amit Sharma
similarity 0.61
Abstract

We consider the problem of estimating the trace of an implicit matrix $\mathbf{A} \in \mathbb{R}^{d^p\times d^p}$ that can only be accessed through matrix-vector products queries. The \textit{Hutchinson trace estimator}% ~\cite{Girard1987algorithme, article-hutchinson} is a classical sketching method for this problem. Their estimator, $H_{m}(\mathbf{A}) = \frac{1}{m} \sum_{i=1}^{m} {\mathbf{z}^{(i)}}^T \mathbf{A} \mathbf{z}^{(i)}, \quad \text{where } \ {\mathbf{z}^{(i)}}\in \mathbb{R}^{d^p}$, and $z^{(i)}_j \in {N}(0, 1), j\in [d^p]$, satisfies the following guarantees: (i) $\mathbb{E}[H_{m}(\mathbf{A})]=\operatorname{tr}(\mathbf{A})$, and (ii) $\mathrm{Var}[H_{m}(\mathbf{A})]=\frac{2}{m}||\mathbf{A}||_F^2$. Generating one query vector $\mathbf{z}^{(i)}$ requires $O(d^p)$ random bits; thus, $m$ queries require $O(md^p)$ random bits, which can be prohibitive in large-scale applications. Recent work by Meyer et al.~\cite{meyer2025hutchinsonsestimatorbadkroneckertraceestimation} proposes a variant of the Hutchinson trace estimator in which each query vector in $\mathbb{R}^{d^p}$ is constructed as the Kronecker product of $p$ random vectors in $\mathbb{R}^d$, requiring $O(mpd)$ random bits for $m$ query vectors. The estimator of~\cite{meyer2025hutchinsonsestimatorbadkroneckertraceestimation} is unbiased; however, its variance grows exponentially with $p$. In this work, we address this limitation by proposing a sketching-based estimator that requires $O\!\big(p (d + m)\log m\big)$ random bits, yields an unbiased estimate of the trace, and simultaneously achieves a variance bound that grows polynomially with $p$.

0.29

The Nelson-Nguyen Conjecture via Mean-to-Moments Concentration

cs.DS ·2026-09-18 ·Tung Mai, Anup Rao
theory similarity 0.61
Abstract

An oblivious subspace embedding (OSE) is a distribution over matrices that approximately preserves the squared Euclidean norm of every vector in any fixed low-dimensional subspace. We prove the Nelson-Nguyen conjecture: for every $0 < δ< 1$, there exists a distribution that gives an OSE with embedding dimension $O((d + \log(1/δ))/\varepsilon^2)$ and column sparsity $s = O(\log(d/δ)/\varepsilon)$, with failure probability at most $δ$. We first bound the mean spectral error using a trace-moment argument and then upgrade this bound to the desired high-probability guarantee using concentration and resampling. ChatGPT-5.6-Pro was used in proving and writing the results of this manuscript.

0.36

Fast Length-Squared Sampling for Positive-Semidefinite Matrices

cs.DS cs.LG ·2026-08-12 ·Rajarshi Bhattacharjee, Ethan N. Epperly, Cameron Musco, Aaron Tian
similarity 0.61
Abstract

We describe a simple rejection-sampling-based algorithm to perform length-squared sampling on an $n \times n$ positive-semidefinite (psd) matrix: that is, to sample a column with probability proportional to its squared $\ell_2$-norm. The algorithm runs in just $O(n)$ expected time, which is significantly sublinear in the input matrix size. The runtime is optimal, even when the input is assumed to be diagonal. Our result has several applications. Length-squared sampling is used by a number of sublinear time algorithms for matrix problems, like low-rank approximation and eigenvalue approximation. Often, it is assumed that the algorithm is given access to the matrix column norms, and thus can perform length-squared sampling efficiently. Our result shows that, at least for psd matrices, we can remove this assumption. We also discuss an application to an asymptotically optimal algorithm for estimating the Frobenius norm of a psd matrix to relative error. Finally, we show that our sampling algorithm yields a very simple sublinear time algorithm for the robust psd low-rank approximation problem introduced by Bakshi et al. (FOCS, 2020), which nearly matches the more complex method developed there.

0.04

A Nonadaptive Sparse Fourier Transform in Every Dimension

cs.DS cs.ITmath.NA ·2026-11-19 ·Mahdi Cheraghchi, Jingyi Lyu
similarity 0.60
Abstract

Let $G=(\mathbb{Z}/2^a\mathbb{Z})^d$, of order $N=2^{ad}$. Given point-query access to any complex signal $X$ with Fourier transform $\hat{X}$ over $G$, we provide a randomized algorithm that constructs a $k$-sparse estimate $\widetilde{X}$ via non-adaptive queries such that, with large probability, $\|\widetilde{X}-\hat{X}\|_2^2 \leq C \cdot \|H_k(\hat{X})-\hat{X}\|_2^2$, for an absolute constant $C>0$, where $H_k(\cdot)$ denotes the best $k$-sparse approximation. The constant $C$ can be improved to any desired $1+\varepsilon$ by either supplying a constant-factor estimate on the $k$-sparse tail norm or allowing an arbitrarily small additive error term $δ\|\hat{X}\|_2^2$ on the right-hand side. With a supplied tail estimate, we can also satisfy an $\ell_\infty/\ell_2$ heavy hitters guarantee. For fixed $δ$, the number of samples is $O((k/\varepsilon^2)(\log N)\log(k/\varepsilon))$, and the recovery algorithm requires a polynomial in $(k/\varepsilon)\log N$ exact operations. The algorithm naturally extends to $G=(\mathbb{Z}/b^a\mathbb{Z})^d$ for any fixed integer $b>1$.

0.32

Nuclear Norm-Regularized Bayesian Matrix Completion

cs.LG stat.ML ·2026-09-24 ·Calvin Tolbert
similarity 0.60
Abstract · 40 pages, 7 figures

Nuclear-norm-regularized least squares is a standard approach to matrix completion, but it yields only a point estimate. Its Bayesian counterpart, a prior combining the nuclear norm with a Frobenius-norm term, gives a strongly log-concave though nonsmooth posterior when the noise precision is known. In practice the precision is unknown, and placing a truncated Jeffreys prior on it makes the joint posterior neither log-concave nor smooth. To our knowledge, we give the first sampler for this model with an explicit non-asymptotic guarantee: its output is within a prescribed total-variation or Wasserstein distance of the posterior on the matrix after a number of steps polynomial in the matrix dimensions and the reciprocal of the target accuracy. The sampler never targets a continuous distribution that is not strongly log-concave. It discretizes the precision onto a grid, estimates its posterior by thermodynamic integration along the tilted conditional posteriors of the matrix, and bounds the error this propagates to the posterior on the matrix. The approach applies whenever non-log-concavity is confined to a bounded scalar hyperparameter and the conditional distributions are strongly log-concave with smooth-plus-Lipschitz potentials. Our result establishes feasibility; the polynomial complexity is not intended as a practical algorithm at current problem scales.

0.26

Information-Theoretic Limits for Rectangular Spiked Matrix Models with Rotationally Invariant Noise

cs.IT cond-mat.dis-nnmath.ST ·2026-10-12 ·Qun Chen, Rudy Skerk, Jean Barbier, Francesco Camilli, Junjie Ma +1 more
similarity 0.60
Abstract

We study the information-theoretic limits of inference in rectangular rank-one spiked matrix models with additive rotationally invariant noise, thereby going beyond the standard assumption of independent noise entries. Using the replica method from statistical physics, we derive a variational formula for the mutual information between the signal and the data, together with a system of saddle point equations predicting the minimum mean squared error in estimating the rank-one spike. We further show that, in the Bayes-optimal setting, these saddle point equations coincide with the fixed point equations of the state evolution of a recently proposed orthogonal approximate message passing algorithm with Bayes-optimal denoisers. This equivalence provides an algorithmic interpretation of the replica prediction and supports the Bayes-optimality of orthogonal approximate message passing whenever the relevant fixed point is unique. Numerical evaluations of the saddle point equations for several rotationally invariant noise ensembles and signal priors, together with finite-size simulations of the algorithm, confirm the asymptotic predictions. They illustrate both regimes with a unique informative fixed point, where orthogonal approximate message passing is predicted to attain the minimum mean squared error, and regimes with multiple fixed points, where a statistical-to-computational gap exists.

0.39