Loading…
Clustering from sparse pairwise measurements
We consider the problem of grouping items into clusters based on few random pairwise comparisons between the items. We introduce three closely related algorithms for this task: a belief propagation algorithm approximating the Bayes optimal solution, and two spectral algorithms based on the non-backt...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Conference Proceeding |
| Language: | English |
| Subjects: | |
| Online Access: | Request full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | |
|---|---|
| cites | |
| container_end_page | 784 |
| container_issue | |
| container_start_page | 780 |
| container_title | |
| container_volume | |
| creator | Saade, Alaa Krzakala, Florent Lelarge, Marc Zdeborova, Lenka |
| description | We consider the problem of grouping items into clusters based on few random pairwise comparisons between the items. We introduce three closely related algorithms for this task: a belief propagation algorithm approximating the Bayes optimal solution, and two spectral algorithms based on the non-backtracking and Bethe Hessian operators. For the case of two symmetric clusters, we conjecture that these algorithms are asymptotically optimal in that they detect the clusters as soon as it is information theoretically possible to do so. We substantiate this claim for one of the spectral approaches we introduce. |
| doi_str_mv | 10.1109/ISIT.2016.7541405 |
| format | conference_proceeding |
| fullrecord | <record><control><sourceid>proquest_CHZPO</sourceid><recordid>TN_cdi_proquest_miscellaneous_1835640513</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>7541405</ieee_id><sourcerecordid>1835640513</sourcerecordid><originalsourceid>FETCH-LOGICAL-h2005-6fecb7654c057c01207f827e4018fe37c8b6a72b2f55831310ae1f798e238e3a3</originalsourceid><addsrcrecordid>eNotkMtKxEAURFtBcBznA8RNli5MvLc7_chSgo_AgAvHdeiE29qSl90J4t8bmFlVLQ5FVTF2g5AhQvFQvVeHjAOqTMscc5BnbFdogxIKQAOKn7MNR6lTg6gv2VWM3wBCC-Abdl92S5wp-OEzcWHskzjZECmZrA-_fjU92bgE6mmY4zW7cLaLtDvpln08Px3K13T_9lKVj_v0iwPIVDlqG61k3oLULSAH7QzXlK9tHAndmkZZzRvupDQCBYIldLowxIUhYcWW3R1zpzD-LBTnuvexpa6zA41LrNEIqdadKFb09oh6Iqqn4Hsb_urTD-If84NPlg</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype><pqid>1835640513</pqid></control><display><type>conference_proceeding</type><title>Clustering from sparse pairwise measurements</title><source>IEEE Xplore All Conference Series</source><creator>Saade, Alaa ; Krzakala, Florent ; Lelarge, Marc ; Zdeborova, Lenka</creator><creatorcontrib>Saade, Alaa ; Krzakala, Florent ; Lelarge, Marc ; Zdeborova, Lenka</creatorcontrib><description>We consider the problem of grouping items into clusters based on few random pairwise comparisons between the items. We introduce three closely related algorithms for this task: a belief propagation algorithm approximating the Bayes optimal solution, and two spectral algorithms based on the non-backtracking and Bethe Hessian operators. For the case of two symmetric clusters, we conjecture that these algorithms are asymptotically optimal in that they detect the clusters as soon as it is information theoretically possible to do so. We substantiate this claim for one of the spectral approaches we introduce.</description><identifier>EISSN: 2157-8117</identifier><identifier>EISBN: 9781509018062</identifier><identifier>EISBN: 1509018069</identifier><identifier>DOI: 10.1109/ISIT.2016.7541405</identifier><language>eng</language><publisher>IEEE</publisher><subject>Algorithm design and analysis ; Algorithms ; Approximation ; Approximation algorithms ; Asymptotic properties ; Belief propagation ; Clustering algorithms ; Clusters ; Density measurement ; Information theory ; Jacobian matrices ; Optimization ; Spectra ; Tasks</subject><ispartof>2016 IEEE International Symposium on Information Theory (ISIT), 2016, p.780-784</ispartof><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/7541405$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>309,310,314,780,784,789,790,27924,27925,54555,54932</link.rule.ids><linktorsrc>$$Uhttps://ieeexplore.ieee.org/document/7541405$$EView_record_in_IEEE$$FView_record_in_$$GIEEE</linktorsrc></links><search><creatorcontrib>Saade, Alaa</creatorcontrib><creatorcontrib>Krzakala, Florent</creatorcontrib><creatorcontrib>Lelarge, Marc</creatorcontrib><creatorcontrib>Zdeborova, Lenka</creatorcontrib><title>Clustering from sparse pairwise measurements</title><title>2016 IEEE International Symposium on Information Theory (ISIT)</title><addtitle>ISIT</addtitle><description>We consider the problem of grouping items into clusters based on few random pairwise comparisons between the items. We introduce three closely related algorithms for this task: a belief propagation algorithm approximating the Bayes optimal solution, and two spectral algorithms based on the non-backtracking and Bethe Hessian operators. For the case of two symmetric clusters, we conjecture that these algorithms are asymptotically optimal in that they detect the clusters as soon as it is information theoretically possible to do so. We substantiate this claim for one of the spectral approaches we introduce.</description><subject>Algorithm design and analysis</subject><subject>Algorithms</subject><subject>Approximation</subject><subject>Approximation algorithms</subject><subject>Asymptotic properties</subject><subject>Belief propagation</subject><subject>Clustering algorithms</subject><subject>Clusters</subject><subject>Density measurement</subject><subject>Information theory</subject><subject>Jacobian matrices</subject><subject>Optimization</subject><subject>Spectra</subject><subject>Tasks</subject><issn>2157-8117</issn><isbn>9781509018062</isbn><isbn>1509018069</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>2016</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNotkMtKxEAURFtBcBznA8RNli5MvLc7_chSgo_AgAvHdeiE29qSl90J4t8bmFlVLQ5FVTF2g5AhQvFQvVeHjAOqTMscc5BnbFdogxIKQAOKn7MNR6lTg6gv2VWM3wBCC-Abdl92S5wp-OEzcWHskzjZECmZrA-_fjU92bgE6mmY4zW7cLaLtDvpln08Px3K13T_9lKVj_v0iwPIVDlqG61k3oLULSAH7QzXlK9tHAndmkZZzRvupDQCBYIldLowxIUhYcWW3R1zpzD-LBTnuvexpa6zA41LrNEIqdadKFb09oh6Iqqn4Hsb_urTD-If84NPlg</recordid><startdate>20160701</startdate><enddate>20160701</enddate><creator>Saade, Alaa</creator><creator>Krzakala, Florent</creator><creator>Lelarge, Marc</creator><creator>Zdeborova, Lenka</creator><general>IEEE</general><scope>6IE</scope><scope>6IH</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIO</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>20160701</creationdate><title>Clustering from sparse pairwise measurements</title><author>Saade, Alaa ; Krzakala, Florent ; Lelarge, Marc ; Zdeborova, Lenka</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-h2005-6fecb7654c057c01207f827e4018fe37c8b6a72b2f55831310ae1f798e238e3a3</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>2016</creationdate><topic>Algorithm design and analysis</topic><topic>Algorithms</topic><topic>Approximation</topic><topic>Approximation algorithms</topic><topic>Asymptotic properties</topic><topic>Belief propagation</topic><topic>Clustering algorithms</topic><topic>Clusters</topic><topic>Density measurement</topic><topic>Information theory</topic><topic>Jacobian matrices</topic><topic>Optimization</topic><topic>Spectra</topic><topic>Tasks</topic><toplevel>online_resources</toplevel><creatorcontrib>Saade, Alaa</creatorcontrib><creatorcontrib>Krzakala, Florent</creatorcontrib><creatorcontrib>Lelarge, Marc</creatorcontrib><creatorcontrib>Zdeborova, Lenka</creatorcontrib><collection>IEEE Electronic Library (IEL) Conference Proceedings</collection><collection>IEEE Proceedings Order Plan (POP) 1998-present by volume</collection><collection>IEEE Xplore All Conference Proceedings</collection><collection>IEEE Electronic Library (IEL)</collection><collection>IEEE Proceedings Order Plans (POP) 1998-present</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext_linktorsrc</fulltext></delivery><addata><au>Saade, Alaa</au><au>Krzakala, Florent</au><au>Lelarge, Marc</au><au>Zdeborova, Lenka</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>Clustering from sparse pairwise measurements</atitle><btitle>2016 IEEE International Symposium on Information Theory (ISIT)</btitle><stitle>ISIT</stitle><date>2016-07-01</date><risdate>2016</risdate><spage>780</spage><epage>784</epage><pages>780-784</pages><eissn>2157-8117</eissn><eisbn>9781509018062</eisbn><eisbn>1509018069</eisbn><abstract>We consider the problem of grouping items into clusters based on few random pairwise comparisons between the items. We introduce three closely related algorithms for this task: a belief propagation algorithm approximating the Bayes optimal solution, and two spectral algorithms based on the non-backtracking and Bethe Hessian operators. For the case of two symmetric clusters, we conjecture that these algorithms are asymptotically optimal in that they detect the clusters as soon as it is information theoretically possible to do so. We substantiate this claim for one of the spectral approaches we introduce.</abstract><pub>IEEE</pub><doi>10.1109/ISIT.2016.7541405</doi><tpages>5</tpages><oa>free_for_read</oa></addata></record> |
| fulltext | fulltext_linktorsrc |
| identifier | EISSN: 2157-8117 |
| ispartof | 2016 IEEE International Symposium on Information Theory (ISIT), 2016, p.780-784 |
| issn | 2157-8117 |
| language | eng |
| recordid | cdi_proquest_miscellaneous_1835640513 |
| source | IEEE Xplore All Conference Series |
| subjects | Algorithm design and analysis Algorithms Approximation Approximation algorithms Asymptotic properties Belief propagation Clustering algorithms Clusters Density measurement Information theory Jacobian matrices Optimization Spectra Tasks |
| title | Clustering from sparse pairwise measurements |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-28T04%3A00%3A18IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_CHZPO&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=Clustering%20from%20sparse%20pairwise%20measurements&rft.btitle=2016%20IEEE%20International%20Symposium%20on%20Information%20Theory%20(ISIT)&rft.au=Saade,%20Alaa&rft.date=2016-07-01&rft.spage=780&rft.epage=784&rft.pages=780-784&rft.eissn=2157-8117&rft_id=info:doi/10.1109/ISIT.2016.7541405&rft.eisbn=9781509018062&rft.eisbn_list=1509018069&rft_dat=%3Cproquest_CHZPO%3E1835640513%3C/proquest_CHZPO%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-h2005-6fecb7654c057c01207f827e4018fe37c8b6a72b2f55831310ae1f798e238e3a3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1835640513&rft_id=info:pmid/&rft_ieee_id=7541405&rfr_iscdi=true |