Determinant-Based Error Bounds for CUR Matrix Approximation: Oversampling and Volume Sampling
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915832707153920 |
|---|---|
| author | de Hoog, Frank Hegland, Markus |
| author_facet | de Hoog, Frank Hegland, Markus |
| contents | We derive error bounds for CUR matrix approximation using determinant-based methods that relate local projection errors to global approximation quality. For general matrices, we establish determinant identities for bordered Gramian matrices that decompose CUR approximation errors into interpretable local components. These identities connect projection errors onto submatrix column spaces directly to determinants, providing geometric insight into approximation degradation. We develop a probabilistic framework based on volume sampling that yields interpolation-type error bounds quantifying the benefits of oversampling: when $r > k$ rows are selected for $k$ columns, the expected error factor transitions linearly from $(k+1)^2$ (no oversampling) to $(k+1)$ (full oversampling). Our analysis establishes that the expected squared error is bounded by this interpolation factor times the squared error of the best rank-$k$ approximation, directly connecting CUR approximation quality to the optimal low-rank approximation. The framework applies to both CUR decomposition for general matrices and the Nyström method for symmetric positive semi-definite matrices, providing a unified theoretical foundation for determinant-based low-rank approximation analysis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_15102 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Determinant-Based Error Bounds for CUR Matrix Approximation: Oversampling and Volume Sampling de Hoog, Frank Hegland, Markus Numerical Analysis 65F55 (Primary) 15A15 (Secondary) We derive error bounds for CUR matrix approximation using determinant-based methods that relate local projection errors to global approximation quality. For general matrices, we establish determinant identities for bordered Gramian matrices that decompose CUR approximation errors into interpretable local components. These identities connect projection errors onto submatrix column spaces directly to determinants, providing geometric insight into approximation degradation. We develop a probabilistic framework based on volume sampling that yields interpolation-type error bounds quantifying the benefits of oversampling: when $r > k$ rows are selected for $k$ columns, the expected error factor transitions linearly from $(k+1)^2$ (no oversampling) to $(k+1)$ (full oversampling). Our analysis establishes that the expected squared error is bounded by this interpolation factor times the squared error of the best rank-$k$ approximation, directly connecting CUR approximation quality to the optimal low-rank approximation. The framework applies to both CUR decomposition for general matrices and the Nyström method for symmetric positive semi-definite matrices, providing a unified theoretical foundation for determinant-based low-rank approximation analysis. |
| title | Determinant-Based Error Bounds for CUR Matrix Approximation: Oversampling and Volume Sampling |
| topic | Numerical Analysis 65F55 (Primary) 15A15 (Secondary) |
| url | https://arxiv.org/abs/2512.15102 |