A Combinatorial Aliasing-Based Sparse Fourier Transform

Pengcheng QIU; Feng YU

doi:10.1587/transfun.E98.A.1968

A Combinatorial Aliasing-Based Sparse Fourier Transform

Pengcheng QIU, Feng YU

Full Text Views

0

Cite this

Summary :

The sparse Fourier transform (SFT) seeks to recover k non-negligible Fourier coefficients from a k-sparse signal of length N (k«N). A single frequency signal can be recovered via the Chinese remainder theorem (CRT) with sub-sampled discrete Fourier transforms (DFTs). However, when there are multiple non-negligible coefficients, more of them may collide, and multiple stages of sub-sampled DFTs are needed to deal with such collisions. In this paper, we propose a combinatorial aliasing-based SFT (CASFT) algorithm that is robust to noise and greatly reduces the number of stages by iteratively recovering coefficients. First, CASFT detects collisions and recovers coefficients via the CRT in a single stage. These coefficients are then subtracted from each stage, and the process iterates through the other stages. With a computational complexity of O(klog klog ²N) and sample complexity of O(klog ²N), CASFT is a novel and efficient SFT algorithm.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E98-A No.9 pp.1968-1972

Publication Date: 2015/09/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E98.A.1968

Type of Manuscript: LETTER

Category: Digital Signal Processing

Authors

Pengcheng QIU
Zhejiang University
Feng YU
Zhejiang University

Keyword

sparse Fourier transform, Chinese remainder theorem, aliasing, noise robustness

Cite this

Copy

Pengcheng QIU, Feng YU, "A Combinatorial Aliasing-Based Sparse Fourier Transform" in IEICE TRANSACTIONS on Fundamentals, vol. E98-A, no. 9, pp. 1968-1972, September 2015, doi: 10.1587/transfun.E98.A.1968.
Abstract: The sparse Fourier transform (SFT) seeks to recover k non-negligible Fourier coefficients from a k-sparse signal of length N (k«N). A single frequency signal can be recovered via the Chinese remainder theorem (CRT) with sub-sampled discrete Fourier transforms (DFTs). However, when there are multiple non-negligible coefficients, more of them may collide, and multiple stages of sub-sampled DFTs are needed to deal with such collisions. In this paper, we propose a combinatorial aliasing-based SFT (CASFT) algorithm that is robust to noise and greatly reduces the number of stages by iteratively recovering coefficients. First, CASFT detects collisions and recovers coefficients via the CRT in a single stage. These coefficients are then subtracted from each stage, and the process iterates through the other stages. With a computational complexity of O(klog klog ²N) and sample complexity of O(klog ²N), CASFT is a novel and efficient SFT algorithm.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E98.A.1968/_p

Copy

@ARTICLE{e98-a_9_1968,
author={Pengcheng QIU, Feng YU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Combinatorial Aliasing-Based Sparse Fourier Transform},
year={2015},
volume={E98-A},
number={9},
pages={1968-1972},
abstract={The sparse Fourier transform (SFT) seeks to recover k non-negligible Fourier coefficients from a k-sparse signal of length N (k«N). A single frequency signal can be recovered via the Chinese remainder theorem (CRT) with sub-sampled discrete Fourier transforms (DFTs). However, when there are multiple non-negligible coefficients, more of them may collide, and multiple stages of sub-sampled DFTs are needed to deal with such collisions. In this paper, we propose a combinatorial aliasing-based SFT (CASFT) algorithm that is robust to noise and greatly reduces the number of stages by iteratively recovering coefficients. First, CASFT detects collisions and recovers coefficients via the CRT in a single stage. These coefficients are then subtracted from each stage, and the process iterates through the other stages. With a computational complexity of O(klog klog ²N) and sample complexity of O(klog ²N), CASFT is a novel and efficient SFT algorithm.},
keywords={},
doi={10.1587/transfun.E98.A.1968},
ISSN={1745-1337},
month={September},}

Copy

TY - JOUR
TI - A Combinatorial Aliasing-Based Sparse Fourier Transform
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1968
EP - 1972
AU - Pengcheng QIU
AU - Feng YU
PY - 2015
DO - 10.1587/transfun.E98.A.1968
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E98-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2015
AB - The sparse Fourier transform (SFT) seeks to recover k non-negligible Fourier coefficients from a k-sparse signal of length N (k«N). A single frequency signal can be recovered via the Chinese remainder theorem (CRT) with sub-sampled discrete Fourier transforms (DFTs). However, when there are multiple non-negligible coefficients, more of them may collide, and multiple stages of sub-sampled DFTs are needed to deal with such collisions. In this paper, we propose a combinatorial aliasing-based SFT (CASFT) algorithm that is robust to noise and greatly reduces the number of stages by iteratively recovering coefficients. First, CASFT detects collisions and recovers coefficients via the CRT in a single stage. These coefficients are then subtracted from each stage, and the process iterates through the other stages. With a computational complexity of O(klog klog ²N) and sample complexity of O(klog ²N), CASFT is a novel and efficient SFT algorithm.
ER -