Convergence and Near-optimal Sampling for Multivariate Function Approximations in Irregular Domains via Vandermonde with Arnoldi
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908369460133888 |
|---|---|
| author | Zhu, Wenqi Nakatsukasa, Yuji |
| author_facet | Zhu, Wenqi Nakatsukasa, Yuji |
| contents | Vandermonde matrices are usually exponentially ill-conditioned and often result in unstable approximations. In this paper, we introduce and analyze the \textit{multivariate Vandermonde with Arnoldi (V+A) method}, which is based on least-squares approximation together with a Stieltjes orthogonalization process, for approximating continuous, multivariate functions on $d$-dimensional irregular domains. The V+A method addresses the ill-conditioning of the Vandermonde approximation by creating a set of discrete orthogonal bases with respect to a discrete measure. The V+A method is simple and general, relying only on the domain's sample points. This paper analyzes the sample complexity of {the least-squares approximation that uses the V+A method}. We show that, for a large class of domains, this approximation gives a well-conditioned and near-optimal $N$-dimensional least-squares approximation using $M=O(N^2)$ equispaced sample points or $M=O(N^2\log N)$ random sample points, independently of $d$. We provide a comprehensive analysis of the error estimates and the rate of convergence of the least-squares approximation that uses the V+A method. Based on the multivariate V+A techniques, we propose a new variant of the weighted V+A least-squares algorithm that uses only $M=O(N\log N)$ sample points to achieve a near-optimal approximation. {Our initial numerical results validate that the V+A least-squares approximation method provides well-conditioned and near-optimal approximations for multivariate functions on (irregular) domains. Additionally, the (weighted) least-squares approximation that uses the V+A method performs competitively with state-of-the-art orthogonalization techniques and can serve as a practical tool for selecting near-optimal distributions of sample points in irregular domains. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_12241 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Convergence and Near-optimal Sampling for Multivariate Function Approximations in Irregular Domains via Vandermonde with Arnoldi Zhu, Wenqi Nakatsukasa, Yuji Numerical Analysis 41A05, 65D05, 65D10 Vandermonde matrices are usually exponentially ill-conditioned and often result in unstable approximations. In this paper, we introduce and analyze the \textit{multivariate Vandermonde with Arnoldi (V+A) method}, which is based on least-squares approximation together with a Stieltjes orthogonalization process, for approximating continuous, multivariate functions on $d$-dimensional irregular domains. The V+A method addresses the ill-conditioning of the Vandermonde approximation by creating a set of discrete orthogonal bases with respect to a discrete measure. The V+A method is simple and general, relying only on the domain's sample points. This paper analyzes the sample complexity of {the least-squares approximation that uses the V+A method}. We show that, for a large class of domains, this approximation gives a well-conditioned and near-optimal $N$-dimensional least-squares approximation using $M=O(N^2)$ equispaced sample points or $M=O(N^2\log N)$ random sample points, independently of $d$. We provide a comprehensive analysis of the error estimates and the rate of convergence of the least-squares approximation that uses the V+A method. Based on the multivariate V+A techniques, we propose a new variant of the weighted V+A least-squares algorithm that uses only $M=O(N\log N)$ sample points to achieve a near-optimal approximation. {Our initial numerical results validate that the V+A least-squares approximation method provides well-conditioned and near-optimal approximations for multivariate functions on (irregular) domains. Additionally, the (weighted) least-squares approximation that uses the V+A method performs competitively with state-of-the-art orthogonalization techniques and can serve as a practical tool for selecting near-optimal distributions of sample points in irregular domains. |
| title | Convergence and Near-optimal Sampling for Multivariate Function Approximations in Irregular Domains via Vandermonde with Arnoldi |
| topic | Numerical Analysis 41A05, 65D05, 65D10 |
| url | https://arxiv.org/abs/2301.12241 |