Advanced Search

This paper is a survey of recent results on some problems of supervised learning in the setting formulated by Cucker and Smale. Supervised learning, or learning-from-examples, refers to a process that builds on the base of available data of inputs $x_i$ and outputs $y_i$, i = 1,...,m, a function that best represents the relation between the inputs x ∈ X and the corresponding outputs y ∈ Y. The goal is to find an estimator $f_z$ on the base of given data $z:=((x₁,y₁),...,(x_m,y_m))$ that approximates well the regression function $f_{\rho }$ of...

We study nonlinear m-term approximation in a Banach space with regard to a basis. It is known that in the case of a greedy basis (like the Haar basis in $L_p\left([0,1]\right)$, 1 < p < ∞) a greedy type algorithm realizes nearly best m-term approximation for any individual function. In this paper we generalize this result in two directions. First, instead of a greedy algorithm we consider a weak greedy algorithm. Second, we study in detail unconditional nongreedy bases (like the multivariate Haar basis ${}^d=\times ...\times$ in $L_p\left({[0,1]}^d\right)$,...

We study the following nonlinear method of approximation by trigonometric polynomials. For a periodic function f we take as an approximant a trigonometric polynomial of the form $Gₘ\left(f\right):={\sum }_{k\in \Lambda }f̂\left(k\right)e^{i(k,x)}$, where $\Lambda \subset {\mathbb{Z}}^d$ is a set of cardinality m containing the indices of the m largest (in absolute value) Fourier coefficients f̂(k) of the function f. Note that Gₘ(f) gives the best m-term approximant in the L₂-norm, and therefore, for each f ∈ L₂, ||f-Gₘ(f)||₂ → 0 as m → ∞. It is known from previous results that in the case of...

We consider convergence of thresholding type approximations with regard to general complete minimal systems eₙ in a quasi-Banach space X. Thresholding approximations are defined as follows. Let eₙ* ⊂ X* be the conjugate (dual) system to eₙ; then define for ε > 0 and x ∈ X the thresholding approximations as $T_{\epsilon }\left(x\right):={\sum }_{j\in D_{\epsilon }\left(x\right)}e{*}_j\left(x\right)e_j$, where $D_{\epsilon }\left(x\right):=j:|e{*}_j\left(x\right)|\ge \epsilon$. We study a generalized version of $T_{\epsilon }$ that we call the weak thresholding approximation. We modify the $T_{\epsilon }\left(x\right)$ in the following way. For ε > 0, t ∈ (0,1) we set $D_{t,\epsilon }\left(x\right):=j:t\epsilon \le |e{*}_j\left(x\right)|<\epsilon$ and consider the weak...

We study Lebesgue-type inequalities for greedy approximation with respect to quasi-greedy bases. We mostly concentrate on the $L_p$ spaces. The novelty of the paper is in obtaining better Lebesgue-type inequalities under extra assumptions on a quasi-greedy basis than known Lebesgue-type inequalities for quasi-greedy bases. We consider uniformly bounded quasi-greedy bases of $L_p$, 1 < p < ∞, and prove that for such bases an extra multiplier in the Lebesgue-type inequality can be taken as C(p)ln(m+1)....