Efficient Function Approximation Under Heteroskedastic Noise
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911102382637056 |
|---|---|
| author | Nakatsukasa, Yuji Zhang, Yifu |
| author_facet | Nakatsukasa, Yuji Zhang, Yifu |
| contents | Approximating a function $f(x)$ on $[-1,1]$ based on $N+1$ samples is a classical problem in numerical analysis. If the samples come with heteroskedastic noise depending on $x$ of variance $σ(x)^2$, an $O(N\log N)$ algorithm for this problem has not yet been found in the current literature. In this paper, we propose a method called HeteroChebtrunc, adapted from an algorithm named NoisyChebtrunc. Using techniques in high-dimensional probability, we show that with high probability, HeteroChebtrunc achieves a tighter infinity-norm error bound than NoisyChebtrunc under heteroskedastic noise. This algorithm runs in $O(N+\hat{N}\log \hat{N})$ operations, where $\hat{N}\ll N$ is a chosen parameter. While investigating the properties of HeteroChebtrunc, we also derive a high-probability non-asymptotic relative error bound on the sample variance estimator for subgaussian variables, which is potentially another result of broader interest. We provide numerical experiments to demonstrate the improved uniform error of our algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_08683 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient Function Approximation Under Heteroskedastic Noise Nakatsukasa, Yuji Zhang, Yifu Numerical Analysis Approximating a function $f(x)$ on $[-1,1]$ based on $N+1$ samples is a classical problem in numerical analysis. If the samples come with heteroskedastic noise depending on $x$ of variance $σ(x)^2$, an $O(N\log N)$ algorithm for this problem has not yet been found in the current literature. In this paper, we propose a method called HeteroChebtrunc, adapted from an algorithm named NoisyChebtrunc. Using techniques in high-dimensional probability, we show that with high probability, HeteroChebtrunc achieves a tighter infinity-norm error bound than NoisyChebtrunc under heteroskedastic noise. This algorithm runs in $O(N+\hat{N}\log \hat{N})$ operations, where $\hat{N}\ll N$ is a chosen parameter. While investigating the properties of HeteroChebtrunc, we also derive a high-probability non-asymptotic relative error bound on the sample variance estimator for subgaussian variables, which is potentially another result of broader interest. We provide numerical experiments to demonstrate the improved uniform error of our algorithm. |
| title | Efficient Function Approximation Under Heteroskedastic Noise |
| topic | Numerical Analysis |
| url | https://arxiv.org/abs/2508.08683 |