<div>It is a central problem in both statistics and computer science to understand the theoretical foundation of machine learning, especially deep learning. During the past decade, deep learning has achieved remarkable successes in solving many complex artificial intelligence tasks. The aim of this dissertation is to understand deep neural networks (DNNs) and other nonparametric methods in machine learning. In particular, three machine learning models have been studied: weight normalized DNNs, sparse DNNs, and the compositional nonparametric model.</div><div></div><div><br></div><div>The first chapter presents a general framework for norm-based capacity control for <i>L_p,q</i> weight normalized DNNs. We establish the upper bound on the Rademacher complexities of this family. Especially, with an <i>L_1,infty</i> normalization, we discuss properties of a width-independent capacity control, which only depends on the depth by a square root term. Furthermore, if the activation functions are anti-symmetric, the bound on the Rademacher complexity is independent of both the width and the depth up to a log factor. In addition, we study the weight normalized deep neural networks with rectified linear units (ReLU) in terms of functional characterization and approximation properties. In particular, for an <i>L_1,infty</i> weight normalized network with ReLU, the approximation error can be controlled by the <i>L₁</i> norm of the output layer.</div><div></div><div><br></div><div>In the second chapter, we study <i>L_1,infty</i>-weight normalization for deep neural networks with bias neurons to achieve the sparse architecture. We theoretically establish the generalization error bounds for both regression and classification under the <i>L_1,infty</i>-weight normalization. It is shown that the upper bounds are independent of the network width and <i>k^1/2</i>-dependence on the network depth <i>k</i>. These results provide theoretical justifications on the usage of such weight normalization to reduce the generalization error. We also develop an easily implemented gradient projection descent algorithm to practically obtain a sparse neural network. We perform various experiments to validate our theory and demonstrate the effectiveness of the resulting approach.</div><div></div><div><br></div><div>In the third chapter, we propose a compositional nonparametric method in which a model is expressed as a labeled binary tree of <i>2k+1</i> nodes, where each node is either a summation, a multiplication, or the application of one of the <i>q</i> basis functions to one of the <i>m₁</i> covariates. We show that in order to recover a labeled binary tree from a given dataset, the sufficient number of samples is <i>O(k </i>log<i>(m₁q)+</i>log<i>(k!))</i>, and the necessary number of samples is <i>Omega(k </i>log<i>(m₁q)-</i>log<i>(k!))</i>. We further propose a greedy algorithm for regression in order to validate our theoretical findings through synthetic experiments.</div>

Métodos tipo simplex são a base dos principais softwares utilizados na resolução de problemas de otimização linear. A implementação computacional direta destes métodos, assim como são descritos na teoria, leva a resultados indesejáveis na resolução de problemas reais de grande porte. Assim, a utilização de técnicas computacionais adequadas é fundamental para uma implementação eficiente e estável. Neste trabalho, as principais técnicas são discutidas, com enfoque naquelas que buscam proporcionar a estabilidade numérica do método: utilização de tolerâncias, estabilização do teste da razão, mudança de escala e representação da matriz básica. Para este último tópico, são apresentadas duas técnicas, a Forma Produto da Inversa e a Decomposição LU. A análise das abordagens é feita baseando-se na resolução dos problemas da biblioteca Netlib / Simplex-type methods are the basis of the main linear optimization solvers. The straightforward implementation of these methods as they are presented in theory yield unexpected results in solving reallife large-scale problems. Hence, it is essencial to use suitable computational techniques for an efficient and stable implementation. In this thesis, we address the main techniques focusing on those which aim for numerical stability of the method: use of tolerances, stable ratio test, scaling and representation of the basis matrix. For the latter topic, we present two techniques, the Product Form of Inverse and the LU decomposition. The Netlib problems are solved using the approaches addressed and the results are analyzed

