{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/106187"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/106187","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Regularized weighted Chebyshev approximations for support estimation","abstract":"We introduce a new method for estimating the support size of an unknown distribution which provably matches the performance bounds of the stateof-the-art techniques in the area and outperforms them in practice. In particular, we present both theoretical and computer simulation results that illustrate the utility and performance improvements of our method. The theoretical analysis relies on introducing a new weighted Chebyshev polynomial approximation method, jointly optimizing the bias and variance components of the risk, and combining the weighted minmax polynomial approximation method with discretized semi-infinite programming solvers. Such a setting allows for casting the estimation problem as a linear program (LP) with a small number of variables and constraints that may be solved as efficiently as the original Chebyshev approximation problem. Our technique is tested on synthetic data and textual data (Shakespeare’s plays), and is used to address an important problem in computational biology - estimating the number of bacterial genera in the human gut. On synthetic datasets, for practically relevant sample sizes, we observe significant improvements in the value of the worst-case risk compared to existing methods. The same is true of the text data. For the bioinformatics application, using metagenomic data from the NIH Human Gut and the American Gut Microbiome Projects, we generate a list of frequencies of bacterial taxa that allows us to estimate the number of bacterial genera to ∼ 2300.","abstract_html":"We introduce a new method for estimating the support size of an unknown distribution which provably matches the performance bounds of the stateof-the-art techniques in the area and outperforms them in practice. In particular, we present both theoretical and computer simulation results that illustrate the utility and performance improvements of our method. The theoretical analysis relies on introducing a new weighted Chebyshev polynomial approximation method, jointly optimizing the bias and variance components of the risk, and combining the weighted minmax polynomial approximation method with discretized semi-infinite programming solvers. Such a setting allows for casting the estimation problem as a linear program (LP) with a small number of variables and constraints that may be solved as efficiently as the original Chebyshev approximation problem. Our technique is tested on synthetic data and textual data (Shakespeare’s plays), and is used to address an important problem in computational biology - estimating the number of bacterial genera in the human gut. On synthetic datasets, for practically relevant sample sizes, we observe significant improvements in the value of the worst-case risk compared to existing methods. The same is true of the text data. For the bioinformatics application, using metagenomic data from the NIH Human Gut and the American Gut Microbiome Projects, we generate a list of frequencies of bacterial taxa that allows us to estimate the number of bacterial genera to ∼ 2300.","abstract_has_math":false,"creators":["Chien, I"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Milenkovic, Olgica"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2020,"date_issued":"2020-03-02T21:58:11Z","date_published":"2020-03-02T21:58:11Z","updated_at":"2026-07-22T22:24:45Z","subjects":["Support estimation","Chebyshev polynomials"],"languages":["en"],"rights":["Copyright I Chien 2019"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/106187","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Milenkovic, Olgica"]},{"key":"dc:creator","label":"Author","values":["Chien, I"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2020-03-02T21:58:11Z","2019-11-13","2019-12"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Support estimation","Chebyshev polynomials"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright I Chien 2019"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/106187"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["We introduce a new method for estimating the support size of an unknown distribution which provably matches the performance bounds of the stateof-the-art techniques in the area and outperforms them in practice. In particular, we present both theoretical and computer simulation results that illustrate the utility and performance improvements of our method. The theoretical analysis relies on introducing a new weighted Chebyshev polynomial approximation method, jointly optimizing the bias and variance components of the risk, and combining the weighted minmax polynomial approximation method with discretized semi-infinite programming solvers. Such a setting allows for casting the estimation problem as a linear program (LP) with a small number of variables and constraints that may be solved as efficiently as the original Chebyshev approximation problem. Our technique is tested on synthetic data and textual data (Shakespeare’s plays), and is used to address an important problem in computational biology - estimating the number of bacterial genera in the human gut. On synthetic datasets, for practically relevant sample sizes, we observe significant improvements in the value of the worst-case risk compared to existing methods. The same is true of the text data. For the bioinformatics application, using metagenomic data from the NIH Human Gut and the American Gut Microbiome Projects, we generate a list of frequencies of bacterial taxa that allows us to estimate the number of bacterial genera to ∼ 2300.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-02-28 without embargo terms","The student, I Chien, accepted the attached license on 2019-11-13 at 12:25.","The student, I Chien, submitted this Thesis for approval on 2019-11-13 at 13:34.","This Thesis was approved for publication on 2019-11-13 at 14:26.","DSpace SAF Submission Ingestion Package generated from Vireo submission #14547 on 2020-02-28 at 17:13:37","Made available in DSpace on 2020-03-02T21:58:11Z (GMT). No. of bitstreams: 2 CHIEN-THESIS-2019.pdf: 578206 bytes, checksum: e3b592aeffd590ea360477862b3ca1a2 (MD5) LICENSE.txt: 4204 bytes, checksum: 19f099b75307ad782f32418e8a4846d4 (MD5) Previous issue date: 2019-11-13"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Regularized weighted Chebyshev approximations for support estimation"]}]}],"canonical_facts":{"dc:contributor":["Milenkovic, Olgica"],"dc:creator":["Chien, I"],"dc:date":["2020-03-02T21:58:11Z","2019-11-13","2019-12"],"dc:description":["We introduce a new method for estimating the support size of an unknown distribution which provably matches the performance bounds of the stateof-the-art techniques in the area and outperforms them in practice. In particular, we present both theoretical and computer simulation results that illustrate the utility and performance improvements of our method. The theoretical analysis relies on introducing a new weighted Chebyshev polynomial approximation method, jointly optimizing the bias and variance components of the risk, and combining the weighted minmax polynomial approximation method with discretized semi-infinite programming solvers. Such a setting allows for casting the estimation problem as a linear program (LP) with a small number of variables and constraints that may be solved as efficiently as the original Chebyshev approximation problem. Our technique is tested on synthetic data and textual data (Shakespeare’s plays), and is used to address an important problem in computational biology - estimating the number of bacterial genera in the human gut. On synthetic datasets, for practically relevant sample sizes, we observe significant improvements in the value of the worst-case risk compared to existing methods. The same is true of the text data. For the bioinformatics application, using metagenomic data from the NIH Human Gut and the American Gut Microbiome Projects, we generate a list of frequencies of bacterial taxa that allows us to estimate the number of bacterial genera to ∼ 2300.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-02-28 without embargo terms","The student, I Chien, accepted the attached license on 2019-11-13 at 12:25.","The student, I Chien, submitted this Thesis for approval on 2019-11-13 at 13:34.","This Thesis was approved for publication on 2019-11-13 at 14:26.","DSpace SAF Submission Ingestion Package generated from Vireo submission #14547 on 2020-02-28 at 17:13:37","Made available in DSpace on 2020-03-02T21:58:11Z (GMT). No. of bitstreams: 2 CHIEN-THESIS-2019.pdf: 578206 bytes, checksum: e3b592aeffd590ea360477862b3ca1a2 (MD5) LICENSE.txt: 4204 bytes, checksum: 19f099b75307ad782f32418e8a4846d4 (MD5) Previous issue date: 2019-11-13"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/106187"],"dc:language":["en"],"dc:rights":["Copyright I Chien 2019"],"dc:subject":["Support estimation","Chebyshev polynomials"],"dc:title":["Regularized weighted Chebyshev approximations for support estimation"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:45Z"}