Refinement-based Christoffel sampling for least squares approximation in non-orthogonal bases
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_ | 1866917156002725888 |
|---|---|
| author | Herremans, Astrid Adcock, Ben |
| author_facet | Herremans, Astrid Adcock, Ben |
| contents | We introduce a refinement-based Christoffel sampling (RCS) algorithm for least squares approximation in the span of a given, generally non-orthogonal set of functions $Φ_n = \{ϕ_1, \dots, ϕ_n\}$. A standard sampling strategy for this problem is Christoffel sampling, which achieves near-best approximations in probability using only $\mathcal{O}(n \log(n))$ samples. However, it requires i.i.d. sampling from a distribution whose density is proportional to the inverse Christoffel function $k_n$, the computation of which requires an orthonormal basis. As a result, existing approaches for non-orthogonal bases $Φ_n$ typically rely on costly discrete orthogonalization. We propose a new iterative algorithm, inspired by recent advances in approximate leverage score sampling, that avoids this bottleneck. Crucially, while the computational cost of discrete orthogonalization grows proportionally with $\|k_n\|_{L^\infty(X)}$, the cost of our approach increases only logarithmically in $\|k_n\|_{L^\infty(X)}$. In addition, we account for finite-precision effects by considering a numerical variant of the Christoffel function, ensuring that the algorithm relies only on computable quantities. Alongside a convergence proof, we present extensive numerical experiments demonstrating the efficiency and robustness of the proposed method. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_08461 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Refinement-based Christoffel sampling for least squares approximation in non-orthogonal bases Herremans, Astrid Adcock, Ben Numerical Analysis 41A10, 41A63, 42C15, 65C05 We introduce a refinement-based Christoffel sampling (RCS) algorithm for least squares approximation in the span of a given, generally non-orthogonal set of functions $Φ_n = \{ϕ_1, \dots, ϕ_n\}$. A standard sampling strategy for this problem is Christoffel sampling, which achieves near-best approximations in probability using only $\mathcal{O}(n \log(n))$ samples. However, it requires i.i.d. sampling from a distribution whose density is proportional to the inverse Christoffel function $k_n$, the computation of which requires an orthonormal basis. As a result, existing approaches for non-orthogonal bases $Φ_n$ typically rely on costly discrete orthogonalization. We propose a new iterative algorithm, inspired by recent advances in approximate leverage score sampling, that avoids this bottleneck. Crucially, while the computational cost of discrete orthogonalization grows proportionally with $\|k_n\|_{L^\infty(X)}$, the cost of our approach increases only logarithmically in $\|k_n\|_{L^\infty(X)}$. In addition, we account for finite-precision effects by considering a numerical variant of the Christoffel function, ensuring that the algorithm relies only on computable quantities. Alongside a convergence proof, we present extensive numerical experiments demonstrating the efficiency and robustness of the proposed method. |
| title | Refinement-based Christoffel sampling for least squares approximation in non-orthogonal bases |
| topic | Numerical Analysis 41A10, 41A63, 42C15, 65C05 |
| url | https://arxiv.org/abs/2510.08461 |