CS Paper Radar

Unbiased Low-Rank Approximation for Repeated Matrix-Vector Multiplication: Stability and Optimal Sampling

Kang Liu

cs.LG stat.MLmath.NAmath.OCmath.RA ·submitted 2026-10-31 09:59 UTC · v1

Abstract

Replacing the matrix in an iteration with random low-rank matrices can reduce the cost of matrix-vector multiplication. However, even if the sampled matrices equal the original matrix in expectation, the expected squared norm of the random iterates may grow while the original iteration converges. Under a fixed rank bound, we study how to choose the distribution of these random matrices to minimize this growth when sampling independently at each step. We derive an exact formula for the optimal asymptotic growth factor and use it to determine when the expected squared norm can converge to zero. We then characterize precisely when a fixed sampling distribution achieves this optimal factor and construct finite-support optimal distributions in every attainable case. These results determine the minimum rank required for stability and provide optimal sampling designs under the prescribed rank constraint.

Closest papers

Nearest neighbours by meaning across the whole index.

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.70
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 Subsampled Davis-Kahan Bound for Large-Scale Eigenspace Estimation

cs.LG stat.MLstat.ME ·2026-09-06 ·Huan Qing
theoryhot direction similarity 0.67
Abstract · 24 pages

The Davis-Kahan theorem is a fundamental tool in spectral analysis, providing quantitative control over the distance between the eigenspaces of a symmetric matrix and its perturbation. However, when the matrix dimension is large, computing leading eigenvectors is computationally expensive, limiting the practical use of spectral methods in modern large-scale applications. This paper addresses this problem by proposing an independent Bernoulli sampling scheme and proves that the leading left singular vectors of the subsampled matrix faithfully approximate the target subspace of a low-rank symmetric matrix. Our main result is a subsampled Davis-Kahan bound that gives an explicit error bound depending directly on the sampling probability. The bound reveals the trade-off: the computational cost scales linearly with the sampling probability, while the statistical error scales as the inverse square root of the sampling probability. Our result thus extends the Davis-Kahan theorem to the subsampled setting, enabling scalable spectral analysis of large-scale symmetric matrices.

0.25

Approximate Matrix Multiplication through Joint Leverage Score Sampling

eess.SP math.NA ·2026-10-21 ·Neophytos Charalambides, Mert Pilanci, Alfred O. Hero
similarity 0.65
Abstract

In this paper, we investigate approximate matrix multiplication through random sampling. Specifically, we propose using a non-uniform sampling distribution constructed from the leverage scores of the two matrices, and characterize the associated approximation error in terms of the matrix spectral norm; which is well-known to better characterize the downstream error when the matrix product operator is applied to an input vector. We provide the probability error bounds for the proposed algorithm are also given, and discuss connections to data-oblivious approximate matrix multiplication, and graph sparsification algorithms.

0.18

Matrix Samplers and Quantum-Proof Extractors: Their Correspondence and Almost-Optimal Constructions

cs.CC quant-ph ·2026-10-27 ·Kuan Cheng, Ruiyang Wu
similarity 0.60
Abstract

We establish an equivalence between matrix samplers and quantum-proof randomness extractors. The classical sampler-extractor equivalence is established by a seminal work of Zuckerman (Random Structures & Algorithms, 1997). Using this equivalence, we construct explicit strong matrix samplers with optimal randomness overhead and near-optimal sample complexity via constructing quantum-proof extractors. Specifically for matrix dimension $D$, accuracy $\varepsilon$ and failure probability $δ\leq\varepsilon$, our matrix sampler uses $$ m+O_α(\log(D/δ))\text{ random bits and } O_α\!\left(\varepsilon^{-2-α}\log^{1+α}(D/δ)\right)\text{ samples}, $$ for any constant $α>0$. Compared with the matrix sampler of Xun and Zuckerman (CCC 2025), our construction has improvements in two aspects. Under optimal random seed length, we can replace the $\operatorname{poly} D$ dependence in the number of samples by $O(\log^{1+α} D)$. Under the same scale of sample size, we can remove their $\log\log D$ factor in the length of the random seed. Our underlying strong quantum-proof extractor has output length $n-O_α(a+\log(1/η))$ and seed length at most $(1+α)\log a+(2+α)\log(1/η)+O_α(1)$ for $n$-bit sources with conditional min-entropy $n-a$ and error $η$. We also obtain strong quantum-proof extractors for every constant entropy rate, for any error as small as $2^{-Ω(n)}$, having optimal seed length $O(\log(n/η))$ and output length $Ω(n)$, improving previous constructions.

0.09

The rank of the random $k$-XORSAT matrix beyond satisfiability

cs.DM math.PRmath.CO ·2026-10-19 ·Amin Coja-Oghlan, Maurice Rolvien
similarity 0.60
Abstract

The random $k$-XORSAT matrix is an $m\times n$ random matrix $\mathbf A$ over $\mathbb F_2$ that represents a random instance of the $k$-XORSAT problem. Each row of $\mathbf A$ contains precisely $k\geq3$ non-zero entries in random positions. The rows are drawn independently. The matrix $\mathbf A$ is known to have full row rank for $m/n$ below the random $k$-XORSAT satisfiability threshold, which is known explicitly [Dubois, Mandler~2002; Pittel, Sorkin~2016]. Motivated by a problem from quantum game theory and refining a result of Cooper, Frieze and Pegden (2019), we determine the limiting distribution of the rank of $\mathbf A$ beyond the satisfiability threshold.

