CaltechTHESIS
  A Caltech Library Service

Topics in randomized numerical linear algebra

Citation

Gittens, Alex A. (2013) Topics in randomized numerical linear algebra. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechTHESIS:06102013-100609092

Abstract

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.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:numerical linear algebra; randomized numerical linear algebra; low-rank approximation; matrix laplace transform; randomized matrix sparsification
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Applied And Computational Mathematics
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Tropp, Joel A.
Thesis Committee:
  • Owhadi, Houman (chair)
  • Hassibi, Babak
  • Chandrasekaran, Venkat
  • Tropp, Joel A.
Defense Date:31 May 2013
Funders:
Funding AgencyGrant Number
ONRN00014-08-1-0883
ONRN00014-11-1-0025
AFOSRFA9550-09-1-0643
Sloan FellowshipUNSPECIFIED
ONRN00014-11-1002
DARPAN66001-08-1-2065
Record Number:CaltechTHESIS:06102013-100609092
Persistent URL:http://resolver.caltech.edu/CaltechTHESIS:06102013-100609092
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7880
Collection:CaltechTHESIS
Deposited By: Alex Gittens
Deposited On:14 Jan 2014 21:47
Last Modified:27 Jan 2014 18:14

Thesis Files

[img]
Preview
PDF (complete thesis) - Final Version
See Usage Policy.

2480Kb
[img]
Preview
PDF (front matter) - Final Version
See Usage Policy.

123Kb
[img]
Preview
PDF (ch1 (intro and contributions)) - Final Version
See Usage Policy.

186Kb
[img]
Preview
PDF (ch2 (eigenvalue bounds)) - Final Version
See Usage Policy.

318Kb
[img]
Preview
PDF (ch3 (sparsification)) - Final Version
See Usage Policy.

224Kb
[img]
Preview
PDF (ch4 (prelims for low-rank algs)) - Final Version
See Usage Policy.

170Kb
[img]
Preview
PDF (ch5 (fast low-rank approx)) - Final Version
See Usage Policy.

746Kb
[img]
Preview
PDF (ch6 (spsd sketching)) - Final Version
See Usage Policy.

1227Kb
[img]
Preview
PDF (bibliography) - Final Version
See Usage Policy.

210Kb

Repository Staff Only: item control page