abstract: This thesis considers the application of basis pursuit to several problems in system identification. After reviewing some key results in the theory of basis pursuit and compressed sensing, numerical experiments are presented that explore the application of basis pursuit to the black-box identification of linear time-invariant (LTI) systems with both finite (FIR) and infinite (IIR) impulse responses, temporal systems modeled by ordinary differential equations (ODE), and spatio-temporal systems modeled by partial differential equations (PDE). For LTI systems, the experimental results illustrate existing theory for identification of LTI FIR systems. It is seen that basis pursuit does not identify sparse LTI IIR systems, but it does identify alternate systems with nearly identical magnitude response characteristics when there are small numbers of non-zero coefficients. For ODE systems, the experimental results are consistent with earlier research for differential equations that are polynomials in the system variables, illustrating feasibility of the approach for small numbers of non-zero terms. For PDE systems, it is demonstrated that basis pursuit can be applied to system identification, along with a comparison in performance with another existing method. In all cases the impact of measurement noise on identification performance is considered, and it is empirically observed that high signal-to-noise ratio is required for successful application of basis pursuit to system identification problems. / Dissertation/Thesis / M.A. Mathematics 2012

Ce mémoire porte sur l'utilisation de dictionnaires en analyse et restauration d'images numériques. Nous nous sommes intéressés aux différents aspects mathématiques et pratiques de ce genre de méthodes: modélisation, analyse de propriétés de la solution d'un modèle, analyse numérique, apprentissage du dictionnaire et expérimentation. Après le Chapitre 1, qui retrace les étapes les plus significatives de ce domaine, nous présentons dans le Chapitre 2 notre implémentation et les résultats que nous avons obtenus avec le modèle consistant à résoudre \begin{equation}\label{tv-inf} \left\{\begin{array}{l} \min_{w} TV(w), \\ \mbox{sous les contraintes } |\PS{w-v}{\psi}|\leq \tau, \forall \psi \in \DD \end{array}\right. \end{equation} pour $v\in\RRN$, une donnée initiale, $\tau>0$, $TV(\cdot)$ la variation totale et un dictionnaire {\em invariant par translation} $\DD$. Le dictionnaire est, en effet, construit comme toutes les translations d'un ensemble $\FF$ d'éléments de $\RRN$ (des caractéristiques ou des patchs). L'implémentation de ce modèle avec ce genre de dictionnaire est nouvelle. (Les auteurs avaient jusque là considéré des dictionnaires de paquets d'ondelettes ou de curvelets.) La souplesse de la construction du dictionnaire a permis de conduire plusieurs expériences dont les enseignements sont rapportés dans les Chapitre 2 et 3. Les expériences du Chapitre 2 confirment que, pour obtenir de bons résultats en débruitage avec le modèle ci-dessus, le dictionnaire doit bien représenter la courbure des textures. Ainsi, lorsque l'on utilise un dictionnaire de Gabor, il vaut mieux utiliser des filtres de Gabor dont le support est isotrope (ou presque isotrope). En effet, pour représenter la courbure d'une texture ayant une fréquence donnée et vivant sur un support $\Omega$, il faut que le support, en espace, des filtres de Gabor permette un ``pavage'' avec peu d'éléments du support $\Omega$. Dans la mesure o\`{u}, pour une classe générale d'images, le support $\Omega$ est indépendant de la fréquence de la texture, le plus raisonnable est bien de choisir des filtres de Gabor dont le support est isotrope. Ceci est un argument fort en faveur des paquets d'ondelettes, qui permettent en plus d'avoir plusieurs tailles de supports en espace (pour une fréquence donnée) et pour lesquelles \eqref{tv-inf} peut être résolu rapidement. Dans le Chapitre 3 nous présentons des expériences dans lesquels le dictionnaire contient les courbures de formes connues (des lettres). Le terme d'attache aux données du modèle \eqref{tv-inf} autorise l'apparition dans le résidu $w^*-v$ de toutes les structures, sauf des formes ayant servi à construire le dictionnaire. Ainsi, on s'attend à ce que les forment restent dans le résultat $w^*$ et que les autres structures en soient absente. Nos expériences portent sur un problème de séparation de sources et confirment cette impression. L'image de départ contient des lettres (connues) sur un fond très structuré (une image). Nous montrons qu'il est possible, avec \eqref{tv-inf}, d'obtenir une séparation raisonnable de ces structures. Enfin ce travail met bien en évidence que le dictionnaire $\DD$ doit contenir la {\em courbure} des éléments que l'on cherche à préserver et non pas les éléments eux-mêmes, comme on pourrait le penser na\"{\i}vement. Le Chapitre 4 présente un travail dans lequel nous avons cherché à faire collaborer la méthode K-SVD avec le modèle \eqref{tv-inf}. Notre idée de départ est d'utiliser le fait que quelques itérations de l'algorithme qu'il utilise pour résoudre \eqref{tv-inf} permettent de faire réapparaître des structures absentes de l'image servant à l'initialisation de l'algorithme (et dont la courbure est présente dans le dictionnaire). Nous appliquons donc quelques une de ces itérations au résultat de K-SVD et retrouvons bien les textures perdues. Ceci permet un gain visuel et en PSNR. Dans le Chapitre 5, nous exposons un schéma numérique pour résoudre une variante du Basis Pursuit. Celle-ci consiste à appliquer un algorithme du point proximal à ce modèle. L'intérêt est de transformer un problème convexe non-différentiable en une suite (convergeant rapidement) de problèmes convexes très réguliers. Nous montrons la convergence théorique de l'algorithme. Celle-ci est confirmée par l'expérience. Cet algorithme permet d'améliorer considérablement la qualité (en terme de parcimonie) de la solution par rapport à l'état de l'art concernant la résolution pratique du Basis Pursuit. Nous nous espérons que cet algorithme devrait avoir un impact conséquent dans ce domaine en rapide développement. Dans le Chapitre 6, nous adapte aux cas d'un modèle variationnel, dont le terme régularisant est celui du Basis Pursuit et dont le terme d'attache aux données est celui du modèle \eqref{tv-inf}, un résultat de D. Donoho (voir [55]). Ce résultat montre que, sous une condition liant le dictionnaire définissant le terme régularisant au dictionnaire définissant le terme d'attache aux données, il est possible d'étendre les résultats de D. Donoho aux modèles qui nous intéressent dans ce chapitre. Le résultat obtenu dit que, si la donnée initiale est très parcimonieuse, la solution du modèle est proche de sa décomposition la plus parcimonieuse. Ceci garantie la stabilité du modèle dans ce cadre et fait un lien entre régularisation $l^1$ et $l^0$, pour ce type d'attache aux données. Le Chapitre 7 contient l'étude d'une variante du Matching Pursuit. Dans cette variante, nous proposons de réduire le produit scalaire avec l'élément le mieux corrélé au résidu, avant de modifier le résidu. Ceci pour une fonction de seuillage général. En utilisant des propriétés simples de ces fonctions de seuillage, nons montrons que l'algorithme ainsi obtenu converge vers la projection orthogonale de la donnée sur l'espace linéaire engendré par le dictionnaire (le tout modulo une approximation quantifiée par les caractéristiques de la fonction de seuillage). Enfin, sous une hypothèse faible sur la fonction de seuillage (par exemple le seuillage dur la satisfait), cet algorithme converge en un temps fini que l'on peut déduire des propriétés de la fonction de seuillage. Typiquement, cet algorithme peut-être utilisé pour faire les projections orthogonales dans l'algorithme ``Orthogonal Matching Pursuit''. Ceci nous n'avons pas encore été fait. Le Chapitre 8 explore enfin la problématique de l'apprentissage de dictionnaires. Le point de vue développé est de considerer cette problématique comme un problème d'estimation de paramètres dans une famille de modèles génératifs additifs. L'introduction de switchs aléatoires de Bernoulli activant ou désactivant chaque élément d'un dictionnaire invariant par translation à estimer en permet l'identification dans des conditions assez générales en particulier dans le cas o\`{u} les coefficients sont gaussiens. En utilisant une technique d'EM variationel et d'approximation de la loi a posteriori par champ moyen, nous dérivons d'un principe d'estimation par maximum de vraisemblance un nouvel algorithme effectif d'apprentissage de dictionaire que l'on peut apparenter pour certains aspects à l'algorithme K-SVD. Les résultats expérimentaux sur données synthétiques illustrent la possibilité d'une identification correcte d'un dictionaire source et de plusieurs applications en décomposition d'images et en débruitage.

Seismic inversion using a global optimization algorithm is a non-linear, model-driven process. It yields an optimal solution of the cost function – reflectivity/acoustic impedance, when prior information is sparse. The inversion result offers detailed interpretations of thin layers, internal stratigraphy, and lateral continuity and connectivity of sand bodies. This study compared two stable and robust global optimization techniques, Simulated Annealing (SA) and Basis Pursuit Inversion (BPI) as applied to post-stack seismic data from the Gulf of Mexico. Both methods use different routines and constraints to search for the minimum error energy function. Estimation of inversion parameters in SA is rigorous and more reliable because it depends on prior knowledge of subsurface geology. The BPI algorithm is a more robust deterministic process. It was developed as an alternative method to incorporating a priori information. Results for the Gulf of Mexico show that BPI gives a better stratigraphic and structural actualization due to its capacity to delineate layers thinner than the tuning thickness. The SA algorithm generates both absolute and relative impedances, which provide both qualitative and quantitative characterization of thin-bed reservoirs.

Constrained by practical and economical considerations, one often uses seismic data with missing traces. The use of such data results in image artifacts and poor spatial resolution. Sometimes due to practical limitations, measurements may be available on a perturbed grid, instead of on the designated grid. Due to algorithmic requirements, when such measurements are viewed as those on the designated grid, the recovery procedures may result in additional artifacts. This paper interpolates incomplete data onto regular grid via the Fourier domain, using a recently developed greedy algorithm. The basic objective is to study experimentally as to what could be the size of the perturbation in measurement coordinates that allows for the measurements on the perturbed grid to be considered as on the designated grid for faithful recovery. Our experimental work shows that for compressible signals, a uniformly distributed perturbation can be offset with slightly more number of measurements.

In a series of work initiated by Nemirovsky and Yudin, and later extended by Nesterov, first-order algorithms for unconstrained minimization with optimal theoretical complexity bound have been proposed. On the other hand, conjugate gradient algorithms as one of the widely used first-order techniques suffer from the lack of a finite complexity bound. In fact their performance can possibly be quite poor. This dissertation is partially on tightening the gap between these two classes of algorithms, namely the traditional conjugate gradient methods and optimal first-order techniques. We derive conditions under which conjugate gradient methods attain the same complexity bound as in Nemirovsky-Yudin's and Nesterov's methods. Moreover, we propose a conjugate gradient-type algorithm named CGSO, for Conjugate Gradient with Subspace Optimization, achieving the optimal complexity bound with the payoff of a little extra computational cost. We extend the theory of CGSO to convex problems with linear constraints. In particular we focus on solving $l_1$-regularized least square problem, often referred to as Basis Pursuit Denoising (BPDN) problem in the optimization community. BPDN arises in many practical fields including sparse signal recovery, machine learning, and statistics. Solving BPDN is fairly challenging because the size of the involved signals can be quite large; therefore first order methods are of particular interest for these problems. We propose a quasi-Newton proximal method for solving BPDN. Our numerical results suggest that our technique is computationally effective, and can compete favourably with the other state-of-the-art solvers.

Today's industry uses increasingly complex machines, some with extremely demanding performance criteria. Failed machines can lead to economic loss and safety problems due to unexpected production stoppages. Fault diagnosis in the condition monitoring of these machines is crucial for increasing machinery availability and reliability. Fault diagnosis of machinery is often a difficult and daunting task. To be truly effective, the process needs to be automated to reduce the reliance on manual data interpretation. It is the aim of this research to automate this process using data from machinery vibrations. This thesis focuses on the design, development, and application of an automatic diagnosis procedure for rolling element bearing faults. Rolling element bearings are representative elements in most industrial rotating machinery. Besides, these elements can also be tested economically in the laboratory using relatively simple test rigs. Novel modern signal processing methods were applied to vibration signals collected from rolling element tests to destruction. These included three advanced timefrequency signal processing techniques, best basis Discrete Wavelet Packet Analysis (DWPA), Matching Pursuit (MP), and Basis Pursuit (BP). This research presents the first application of the Basis Pursuit to successfully diagnosing rolling element faults. Meanwhile, Best basis DWPA and Matching Pursuit were also benchmarked with the Basis Pursuit, and further extended using some novel ideas particularly on the extraction of defect related features. The DWPA was researched in two aspects: i) selecting a suitable wavelet, and ii) choosing a best basis. To choose the most appropriate wavelet function and decomposition tree of best basis in bearing fault diagnostics, several different wavelets and decomposition trees for best basis determination were applied and comparisons made. The Matching Pursuit and Basis Pursuit techniques were effected by choosing a powerful wavelet packet dictionary. These algorithms were also studied in their ability to extract precise features as well as their speed in achieving a result. The advantage and disadvantage of these techniques for feature extraction of bearing faults were further evaluated. An additional contribution of this thesis is the automation of fault diagnosis by using Artificial Neural Networks (ANNs). Most of work presented in the current literature has been concerned with the use of a standard pre-processing technique - the spectrum. This research employed additional pre-processing techniques such as the spectrogram and DWPA based Kurtosis, as well as the MP and BP features that were subsequently incorporated into ANN classifiers. Discrete Wavelet Packets and Spectra, were derived to extract features by calculating RMS (root mean square), Crest Factor, Variance, Skewness, Kurtosis, and Matched Filter. Certain spikes in Matching Pursuit analysis and Basis Pursuit analysis were also used as features. These various alternative methods of pre-processing for feature extraction were tested, and evaluated with the criteria of the classification performance of Neural Networks. Numerous experimental tests were conducted to simulate the real world environment. The data were obtained from a variety of bearings with a series of fault severities. The mechanism of bearing fault development was analysed and further modelled to evaluate the performance of this research methodology. The results of the researched methodology are presented, discussed, and evaluated in the results and discussion chapter of this thesis. The Basis Pursuit technique proved to be effective in diagnostic tasks. The applied Neural Network classifiers were designed as multi layer Feed Forward Neural Networks. Using these Neural Networks, automatic diagnosis methods based on spectrum analysis, DWPA, Matching Pursuit, and Basis Pursuit proved to be effective in diagnosing different conditions such as normal bearings, bearings with inner race and outer race faults, and rolling element faults, with high accuracy. Future research topics are proposed in the final chapter of the thesis to provide perspectives and suggestions for advancing research into fault diagnosis and condition monitoring.

We study a scalable approach to information fusion for large sensor networks. The algorithm, field inversion by consensus and compressed sensing (FICCS), is a distributed method for detection, localization, and estimation of a propagating field generated by an unknown number of point sources. The approach combines results in the areas of distributed average consensus and compressed sensing to form low dimensional linear projections of all sensor readings throughout the network, allowing each node to reconstruct a global estimate of the field. Compressed sensing is applied to continuous source localization by quantizing the potential locations of sources, transforming the model of sensor observations to a finite discretized linear model. We study the effects of structured modeling errors induced by spatial quantization and the robustness of ℓ1 penalty methods for field inversion. We develop a perturbations method to analyze the effects of spatial quantization error in compressed sensing and provide a model-robust version of noise-aware basis pursuit with an upperbound on the sparse reconstruction error. Numerical simulations illustrate system design considerations by measuring the performance of decentralized field reconstruction, detection performance of point phenomena, comparing trade-offs of quantization parameters, and studying various sparse estimators. The method is extended to time-varying systems using a recursive sparse estimator that incorporates priors into ℓ1 penalized least squares. This thesis presents the advantages of inter-sensor measurement mixing as a means of efficiently spreading information throughout a network, while identifying sparse estimation as an enabling technology for scalable distributed field reconstruction systems.

Chen, Donoho a Saunders (1998) studují problematiku hledání řídké reprezentace vektorů (signálů) s použitím speciálních přeurčených systémů vektorů vyplňujících prostor signálu. Takovéto systémy (někdy jsou také nazývány frejmy) jsou typicky vytvořeny buď rozšířením existující báze, nebo sloučením různých bazí. Narozdíl od vektorů, které tvoří konečně rozměrné prostory, může být problém formulován i obecněji v rámci nekonečně rozměrných separabilních Hilbertových prostorů (Veselý, 2002b; Christensen, 2003). Tento funkcionální přístup nám umožňuje nacházet v těchto prostorech přesnější reprezentace objektů, které, na rozdíl od vektorů, nejsou diskrétní. V této disertační práci se zabývám hledáním řídkých representací v přeurčených modelech časových řad náhodných veličin s konečnými druhými momenty. Numerická studie zachycuje výhody a omezení tohoto přístupu aplikovaného na zobecněné lineární modely a na vícerozměrné ARMA modely. Analýzou mnoha numerických simulací i modelů reálných procesů můžeme říci, že tyto metody spolehlivě identifikují parametry blízké nule, a tak nám umožňují redukovat původně špatně podmíněný přeparametrizovaný model. Tímto významně redukují počet odhadovaných parametrů. V konečném důsledku se tak nemusíme starat o řády modelů, jejichž zjišťování je většinou předběžným krokem standardních technik. Pro kratší časové řady (100 a méně vzorků) řídké odhady dávají lepší predikce v porovnání s těmi, které jsou založené na standardních metodách (např. maximální věrohodnosti v MATLABu - MATLAB System Identification Toolbox (IDENT)). Pro delší časové řady (500 a více) obě techniky dávají v podstatě stejně přesné predikce. Na druhou stranu řešení těchto problémů je náročnější, a to i časově, nicméně výpočetní doba je stále přijatelná.

Considérons un vecteur gaussien Y de loi N (m,sigma²Idn) et X une matrice de dimension n x p avec Y observé, m inconnu, Sigma et X connus. Dans le cadre du modèle linéaire, m est supposé être une combinaison linéaire des colonnes de X. En petite dimension, lorsque n ≥ p et que ker (X) = 0, il existe alors un unique paramètre Beta* tel que m = X Beta* ; on peut alors réécrire Y sous la forme Y = X Beta* + Epsilon. Dans le cadre du modèle linéaire gaussien en petite dimension, nous construisons une nouvelle procédure de tests multiples contrôlant le FWER pour tester les hypothèses nulles Beta*i = 0 pour i appartient à [[1,p]]. Cette procédure est appliquée en métabolomique au travers du programme ASICS qui est disponible en ligne. ASICS permet d'identifier et de quantifier les métabolites via l'analyse des spectres RMN. En grande dimension, lorsque n < p on a ker (X) ≠ 0, ainsi le paramètre Beta* décrit précédemment n'est pas unique. Dans le cas non bruité lorsque Sigma = 0, impliquant que Y = m, nous montrons que les solutions du système linéaire d'équations Y = X Beta avant un nombre de composantes non nulles minimales s'obtiennent via la minimisation de la "norme" lAlpha avec Alpha suffisamment petit. / Let Y be a Gaussian vector distributed according to N (m,sigma²Idn) and X a matrix of dimension n x p with Y observed, m unknown, sigma and X known. In the linear model, m is assumed to be a linear combination of the columns of X In small dimension, when n ≥ p and ker (X) = 0, there exists a unique parameter Beta* such that m = X Beta*; then we can rewrite Y = Beta* + Epsilon. In the small-dimensional linear Gaussian model framework, we construct a new multiple testing procedure controlling the FWER to test the null hypotheses Beta*i = 0 for i belongs to [[1,p]]. This procedure is applied in metabolomics through the freeware ASICS available online. ASICS allows to identify and to qualify metabolites via the analyse of RMN spectra. In high dimension, when n < p we have ker (X) ≠ 0 consequently the parameter Beta* described above is no longer unique. In the noiseless case when Sigma = 0, implying thus Y = m, we show that the solutions of the linear system of equation Y = X Beta having a minimal number of non-zero components are obtained via the lalpha with alpha small enough.

Exploiting signal sparsity has recently received considerable attention in a variety of areas including signal and image processing, compressive sensing, machine learning and so on. Many of these applications involve optimization models that are regularized by certain sparsity-promoting metrics. Two most popular regularizers are based on the l1 norm that approximates sparsity of vectorized signals and the total variation (TV) norm that serves as a measure of gradient sparsity of an image. Nevertheless, the l1 and TV terms are merely two representative measures of sparsity. To explore the matter of sparsity further, in this thesis we investigate relaxations of the regularizers to nonconvex terms such as lp and TVp "norms" with 0 <= p < 1. The contributions of the thesis are two-fold. First, several methods to approach globally optimal solutions of related nonconvex problems for improved signal/image reconstruction quality have been proposed. Most algorithms studied in the thesis fall into the category of iterative reweighting schemes for which nonconvex problems are reduced to a series of convex sub-problems. In this regard, the second main contribution of this thesis has to do with complexity improvement of the l1/TV-regularized methodology for which accelerated algorithms are developed. Along with these investigations, new techniques are proposed to address practical implementation issues. These include the development of an lp-related solver that is easily parallelizable, and a matrix-based analysis that facilitates implementation for TV-related optimizations. Computer simulations are presented to demonstrate merits of the proposed models and algorithms as well as their applications for solving general linear inverse problems in the area of signal and image denoising, signal sparse representation, compressive sensing, and compressive imaging. / Graduate