Topics in randomized numerical linear algebra

This thesis studies three classes of randomized numerical linear algebra algorithms, namely: (i) randomized matrix sparsification algorithms, (ii) low-rank approximation algorithms that use randomized unitary transformations, and (iii) low-rank approximation algorithms for positive-semidefinite (PSD) matrices.

Randomized matrix sparsification algorithms set randomly chosen entries of the input matrix to zero. When the approximant is substituted for the original matrix in computations, its sparsity allows one to employ faster sparsity-exploiting algorithms. This thesis contributes bounds on the approximation error of nonuniform randomized sparsification schemes, measured in the spectral norm and two NP-hard norms that are of interest in computational graph theory and subset selection applications.

Low-rank approximations based on randomized unitary transformations have several desirable properties: they have low communication costs, are amenable to parallel implementation, and exploit the existence of fast transform algorithms. This thesis investigates the tradeoff between the accuracy and cost of generating such approximations. State-of-the-art spectral and Frobenius-norm error bounds are provided.

The last class of algorithms considered are SPSD "sketching" algorithms. Such sketches can be computed faster than approximations based on projecting onto mixtures of the columns of the matrix. The performance of several such sketching schemes is empirically evaluated using a suite of canonical matrices drawn from machine learning and data analysis applications, and a framework is developed for establishing theoretical error bounds.

In addition to studying these algorithms, this thesis extends the Matrix Laplace Transform framework to derive Chernoff and Bernstein inequalities that apply to all the eigenvalues of certain classes of random matrices. These inequalities are used to investigate the behavior of the singular values of a matrix under random sampling, and to derive convergence rates for each individual eigenvalue of a sample covariance matrix.

Brf1 post-transcriptionally regulates pluripotency and differentiation responses downstream of Erk MAP Kinase

FGF/Erk MAP Kinase Signaling is a central regulator of mouse embryonic stem cell (mESC) self-renewal, pluripotency and differentiation. However, the mechanistic connection between this signaling pathway activity and the gene circuits stabilizing mESCs in vitro remain unclear. Here we show that FGF signaling post-transcriptionally regulates the mESC transcription factor network by controlling the expression of Brf1 (zfp36l1), an AU-rich element mRNA binding protein. Changes in Brf1 level disrupts the expression of core pluripotency-associated genes and attenuates mESC self-renewal without inducing differentiation. These regulatory effects are mediated by rapid and direct destabilization of Brf1 targets, such as Nanog mRNA. Interestingly, enhancing Brf1 expression does not compromise mESC pluripotency, but does preferentially regulate differentiation to mesendoderm by accelerating the expression of primitive streak markers. Together, these studies demonstrate that FGF signals utilize targeted mRNA degradation by Brf1 to enable rapid post-transcriptional control of gene expression.

Sensitivity map of laser tweezers Raman spectroscopy for single-cell analysis of colorectal cancer

Raman spectroscopy on single, living epithelial cells captured in a laser trap is shown to have diagnostic power over colorectal cancer. This new single-cell technology comprises three major components: primary culture processing of human tissue samples to produce single-cell suspensions, Raman detection on singly trapped cells, and diagnoses of the cells by artificial neural network classifications. it is compared with DNA flow cytometry for similarities and differences. Its advantages over tissue Raman spectroscopy are also discussed. In the actual construction of a diagnostic model for colorectal cancer, real patient data were taken to generate a training set of 320 Raman spectra and, a test set of 80. By incorporating outlier corrections to a conventional binary neural classifier, our network accomplished significantly better predictions than logistic regressions, with sensitivity improved from 77.5% to 86.3% and specificity improved from 81.3% to 86.3% for the training set and moderate improvements for the test set. Most important, the network approach enables a sensitivity map analysis to quantitate the relevance of each Raman band to the normal-to-cancer transform at the cell level. Our technique has direct clinic applications for diagnosing cancers and basic science potential in the study of cell dynamics of carcinogenesis. (C) 2007 Society of Photo-Optical Instrumentation Engineers.