Metraipolis › archive › dc_3a33c91040ca

Fast Length-Squared Sampling for Positive-Semidefinite Matrices — arXiv:2608.12503

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.12503
License (as archived)
CC0-1.0
Archived
2026-10-19T04:27:46.730Z
SHA-256 of the archived text
86a8114e961a5c5e009f4a011de11edc13c896a5ecf183cc5318553529b5ade0
Stable URL of this page
https://metraipolis.com/documento/dc_3a33c91040ca

How to cite

Fast Length-Squared Sampling for Positive-Semidefinite Matrices — arXiv:2608.12503 — arXiv (en), https://arxiv.org/abs/2608.12503 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3a33c91040ca (Metraipolis archive dc_3a33c91040ca, sha256 86a8114e961a5c5e009f4a011de11edc13c896a5ecf183cc5318553529b5ade0)
BibTeX
@misc{dc3a33c91040ca,
  title = {Fast Length-Squared Sampling for Positive-Semidefinite Matrices — arXiv:2608.12503},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.12503},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3a33c91040ca; sha256 86a8114e961a5c5e009f4a011de11edc13c896a5ecf183cc5318553529b5ade0},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.12503. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-08-14 in cs.LG).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2608.12503 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T04:20:35.883Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-08-14?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).