Neuroimagiologia funcional é uma área da neurociência que visa o desenvolvimento de diversas técnicas para mapear a atividade do sistema nervoso e esteve sob constante desenvolvimento durante as últimas décadas devido à sua grande importância para aplicações clínicas e pesquisa. Técnicas usualmente utilizadas, como imagem por ressonância magnética functional (fMRI) e tomografia por emissão de pósitrons (PET) têm ótima resolução espacial (~ mm), mas uma resolução temporal limitada (~ s), impondo um grande desafio para nossa compreensão a respeito da dinâmica de funções cognitivas mais elevadas, cujas oscilações podem ocorrer em escalas temporais muito mais finas (~ ms). Tal limitação ocorre pelo fato destas técnicas medirem respostas biológicas lentas que são correlacionadas de maneira indireta com a atividade elétrica cerebral. As duas principais técnicas capazes de superar essa limitação são a Eletro- e Magnetoencefalografia (EEG/MEG), que são técnicas não invasivas para medir os campos elétricos e magnéticos no escalpo, respectivamente, gerados pelas fontes elétricas cerebrais. Ambas possuem resolução temporal na ordem de milisegundo, mas tipicalmente uma baixa resolução espacial (~ cm) devido à natureza mal posta do problema inverso eletromagnético. Um imenso esforço vem sendo feito durante as últimas décadas para melhorar suas resoluções espaciais através da incorporação de informação relevante ao problema de outras técnicas de imagens e/ou de vínculos biologicamente inspirados aliados ao desenvolvimento de métodos matemáticos e algoritmos sofisticados. Neste trabalho focaremos em EEG, embora todas técnicas aqui apresentadas possam ser igualmente aplicadas ao MEG devido às suas formas matemáticas idênticas. Em particular, nós exploramos esparsidade como uma importante restrição matemática dentro de uma abordagem Bayesiana chamada Aprendizagem Bayesiana Esparsa (SBL), que permite a obtenção de soluções únicas significativas no problema de reconstrução de fontes. Além disso, investigamos como incorporar diferentes estruturas como graus de liberdade nesta abordagem, que é uma aplicação de esparsidade estruturada e mostramos que é um caminho promisor para melhorar a precisão de reconstrução de fontes em métodos de imagens eletromagnéticos. / Functional Neuroimaging is an area of neuroscience which aims at developing several techniques to map the activity of the nervous system and has been under constant development in the last decades due to its high importance in clinical applications and research. Common applied techniques such as functional magnetic resonance imaging (fMRI) and positron emission tomography (PET) have great spatial resolution (~ mm), but a limited temporal resolution (~ s), which poses a great challenge on our understanding of the dynamics of higher cognitive functions, whose oscillations can occur in much finer temporal scales (~ ms). Such limitation occurs because these techniques rely on measurements of slow biological responses which are correlated in a complicated manner to the actual electric activity. The two major candidates that overcome this shortcoming are Electro- and Magnetoencephalography (EEG/MEG), which are non-invasive techniques that measure the electric and magnetic fields on the scalp, respectively, generated by the electrical brain sources. Both have millisecond temporal resolution, but typically low spatial resolution (~ cm) due to the highly ill-posed nature of the electromagnetic inverse problem. There has been a huge effort in the last decades to improve their spatial resolution by means of incorporating relevant information to the problem from either other imaging modalities and/or biologically inspired constraints allied with the development of sophisticated mathematical methods and algorithms. In this work we focus on EEG, although all techniques here presented can be equally applied to MEG because of their identical mathematical form. In particular, we explore sparsity as a useful mathematical constraint in a Bayesian framework called Sparse Bayesian Learning (SBL), which enables the achievement of meaningful unique solutions in the source reconstruction problem. Moreover, we investigate how to incorporate different structures as degrees of freedom into this framework, which is an application of structured sparsity and show that it is a promising way to improve the source reconstruction accuracy of electromagnetic imaging methods.

