On Unbiased Low-Rank Approximation with Minimum Distortion
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_ | 1866910055527350272 |
|---|---|
| author | Barnes, Leighton Pate Cameron, Stephen Howard, Benjamin |
| author_facet | Barnes, Leighton Pate Cameron, Stephen Howard, Benjamin |
| contents | We describe an algorithm for sampling a low-rank random matrix $Q$ that best approximates a fixed target matrix $P\in\mathbb{C}^{n\times m}$ in the following sense: $Q$ is unbiased, i.e., $\mathbb{E}[Q] = P$; $\mathsf{rank}(Q)\leq r$; and $Q$ minimizes the expected Frobenius norm error $\mathbb{E}\|P-Q\|_F^2$. Our algorithm mirrors the solution to the efficient unbiased sparsification problem for vectors, except applied to the singular components of the matrix $P$. Optimality is proven by showing that our algorithm matches the error from an existing lower bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_09647 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Unbiased Low-Rank Approximation with Minimum Distortion Barnes, Leighton Pate Cameron, Stephen Howard, Benjamin Data Structures and Algorithms Information Theory Machine Learning Probability Statistics Theory We describe an algorithm for sampling a low-rank random matrix $Q$ that best approximates a fixed target matrix $P\in\mathbb{C}^{n\times m}$ in the following sense: $Q$ is unbiased, i.e., $\mathbb{E}[Q] = P$; $\mathsf{rank}(Q)\leq r$; and $Q$ minimizes the expected Frobenius norm error $\mathbb{E}\|P-Q\|_F^2$. Our algorithm mirrors the solution to the efficient unbiased sparsification problem for vectors, except applied to the singular components of the matrix $P$. Optimality is proven by showing that our algorithm matches the error from an existing lower bound. |
| title | On Unbiased Low-Rank Approximation with Minimum Distortion |
| topic | Data Structures and Algorithms Information Theory Machine Learning Probability Statistics Theory |
| url | https://arxiv.org/abs/2505.09647 |