Positive semidefinite matrices arise in a variety of fields, including statistics, signal processing, and machine learning. Unfortunately, when these matrices are high-dimensional and/or must be operated upon many times, expensive calculations such as the spectral decomposition quickly become a computational bottleneck.
A common alternative is to replace the original positive semidefinite matrices with low-rank approximations whose spectral decompositions can be more easily computed. In this thesis, we develop approaches based on the Nyström method, which approximates a positive semidefinite matrix using a data-dependent orthogonal projection. As the Nyström approximation is conditioned on a given principal submatrix of its argument, it essentially recasts low-rank approximation as a subset selection problem.
We begin by deriving the Nyström approximation and developing a number of fundamental results, including new characterizations of its spectral properties and approximation error. We then address the problem of subset selection through a study of randomized sampling algorithms. We provide new bounds for the approximation error under uniformly random sampling, as well as bounds for two new data-dependent sampling methods. We continue by extending these results to random positive definite matrices, deriving statistics for the approximation error of matrices with Wishart and beta distributions, as well as for a broader class of orthogonally invariant and residual independent matrices.
Once this theoretical foundation has been established, we turn to practical applications of Nyström methods. We explore new exact and approximate sampling methods for randomized subset selection, and develop greedy approaches for subset optimization. We conclude by developing the Nyström approximation as a low-rank covariance estimator that provides for computationally efficient spectral analysis while shrinking the eigenvalues of the sample covariance. After deriving expressions for its bias and mean squared error, we illustrate the effectiveness of the Nyström covariance estimator through empirical examples in adaptive beamforming and image denoising.
|Advisor:||Wolfe, Patrick J.|
|School Location:||United States -- Massachusetts|
|Source:||DAI-B 72/09, Dissertation Abstracts International|
|Keywords:||High-dimentional data, Low-rank approximation, Matrix approximation, Nystrom extension, Positive semidefinite matrices|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be