Back to search

Michigan State University

Sparse harmonic transforms

Abstract

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.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Choi, Bosu
Contributors dc:contributor
  • Iwen, Mark
  • Christlieb, Andrew
  • Zhou, Zhengfeng
  • Cheng, Yingda
  • Hirn, Matthew

Subjects

dc:subject × 2

Rights

dc:rights
Statement dc:rights
  • In Copyright
Language dc:language
English

Identifiers

dc:identifier.*
Identifier
etd:19383
isbn:9780438300750
isbn:0438300750
oclc:1078988135
umi:10929241
local:Choi_grad.msu_0128D_16277

Chain of custody

source
Harvested from
Michigan State University
Base URL
d.lib.msu.edu/oai
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Choi, Bosu. Sparse harmonic transforms. 2018. https://doi.org/doi:10.25335/fq73-3154