Dans le contexte général de la résolution de problèmes inverses en acoustique et traitement du signal audio les défis sont nombreux. Pour la résolution de ces problèmes, leur caractère souvent mal posé nécessite de considérer des modèles de signaux appropriés. Les travaux de cette thèse montrent sur la base d'un cadre algorithmique générique polyvalent comment les différentes formes de parcimonie (à l'analyse ou à la synthèse, simple, structurée ou sociale) sont particulièrement adaptées à la reconstruction de signaux sonores dans un cadre mono ou multicanal. Le cœur des travaux de thèse permet de mettre en évidence les limites des conditions d'évaluation de l'état de l'art pour le problème de désaturation et de mettre en place un protocole rigoureux d'évaluation à grande échelle pour identifier les méthodes les plus appropriées en fonction du contexte (musique ou parole, signaux fortement ou faiblement dégradés). On démontre des améliorations de qualité substantielles par rapport à l'état de l'art dans certains régimes avec des configurations qui n'avaient pas été précédemment considérées, nous obtenons également des accélérations conséquentes. Enfin, un volet des travaux aborde la localisation de sources sonores sous l'angle de l'apprentissage statistique « virtuellement supervisé ». On montre avec cette méthode des résultats encourageants sur l'estimation de directions d'arrivée et de distance. / Today's challenges in the context of audio and acoustic signal processing inverse problems are multiform. Addressing these problems often requires additional appropriate signal models due to their inherent ill-posedness. This work focuses on designing and evaluating audio reconstruction algorithms. Thus, it shows how various sparse models (analysis, synthesis, plain, structured or “social”) are particularly suited for single or multichannel audio signal reconstruction. The core of this work notably identifies the limits of state-of-the-art methods evaluation for audio declipping and proposes a rigourous large-scale evaluation protocol to determine the more appropriate methods depending on the context (music or speech, moderately or highly degraded signals). Experimental results demonstrate substantial quality improvements for some newly considered testing configurations. We also show computational efficiency of the different methods and considerable speed improvements. Additionally, a part of this work is dedicated to the sound source localization problem. We address it with a “virtually supervised” machine learning technique. Experiments show with this method promising results on distance and direction of arrival estimation.

La séparation de sources en aveugle (SSA) vise à rechercher des signaux sources inconnus et mélangés de manière inconnue au sein de plusieurs observations. Cette approche très générique et non-supervisée ne fournit cependant pas nécessairement des résultats exploitables. Il est alors nécessaire d’ajouter des contraintes, notamment physiques, afin de privilégier la recherche de sources ayant une structure particulière. La factorisation en matrices positives (non-negative matrix factorization, NMF) qui fait plus précisément l’objet de cette thèse recherche ainsi des sources positives observées au travers de mélanges linéaires positifs.L’ajout de davantage d’information reste cependant souvent nécessaire afin de pouvoir séparer les sources. Nous nous intéressons ainsi au concept de parcimonie qui permet d’améliorer le contraste entre celles-ci tout en produisant des approches très robustes, en particulier au bruit. Nous montrons qu’afin d’obtenir des solutions stables, les contraintes de positivité et la régularisation parcimonieuse doivent être appliqués de manière adéquate. Aussi, l’utilisation de la parcimonie dans un espace transformé potentiellement redondant, permettant de capturer la structure de la plu- part des signaux naturels, se révèle difficile à appliquer au côté de la contrainte de positivité dans l’espace direct. Nous proposons ainsi un nouvel algorithme de NMF parcimonieuse, appelé nGMCA (non-negative Generalized Morphological Component Analysis), qui surmonte ces difficultés via l’utilisation de techniques de calcul proximal. Des expérimentations sur des données simulées montrent que cet algorithme est robuste à une contamination par du bruit additif Gaussien, à l’aide d’une gestion automatique du paramètre de parcimonie. Des comparaisons avec des algorithmes de l’état-de-l’art en NMF sur des données réalistes montrent l’efficacité ainsi que la robustesse de l’approche proposée.Finalement, nous appliquerons nGMCA sur des données de chromatographie en phase liquide - spectrométrie de masse (liquid chromatography - mass spectrometry, LC-MS). L’observation de ces données montre qu’elles sont contaminées par du bruit multiplicatif, lequel détériore grandement les résultats des algorithmes de NMF. Une extension de nGMCA conçue pour prendre en compte ce type de bruit à l’aide d’un a priori non-stationnaire permet alors d’obtenir d’excellents résultats sur des données réelles annotées. / Blind source separation aims at extracting unknown source signals from observations where these sources are mixed together by an unknown process. However, this very generic and non-supervised approach does not always provide exploitable results. Therefore, it is often necessary to add more constraints, generally arising from physical considerations, in order to favor the recovery of sources with a particular sought-after structure. Non-negative matrix factorization (NMF), which is the main focus of this thesis, aims at searching for non-negative sources which are observed through non-negative linear mixtures.In some cases, further information still remains necessary in order to correctly separate the sources. Here, we focus on the sparsity concept, which helps improving the contrast between the sources, while providing very robust approaches, even when the data are contaminated by noise. We show that in order to obtain stable solutions, the non-negativity and sparse constraints must be applied adequately. In addition, using sparsity in a potentially redundant transformed domain could allow to capture the structure of most of natural image, but this kind of regularization proves difficult to apply together with the non-negativity constraint in the direct domain. We therefore propose a sparse NMF algorithm, named nGMCA (non-negative Generalized Morphological Component Analysis), which overcomes these difficulties by making use of proximal calculus techniques. Experiments on simulated data show that this algorithm is robust to additive Gaussian noise contamination, with an automatic control of the sparsity parameter. This novel algorithm also proves to be more efficient and robust than other state-of-the-art NMF algorithms on realistic data.Finally, we apply nGMCA on liquid chromatography - mass spectrometry data. Observation of these data show that they are contaminated by multiplicative noise, which greatly deteriorates the results of the NMF algorithms. An extension of nGMCA was designed to take into account this type of noise, thanks to the use of a non-stationary prior. This extension is then able to obtain excellent results on annotated real data.

