Clustering via matrix exponentiation
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, February 2004.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/17671 |
| _version_ | 1826191828711374848 |
|---|---|
| author | Zhou, Hanson M. (Hanson Mi), 1977- |
| author2 | Santosh Vempala. |
| author_facet | Santosh Vempala. Zhou, Hanson M. (Hanson Mi), 1977- |
| author_sort | Zhou, Hanson M. (Hanson Mi), 1977- |
| collection | MIT |
| description | Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, February 2004. |
| first_indexed | 2024-09-23T09:01:55Z |
| format | Thesis |
| id | mit-1721.1/17671 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T09:01:55Z |
| publishDate | 2005 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/176712019-04-10T20:19:02Z Clustering via matrix exponentiation Zhou, Hanson M. (Hanson Mi), 1977- Santosh Vempala. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, February 2004. Includes bibliographical references (leaves 26-27). Given a set of n points with a matrix of pairwise similarity measures, one would like to partition the points into clusters so that similar points are together and different ones apart. We present an algorithm requiring only matrix exponentiation that performs well in practice and bears an elegant interpretation in terms of random walks on a graph. Under a certain mixture model involving planting a partition via randomized rounding of tailored matrix entries, the algorithm can be proven effective for only a single squaring. It is shown that the clustering performance of the algorithm degrades with larger values of the exponent, thus revealing that a single squaring is optimal. by Hanson M. Zhou. S.M. 2005-06-02T16:38:38Z 2005-06-02T16:38:38Z 2003 2004 Thesis http://hdl.handle.net/1721.1/17671 55677179 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 27 leaves 1209849 bytes 1210232 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Zhou, Hanson M. (Hanson Mi), 1977- Clustering via matrix exponentiation |
| title | Clustering via matrix exponentiation |
| title_full | Clustering via matrix exponentiation |
| title_fullStr | Clustering via matrix exponentiation |
| title_full_unstemmed | Clustering via matrix exponentiation |
| title_short | Clustering via matrix exponentiation |
| title_sort | clustering via matrix exponentiation |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/17671 |
| work_keys_str_mv | AT zhouhansonmhansonmi1977 clusteringviamatrixexponentiation |