Sampling-based algorithms for dimension reduction
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2007.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2007
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/38935 |
| _version_ | 1826197827453190144 |
|---|---|
| author | Deshpande, Amit Jayant |
| author2 | Santosh S. Vempala and Daniel A. Spielman. |
| author_facet | Santosh S. Vempala and Daniel A. Spielman. Deshpande, Amit Jayant |
| author_sort | Deshpande, Amit Jayant |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2007. |
| first_indexed | 2024-09-23T10:54:26Z |
| format | Thesis |
| id | mit-1721.1/38935 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T10:54:26Z |
| publishDate | 2007 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/389352019-05-22T03:11:01Z Sampling-based algorithms for dimension reduction Deshpande, Amit Jayant Santosh S. Vempala and Daniel A. Spielman. Massachusetts Institute of Technology. Dept. of Mathematics. Massachusetts Institute of Technology. Dept. of Mathematics. Mathematics. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2007. Includes bibliographical references (p. 51-52). Can one compute a low-dimensional representation of any given data by looking only at its small sample, chosen cleverly on the fly? Motivated by the above question, we consider the problem of low-rank matrix approximation: given a matrix A..., one wants to compute a rank-k matrix (where k << min{m, n}) nearest to A in the Frobenius norm (also known as the Hilbert-Schmidt norm). We prove that using a sample of roughly O(k/[epsilon]) rows of A one can compute, with high probability, a (1 + [epsilon])-approximation to the nearest rank-k matrix. This gives an algorithm for low-rank approximation with an improved error guarantee (compared to the additive [epsilon]... guarantee known earlier from the work of Frieze, Kannan, and Vempala) and running time O(Mk/[epsilon]), where M is the number of non-zero entries of A. The proof is based on two sampling techniques called adaptive sampling and volume sampling, and some linear algebraic tools. Low-rank matrix approximation under the Frobenius norm is equivalent to the problem of finding a low-dimensional subspace that minimizes the sum of squared distances to given points. The general subspace approximation problem asks one to find a low-dimensional subspace that minimizes the sum of p-th powers of distances (for p > 1) to given points. We generalize our sampling techniques and prove similar sampling-based dimension reduction results for subspace approximation. However, the proof is geometric. by Amit Jayant Deshpande. Ph.D. 2007-09-28T13:13:54Z 2007-09-28T13:13:54Z 2007 2007 Thesis http://hdl.handle.net/1721.1/38935 166267550 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 52 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Mathematics. Deshpande, Amit Jayant Sampling-based algorithms for dimension reduction |
| title | Sampling-based algorithms for dimension reduction |
| title_full | Sampling-based algorithms for dimension reduction |
| title_fullStr | Sampling-based algorithms for dimension reduction |
| title_full_unstemmed | Sampling-based algorithms for dimension reduction |
| title_short | Sampling-based algorithms for dimension reduction |
| title_sort | sampling based algorithms for dimension reduction |
| topic | Mathematics. |
| url | http://hdl.handle.net/1721.1/38935 |
| work_keys_str_mv | AT deshpandeamitjayant samplingbasedalgorithmsfordimensionreduction |