The Rasch sampler is an efficient algorithm to sample binary matrices with given marginal sums. It is a Markov chain Monte Carlo (MCMC) algorithm. The program can handle matrices of up to 1024 rows and 64 columns. A special option allows to sample square matrices with given marginals and fixed main diagonal, a problem prominent in social network analysis. In all cases the stationary distribution is uniform. The user has control on the serial dependency. (authors' abstract)

Compressed Sensing (CS) is an emerging paradigm in which signals are recovered from undersampled nonadaptive linear measurements taken at a rate proportional to the signal's true information content as opposed to its ambient dimension. The resulting problem consists in finding a sparse solution to an underdetermined system of linear equations. It has now been established, both theoretically and empirically, that certain optimization algorithms are able to solve such problems. Iterative Hard Thresholding (IHT) (Blumensath and Davies, 2007), which is the focus of this thesis, is an established CS recovery algorithm which is known to be effective in practice, both in terms of recovery performance and computational efficiency. However, theoretical analysis of IHT to date suffers from two drawbacks: state-of-the-art worst-case recovery conditions have not yet been quantified in terms of the sparsity/undersampling trade-off, and also there is a need for average-case analysis in order to understand the behaviour of the algorithm in practice. In this thesis, we present a new recovery analysis of IHT, which considers the fixed points of the algorithm. In the context of arbitrary matrices, we derive a condition guaranteeing convergence of IHT to a fixed point, and a condition guaranteeing that all fixed points are 'close' to the underlying signal. If both conditions are satisfied, signal recovery is therefore guaranteed. Next, we analyse these conditions in the case of Gaussian measurement matrices, exploiting the realistic average-case assumption that the underlying signal and measurement matrix are independent. We obtain asymptotic phase transitions in a proportional-dimensional framework, quantifying the sparsity/undersampling trade-off for which recovery is guaranteed. By generalizing the notion of xed points, we extend our analysis to the variable stepsize Normalised IHT (NIHT) (Blumensath and Davies, 2010). For both stepsize schemes, comparison with previous results within this framework shows a substantial quantitative improvement. We also extend our analysis to a related algorithm which exploits the assumption that the underlying signal exhibits tree-structured sparsity in a wavelet basis (Baraniuk et al., 2010). We obtain recovery conditions for Gaussian matrices in a simplified proportional-dimensional asymptotic, deriving bounds on the oversampling rate relative to the sparsity for which recovery is guaranteed. Our results, which are the first in the phase transition framework for tree-based CS, show a further significant improvement over results for the standard sparsity model. We also propose a dynamic programming algorithm which is guaranteed to compute an exact tree projection in low-order polynomial time.

Thesis (MSc (Physics))--University of Stellenbosch, 2005. / It was Wigner that in the 1950’s first introduced the idea of modelling physical reality with an ensemble of random matrices while studying the energy levels of heavy atomic nuclei. Since then, the field of Random Matrix Theory has grown tremendously, with applications ranging from fluctuations on the economic markets to M-theory. It is the purpose of this thesis to discuss the basic concepts of Random Matrix Theory, using the ensembles of random matrices originally introduced by Wigner, the Gaussian ensembles, as a starting point. As Random Matrix Theory is classically concerned with the statistical properties of levels sequences, we start with a brief introduction to the statistical analysis of a level sequence before getting to the introduction of the Gaussian ensembles. With the ensembles defined, we move on to the statistical properties that they predict. In the light of these predictions, a few of the classical applications of Random Matrix Theory are discussed, and as an example of some of the important concepts, the Anderson model of localization is investigated in some detail.

published_or_final_version / Electrical and Electronic Engineering / Doctoral / Doctor of Philosophy

Please download this dissertation to see the abstract.

Diagonally dominant matrices arise in many applications. In this work, we exploit the structure of diagonally dominant matrices to provide sharp entrywise relative perturbation bounds. We first generalize the results of Dopico and Koev to provide relative perturbation bounds for the LDU factorization with a well conditioned L factor. We then establish relative perturbation bounds for the inverse that are entrywise and independent of the condition number. This allows us to also present relative perturbation bounds for the linear system Ax=b that are independent of the condition number. Lastly, we continue the work of Ye to provide relative perturbation bounds for the eigenvalues of symmetric indefinite matrices and non-symmetric matrices.

Cette thèse traite essentiellement de deux systèmes intégrables associés à des algèbres de Lie simples. Les deux résultats principaux sont la construction et l'intégrabilité au sens de Liouville des réseaux de 2-Toda et de Full Kostant-Toda périodique sur toute algèbre de Lie simple. Ces réseaux sont l'un et l'autre décrit par un champ hamiltonien associé à un crochet de Poisson qui provient d'une algèbre de Lie munie d'une R-matrice. Nous construisons dans les deux cas une grande famille de constantes de mouvement que nous utilisons pour démontrer l'intégrabilité au sens de Liouville des deux systèmes. Nos constructions et nos démonstrations font appel à de nombreux résultats sur les algèbres de Lie simples, leurs R-matrices, leurs fonctions Ad-invariantes et leurs systèmes de racines.

Nous proposons de traiter l'extraction de la mélodie principale, ainsi que la séparation de l'instrument jouant cette mélodie. La première tâche appartient au domaine de la recherche d'information musicale (MIR) : nous cherchons à indexer les morceaux de musique à l'aide de leur mélodie. La seconde application est la séparation aveugle de sources sonores (BASS) : extraire une piste audio pour chaque source présente dans un mélange sonore. La séparation de la mélodie principale et de l'accompagnement et l'extraction de cette mélodie sont traitées au sein d'un même cadre statistique. Le modèle pour l'instrument principal est un modèle de production source/filtre. Il suppose deux états cachés correspondant à l'état du filtre et de la source. Le modèle spectral choisi permet de prendre compte les fréquences fondamentales de l'instrument désiré et de séparer ce dernier de l'accompagnement. Deux modèles de signaux sont proposés, un modèle de mélange de gaussiennes amplifiées (GSMM) et un modèle de mélange instantané (IMM). L'accompagnement est modélisé par un modèle spectral plus général. Cinq systèmes sont proposés, trois systèmes fournissent la mélodie sous forme de séquence de fréquences fondamentales, un système fournit les notes de la mélodie et le dernier système sépare l'instrument principal de l'accompagnement. Les résultats en estimation de la mélodie et en séparation sont du niveau de l'état de l'art, comme l'ont montré nos participations aux évaluations internationales (MIREX'08, MIREX'09 et SiSEC'08). Nous avons ainsi réussi à intégrer de la connaissance musicale améliorant les résultats de travaux antérieurs sur la séparation de sources sonores.

