Randomized strong rank-revealing QR for column subset selection and low-rank matrix approximation
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910890237886464 |
|---|---|
| author | Grigori, Laura Xue, Zhipeng |
| author_facet | Grigori, Laura Xue, Zhipeng |
| contents | We discuss a randomized strong rank-revealing QR factorization that effectively reveals the spectrum of a matrix $\textbf{M}$. This factorization can be used to address problems such as selecting a subset of the columns of $\textbf{M}$, computing its low-rank approximation, estimating its rank, or approximating its null space. Given a random sketching matrix $\pmbΩ$ that satisfies the $ε$-embedding property for a subspace within the range of $\textbf{M}$, the factorization relies on selecting columns that allow to reveal the spectrum via a deterministic strong rank-revealing QR factorization of $\textbf{M}^{sk} = \pmbΩ\textbf{M}$, the sketch of $\textbf{M}$. We show that this selection leads to a factorization with strong rank-revealing properties, making it suitable for approximating the singular values of $\textbf{M}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_18496 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Randomized strong rank-revealing QR for column subset selection and low-rank matrix approximation Grigori, Laura Xue, Zhipeng Numerical Analysis We discuss a randomized strong rank-revealing QR factorization that effectively reveals the spectrum of a matrix $\textbf{M}$. This factorization can be used to address problems such as selecting a subset of the columns of $\textbf{M}$, computing its low-rank approximation, estimating its rank, or approximating its null space. Given a random sketching matrix $\pmbΩ$ that satisfies the $ε$-embedding property for a subspace within the range of $\textbf{M}$, the factorization relies on selecting columns that allow to reveal the spectrum via a deterministic strong rank-revealing QR factorization of $\textbf{M}^{sk} = \pmbΩ\textbf{M}$, the sketch of $\textbf{M}$. We show that this selection leads to a factorization with strong rank-revealing properties, making it suitable for approximating the singular values of $\textbf{M}$. |
| title | Randomized strong rank-revealing QR for column subset selection and low-rank matrix approximation |
| topic | Numerical Analysis |
| url | https://arxiv.org/abs/2503.18496 |