Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Deterministic Sparse FFT for Functions with Structured Fourier Sparsity
104
0
0.0
(
0
)
Added by
Sina Bittens
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Authors
Sina Bittens
Ask ChatGPT about the research
No Arabic abstract
In this paper a deterministic sparse Fourier transform algorithm is presented which breaks the quadratic-in-sparsity runtime bottleneck for a large class of periodic functions exhibiting structured frequency support. These functions include, e.g., the oft-considered set of block frequency sparse functions of the form $$f(x) = sum^{n}_{j=1} sum^{B-1}_{k=0} c_{omega_j + k} e^{i(omega_j + k)x},~~{ omega_1, dots, omega_n } subset left(-leftlceil frac{N}{2}rightrceil, leftlfloor frac{N}{2}rightrfloorright]capmathbb{Z}$$ as a simple subclass. Theoretical error bounds in combination with numerical experiments demonstrate that the newly proposed algorithms are both fast and robust to noise. In particular, they outperform standard sparse Fourier transforms in the rapid recovery of block frequency sparse functions of the type above.
rate research
Read More
In this paper we revisit the deterministic version of the Sparse Fourier Transform problem, which asks to read only a few entries of $x in mathbb{C}^n$ and design a recovery algorithm such that the output of the algorithm approximates $hat x$, the Discrete Fourier Transform (DFT) of $x$. The randomized case has been well-understood, while the main work in the deterministic case is that of Merhi et al.@ (J Fourier Anal Appl 2018), which obtains $O(k^2 log^{-1}k cdot log^{5.5}n)$ samples and a similar runtime with the $ell_2/ell_1$ guarantee. We focus on the stronger $ell_{infty}/ell_1$ guarantee and the closely related problem of incoherent matrices. We list our contributions as follows. 1. We find a deterministic collection of $O(k^2 log n)$ samples for the $ell_infty/ell_1$ recovery in time $O(nk log^2 n)$, and a deterministic collection of $O(k^2 log^2 n)$ samples for the $ell_infty/ell_1$ sparse recovery in time $O(k^2 log^3n)$. 2. We give new deterministic constructions of incoherent matrices that are row-sampled submatrices of the DFT matrix, via a derandomization of Bernsteins inequality and bounds on exponential sums considered in analytic number theory. Our first construction matches a previous randomized construction of Nelson, Nguyen and Woodruff (RANDOM12), where there was no constraint on the form of the incoherent matrix. Our algorithms are nearly sample-optimal, since a lower bound of $Omega(k^2 + k log n)$ is known, even for the case where the sensing matrix can be arbitrarily designed. A similar lower bound of $Omega(k^2 log n/ log k)$ is known for incoherent matrices.
We propose a deterministic Kaczmarz method for solving linear systems $Ax=b$ with $A$ nonsingular. Instead of using orthogonal projections, we use reflections in the original Kaczmarz iterative method. This generates a series of points on an $n$-sphere $S$ centered at the solution $x_*=A^{-1}b$. We show that these points are nicely distributed on $S$. Taking the average of several points will lead to an effective approximation to the solution. We will show how to choose these points efficiently. The numerical tests show that in practice this deterministic scheme converges much faster than we expected and can beat the (block) randomized Kaczmarz methods.
Computing the dominant Fourier coefficients of a vector is a common task in many fields, such as signal processing, learning theory, and computational complexity. In the Sparse Fast Fourier Transform (Sparse FFT) problem, one is given oracle access to a $d$-dimensional vector $x$ of size $N$, and is asked to compute the best $k$-term approximation of its Discrete Fourier Transform, quickly and using few samples of the input vector $x$. While the sample complexity of this problem is quite well understood, all previous approaches either suffer from an exponential dependence of runtime on the dimension $d$ or can only tolerate a trivial amount of noise. This is in sharp contrast with the classical FFT algorithm of Cooley and Tukey, which is stable and completely insensitive to the dimension of the input vector: its runtime is $O(Nlog N)$ in any dimension $d$. In this work, we introduce a new high-dimensional Sparse FFT toolkit and use it to obtain new algorithms, both on the exact, as well as in the case of bounded $ell_2$ noise. This toolkit includes i) a new strategy for exploring a pruned FFT computation tree that reduces the cost of filtering, ii) new structural properties of adaptive aliasing filters recently introduced by Kapralov, Velingker and ZandiehSODA19, and iii) a novel lazy estimation argument, suited to reducing the cost of estimation in FFT tree-traversal approaches. Our robust algorithm can be viewed as a highly optimized sparse, stable extension of the Cooley-Tukey FFT algorithm. Finally, we explain the barriers we have faced by proving a conditional quadratic lower bound on the running time of the well-studied non-equispaced Fourier transform problem. This resolves a natural and frequently asked question in computational Fourier transforms. Lastly, we provide a preliminary experimental evaluation comparing the runtime of our algorithm to FFTW and SFFT 2.0.
Traditional probabilistic methods for the simulation of advection-diffusion equations (ADEs) often overlook the entropic contribution of the discretization, e.g., the number of particles, within associated numerical methods. Many times, the gain in accuracy of a highly discretized numerical model is outweighed by its associated computational costs or the noise within the data. We address the question of how many particles are needed in a simulation to best approximate and estimate parameters in one-dimensional advective-diffusive transport. To do so, we use the well-known Akaike Information Criterion (AIC) and a recently-developed correction called the Computational Information Criterion (COMIC) to guide the model selection process. Random-walk and mass-transfer particle tracking methods are employed to solve the model equations at various levels of discretization. Numerical results demonstrate that the COMIC provides an optimal number of particles that can describe a more efficient model in terms of parameter estimation and model prediction compared to the model selected by the AIC even when the data is sparse or noisy, the sampling volume is not uniform throughout the physical domain, or the error distribution of the data is non-IID Gaussian.
This paper proposes a novel, rigorous and simple Fourier-transformation approach to study resonances in a perfectly conducting slab with finite number of subwavelength slits of width $hll 1$. Since regions outside the slits are variable separated, by Fourier transforming the governing equation, we could express field in the outer regions in terms of field derivatives on the aperture. Next, in each slit where variable separation is still available, wave field could be expressed as a Fourier series in terms of a countable basis functions with unknown Fourier coefficients. Finally, by matching field on the aperture, we establish a linear system of infinite number of equations governing the countable Fourier coefficients. By carefully asymptotic analysis of each entry of the coefficient matrix, we rigorously show that, by removing only a finite number of rows and columns, the resulting principle sub-matrix is diagonally dominant so that the infinite dimensional linear system can be reduced to a finite dimensional linear system. Resonance frequencies are exactly those frequencies making the linear system rank-deficient. This in turn provides a simple, asymptotic formula describing resonance frequencies with accuracy ${cal O}(h^3log h)$. We emphasize that such a formula is more accurate than all existing results and is the first accurate result especially for slits of number more than two to our best knowledge. Moreover, this asymptotic formula rigorously confirms a fact that the imaginary part of resonance frequencies is always ${cal O}(h)$ no matter how we place the slits as long as they are spaced by distances independent of width $h$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