0.25

Lower Bounds for Smooth Nonconvex Zeroth-Order Optimization: The Price of Determinism under Low Curvature Trace

cs.LG ·2026-10-20 ·Yuxing Peng, Zhiqing Tang, Weijia Jia
theorycode/data similarity 0.60
Abstract · 60 pages, 2 figures, 1 table; Lean 4 formalization of the deterministic bounds: https://github.com/Pyx9876/zo-lower-bounds-lean (also in the…

Low curvature trace, an effective rank condition, is a common explanation for why randomized zeroth-order methods scale to high-dimensional tasks such as language model fine-tuning. Can deterministic methods achieve the same savings? We show that they cannot. We study finding $\varepsilon$-stationary points of $L$-smooth nonconvex functions on $\mathbb{R}^d$ from exact function values, assuming that below the starting value the Hessian is dominated by a fixed matrix with trace at most $LE$; this is a fixed-matrix form of the effective rank condition used to explain zeroth-order fine-tuning. When $ET\le d$, the Gaussian two-point method that such fine-tuning uses needs only $O(ET)$ calls if it rejects steps that raise $f$, where $T=LΔ/\varepsilon^2$ is the iteration count of gradient descent from initial gap $Δ$, and we prove that every randomized method needs $Ω(ET)$ calls, so this cost is optimal up to constants. In contrast, every deterministic method needs $\widetildeΩ(d\min\{T,\sqrt{ET}\})$ calls, and adaptive subspace search attains $O(d\min\{T,\sqrt{ET}\})$: a deterministic method pays about $d$ calls per discovered direction, and the trace budget allows about $\sqrt{ET}$ directions. Determinism thus multiplies the cost by a factor of order $d/(E+\sqrt{ET})$ up to logarithmic factors, which grows linearly with $d$ for fixed $E$ and $T$; once $E$ exceeds $T$ by a logarithmic factor, deterministic methods need $Ω(dT)$ calls, as without any trace budget. Our lower bounds hold for $C^\infty$ functions with the matrix bound on all of $\mathbb{R}^d$, even when each call also returns gradient projections priced by rank.

0.23

Linear Ensemble Sampling with Smaller Ensembles

cs.LG stat.ML ·2026-09-12 ·Taehyun Hwang, Min-hwan Oh
hot direction similarity 0.59
Abstract

Ensemble sampling offers a practical approach to randomized exploration by maintaining a collection of models, but how small an ensemble can be while retaining strong regret guarantees remains unresolved. In particular, the existing guarantees use an ensemble size of $Θ(d\log T)$, leaving a logarithmic gap in the horizon $T$ relative to the intrinsic $Ω(d)$ ensemble-size barrier. We aim to narrow this gap by proposing an ensemble sampling algorithm that refreshes the ensemble only when the regularized Gram matrix changes substantially. This mechanism localizes the perturbation analysis to epochs with controlled Gram-matrix drift and reduces the sufficient ensemble size to $Θ(d\log d+d\log\log T)$, while preserving the state-of-the-art $\tilde O(d^{3/2}\sqrt T)$ regret for ensemble sampling with arbitrary bounded arm sets. We further show that, when the arm set is finite of cardinality $K$, the proposed algorithm achieves the sharper regret bound $\tilde O(d\sqrt{T\log K})$. To the best of our knowledge, this is the first ensemble-sampling guarantee that simultaneously recovers both canonical regret scalings known for randomized linear bandit algorithms: the $\tilde O(d^{3/2}\sqrt{T})$ rate for arbitrary bounded arm sets and the $\tilde O (d\sqrt{T\log K})$ rate for finite arm sets. The algorithm also admits an anytime implementation without resetting past data, and experiments show that it remains competitive with baselines while using substantially smaller ensembles.

0.35

A new analysis of the randomly pivoted Cholesky algorithm

cs.DS math.NAstat.CO ·2026-08-21 ·Ethan N. W. Epperly
similarity 0.59
Abstract · 12 pages, 1 figure

The randomly pivoted Cholesky algorithm is one of the leading methods for computing a low-rank approximation to a large positive-semidefinite matrix. However, while it consistently achieves accuracy comparable to or better than competing methods of its type in experiments, its theoretical analysis lags somewhat behind other methods. This paper closes this gap, proving that randomly pivoted Cholesky produces an approximation with expected error within a $1+\varepsilon$ factor of the optimal rank-$r$ approximation in $\mathcal{O}(r/\varepsilon + r\sqrt{\log r})$ steps. This result nearly matches the optimal complexity $Θ(r/\varepsilon)$ for any low-rank approximation method based on a partial Cholesky decomposition (also known as a column Nyström approximation). The paper also presents bounds on the randomly pivoted Cholesky trace and spectral-norm errors that hold with high probability. The mathematical argument is largely due to GPT 5.6-Sol (Pro), with some refinements by the author.

0.33