{"corpus_id":30077028,"paper_sha":"15fe223065a2cf3d4d1d269dac340906a14dcf4a","doi":"10.1137/15M1036713","arxiv_id":null,"pmid":null,"pmcid":null,"mag_id":2540556405,"dblp_id":"journals/siamam/BruntonBPK16","acl_id":null,"title":"Sparse Sensor Placement Optimization for Classification","year":2016,"publication_date":"2016-10-01","venue":"SIAM Journal on Applied Mathematics","journal":{"name":"SIAM J. Appl. Math.","pages":"2099-2122","volume":"76"},"journal_issn":null,"journal_title":null,"publication_types":["JournalArticle"],"pubmed_pub_types":null,"s2_fields_of_study":["Mathematics","Computer Science","Engineering"],"reference_count":71,"citation_count":83,"influential_citation_count":5,"is_open_access":false,"arxiv_categories":null,"arxiv_license":null,"arxiv_journal_ref":null,"mesh_headings":null,"chemicals":null,"comments_corrections":null,"source_flags":1,"s2_open_access_pdf_url":null,"s2_open_access_landing_url":null,"s2_open_access_license":null,"s2_open_access_status":null,"pmc_open_access_pdf_url":null,"pmc_open_access_landing_url":null,"pmc_open_access_license":null,"pmc_open_access_status":null,"unpaywall_open_access_pdf_url":null,"unpaywall_open_access_landing_url":null,"unpaywall_open_access_license":null,"unpaywall_open_access_status":null,"abstract":"Choosing a limited set of sensor locations to characterize or classify a high-dimensional system is an important challenge in engineering design. Traditionally, optimizing the sensor locations involves a brute-force, combinatorial search, which is NP-hard and is computationally intractable for even moderately large problems. Using recent advances in sparsity-promoting techniques, we present a novel algorithm to solve this sparse sensor placement optimization for classification (SSPOC) that exploits low-dimensional structure exhibited by many high-dimensional systems. Our approach is inspired by compressed sensing, a framework that reconstructs data from few measurements. If only classification is required, reconstruction can be circumvented and the measurements needed are orders-of-magnitude fewer still. Our algorithm solves an $\\ell_1$ minimization to find the fewest nonzero entries of the full measurement vector that exactly reconstruct the discriminant vector in feature space; these entries represent sensor locations that best inform the decision task. We demonstrate the SSPOC algorithm on five classification tasks, using datasets from a diverse set of examples, including physical dynamical systems, image recognition, and microarray cancer identification. Once training identifies sensor locations, data taken at these locations forms a low-dimensional measurement space, and we perform computationally efficient classification with accuracy approaching that of classification using full-state data. The algorithm also works when trained on heavily subsampled data, eliminating the need for unrealistic full-state training data.","claims":[{"public_id":"cl_5de3b271b8c5e89509dbfeb07c34efc1","status":"active","text":"A novel sparse sensor placement optimization for classification algorithm identifies a few sensor locations by solving an L1 minimization that exactly reconstructs the discriminant vector in feature space.","confidence":0.98,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_5de3b271b8c5e89509dbfeb07c34efc1"},{"public_id":"cl_1fc6a829aa2c3e495b248943a3a7970b","status":"active","text":"The approach was demonstrated on five classification tasks spanning physical dynamical systems, image recognition, and microarray cancer identification.","confidence":0.97,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_1fc6a829aa2c3e495b248943a3a7970b"},{"public_id":"cl_f660f7489de1615076b0d96838a2acdd","status":"active","text":"The method works when trained on heavily subsampled data, avoiding the need for full-state training data.","confidence":0.95,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_f660f7489de1615076b0d96838a2acdd"},{"public_id":"cl_c4b8a2d199a93458bd0cfa15f003327b","status":"active","text":"The selected sensor locations form a low-dimensional measurement space that supports computationally efficient classification with accuracy approaching full-state-data classification.","confidence":0.94,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_c4b8a2d199a93458bd0cfa15f003327b"}],"concepts":[{"public_id":"co_137ae382641b331bb8a1a7a7bd941546","status":"active","name":"sparse sensor placement optimization for classification","description":"An algorithmic framework for choosing a small set of sensor locations that are most informative for a classification task.","types":["method"],"aliases":["SSPOC"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_137ae382641b331bb8a1a7a7bd941546"},{"public_id":"co_1743d1ad32ce6011dfde9551edb97fe3","status":"active","name":"five classification tasks","description":"The set of five benchmark classification problems used to evaluate the algorithm.","types":["evaluation set"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_1743d1ad32ce6011dfde9551edb97fe3"},{"public_id":"co_1cd0d46c01a2bc567a247ae910e78ef7","status":"active","name":"full-state training data","description":"Training data consisting of complete measurements of the underlying system state.","types":["data"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_1cd0d46c01a2bc567a247ae910e78ef7"},{"public_id":"co_77fb071f6eb0c7f28ffa6ce62a281d98","status":"active","name":"classification","description":"The decision task of assigning observations to one of several classes.","types":["task"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_77fb071f6eb0c7f28ffa6ce62a281d98"},{"public_id":"co_937b5eee49329d6db50ef412ca3ba870","status":"active","name":"low-dimensional measurement space","description":"A reduced sensor-based feature space constructed from measurements at selected locations.","types":["feature space"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_937b5eee49329d6db50ef412ca3ba870"},{"public_id":"co_9b83375a2ea0e356c1463e0c60b8c54f","status":"active","name":"heavily subsampled data","description":"Training data in which only a small fraction of the full measurements are available.","types":["data"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_9b83375a2ea0e356c1463e0c60b8c54f"},{"public_id":"co_ad2a996baf79f6248cf8a16de563d7f7","status":"active","name":"discriminant vector in feature space","description":"A classification-separating vector in feature space whose nonzero entries correspond to informative sensor locations.","types":["representation"],"aliases":["discriminant vector"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_ad2a996baf79f6248cf8a16de563d7f7"},{"public_id":"co_b844aa1ccf74cebf893682027b4264fd","status":"active","name":"image recognition","description":"A classification domain involving labeled visual data.","types":["application domain"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_b844aa1ccf74cebf893682027b4264fd"},{"public_id":"co_d1ba2c93f469fa58a52b698f0d46feec","status":"active","name":"physical dynamical systems","description":"Time-evolving physical systems used as one class of evaluation datasets.","types":["application domain"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_d1ba2c93f469fa58a52b698f0d46feec"},{"public_id":"co_d28cd7fdfdb3fe062cc5755269364b5d","status":"active","name":"L1 minimization","description":"An optimization procedure that promotes sparsity by minimizing the sum of absolute values of variables.","types":["optimization method"],"aliases":["_1 minimization"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_d28cd7fdfdb3fe062cc5755269364b5d"},{"public_id":"co_dd1c6c1059afeb5fb2dc62550bfb48da","status":"active","name":"full-state data","description":"Complete high-dimensional system measurements used as a reference for classification performance.","types":["data"],"aliases":["full-state"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_dd1c6c1059afeb5fb2dc62550bfb48da"}],"external_ids":{"DOI":"10.1137/15M1036713","ArXiv":null,"PubMed":null,"PubMedCentral":null,"MAG":2540556405,"DBLP":"journals/siamam/BruntonBPK16","ACL":null},"open_access":{"is_open_access":false,"pdf_url":null,"landing_url":"https://sah.borca.ai/papers/30077028","source":null,"pdf_url_source":null,"license":null,"reason":"pdf_url_not_indexed"},"reference_availability":{"status":"available","references_indexed":true,"full_text_available":false,"full_text_source":null,"count_basis":"semantic_scholar_metadata","extraction_status":"not_applicable","reason":null},"source":{"provider":"episteme2","base_corpus":"semantic_scholar_dump","freshness_mode":"unknown","basis":["semantic_scholar_metadata","postgres_metadata"],"limits":["paper metadata is based on indexed upstream scholarly datasets","claims and concepts are available only for extracted papers","absence of claims or concepts means no extracted graph data is available in this response"],"status":"available","degraded":false,"degraded_reasons":[],"diagnostics":{"status":"available","degraded":false,"degraded_reasons":[],"metadata_status":"available","graph_status":"available","abstract_status":"available"},"source_flags":1},"paper_id":636370,"paper_uid":"b0ea6201-3596-463f-8369-27693a59f76f","canonical_identity":{"paper_id":636370,"paper_uid":"b0ea6201-3596-463f-8369-27693a59f76f","identity_status":"available","lookup_basis":"semantic_scholar_external_id","compatibility_path":"corpus_id"},"url":"https://sah.borca.ai/papers/30077028"}