{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/88135"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/88135","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"New group testing paradigms: from practice to theory","abstract":"We propose a novel group testing framework, termed semi-quantitative group testing, motivated by a class of problems arising in genome screening experiments in addition to other applications such as interpretable rule learning for decision making. Semi-quantitative group testing (SQGT) is a (possibly) non-binary pooling scheme that may be viewed as a concatenation of an adder channel and an integer-valued quantizer. In its full generality, SQGT may be viewed as a unifying framework for group testing, in the sense that most group testing models are special instances of SQGT. For the new testing scheme, we define the notion of SQ-disjunct and SQ-separable test matrices, representing generalizations of classical disjunct and separable matrices. We describe combinatorial and probabilistic constructions for such matrices without considering any restriction on the thresholds of the SQGT model (i.e. SQGT with arbitrary thresholds). Then, we focus on the important special case in which the thresholds are equidistant, and construct SQ-disjunct and SQ-separable matrices for this model. While for most of the constructions described in this dissertation, it is assumed that the number of defectives is much smaller than total number of test subjects, we also consider the case in which there is no restriction on the number of defectives and they may be as large as the total number of subjects. For the constructed matrices, we describe a number of efficient decoding algorithms based on algebraic methods and message passing on graphical models. Finally, we introduce the novel probabilistic group testing framework of Poisson group testing, applicable to dynamic testing with diminishing relative rates of defectives. For this new model, we consider both nonadaptive and adaptive testing schemes and develop lower bounds and tight constructive upper bounds on the number of required tests.","abstract_html":"We propose a novel group testing framework, termed semi-quantitative group testing, motivated by a class of problems arising in genome screening experiments in addition to other applications such as interpretable rule learning for decision making. Semi-quantitative group testing (SQGT) is a (possibly) non-binary pooling scheme that may be viewed as a concatenation of an adder channel and an integer-valued quantizer. In its full generality, SQGT may be viewed as a unifying framework for group testing, in the sense that most group testing models are special instances of SQGT. For the new testing scheme, we define the notion of SQ-disjunct and SQ-separable test matrices, representing generalizations of classical disjunct and separable matrices. We describe combinatorial and probabilistic constructions for such matrices without considering any restriction on the thresholds of the SQGT model (i.e. SQGT with arbitrary thresholds). Then, we focus on the important special case in which the thresholds are equidistant, and construct SQ-disjunct and SQ-separable matrices for this model. While for most of the constructions described in this dissertation, it is assumed that the number of defectives is much smaller than total number of test subjects, we also consider the case in which there is no restriction on the number of defectives and they may be as large as the total number of subjects. For the constructed matrices, we describe a number of efficient decoding algorithms based on algebraic methods and message passing on graphical models. Finally, we introduce the novel probabilistic group testing framework of Poisson group testing, applicable to dynamic testing with diminishing relative rates of defectives. For this new model, we consider both nonadaptive and adaptive testing schemes and develop lower bounds and tight constructive upper bounds on the number of required tests.","abstract_has_math":false,"creators":["Emad, Amin"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Milenkovic, Olgica","Bresler, Yoram","Moulin, Pierre","Nedich, Angelia","Raginsky, Maxim","Wu, Yihong"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015-09-29T20:49:24Z","date_published":"2015-09-29T20:49:24Z","updated_at":"2026-07-22T22:26:31Z","subjects":["Integer Compressed Sensing","Group Testing","Sparse Signal Recovery","Semi-quantitative Group Testing","Code Construction","Decoding Algorithm","Message Passing"],"languages":["en"],"rights":["Copyright 2015 Amin Emad"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/88135","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Milenkovic, Olgica","Bresler, Yoram","Moulin, Pierre","Nedich, Angelia","Raginsky, Maxim","Wu, Yihong"]},{"key":"dc:creator","label":"Author","values":["Emad, Amin"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015-09-29T20:49:24Z","2017-09-30T09:15:38Z","2015-08","2015-05-18","2015-8"]},{"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":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"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":["Integer Compressed Sensing","Group Testing","Sparse Signal Recovery","Semi-quantitative Group Testing","Code Construction","Decoding Algorithm","Message Passing"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2015 Amin Emad"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/88135"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["We propose a novel group testing framework, termed semi-quantitative group testing, motivated by a class of problems arising in genome screening experiments in addition to other applications such as interpretable rule learning for decision making. Semi-quantitative group testing (SQGT) is a (possibly) non-binary pooling scheme that may be viewed as a concatenation of an adder channel and an integer-valued quantizer. In its full generality, SQGT may be viewed as a unifying framework for group testing, in the sense that most group testing models are special instances of SQGT. For the new testing scheme, we define the notion of SQ-disjunct and SQ-separable test matrices, representing generalizations of classical disjunct and separable matrices. We describe combinatorial and probabilistic constructions for such matrices without considering any restriction on the thresholds of the SQGT model (i.e. SQGT with arbitrary thresholds). Then, we focus on the important special case in which the thresholds are equidistant, and construct SQ-disjunct and SQ-separable matrices for this model. While for most of the constructions described in this dissertation, it is assumed that the number of defectives is much smaller than total number of test subjects, we also consider the case in which there is no restriction on the number of defectives and they may be as large as the total number of subjects. For the constructed matrices, we describe a number of efficient decoding algorithms based on algebraic methods and message passing on graphical models. Finally, we introduce the novel probabilistic group testing framework of Poisson group testing, applicable to dynamic testing with diminishing relative rates of defectives. For this new model, we consider both nonadaptive and adaptive testing schemes and develop lower bounds and tight constructive upper bounds on the number of required tests.","Submission published under a 24 month embargo labeled 'U of I only', the embargo will last until 2017-08-01","The student, Amin Emad, accepted the attached license on 2015-05-15 at 15:20.","The student, Amin Emad, submitted this Dissertation for approval on 2015-05-15 at 15:32.","This Dissertation was approved for publication on 2015-05-18 at 08:17.","DSpace SAF Submission Ingestion Package generated from Vireo submission #8244 on 2015-09-29 at 14:58:26","Made available in DSpace on 2015-09-29T20:49:24Z (GMT). No. of bitstreams: 2 EMAD-DISSERTATION-2015.pdf: 1192523 bytes, checksum: d4307f85644fa0dabd6e0f1ace645706 (MD5) LICENSE.txt: 4206 bytes, checksum: a20923dba5a24420273432f5c70875cc (MD5) Previous issue date: 2015-05-18","Embargo set by: Seth Robbins for item 89415 Lift date: 2017-09-29T20:50:34Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 89415 on 2017-09-30T09:15:38Z."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["New group testing paradigms: from practice to theory"]}]}],"canonical_facts":{"dc:contributor":["Milenkovic, Olgica","Bresler, Yoram","Moulin, Pierre","Nedich, Angelia","Raginsky, Maxim","Wu, Yihong"],"dc:creator":["Emad, Amin"],"dc:date":["2015-09-29T20:49:24Z","2017-09-30T09:15:38Z","2015-08","2015-05-18","2015-8"],"dc:description":["We propose a novel group testing framework, termed semi-quantitative group testing, motivated by a class of problems arising in genome screening experiments in addition to other applications such as interpretable rule learning for decision making. Semi-quantitative group testing (SQGT) is a (possibly) non-binary pooling scheme that may be viewed as a concatenation of an adder channel and an integer-valued quantizer. In its full generality, SQGT may be viewed as a unifying framework for group testing, in the sense that most group testing models are special instances of SQGT. For the new testing scheme, we define the notion of SQ-disjunct and SQ-separable test matrices, representing generalizations of classical disjunct and separable matrices. We describe combinatorial and probabilistic constructions for such matrices without considering any restriction on the thresholds of the SQGT model (i.e. SQGT with arbitrary thresholds). Then, we focus on the important special case in which the thresholds are equidistant, and construct SQ-disjunct and SQ-separable matrices for this model. While for most of the constructions described in this dissertation, it is assumed that the number of defectives is much smaller than total number of test subjects, we also consider the case in which there is no restriction on the number of defectives and they may be as large as the total number of subjects. For the constructed matrices, we describe a number of efficient decoding algorithms based on algebraic methods and message passing on graphical models. Finally, we introduce the novel probabilistic group testing framework of Poisson group testing, applicable to dynamic testing with diminishing relative rates of defectives. For this new model, we consider both nonadaptive and adaptive testing schemes and develop lower bounds and tight constructive upper bounds on the number of required tests.","Submission published under a 24 month embargo labeled 'U of I only', the embargo will last until 2017-08-01","The student, Amin Emad, accepted the attached license on 2015-05-15 at 15:20.","The student, Amin Emad, submitted this Dissertation for approval on 2015-05-15 at 15:32.","This Dissertation was approved for publication on 2015-05-18 at 08:17.","DSpace SAF Submission Ingestion Package generated from Vireo submission #8244 on 2015-09-29 at 14:58:26","Made available in DSpace on 2015-09-29T20:49:24Z (GMT). No. of bitstreams: 2 EMAD-DISSERTATION-2015.pdf: 1192523 bytes, checksum: d4307f85644fa0dabd6e0f1ace645706 (MD5) LICENSE.txt: 4206 bytes, checksum: a20923dba5a24420273432f5c70875cc (MD5) Previous issue date: 2015-05-18","Embargo set by: Seth Robbins for item 89415 Lift date: 2017-09-29T20:50:34Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 89415 on 2017-09-30T09:15:38Z."],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/88135"],"dc:language":["en"],"dc:rights":["Copyright 2015 Amin Emad"],"dc:subject":["Integer Compressed Sensing","Group Testing","Sparse Signal Recovery","Semi-quantitative Group Testing","Code Construction","Decoding Algorithm","Message Passing"],"dc:title":["New group testing paradigms: from practice to theory"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:31Z"}