Le développement de méthodes de décomposition de tableaux multi-dimensionnels suscite toujours autant d'attention, notamment d'un point de vue applicatif. La plupart des algorithmes, de décompositions tensorielles, existants requièrent une estimation du rang du tenseur et sont sensibles à une surestimation de ce dernier. Toutefois, une telle estimation peut être difficile par exemple pour des rapports signal à bruit faibles. D'un autre côté, estimer simultanément le rang et les matrices de facteurs du tenseur ou du tenseur cœur n'est pas tâche facile tant les problèmes de minimisation de rang sont généralement NP-difficiles. Plusieurs travaux existants proposent d'utiliser la norme nucléaire afin de servir d'enveloppe convexe de la fonction de rang. Cependant, la minimisation de la norme nucléaire engendre généralement un coût de calcul prohibitif pour l'analyse de données de grande taille. Dans cette thèse, nous nous sommes donc intéressés à l'approximation d'un tenseur bruité par un tenseur de rang faible. Plus précisément, nous avons étudié trois modèles de décomposition tensorielle, le modèle CPD (Canonical Polyadic Decomposition), le modèle BTD (Block Term Decomposition) et le modèle MTD (Multilinear Tensor Decomposition). Pour chacun de ces modèles, nous avons proposé une nouvelle méthode d'estimation de rang utilisant une métrique moins coûteuse exploitant la parcimonie de groupe. Ces méthodes de décomposition comportent toutes deux étapes : une étape d'estimation de rang, et une étape d'estimation des matrices de facteurs exploitant le rang estimé. Des simulations sur données simulées et sur données réelles montrent que nos méthodes présentent toutes une plus grande robustesse à la présence de bruit que les approches classiques. / Last decades, tensor decompositions have gained in popularity in several application domains. Most of the existing tensor decomposition methods require an estimating of the tensor rank in a preprocessing step to guarantee an outstanding decomposition results. Unfortunately, learning the exact rank of the tensor can be difficult in some particular cases, such as for low signal to noise ratio values. The objective of this thesis is to compute the best low-rank tensor approximation by a joint estimation of the rank and the loading matrices from the noisy tensor. Based on the low-rank property and an over estimation of the loading matrices or the core tensor, this joint estimation problem is solved by promoting group sparsity of over-estimated loading matrices and/or the core tensor. More particularly, three new methods are proposed to achieve efficient low rank estimation for three different tensors decomposition models, namely Canonical Polyadic Decomposition (CPD), Block Term Decomposition (BTD) and Multilinear Tensor Decomposition (MTD). All the proposed methods consist of two steps: the first step is designed to estimate the rank, and the second step uses the estimated rank to compute accurately the loading matrices. Numerical simulations with noisy tensor and results on real data the show effectiveness of the proposed methods compared to the state-of-the-art methods.

