In approximation theory, three classical types of results are direct theorems, Bernstein inequalities, and inverse theorems. In this paper, we include results about radial basis function (RBF) approximation from all three classes. Bernstein inequalities are a recent development in the theory of RBF approximation, and on Rd, only L2 results are known for RBFs with algebraically decaying Fourier transforms (e.g. the Sobolev splines and thin-plate splines). We will therefore extend what is known by establishing Lp Bernstein inequalities for RBF networks on Rd. These inequalities involve bounding a Bessel-potential norm of an RBF network by its corresponding Lp norm in terms of the separation radius associated with the network. While Bernstein inequalities have a variety of applications in approximation theory, they are most commonly used to prove inverse theorems. Therefore, using the Lp Bernstein inequalities for RBF approximants, we will establish the corresponding inverse theorems. The direct theorems of this paper relate to approximation in Lp(Rd) by RBFs which are perturbations of Green's functions. Results of this type are known for certain compact domains, and results have recently been derived for approximation in Lp(Rd) by RBFs that are Green's functions. Therefore, we will prove that known results for approximation in Lp(Rd) hold for a larger class of RBFs. We will then show how this result can be used to derive rates for approximation by Wendland functions.

La première partie de cette thèse introduit de nouveaux algorithmes de décomposition parcimonieuse de signaux. Basés sur Matching Pursuit (MP) ils répondent au problème suivant : comment réduire le temps de calcul de l'étape de sélection de MP, souvent très coûteuse. En réponse, nous sous-échantillonnons le dictionnaire à chaque itération, en lignes et en colonnes. Nous montrons que cette approche fondée théoriquement affiche de bons résultats en pratique. Nous proposons ensuite un algorithme itératif de descente de gradient par blocs de coordonnées pour sélectionner des caractéristiques en classification multi-classes. Celui-ci s'appuie sur l'utilisation de codes correcteurs d'erreurs transformant le problème en un problème de représentation parcimonieuse simultanée de signaux. La deuxième partie expose de nouvelles inégalités de concentration empiriques de type Bernstein. En premier, elles concernent la théorie des U-statistiques et sont utilisées pour élaborer des bornes en généralisation dans le cadre d'algorithmes de ranking. Ces bornes tirent parti d'un estimateur de variance pour lequel nous proposons un algorithme de calcul efficace. Ensuite, nous présentons une version empirique de l'inégalité de type Bernstein proposée par Freedman [1975] pour les martingales. Ici encore, la force de notre borne réside dans l'introduction d'un estimateur de variance calculable à partir des données. Cela nous permet de proposer des bornes en généralisation pour l'ensemble des algorithmes d'apprentissage en ligne améliorant l'état de l'art et ouvrant la porte à une nouvelle famille d'algorithmes d'apprentissage tirant parti de cette information empirique. / The first part of this thesis introduces new algorithms for the sparse encoding of signals. Based on Matching Pursuit (MP) they focus on the following problem : how to reduce the computation time of the selection step of MP. As an answer, we sub-sample the dictionary in line and column at each iteration. We show that this theoretically grounded approach has good empirical performances. We then propose a bloc coordinate gradient descent algorithm for feature selection problems in the multiclass classification setting. Thanks to the use of error-correcting output codes, this task can be seen as a simultaneous sparse encoding of signals problem. The second part exposes new empirical Bernstein inequalities. Firstly, they concern the theory of the U-Statistics and are applied in order to design generalization bounds for ranking algorithms. These bounds take advantage of a variance estimator and we propose an efficient algorithm to compute it. Then, we present an empirical version of the Bernstein type inequality for martingales by Freedman [1975]. Again, the strength of our result lies in the variance estimator computable from the data. This allows us to propose generalization bounds for online learning algorithms which improve the state of the art and pave the way to a new family of learning algorithms taking advantage of this empirical information.

Les travaux de recherche de cette thèse concernent l'encadrement de la constante de Markov Bernstein pour la norme L2 associée aux mesures de Jacobi et Gegenbauer généralisée. Ce travail est composé de deux parties : dans la première partie, nous avons développé une généralisation de l'algorithme qd pour les matrices symétriques définies positives à largeur de bande $\ell$ et nous avons construit l'algorithme qd pour les matrices de Jacobi par blocs. Ensuite, nous l'avons généralisé aux cas des matrices par bloc à largeur de bande $\ell$. Ces algorithmes nous permettent de trouver un majorant de la constante. Enfin, nous avons développé le déterminant caractéristique d'une matrice symétrique définie positive pentadiagonale, ce qui nous permet d'obtenir un minorant de la constante en utilisant la méthode de Newton. La deuxième partie est consacrée à l'application de tous les outils développés à l'encadrement de la constante de Markov Bernstein pour la norme L2 associée à la mesure de Gegenbauer généralisée. / The aim of this thesis is to find the lower and upper bounds of the constant whichappears in the Markov Bernstein inequalities in L2 norm associated to the Jacobiand generalized Gegenbauer measures. In this work the qd algorithm is studied forobtaining some properties about the asymptotic behavior of some eigenvalues ofband matrices and block band matrices. These eigenvalues are linked to the MarkovBernstein constant. The application of all the tools developed for obtaining lowerand upper bounds of the Markov Bernstein constant in L2 norm associated to thegeneralized Gegenbauer measure is given.

Ce travail est dédié à l’étude des inégalités de type Landau-Kolmogorov en normes L2. Les mesures utilisées sont celles d’Hermite, de Laguerre-Sonin et de Jacobi. Ces inégalités sont obtenues en utilisant une méthode variationnelle. Elles font intervenir la norme d’un polynômes p et celles de ces dérivées. Dans un premier temps, on s'intéresse aux inégalités en une variable réelle qui font intervenir un nombre quelconque de normes. Les constantes correspondantes sont prises dans le domaine où une certaine forme bilinéaire est définie positive. Ensuite, on généralise ces résultats aux polynômes à plusieurs variables réelles en utilisant le produit tensoriel dans L2 et en faisant intervenir au plus les dérivées partielles secondes. Pour les mesures d'Hermite et de Laguerre-Sonin, ces inégalités sont étendues à toutes les fonctions d'un espace de Sobolev. Pour la mesure de Jacobi on donne des inégalités uniquement pour les polynômes d'un degré fixé par rapport à chaque variable. / This thesis is devoted to Landau-Kolmogorov type inequalities in L2 norm. The measures which are used, are the Hermite, the Laguerre-Sonin and the Jacobi ones. These inequalities are obtained by using a variational method and the involved the square norms of a polynomial p and some of its derivatives. Initially, we focused on inequalities in one real variable that involve any number of norms. The corresponding constants are taken in the domain where a certain biblinear form is positive definite. Then we generalize these results to polynomials in several real variables using the tensor product in L2 and involving at most the second partial derivatives. For the Hermite and Laguerrre-Sonin cases, these inequalities are extended to all functions of a Sobolev space. For the Jacobi case inequalities are given only for polynomials of degree fixed with respect to each variable.