In the first part of the paper we study absolute error of sampling discretization of the integral L p -norm for function classes of continuous functions. We use basic approaches from chaining technique to provide general upper bounds for the error of sampling discretization of the L p -norm on a given function class in terms of entropy numbers in the uniform norm of this class. As an example we apply these general results to obtain new error bounds for sampling discretization of the L p -norms on classes of multivariate functions with mixed smoothness. In the second part of the paper we apply our general bounds to study the problem of universal sampling discretization.

We study sparse approximation by greedy algorithms. Our contribution is twofold. First, we prove exact recovery with high probability of random K-sparse signals within ΓK(1+ε)l iterations of the orthogonal matching pursuit (OMP). This result shows that in a probabilistic sense, the OMP is almost optimal for exact recovery. Second, we prove the Lebesgue-type inequalities for the weak Chebyshev greedy algorithm, 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. However, even in the case of a Hilbert space, our results add some new elements to known results on the Lebesgue-type inequalities for the restricted isometry property dictionaries. Our technique is a development of the recent technique created by Zhang.

We study sparse representations and sparse approximations with respect to incoherent dictionaries. We address the problem of designing and analyzing greedy methods of approximation. A key question in this regard is: How to measure efficiency of a specific algorithm? Answering this question, we prove the Lebesgue-type inequalities for algorithms under consideration. A very important new ingredient of the paper is that we perform our analysis in a Banach space instead of a Hilbert space. It is known that in many numerical problems, users are satisfied with a Hilbert space setting and do not consider a more general setting in a Banach space. There are known arguments that justify interest in Banach spaces. In this paper, we give one more argument in favor of consideration of greedy approximation in Banach spaces. We introduce a concept of$M$-coherent dictionary in a Banach space which is a generalization of the corresponding concept in a Hilbert space. We analyze the quasi-orthogonal greedy algorithm (QOGA), which is a generalization of the orthogonal greedy algorithm (orthogonal matching pursuit) for Banach spaces. It is known that the QOGA recovers exactly$S$-sparse signals after$S$iterations provided$S< (1+1/M)/2$. This result is well known for the orthogonal greedy algorithm in Hilbert spaces. The following question is of great importance: Are there dictionaries in$\BBR^{n}$such that their coherence in$\ell_{p}^{n}$is less than their coherence in$\ell_{2}^{n}$for some$p\in (1,\infty)$? We show that the answer to the above question is “yes.” Thus, for such dictionaries, replacing the Hilbert space$\ell_{2}^{n}$by a Banach space$\ell_{p}^{n}$, we improve an upper bound for sparsity that guarantees an exact recovery of a signal.

The general theory of greedy approximation is well developed. Much less is known about how specific features of a dictionary can be used to our advantage. In this paper, we discuss incoherent dictionaries. We build a new greedy algorithm which is called the orthogonal super greedy algorithm (OSGA). We show that the rates of convergence of OSGA and the orthogonal matching pursuit (OMP) with respect to incoherent dictionaries are the same. Based on the analysis of the number of orthogonal projections and the number of iterations, we observed that OSGA is times simpler (more efficient) than OMP. Greedy approximation is also a fundamental tool for sparse signal recovery. The performance of orthogonal multimatching pursuit, a counterpart of OSGA in the compressed sensing setting, is also analyzed under restricted isometry property conditions.

Overcomplete representations are attracting interest in signal processing theory, particularly due to their potential to generate sparse representations of signals. However, in general, the problem of finding sparse representations must be unstable in the presence of noise. This paper establishes the possibility of stable recovery under a combination of sufficient sparsity and favorable structure of the overcomplete system. Considering an ideal underlying signal that has a sufficiently sparse representation, it is assumed that only a noisy version of it can be observed. Assuming further that the overcomplete system is incoherent, it is shown that the optimally sparse approximation to the noisy data differs from the optimally sparse decomposition of the ideal noiseless signal by at most a constant multiple of the noise level. As this optimal-sparsity method requires heavy (combinatorial) computational effort, approximation algorithms are considered. It is shown that similar stability is also available using the basis and the matching pursuit algorithms. Furthermore, it is shown that these methods result in sparse approximation of the noisy data that contains only terms also appearing in the unique sparsest representation of the ideal noiseless sparse signal.

This paper is concerned with the construction and analysis of a universal estimator for the regression problem in supervised learning. Universal means that the estimator does not depend on any a priori assumptions about the regression function to be estimated. The universal estimator studied in this paper consists of a least-square fitting procedure using piecewise constant functions on a partition which depends adaptively on the data. The partition is generated by a splitting procedure which differs from those used in CART algorithms. It is proven that this estimator performs at the optimal convergence rate for a wide class of priors on the regression function. Namely, as will be made precise in the text, if the regression function is in any one of a certain class of approximation spaces (or smoothness spaces of order not exceeding one -- a limitation resulting because the estimator uses piecewise constants) measured relative to the marginal measure, then the estimator converges to the regression function (in the least squares sense) with an optimal rate of convergence in terms of the number of samples. The estimator is also numerically feasible and can be implemented on-line.