Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFPS-SFT: A Multi-dimensional Sparse Fourier Transform Based on the Fourier Projection-slice Theorem
376
0
0.0
(
0
)
Added by
Shaogang Wang
Publication date
2017
fields
Electronic Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We propose a multi-dimensional (M-D) sparse Fourier transform inspired by the idea of the Fourier projection-slice theorem, called FPS-SFT. FPS-SFT extracts samples along lines (1-dimensional slices from an M-D data cube), which are parameterized by random slopes and offsets. The discrete Fourier transform (DFT) along those lines represents projections of M-D DFT of the M-D data onto those lines. The M-D sinusoids that are contained in the signal can be reconstructed from the DFT along lines with a low sample and computational complexity provided that the signal is sparse in the frequency domain and the lines are appropriately designed. The performance of FPS-SFT is demonstrated both theoretically and numerically. A sparse image reconstruction application is illustrated, which shows the capability of the FPS-SFT in solving practical problems.
rate research
Read More
The state-of-the-art automotive radars employ multidimensional discrete Fourier transforms (DFT) in order to estimate various target parameters. The DFT is implemented using the fast Fourier transform (FFT), at sample and computational complexity of $O(N)$ and $O(N log N)$, respectively, where $N$ is the number of samples in the signal space. We have recently proposed a sparse Fourier transform based on the Fourier projection-slice theorem (FPS-SFT), which applies to multidimensional signals that are sparse in the frequency domain. FPS-SFT achieves sample complexity of $O(K)$ and computational complexity of $O(K log K)$ for a multidimensional, $K$-sparse signal. While FPS-SFT considers the ideal scenario, i.e., exactly sparse data that contains on-grid frequencies, in this paper, by extending FPS-SFT into a robust version (RFPS-SFT), we emphasize on addressing noisy signals that contain off-grid frequencies; such signals arise from radar applications. This is achieved by employing a windowing technique and a voting-based frequency decoding procedure; the former reduces the frequency leakage of the off-grid frequencies below the noise level to preserve the sparsity of the signal, while the latter significantly lowers the frequency localization error stemming from the noise. The performance of the proposed method is demonstrated both theoretically and numerically.
In this paper, we theoretically propose a new hashing scheme to establish the sparse Fourier transform in high-dimensional space. The estimation of the algorithm complexity shows that this sparse Fourier transform can overcome the curse of dimensionality. To the best of our knowledge, this is the first polynomial-time algorithm to recover the high-dimensional continuous frequencies.
The Discrete Fourier Transform (DFT) is a fundamental computational primitive, and the fastest known algorithm for computing the DFT is the FFT (Fast Fourier Transform) algorithm. One remarkable feature of FFT is the fact that its runtime depends only on the size $N$ of the input vector, but not on the dimensionality of the input domain: FFT runs in time $O(Nlog N)$ irrespective of whether the DFT in question is on $mathbb{Z}_N$ or $mathbb{Z}_n^d$ for some $d>1$, where $N=n^d$. The state of the art for Sparse FFT, i.e. the problem of computing the DFT of a signal that has at most $k$ nonzeros in Fourier domain, is very different: all current techniques for sublinear time computation of Sparse FFT incur an exponential dependence on the dimension $d$ in the runtime. In this paper we give the first algorithm that computes the DFT of a $k$-sparse signal in time $text{poly}(k, log N)$ in any dimension $d$, avoiding the curse of dimensionality inherent in all previously known techniques. Our main tool is a new class of filters that we refer to as adaptive aliasing filters: these filters allow isolating frequencies of a $k$-Fourier sparse signal using $O(k)$ samples in time domain and $O(klog N)$ runtime per frequency, in any dimension $d$. We also investigate natural average case models of the input signal: (1) worst case support in Fourier domain with randomized coefficients and (2) random locations in Fourier domain with worst case coefficients. Our techniques lead to an $widetilde O(k^2)$ time algorithm for the former and an $widetilde O(k)$ time algorithm for the latter.
By a novel reciprocal space analysis of the measurement, we report a calibrated in situ observation of the bunching effect in a 3D ultracold gas. The calibrated measurement with no free parameters confirms the role of the exchange symmetry and the Hanbury Brown-Twiss effect in the bunching. Also, the enhanced fluctuations of the bunching effect give a quantitative measure of the increased isothermal compressibility. We use 2D images to probe the 3D gas, using the same principle by which computerized tomography reconstructs a 3D image of a body. The powerful reciprocal space technique presented is applicable to systems with one, two, or three dimensions.
In this paper, we redefine the Graph Fourier Transform (GFT) under the DSP$_mathrm{G}$ framework. We consider the Jordan eigenvectors of the directed Laplacian as graph harmonics and the corresponding eigenvalues as the graph frequencies. For this purpose, we propose a shift operator based on the directed Laplacian of a graph. Based on our shift operator, we then define total variation of graph signals, which is used in frequency ordering. We achieve natural frequency ordering and interpretation via the proposed definition of GFT. Moreover, we show that our proposed shift operator makes the LSI filters under DSP$_mathrm{G}$ to become polynomial in the directed Laplacian.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