Cette thèse contribue à la recherche de méthodes de détection de signaux inconnus à très faible Rapport Signal-à-Bruit. Ce travail se concentre sur la définition, l’étude et la mise en œuvre de méthodes efficaces capables de discerner entre observations caractérisées seulement par du bruit de celles qui au contraire contiennent l’information d’intérêt supposée parcimonieuse. Dans la partie applicative, la pertinence de ces méthodes est évaluée sur des données hyperspectrales. Dans la première partie de ce travail, les principes à la base des tests statistiques d’hypothèses et un aperçu général sur les représentations parcimonieuses, l’estimation et la détection sont introduits. Dans la deuxième partie du manuscrit deux tests d’hypothèses statistiques sont proposés et étudiés, adaptés à la détection de signaux parcimonieux. Les performances de détection des tests sont comparés à celles de méthodes fréquentistes et Bayésiennes classiques. Conformément aux données tridimensionnelles considérées dans la partie applicative, et pour se rapprocher de scénarios plus réalistes impliquant des systèmes d’acquisition de données, les méthodes de détection proposées sont adaptées de façon à exploiter un modèle plus précis basé sur des dictionnaires qui prennent en compte l’effet d’étalement spatio-spectral de l’information causée par les fonctions d’étalement du point de l’instrument. Les tests sont finalement appliqués à des données astrophysiques massives de type hyperspectral dans le contexte du Multi Unit Spectroscopic Explorer de l’Observatoire Européen Austral. / This thesis deals with the problem of detecting unknown signals at low Signal- to- Noise Ratio. This work focuses on the definition, study and implementation of efficient methods able to discern only-noise observations from those that presumably carry the information of interest in a sparse way. The relevance of these methods is assessed on hyperspectral data as an applicative part. In the first part of this work, the basic principles of statistical hypothesis testing together with a general overview on sparse representations, estimation and detection are introduced. In the second part of the manuscript, two statistical hypotheses tests are proposed and studied. Both are adapted to the detection of sparse signals. The behaviors and the relative differences between the tests are theoretically investigated through a detailed study of their analytical and structural characteristics. The tests’ detection performances are compared with those of classical frequentist and Bayesian methods. According to the three-dimensional data sets considered in the applicative part, and to be closer to realistic scenarios involving data acquisition systems, the proposed detection strategies are then adapted in order to: i) account for spectrally variable noise; ii) exploit the spectral similarities of neighbors pixels in the spatial domain and iii) exploit the greater accuracy brought by dictionary-based models, which take into account the spatiospectral blur of information caused by instrumental Point Spread Functions. The tests are finally applied to massive astrophysical hyperspectral data in the context of the European Southern Observatory’s Multi Unit Spectroscopic Explorer.

