Low-rank tensor representations can provide highly compressed approximations of functions. These concepts, which essentially amount to generalizations of classical techniques of separation of variables, have proved to be particularly fruitful for functions of many variables. We focus here on problems where the target function is given only implicitly as the solution of a partial differential equation. A first natural question is under which conditions we should expect such solutions to be efficiently approximated in low-rank form. Due to the highly nonlinear nature of the resulting low-rank approximations, a crucial second question is at what expense such approximations can be computed in practice. This article surveys basic construction principles of numerical methods based on low-rank representations as well as the analysis of their convergence and computational complexity.

The purpose of this paper is to quantify the size of the Lebesgue constants $(\boldsymbol {L}_m)_{m=1}^{\infty }$ associated with the thresholding greedy algorithm in terms of a new generation of parameters that modulate accurately some features of a general basis. This fine tuning of constants allows us to provide an answer to the question raised by Temlyakov in 2011 to find a natural sequence of greedy-type parameters for arbitrary bases in Banach (or quasi-Banach) spaces which combined linearly with the sequence of unconditionality parameters $(\boldsymbol {k}_m)_{m=1}^{\infty }$ determines the growth of $(\boldsymbol {L}_m)_{m=1}^{\infty }$ . Multiple theoretical applications and computational examples complement our study.

We study sparse approximation by greedy algorithms. We prove the Lebesgue-type inequalities for the weak Chebyshev greedy algorithm (WCGA), a generalization of the weak orthogonal matching pursuit to the case of a Banach space. The main novelty of these results is a Banach space setting instead of a Hilbert space setting. The results are proved for redundant dictionaries satisfying certain conditions. Then we apply these general results to the case of bases. In particular, we prove that the WCGA provides almost optimal sparse approximation for the trigonometric system in $L_p$, $2\le p<\infty $.

We prove sufficient and necessary conditions for compactness of the Sobolev embeddings of Besov and Triebel–Lizorkin spaces defined on bounded and unbounded uniformly E-porous domains. The asymptotic behaviour of the corresponding entropy numbers is calculated. Some applications to the spectral properties of elliptic operators are described.

Let ${{B}_{p}}$ be the unit ball in ${{\mathbb{L}}_{p}}$ , $0\,<\,p\,<\,1$, and let $\Delta _{+}^{s}$ , $s\,\in \,\mathbb{N}$, be the set of all $s$-monotone functions on a finite interval $I$, i.e., $\Delta _{+}^{s}$ consists of all functions $x\,:\,I\,\mapsto \,\mathbb{R}$ such that the divided differences $[x;\,{{t}_{0}},\,...\,,\,{{t}_{s}}]$ of order $s$ are nonnegative for all choices of $\left( s\,+\,1 \right)$ distinct points ${{t}_{0}},\,.\,.\,.\,,{{t}_{s}}\,\in \,I.$ For the classes $\Delta _{+}^{s}{{B}_{P}}\,:=\,\Delta _{+}^{s}\,\cap \,{{B}_{P}},$ we obtain exact orders of Kolmogorov, linear and pseudo-dimensional widths in the spaces ${{\mathbb{L}}_{q}},$$0\,<\,q\,<\,p\,<\,1$:

$${{d}_{n}}(\Delta _{+}^{s}{{B}_{P}})_{{{\mathbb{L}}_{q}}}^{\text{psd}}\asymp {{d}_{n}}(\Delta _{+}^{s}{{B}_{P}})_{{{\mathbb{L}}_{q}}}^{\text{kol}}\asymp {{d}_{n}}(\Delta _{+}^{s}{{B}_{P}})_{{{\mathbb{L}}_{q}}}^{\text{lin}}\asymp {{n}^{-s}}.$$

The aim of this paper is to provide an analysis of non-linear approximation in the $L_p$-norm $p = d / (d - 1)$ of functions of bounded variation on $\mathbb{R}^d$ with $d > 1$ by polynomials in the Haar system. The exponent $p$ is the natural exponent as it is the correct exponent in the Sobolev inequality. The approximation schemes that we discuss in this paper are mostly related to Haar thresholding and $m$-term approximation. These problems for $d = 2$ are studied in detail in a paper by Cohen, DeVore, Petrushev and Xu. The main aim of this paper is to extend their results to the case $d \geq 2$.

We obtain the optimal order of the $m$-term Haar approximation and prove the stability of Haar thresholding in the BV-norm. As one of the main tools, we establish the boundedness of certain averaging projections in BV.

We study the asymptotic behavior of the n-widths of a class of entire functions in weighted approximation on subsets of the complex plane.