L'imagerie optique de fluorescence permet de localiser des cibles biologiques comme des tumeurs, marquées par des fluorophores. Pour des applications au diagnostic chez l'Homme où l'épaisseur des tissus atteint plusieurs centimètres, la détection parasite de l'autofluorescence naturelle des tissus compromet la détection de la fluorescence d'intérêt et son élimination est la condition sine qua non d'une localisation correcte de la tumeur. L'objet de cette thèse a été l'étude spectrale de l'auto fluorescence des tissus et la mise au point d'une méthode de séparation de spectres aveugle permettant de supprimer sa contribution des mesures. La Factorisation en Matrices Non-négatives a été privilégiée, et de nouveaux algorithmes ont été proposés et testés sur données réelles. Nous avons démontré les performances de notre méthode dans l'amélioration de la détection des marqueurs et la reconstruction de la position de la tumeur en tomographie optique diffuse de fluorescence.

Cette thèse porte sur certaines familles à un paramètre de surfaces de Riemann compactes de genre 2 définies par des surfaces de translation. Les familles que nous considérons constituent des géodésiques de Teichmüller dans l'espace des modules. Nous nous attachons en particulier à décrire ces surfaces par leurs matrices des périodes et par les équations des courbes algébriques associées. Nous étudions notamment les automorphismes admissibles par les surfaces qui sont des courbes réelles à trois composantes réelles dans ces familles. Le principal résultat consiste en une caractérisation explicite des matrices des périodes des courbes réelles à trois composantes réelles appartenant à la famille obtenue par projection dans l'espace des modules de la SL(2,R)-orbite de la surface de translation en "L" pavée par trois carreaux. Nous montrons enfin, grâce à une interprétation en termes de transformations de Schwarz-Christoffel, comment calculer numériquement une équation de la courbe algébrique définie par une surface de translation en "L".