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.
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.
This paper explores the generalized problem of (approximately) computing the largest output entries, with an approximation error dependent solely on the smaller entries, from the viewpoint of sparse recovery, and shows 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 O(T(n, m_{in), k)$.
K. Bringmann, N. Fischer, Vasileios Nakos· 1 citation
This work argues that the KL-NMF method has reached its limits and proposes to use instead the second-order Taylor expansion of the loss, leading to a Newton-type method which provably converges and 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.