Back to Search
Start Over
Greedy algorithms and Kolmogorov widths in Banach spaces
- Source :
- Journal of Approximation Theory. 251:105344
- Publication Year :
- 2020
- Publisher :
- Elsevier BV, 2020.
-
Abstract
- Let $X$ be a Banach space and $\mathcal{K}$ be a compact subset in $X$. We consider a greedy algorithm for finding an $n$-dimensional subspace $V_n\subset X$ which can be used to approximate the elements of $\mathcal{K}$. We are interested in how well the space $V_n$ approximates the elements of $\mathcal{K}$. For this purpose we compare the performance of greedy algorithm measured by $\sigma_n(\mathcal{K})_X:=\text{dist}(\mathcal{K},V_n)_X$ with the Kolmogorov width $d_n(\mathcal{K})_X$ which is the best possible error one can achieve when approximating $\mathcal{K}$ by $n$-dimensional subspaces. Various results in this direction have been given, e.g., in Binev et al. (SIAM J. Math. Anal. (2011)), DeVore et al. (Constr. Approx. (2013)) and Wojtaszczyk (J. Math. Anal. Appl. (2015)). The purpose of the present paper is to continue this line. We shall show that there exists a constant $C>0$ such that $$ \sigma_n(\mathcal{K})_X\leq C n^{-s+\mu}\big(\log(n+2)\big)^{\min(s,1/2)}, \quad \ n\geq 1\,, $$ if Kolmogorov widths $d_n(\mathcal{K})_X$ decay as $n^{-s}$ and the Banach-Mazur distance between an arbitrary $n$-dimensional subspace $V_n \subset X$ and $\ell_2^n$ satisfies $d(V_n,\ell_2^n)\leq C_1 n^\mu$. In particular, when some additional information about the set $\mathcal{K}$ is given then there is no logarithmic factor in this estimate.<br />Comment: 14 pages
- Subjects :
- Numerical Analysis
Logarithm
Applied Mathematics
General Mathematics
010102 general mathematics
Banach space
010103 numerical & computational mathematics
Space (mathematics)
01 natural sciences
Linear subspace
Functional Analysis (math.FA)
Mathematics - Functional Analysis
Combinatorics
Line (geometry)
FOS: Mathematics
0101 mathematics
Constant (mathematics)
Greedy algorithm
Analysis
Subspace topology
Mathematics
Subjects
Details
- ISSN :
- 00219045
- Volume :
- 251
- Database :
- OpenAIRE
- Journal :
- Journal of Approximation Theory
- Accession number :
- edsair.doi.dedup.....129c8b3eb3ff188f0bfe0d060146356b