Higher Order Lipschitz Greedy Recombination Interpolation Method (HOLGRIM)
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913378359836672 |
|---|---|
| author | Lyons, Terry McLeod, Andrew D. |
| author_facet | Lyons, Terry McLeod, Andrew D. |
| contents | In this paper we introduce the Higher Order Lipschitz Greedy Recombination Interpolation Method (HOLGRIM) for finding sparse approximations of Lip$(γ)$ functions, in the sense of Stein, given as a linear combination of a (large) number of simpler Lip$(γ)$ functions. HOLGRIM is developed as a refinement of the Greedy Recombination Interpolation Method (GRIM) in the setting of Lip$(γ)$ functions. HOLGRIM combines dynamic growth-based interpolation techniques with thinning-based reduction techniques in a data-driven fashion. The dynamic growth is driven by a greedy selection algorithm in which multiple new points may be selected at each step. The thinning reduction is carried out by recombination, the linear algebra technique utilised by GRIM. We establish that the number of non-zero weights for the approximation returned by HOLGRIM is controlled by a particular packing number of the data. The level of data concentration required to guarantee that HOLGRIM returns a good sparse approximation is decreasing with respect to the regularity parameter $γ> 0$. Further, we establish complexity cost estimates verifying that implementing HOLGRIM is feasible. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_03232 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Higher Order Lipschitz Greedy Recombination Interpolation Method (HOLGRIM) Lyons, Terry McLeod, Andrew D. Numerical Analysis 97N40, 97N50, 26B35, 65D05, 41A05, 41A25 In this paper we introduce the Higher Order Lipschitz Greedy Recombination Interpolation Method (HOLGRIM) for finding sparse approximations of Lip$(γ)$ functions, in the sense of Stein, given as a linear combination of a (large) number of simpler Lip$(γ)$ functions. HOLGRIM is developed as a refinement of the Greedy Recombination Interpolation Method (GRIM) in the setting of Lip$(γ)$ functions. HOLGRIM combines dynamic growth-based interpolation techniques with thinning-based reduction techniques in a data-driven fashion. The dynamic growth is driven by a greedy selection algorithm in which multiple new points may be selected at each step. The thinning reduction is carried out by recombination, the linear algebra technique utilised by GRIM. We establish that the number of non-zero weights for the approximation returned by HOLGRIM is controlled by a particular packing number of the data. The level of data concentration required to guarantee that HOLGRIM returns a good sparse approximation is decreasing with respect to the regularity parameter $γ> 0$. Further, we establish complexity cost estimates verifying that implementing HOLGRIM is feasible. |
| title | Higher Order Lipschitz Greedy Recombination Interpolation Method (HOLGRIM) |
| topic | Numerical Analysis 97N40, 97N50, 26B35, 65D05, 41A05, 41A25 |
| url | https://arxiv.org/abs/2406.03232 |