Vibration-based structural health monitoring (SHM) seeks to detect, quantify, locate, and prognosticate damage by processing vibration signals measured while the structure is operational. The basic premise of vibration-based SHM is that damage will affect the stiffness, mass or energy dissipation properties of the structure and in turn alter its measured dynamic characteristics. In order to make SHM a practical technology it is necessary to perform damage assessment using only a minimum number of permanently installed sensors. Deducing damage at unmeasured regions of the structural domain requires solving an inverse problem that is underdetermined and(or) ill-conditioned. In addition, the effects of local damage on global vibration response may be overshadowed by the effects of modelling error, environmental changes, sensor noise, and unmeasured excitation. These theoretical and practical challenges render the damage identification inverse problem ill-posed, and in some cases unsolvable with conventional inverse methods. This dissertation proposes and tests a novel interpretation of the damage identification inverse problem. Since damage is inherently local and strictly reduces stiffness and(or) mass, the underdetermined inverse problem can be made uniquely solvable by either imposing sparsity or non-negativity on the solution space. The goal of this research is to leverage this concept in order to prove that damage identification can be performed in practical applications using significantly less measurements than conventional inverse methods require. This dissertation investigates two sparsity inducing methods, L1-norm optimization and the non-negative least squares, in their application to identifying damage from eigenvalues, a minimal sensor-based feature that results in an underdetermined inverse problem. This work presents necessary conditions for solution uniqueness and a method to quantify the bounds on the non-unique solution space. The proposed methods are investigated using a wide range of numerical simulations and validated using a four-story lab-scale frame and a full-scale 17 m long aluminum truss. The findings of this study suggest that leveraging the attributes of both L1-norm optimization and non-negative constrained least squares can provide significant improvement over their standalone applications and over other existing methods of damage detection.

Over the last two decades, dual-polarimetric weather radar has proven to be a valuable instrument providing critical precipitation information through remote sensing of the atmosphere. Modern weather radar systems operate with high sampling rates and long dwell times on targets. Often only limited target information is desired, leading to a pertinent question: could lesser samples have been acquired in the first place? Recently, a revolutionary sampling paradigm – compressed sensing (CS) – has emerged, which asserts that it is possible to recover signals from fewer samples or measurements than traditional methods require without degrading the accuracy of target information. CS methods have recently been applied to point target radars and imaging radars, resulting in hardware simplification advantages, enhanced resolution, and reduction in data processing overheads. But CS applications for volumetric radar targets such as precipitation remain relatively unexamined. This research investigates the potential applications of CS to radar remote sensing of precipitation. In general, weather echoes may not be sparse in space-time or frequency domain. Therefore, CS techniques developed for point targets, such as in aircraft surveillance radar, are not directly applicable to weather radars. However, precipitation samples are highly correlated both spatially and temporally. We, therefore, adopt latest advances in matrix completion algorithms to demonstrate the sparse sensing of weather echoes. Several extensions of this approach are then considered to develop a more general CS-based weather radar processing algorithms in presence of noise, ground clutter and dual-polarimetric data. Finally, a super-resolution approach is presented for the spectral recovery of an undersampled signal when certain frequency information is known.

Coronary artery disease (CAD) is one of the leading causes of death in the world. In the United States alone, it is estimated that approximately every 25 seconds, a new CAD event will occur, and approximately every minute, someone will die of one. The detection of CAD during in its early stages is very critical to reduce the mortality rates. Magnetic resonance imaging of myocardial perfusion (MR-MPI) has been receiving significant attention over the last decade due to its ability to provide a unique view of the microcirculation blood flow in the myocardial tissue through the coronary vascular network. The ability of MR-MPI to detect changes in microcirculation during early stages of ischemic events makes it a useful tool in identifying myocardial tissues that are alive but at the risk of dying. However this technique is not yet fully established clinically due to fundamental limitations imposed by the MRI device physics. The limitations of current MRI schemes often make it challenging to simultaneously achieve high spatio-temporal resolution, sufficient spatial coverage, and good image quality in myocardial perfusion MRI. Furthermore, the acquisitions are typically set up to acquire images during breath holding. This often results in motion artifacts due to improper breath hold patterns. This dissertation deals with developing novel image reconstruction methods in conjunction with non-Cartesian sampling for the reconstruction of dynamic MRI data from highly accelerated / under-sampled Fourier measurements. The reconstruction methods are based on adaptive signal models to represent the dynamic data using few model coefficients. Three novel adaptive reconstruction methods are developed and validated: (a) low rank and sparsity based modeling, (b) blind compressed sensing, and (c) motion compensated compressed sensing. The developed methods are applicable to a wide range of dynamic imaging problems. In the context of MR-MPI, this dissertation show feasibilities that the developed methods can enable free breathing myocardial perfusion MRI acquisitions with high spatio-temporal resolutions ( < 2mm x 2mm, 1 heart beat) and slice coverage (upto 8 slices).