Fitting a graph to vector data
We introduce a measure of how well a combinatorial graph ts a collection of vectors. The optimal graphs under this measure may be computed by solving convex quadratic programs and have many interesting properties. For vectors in d dimensional space, the graphs always have average degree at mo...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2011
|
| Online Access: | http://hdl.handle.net/1721.1/60697 https://orcid.org/0000-0002-4257-4198 |
| _version_ | 1826203174628753408 |
|---|---|
| author | Daitch, Samuel I. Kelner, Jonathan Adam |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Daitch, Samuel I. Kelner, Jonathan Adam |
| author_sort | Daitch, Samuel I. |
| collection | MIT |
| description | We introduce a measure of how well a combinatorial
graph ts a collection of vectors.
The optimal graphs under this measure may
be computed by solving convex quadratic
programs and have many interesting properties.
For vectors in d dimensional space, the
graphs always have average degree at most
2(d+1), and for vectors in 2 dimensions they
are always planar. We compute these graphs
for many standard data sets and show that
they can be used to obtain good solutions to
classifi cation, regression and clustering problems. |
| first_indexed | 2024-09-23T12:32:39Z |
| format | Article |
| id | mit-1721.1/60697 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:32:39Z |
| publishDate | 2011 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | mit-1721.1/606972022-09-28T08:27:35Z Fitting a graph to vector data Daitch, Samuel I. Kelner, Jonathan Adam Massachusetts Institute of Technology. Department of Mathematics Kelner, Jonathan Adam Kelner, Jonathan Adam We introduce a measure of how well a combinatorial graph ts a collection of vectors. The optimal graphs under this measure may be computed by solving convex quadratic programs and have many interesting properties. For vectors in d dimensional space, the graphs always have average degree at most 2(d+1), and for vectors in 2 dimensions they are always planar. We compute these graphs for many standard data sets and show that they can be used to obtain good solutions to classifi cation, regression and clustering problems. National Science Foundation (U.S.) (Grant No. CCF-0634957) National Science Foundation (U.S.) (Grant No.CCF-0843915) 2011-01-24T15:10:18Z 2011-01-24T15:10:18Z 2009-01 2009-01 Article http://purl.org/eprint/type/ConferencePaper 978-1-60558-516-1 http://hdl.handle.net/1721.1/60697 Samuel I. Daitch, Jonathan A. Kelner, and Daniel A. Spielman. 2009. Fitting a graph to vector data. In Proceedings of the 26th Annual International Conference on Machine Learning (ICML '09). ACM, New York, NY, USA, 201-208. DOI=10.1145/1553374.1553400 http://doi.acm.org/10.1145/1553374.1553400 https://orcid.org/0000-0002-4257-4198 en_US http://dx.doi.org/10.1145/1553374.1553400 Proceedings of the 26th Annual International Conference on Machine Learning Attribution-Noncommercial-Share Alike 3.0 Unported http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Association for Computing Machinery MIT web domain |
| spellingShingle | Daitch, Samuel I. Kelner, Jonathan Adam Fitting a graph to vector data |
| title | Fitting a graph to vector data |
| title_full | Fitting a graph to vector data |
| title_fullStr | Fitting a graph to vector data |
| title_full_unstemmed | Fitting a graph to vector data |
| title_short | Fitting a graph to vector data |
| title_sort | fitting a graph to vector data |
| url | http://hdl.handle.net/1721.1/60697 https://orcid.org/0000-0002-4257-4198 |
| work_keys_str_mv | AT daitchsamueli fittingagraphtovectordata AT kelnerjonathanadam fittingagraphtovectordata |