{"id":{"repo_id":"msu","oai_identifier":"oai:d.lib.msu.edu:etd_19383"},"canonical_url":"https://search.ndltd.org/etd/msu/oai:d.lib.msu.edu:etd_19383","repository":{"repo_id":"msu","name":"Michigan State University","base_url":"https://d.lib.msu.edu/oai"},"display":{"title":"Sparse harmonic transforms","abstract":"\"We develop fast function learning algorithms given an assumption that a function can be well approximated by the expansion of a few high-dimensional basis functions. Considering the tensorized Fourier basis functions, several versions of high-dimensional sparse Fourier transforms (SFTs) are discussed. One-dimensional sparse Fourier transforms introduced in [1] and [2] quickly approximate functions represented by only s Fourier basis functions using a few samples (function evaluations) without noise and with noise respectively. The algorithms can be directly applied to compute the Fourier transform of the high-dimensional functions. However, it becomes hard to implement them if the dimension gets too large. In this thesis, we introduce two new concepts: partial unwrapping and tilting. These two ideas allow us to efficiently compute the high-dimensional sparse Fourier transforms using the ideas in [1] and [2]. Furthermore, we develop sublinear-time compressive sensing methods to approximate the multivariate functions by the expansion of a few bounded orthonormal product (BOP) bases which include tensorized Fourier basis functions. These new methods are obtained from CoSaMP by replacing its usual support identification procedure with a new faster one inspired by fast SFT techniques. The resulting sublinearized CoSaMP method allows for the rapid approximation of bounded orthonormal product basis (BOPB)-sparse functions of many variables which are too hideously high-dimensional to be learned by other means. Both numerics and theoretical recovery guarantees will be presented.\"--Page ii.","abstract_html":"&quot;We develop fast function learning algorithms given an assumption that a function can be well approximated by the expansion of a few high-dimensional basis functions. Considering the tensorized Fourier basis functions, several versions of high-dimensional sparse Fourier transforms (SFTs) are discussed. One-dimensional sparse Fourier transforms introduced in [1] and [2] quickly approximate functions represented by only s Fourier basis functions using a few samples (function evaluations) without noise and with noise respectively. The algorithms can be directly applied to compute the Fourier transform of the high-dimensional functions. However, it becomes hard to implement them if the dimension gets too large. In this thesis, we introduce two new concepts: partial unwrapping and tilting. These two ideas allow us to efficiently compute the high-dimensional sparse Fourier transforms using the ideas in [1] and [2]. Furthermore, we develop sublinear-time compressive sensing methods to approximate the multivariate functions by the expansion of a few bounded orthonormal product (BOP) bases which include tensorized Fourier basis functions. These new methods are obtained from CoSaMP by replacing its usual support identification procedure with a new faster one inspired by fast SFT techniques. The resulting sublinearized CoSaMP method allows for the rapid approximation of bounded orthonormal product basis (BOPB)-sparse functions of many variables which are too hideously high-dimensional to be learned by other means. Both numerics and theoretical recovery guarantees will be presented.&quot;--Page ii.","abstract_has_math":false,"creators":["Choi, Bosu"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Iwen, Mark","Christlieb, Andrew","Zhou, Zhengfeng","Cheng, Yingda","Hirn, Matthew"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2018,"date_issued":"2018","date_published":"2018","updated_at":"2026-11-18T17:43:12Z","subjects":["Harmonic functions","Fourier transformations"],"languages":["English"],"rights":["In Copyright"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["etd:19383","isbn:9780438300750","isbn:0438300750","oclc:1078988135","umi:10929241","local:Choi_grad.msu_0128D_16277"],"render_values":[{"text":"etd:19383","href":null,"code":true},{"text":"isbn:9780438300750","href":null,"code":true},{"text":"isbn:0438300750","href":null,"code":true},{"text":"oclc:1078988135","href":null,"code":true},{"text":"umi:10929241","href":null,"code":true},{"text":"local:Choi_grad.msu_0128D_16277","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://doi.org/doi:10.25335/fq73-3154","outbound_label":"DOI","outbound_source":"dc:identifier","record_url":"https://doi.org/doi:10.25335/fq73-3154","record_label":"Repository record","record_kind":"doi","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://d.lib.msu.edu/oai?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Ad.lib.msu.edu%3Aetd_19383","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Iwen, Mark","Christlieb, Andrew","Zhou, Zhengfeng","Cheng, Yingda","Hirn, Matthew"]},{"key":"dc:creator","label":"Author","values":["Choi, Bosu"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2018"]},{"key":"dc:relation","label":"Dc Relation","values":["Electronic Theses & Dissertations"]},{"key":"dc:type","label":"Dc Type","values":["Text","Theses"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Harmonic functions","Fourier transformations"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]},{"key":"dc:rights","label":"Dc Rights","values":["In Copyright"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["etd:19383","isbn:9780438300750","isbn:0438300750","oclc:1078988135","umi:10929241","local:Choi_grad.msu_0128D_16277","https://doi.org/doi:10.25335/fq73-3154"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["\"We develop fast function learning algorithms given an assumption that a function can be well approximated by the expansion of a few high-dimensional basis functions. Considering the tensorized Fourier basis functions, several versions of high-dimensional sparse Fourier transforms (SFTs) are discussed. One-dimensional sparse Fourier transforms introduced in [1] and [2] quickly approximate functions represented by only s Fourier basis functions using a few samples (function evaluations) without noise and with noise respectively. The algorithms can be directly applied to compute the Fourier transform of the high-dimensional functions. However, it becomes hard to implement them if the dimension gets too large. In this thesis, we introduce two new concepts: partial unwrapping and tilting. These two ideas allow us to efficiently compute the high-dimensional sparse Fourier transforms using the ideas in [1] and [2]. Furthermore, we develop sublinear-time compressive sensing methods to approximate the multivariate functions by the expansion of a few bounded orthonormal product (BOP) bases which include tensorized Fourier basis functions. These new methods are obtained from CoSaMP by replacing its usual support identification procedure with a new faster one inspired by fast SFT techniques. The resulting sublinearized CoSaMP method allows for the rapid approximation of bounded orthonormal product basis (BOPB)-sparse functions of many variables which are too hideously high-dimensional to be learned by other means. Both numerics and theoretical recovery guarantees will be presented.\"--Page ii.","(Ph. D.)--Michigan State University. Applied Mathematics, 2018","Includes bibliographical references (pages 133-136)"]},{"key":"dc:format","label":"Dc Format","values":["viii, 136 pages","application/pdf"]},{"key":"dc:title","label":"Title","values":["Sparse harmonic transforms"]}]}],"canonical_facts":{"dc:contributor":["Iwen, Mark","Christlieb, Andrew","Zhou, Zhengfeng","Cheng, Yingda","Hirn, Matthew"],"dc:creator":["Choi, Bosu"],"dc:date":["2018"],"dc:description":["\"We develop fast function learning algorithms given an assumption that a function can be well approximated by the expansion of a few high-dimensional basis functions. Considering the tensorized Fourier basis functions, several versions of high-dimensional sparse Fourier transforms (SFTs) are discussed. One-dimensional sparse Fourier transforms introduced in [1] and [2] quickly approximate functions represented by only s Fourier basis functions using a few samples (function evaluations) without noise and with noise respectively. The algorithms can be directly applied to compute the Fourier transform of the high-dimensional functions. However, it becomes hard to implement them if the dimension gets too large. In this thesis, we introduce two new concepts: partial unwrapping and tilting. These two ideas allow us to efficiently compute the high-dimensional sparse Fourier transforms using the ideas in [1] and [2]. Furthermore, we develop sublinear-time compressive sensing methods to approximate the multivariate functions by the expansion of a few bounded orthonormal product (BOP) bases which include tensorized Fourier basis functions. These new methods are obtained from CoSaMP by replacing its usual support identification procedure with a new faster one inspired by fast SFT techniques. The resulting sublinearized CoSaMP method allows for the rapid approximation of bounded orthonormal product basis (BOPB)-sparse functions of many variables which are too hideously high-dimensional to be learned by other means. Both numerics and theoretical recovery guarantees will be presented.\"--Page ii.","(Ph. D.)--Michigan State University. Applied Mathematics, 2018","Includes bibliographical references (pages 133-136)"],"dc:format":["viii, 136 pages","application/pdf"],"dc:identifier":["etd:19383","isbn:9780438300750","isbn:0438300750","oclc:1078988135","umi:10929241","local:Choi_grad.msu_0128D_16277","https://doi.org/doi:10.25335/fq73-3154"],"dc:language":["English"],"dc:relation":["Electronic Theses & Dissertations"],"dc:rights":["In Copyright"],"dc:subject":["Harmonic functions","Fourier transformations"],"dc:title":["Sparse harmonic transforms"],"dc:type":["Text","Theses"]},"updated_at":"2026-11-18T17:43:12Z"}