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.
We study fixed-tolerance low-rank approximation in the matrix-free setting, where a matrix or linear operator $\mathbf{A}$ is accessible only through matrix-vector products and its rank must be determined adaptively to meet a prescribed error tolerance. We introduce a family of adaptive, matrix-free randomized QB algorithms. A randomized error indicator estimates the residual norm -- in either the Frobenius or the spectral norm -- directly from a random sketch, remaining accurate down to machine precision. A matrix-free rank-pruning step decouples the computational block size from the final rank, so that large, BLAS-3-friendly blocks can be used without over-estimating the rank, and an adjoint-free variant returns the orthonormal basis using only the forward operator. Across test matrices with diverse singular-value decays, the proposed methods attain ranks close to the truncated-SVD optimum while meeting the prescribed tolerance with high probability.
In the seminal sparse matrix multiplication problem the goal is to compute the product of two $n \times n$ matrices when the matrices are sparse, i.e., when the number of nonzeros in the input matrices $m_{in}$ and/or the number of nonzeros in the output matrix $m_{out}$ are much smaller than $n^2$. In this paper, we explore the generalized problem of (approximately) computing the $k$ largest output entries, with an approximation error dependent solely on the smaller entries -- from the viewpoint of sparse recovery, this can be seen as a robust variant of sparse matrix multiplication. Despite the substantial research dedicated to sparse matrix multiplication, almost no existing algorithms are robust in this sense. The one exception is Pagh's algorithm in time $\widetilde O(m_{in} + nk)$ [ITCS'12], and it remained open whether other algorithms can be similarly made robust. Our principal contribution is a black-box reduction from robust sparse matrix multiplication to conventional sparse matrix multiplication with only polylogarithmic overhead. Specifically, we show that any sparse matrix multiplication algorithm with running time $T(n, m_{in}, m_{out})$ can be transformed into a robust algorithm running in time $\widetilde O(T(n, m_{in}, k))$. This reduction leverages an extensive toolkit from sparse recovery, and intriguingly, also involves solving a knapsack-type problem. By plugging in the state-of-the-art algorithm for sparse matrix multiplication by Abboud, Bringmann, Fischer, and K\"unnemann [SODA'24], we achieve significantly improved bounds such as $O((m_{in} + k)^{1.346})$. Notably, in the regime where $k \geq m_{in}^{1.762}$, our reduction culminates in an almost-optimal $k^{1+o(1)}$-time algorithm.
K. Bringmann, N. Fischer, Vasileios Nakos· 1 citation
Nonnegative Matrix Factorization (NMF) is a fundamental tool in unsupervised learning, which approximates a nonnegative matrix by the product of two low-rank nonnegative factors. The Kullback-Leibler (KL) divergence is best suited to measure the data to model discrepancy when the decomposed data sample follows a Poisson distribution, which is the case for count datasets such as term-document matrices or images. Most KL-NMF algorithms in the literature minimize a separable majorant of the loss to find their next iterate. We argue that this method has reached its limits and propose to use instead the second-order Taylor expansion of the loss, leading to a Newton-type method. We minimize this non-separable surrogate by proposing a generalization of the well-known HALS algorithm. This yields an efficient KL-NMF algorithm which provably converges and which competes favorably with state-of-the-art algorithms on a large variety of datasets.
Damien Lesens, Jérémy E. Cohen, Bora Uccar· 0 citations
The set of $n\times n$ correlation matrices, known as the elliptope, has volume decaying at the super-exponential rate $\exp\{-\tfrac14 n^2\log n\}$. We characterize where this vanishing volume concentrates. A uniform draw is entrywise close to the identity yet globally far from it and nearly singular: its maximum absolute correlation is of order $\sqrt{\log n/n}$, its Frobenius distance is asymptotic to $\sqrt n$, its empirical spectral distribution converges to the Marchenko-Pastur law with ratio one, and its smallest eigenvalue has the exact $\operatorname{Beta}(1,d)$ distribution, where $d=n(n-1)/2$, and is therefore of order $n^{-2}$. More generally, distinct off-diagonal entries are exactly pairwise independent under every $\operatorname{LKJ}(\eta)$ law. For the uniform law, this yields a Chen-Stein proof of the extreme-correlation point-process limit and an $O(n^{-1})$ total-variation bound for finite-dimensional exceedance counts relative to Poisson laws with their exact finite-$n$ means. We also identify two distinct scales: $\eta_n\asymp n$ alters the limiting spectrum, whereas $\eta_n\asymp n^2$ is needed to keep the Frobenius distance bounded. Finally, for a bounded, centered i.i.d. off-diagonal specification, projection to the nearest correlation matrix incurs a squared repair cost asymptotically at least one-half of the squared Frobenius norm of its off-diagonal part.
We consider the probability that a discrete random matrix $M_n(\xi)$ is \emph{strongly non-singular}, meaning all its leading principal submatrices are non-singular. This property is equivalent to the existence of an LU factorization. We show that for any discrete random variable $\xi$ with finite support and $|\xi|_\infty<1$, there is a constant probability that $M_n(\xi)$ is strongly non-singular with a growth factor bounded by $n^{5/2+\delta}$. Furthermore, we provide a tight asymptotic lower bound for this probability as $|\xi|_\infty \to 0$. Finally, we provide exact counts for strongly non-singular binary matrices up to $n=9$ and use these to derive improved upper bounds for the Bernoulli case.
S. Mateo, John Urschel, Nicholas West· 0 citations
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 $\Theta(r/\varepsilon)$ for any low-rank approximation method based on a partial Cholesky decomposition (also known as a column Nystr\"om 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.