Computing reconstructions from nonuniform Fourier samples: universality of stability barriers and stable sampling rates

DOI10.1016/J.ACHA.2017.05.004MaRDI QIDQ1713634zbMATH OpenOpenAlexFDO

Authors Ben Adcock, Milana Gataric, José Luis Romero

Publication date 25 January 2019

Published in Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.07698

compactly supported function frame bounds nonuniform Fourier samples rate of convergence reconstruction of algebraic polynomials reconstruction of wavelet coefficients stable recovery

Mathematics Subject Classification ID

Trigonometric approximation (42A10) General harmonic expansions, frames (42C15) Nontrigonometric harmonic analysis involving wavelets and other special systems (42C40) Numerical methods for trigonometric approximation and interpolation (65T40) Numerical methods for wavelets (65T60) Application of orthogonal and other special functions (94A11) Sampling theory in information and communication theory (94A20)

Abstract: We study the problem of recovering an unknown compactly-supported multivariate function from samples of its Fourier transform that are acquired nonuniformly, i.e. not necessarily on a uniform Cartesian grid. Reconstruction problems of this kind arise in various imaging applications, where Fourier samples are taken along radial lines or spirals for example. Specifically, we consider finite-dimensional reconstructions, where a limited number of samples is available, and investigate the rate of convergence of such approximate solutions and their numerical stability. We show that the proportion of Fourier samples that allow for stable approximations of a given numerical accuracy is independent of the specific sampling geometry and is therefore universal for different sampling scenarios. This allows us to relate both sufficient and necessary conditions for different sampling setups and to exploit several results that were previously available only for very specific sampling geometries. The results are obtained by developing: (i) a transference argument for different measures of the concentration of the Fourier transform and Fourier samples; (ii) frame bounds valid up to the critical sampling density, which depend explicitly on the sampling set and the spectrum. As an application, we identify sufficient and necessary conditions for stable and accurate reconstruction of algebraic polynomials or wavelet coefficients from nonuniform Fourier data.

Review text

Let \(D \subset {\mathbb R}^d\) be a centered symmetric convex body, where a convex body is a compact convex set with non-empty interior. The authors reconstruct \(f\in L^2(D)\) from finitely many nonuniform samples of its Fourier transform taken on a closed countable subset \(\Omega \subset {\mathbb R}^d\) which fulfills certain gap condition. Such problems arise in various imaging applications, where Fourier samples are taken along radial lines or spirals. The authors apply an abstract theory of finite-dimensional approximation of continuous sampling problems presented by \textit{B. Adcock} et al. [SIAM J. Imaging Sci. 7, No. 3, 1690--1723 (2014; Zbl 1308.94045)]. They investigate the rate of convergence of approximate solutions and their numerical stability. It is shown that the proportion of Fourier samples that allow for stable approximations of a given accuracy is independent of the specific sampling geometry. For \(d=1\) and \(d=2\), the authors identify necessary and sufficient conditions for stable reconstruction of algebraic polynomials and wavelet coefficients from nonuniform Fourier data. Numerical experiments for stable recovery of wavelet coefficients from nonuniform Fourier samples are presented in [\textit{M. Gataric} and \textit{C. Poon}, SIAM J. Sci. Comput. 38, No. 2, A1075--A1099 (2016; Zbl 1343.65151)].

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Computing reconstructions from nonuniform Fourier samples: universality of stability barriers and stable sampling rates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1713634)