BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Ben Adcock

Ben Adcock appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.NAInformation Theorymath.ITNumerical AnalysisMachine Learningmath.FAComputer Vision

Catalog footprint

What is connected

38works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

38 published item(s)

preprint2026arXiv

Christoffel-DPS: Optimal sensor placement in diffusion posterior sampling for arbitrary distributions

State estimation is a critical task in scientific, engineering and control applications. Since the reliability of reconstructions depends on the number and position of sensors, optimal sensor placement (OSP) is essential in scenarios where measurements are sparse and expensive. Classical OSP approaches rely on Gaussian assumptions and are consequently unable to account for the complex distributions encountered in many real-world systems. Generative-model-based reconstruction using sensor guided diffusion posterior sampling (DPS) has emerged as a promising technique for reconstructing states from highly complex distributions. However, existing sensor-selection methods either require unrealistically many sensors or emulate classical OSP, creating a mismatch between modern recovery models with classical OSP tools motivating the need for fundamentally new ideas towards OSP that match the recent advances made in powerful recovery models. We introduce a distribution-free sensor placement framework based on the Christoffel function: a mathematical formulation of optimal sampling and recovery guarantees for posterior sampling with arbitrary sensors and signal distributions, from which we derive a new OSP strategy with non-asymptotic bounds on the number of sensors needed for recovery. We develop Christoffel-DPS, with offline and online variants, instantiating Christoffel sampling for generative models. Christoffel-DPS outperforms Gaussian OSP baselines and existing generative-model placement methods, validating that distribution-free sensing is both theoretically principled and practically superior. The framework is model-agnostic; we demonstrate its application to a range of unconditional DPS and flow-matching models on structurally non-Gaussian benchmarks, showing the efficacy of Christoffel-DPS in low sensor budget regimes.

0 citations0 reviewsNo code linkedOpen access
preprint2026arXiv

GRIFDIR: Graph Resolution-Invariant FEM Diffusion Models in Function Spaces over Irregular Domains

Score-based diffusion models in infinite-dimensional function spaces provide a mathematically principled framework for modelling function-valued data, offering key advantages such as resolution invariance and the ability to handle irregular discretisations. However, practical implementations have struggled to fully realise these benefits. Existing backbones like Fourier neural operators are often biased towards regular grids and fail to generalise to complex domain topologies. We propose a novel architecture for function-space diffusion models that represents generalised graph convolutional kernels as finite element functions, enabling the model to naturally handle unstructured meshes and complex geometries. We demonstrate the efficacy of our network architecture through a series of unconditional and conditional sampling experiments across diverse geometries, including non-convex and multiply-connected domains. Our results show that the proposed method maintains resolution invariance and achieves high fidelity in capturing functional distributions on non-trivial geometries.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

CAS4DL: Christoffel Adaptive Sampling for function approximation via Deep Learning

The problem of approximating smooth, multivariate functions from sample points arises in many applications in scientific computing, e.g., in computational Uncertainty Quantification (UQ) for science and engineering. In these applications, the target function may represent a desired quantity of interest of a parameterized Partial Differential Equation (PDE). Due to the large cost of solving such problems, where each sample is computed by solving a PDE, sample efficiency is a key concerning these applications. Recently, there has been increasing focus on the use of Deep Neural Networks (DNN) and Deep Learning (DL) for learning such functions from data. In this work, we propose an adaptive sampling strategy, CAS4DL (Christoffel Adaptive Sampling for Deep Learning) to increase the sample efficiency of DL for multivariate function approximation. Our novel approach is based on interpreting the second to last layer of a DNN as a dictionary of functions defined by the nodes on that layer. With this viewpoint, we then define an adaptive sampling strategy motivated by adaptive sampling schemes recently proposed for linear approximation schemes, wherein samples are drawn randomly with respect to the Christoffel function of the subspace spanned by this dictionary. We present numerical experiments comparing CAS4DL with standard Monte Carlo (MC) sampling. Our results demonstrate that CAS4DL often yields substantial savings in the number of samples required to achieve a given accuracy, particularly in the case of smooth activation functions, and it shows a better stability in comparison to MC. These results therefore are a promising step towards fully adapting DL towards scientific computing applications.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Fast and stable approximation of analytic functions from equispaced samples via polynomial frames

We consider approximating analytic functions on the interval $[-1,1]$ from their values at a set of $m+1$ equispaced nodes. A result of Platte, Trefethen \& Kuijlaars states that fast and stable approximation from equispaced samples is generally impossible. In particular, any method that converges exponentially fast must also be exponentially ill-conditioned. We prove a positive counterpart to this `impossibility' theorem. Our `possibility' theorem shows that there is a well-conditioned method that provides exponential decay of the error down to a finite, but user-controlled tolerance $ε> 0$, which in practice can be chosen close to machine epsilon. The method is known as \textit{polynomial frame} approximation or \textit{polynomial extensions}. It uses algebraic polynomials of degree $n$ on an extended interval $[-γ,γ]$, $γ> 1$, to construct an approximation on $[-1,1]$ via a SVD-regularized least-squares fit. A key step in the proof of our main theorem is a new result on the maximal behaviour of a polynomial of degree $n$ on $[-1,1]$ that is simultaneously bounded by one at a set of $m+1$ equispaced nodes in $[-1,1]$ and $1/ε$ on the extended interval $[-γ,γ]$. We show that linear oversampling, i.e., $m = c n \log(1/ε) / \sqrt{γ^2-1}$, is sufficient for uniform boundedness of any such polynomial on $[-1,1]$. This result aside, we also prove an extended impossibility theorem, which shows that such a possibility theorem (and consequently the method of polynomial frame approximation) is essentially optimal.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Towards optimal sampling for learning sparse approximation in high dimensions

In this chapter, we discuss recent work on learning sparse approximations to high-dimensional functions on data, where the target functions may be scalar-, vector- or even Hilbert space-valued. Our main objective is to study how the sampling strategy affects the sample complexity -- that is, the number of samples that suffice for accurate and stable recovery -- and to use this insight to obtain optimal or near-optimal sampling procedures. We consider two settings. First, when a target sparse representation is known, in which case we present a near-complete answer based on drawing independent random samples from carefully-designed probability measures. Second, we consider the more challenging scenario when such representation is unknown. In this case, while not giving a full answer, we describe a general construction of sampling measures that improves over standard Monte Carlo sampling. We present examples using algebraic and trigonometric polynomials, and for the former, we also introduce a new procedure for function approximation on irregular (i.e., nontensorial) domains. The effectiveness of this procedure is shown through numerical examples. Finally, we discuss a number of structured sparsity models, and how they may lead to better approximations.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Deep Neural Networks Are Effective At Learning High-Dimensional Hilbert-Valued Functions From Limited Data

Accurate approximation of scalar-valued functions from sample points is a key task in computational science. Recently, machine learning with Deep Neural Networks (DNNs) has emerged as a promising tool for scientific computing, with impressive results achieved on problems where the dimension of the data or problem domain is large. This work broadens this perspective, focusing on approximating functions that are Hilbert-valued, i.e. take values in a separable, but typically infinite-dimensional, Hilbert space. This arises in science and engineering problems, in particular those involving solution of parametric Partial Differential Equations (PDEs). Such problems are challenging: 1) pointwise samples are expensive to acquire, 2) the function domain is high dimensional, and 3) the range lies in a Hilbert space. Our contributions are twofold. First, we present a novel result on DNN training for holomorphic functions with so-called hidden anisotropy. This result introduces a DNN training procedure and full theoretical analysis with explicit guarantees on error and sample complexity. The error bound is explicit in three key errors occurring in the approximation procedure: the best approximation, measurement, and physical discretization errors. Our result shows that there exists a procedure (albeit non-standard) for learning Hilbert-valued functions via DNNs that performs as well as, but no better than current best-in-class schemes. It gives a benchmark lower bound for how well DNNs can perform on such problems. Second, we examine whether better performance can be achieved in practice through different types of architectures and training. We provide preliminary numerical results illustrating practical performance of DNNs on parametric PDEs. We consider different parameters, modifying the DNN architecture to achieve better and competitive results, comparing these to current best-in-class schemes.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Do log factors matter? On optimal wavelet approximation and the foundations of compressed sensing

A signature result in compressed sensing is that Gaussian random sampling achieves stable and robust recovery of sparse vectors under optimal conditions on the number of measurements. However, in the context of image reconstruction, it has been extensively documented that sampling strategies based on Fourier measurements outperform this purportedly optimal approach. Motivated by this seeming paradox, we investigate the problem of optimal sampling for compressed sensing. Rigorously combining the theories of wavelet approximation and infinite-dimensional compressed sensing, our analysis leads to new error bounds in terms of the total number of measurements $m$ for the approximation of piecewise $α$-Hölder functions. Our theoretical findings suggest that Fourier sampling outperforms random Gaussian sampling when the Hölder exponent $α$ is large enough. Moreover, we establish a provably optimal sampling strategy. This work is an important first step towards the resolution of the claimed paradox, and provides a clear theoretical justification for the practical success of compressed sensing techniques in imaging problems.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

The gap between theory and practice in function approximation with deep neural networks

Deep learning (DL) is transforming industry as decision-making processes are being automated by deep neural networks (DNNs) trained on real-world data. Driven partly by rapidly-expanding literature on DNN approximation theory showing they can approximate a rich variety of functions, such tools are increasingly being considered for problems in scientific computing. Yet, unlike traditional algorithms in this field, little is known about DNNs from the principles of numerical analysis, e.g., stability, accuracy, computational efficiency and sample complexity. In this paper we introduce a computational framework for examining DNNs in practice, and use it to study empirical performance with regard to these issues. We study performance of DNNs of different widths & depths on test functions in various dimensions, including smooth and piecewise smooth functions. We also compare DL against best-in-class methods for smooth function approx. based on compressed sensing (CS). Our main conclusion from these experiments is that there is a crucial gap between the approximation theory of DNNs and their practical performance, with trained DNNs performing relatively poorly on functions for which there are strong approximation results (e.g. smooth functions), yet performing well in comparison to best-in-class methods for other functions. To analyze this gap further, we provide some theoretical insights. We establish a practical existence theorem, asserting existence of a DNN architecture and training procedure that offers the same performance as CS. This establishes a key theoretical benchmark, showing the gap can be closed, albeit via a strategy guaranteed to perform as well as, but no better than, current best-in-class schemes. Nevertheless, it demonstrates the promise of practical DNN approx., by highlighting potential for better schemes through careful design of DNN architectures and training strategies.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Approximating smooth, multivariate functions on irregular domains

In this paper, we introduce a method known as polynomial frame approximation for approximating smooth, multivariate functions defined on irregular domains in $d$ dimensions, where $d$ can be arbitrary. This method is simple, and relies only on orthogonal polynomials on a bounding tensor-product domain. In particular, the domain of the function need not be known in advance. When restricted to a subdomain, an orthonormal basis is no longer a basis, but a frame. Numerical computations with frames present potential difficulties, due to the near-linear dependence of the truncated approximation system. Nevertheless, well-conditioned approximations can be obtained via regularization, for instance, truncated singular value decompositions. We comprehensively analyze such approximations in this paper, providing error estimates for functions with both classical and mixed Sobolev regularity, with the latter being particularly suitable for higher-dimensional problems. We also analyze the sample complexity of the approximation for sample points chosen randomly according to a probability measure, providing estimates in terms of the corresponding \textit{Nikolskii inequality} for the domain. In particular, we show that the sample complexity for points drawn from the uniform measure is quadratic (up to a log factor) in the dimension of the polynomial space, independently of $d$, for a large class of nontrivial domains. This extends a well-known result for polynomial approximation in hypercubes.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Frame approximation with bounded coefficients

Due to their flexibility, frames of Hilbert spaces are attractive alternatives to bases in approximation schemes for problems where identifying a basis is not straightforward or even feasible. Computing a best approximation using frames, however, can be challenging since it requires solving an ill-conditioned linear system. One consequence of this ill-conditioning is that the coefficients of such a frame approximation can grow large. In this paper we resolve this issue by introducing two methods for frame approximation that possess bounded coefficients. As we show, these methods typically lead to little or no deterioration in the approximation accuracy, but successfully avoid the large coefficients inherent to previous approaches, thus making them attractive in situations where large coefficients are undesirable. We also present theoretical analysis to support these conclusions.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Frames and numerical approximation II: generalized sampling

In a previous paper [Adcock & Huybrechs, 2019] we described the numerical approximation of functions using redundant sets and frames. Redundancy in the function representation offers enormous flexibility compared to using a basis, but ill-conditioning often prevents the numerical computation of best approximations. We showed that, in spite of said ill-conditioning, approximations with regularization may still provide accuracy up to order $\sqrtε$, where $ε$ is a small truncation threshold. When using frames, i.e. complete systems that are generally redundant but which provide infinite representations with coefficients of bounded norm, this accuracy can actually be achieved for all functions in a space. Here, we generalize that setting in two ways. We assume information or samples from $f$ from a wide class of linear operators acting on $f$, rather than inner products associated with the best approximation projection. This enables the analysis of fully discrete approximations based, for instance, on function values only. Next, we allow oversampling, leading to least-squares approximations. We show that this leads to much improved accuracy on the order of $ε$ rather than $\sqrtε$. Overall, we demonstrate that numerical function approximation using redundant representations may lead to highly accurate approximations in spite of having to solve ill-conditioned systems of equations.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Improved recovery guarantees and sampling strategies for TV minimization in compressive imaging

In this paper, we consider the use of Total Variation (TV) minimization for compressive imaging; that is, image reconstruction from subsampled measurements. Focusing on two important imaging modalities -- namely, Fourier imaging and structured binary imaging via the Walsh--Hadamard transform -- we derive uniform recovery guarantees asserting stable and robust recovery for arbitrary random sampling strategies. Using this, we then derive a class of theoretically-optimal sampling strategies. For Fourier sampling, we show recovery of an image with approximately $s$-sparse gradient from $m \gtrsim_d s \cdot \log^2(s) \cdot \log^4(N)$ measurements, in $d \geq 1$ dimensions. When $d = 2$, this improves the current state-of-the-art result by a factor of $\log(s) \cdot \log(N)$. It also extends it to arbitrary dimensions $d \geq 2$. For Walsh sampling, we prove that $m \gtrsim_d s \cdot \log^2(s) \cdot \log^2(N/s) \cdot \log^3(N) $ measurements suffice in $d \geq 2$ dimensions. To the best of our knowledge, this is the first recovery guarantee for structured binary sampling with TV minimization.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

On instabilities of deep learning in image reconstruction - Does AI come at a cost?

Deep learning, due to its unprecedented success in tasks such as image classification, has emerged as a new tool in image reconstruction with potential to change the field. In this paper we demonstrate a crucial phenomenon: deep learning typically yields unstablemethods for image reconstruction. The instabilities usually occur in several forms: (1) tiny, almost undetectable perturbations, both in the image and sampling domain, may result in severe artefacts in the reconstruction, (2) a small structural change, for example a tumour, may not be captured in the reconstructed image and (3) (a counterintuitive type of instability) more samples may yield poorer performance. Our new stability test with algorithms and easy to use software detects the instability phenomena. The test is aimed at researchers to test their networks for instabilities and for government agencies, such as the Food and Drug Administration (FDA), to secure safe use of deep learning methods.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

On oracle-type local recovery guarantees in compressed sensing

We present improved sampling complexity bounds for stable and robust sparse recovery in compressed sensing. Our unified analysis based on l1 minimization encompasses the case where (i) the measurements are block-structured samples in order to reflect the structured acquisition that is often encountered in applications; (ii) the signal has an arbitrary structured sparsity, by results depending on its support S. Within this framework and under a random sign assumption, the number of measurements needed by l1 minimization can be shown to be of the same order than the one required by an oracle least-squares estimator. Moreover, these bounds can be minimized by adapting the variable density sampling to a given prior on the signal support and to the coherence of the measurements. We illustrate both numerically and analytically that our results can be successfully applied to recover Haar wavelet coefficients that are sparse in levels from random Fourier measurements in dimension one and two, which can be of particular interest in imaging problems. Finally, a preliminary numerical investigation shows the potential of this theory for devising adaptive sampling strategies in sparse polynomial approximation.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

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

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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Analyzing the structure of multidimensional compressed sensing problems through coherence

Recently it has been established that asymptotic incoherence can be used to facilitate subsampling, in order to optimize reconstruction quality, in a variety of continuous compressed sensing problems, and the coherence structure of certain one-dimensional Fourier sampling problems was determined. This paper extends the analysis of asymptotic incoherence to cover multidimensional reconstruction problems. It is shown that Fourier sampling and separable wavelet sparsity in any dimension can yield the same optimal asymptotic incoherence as in one dimensional case. Moreover in two dimensions the coherence structure is compatible with many standard two dimensional sampling schemes that are currently in use. However, in higher dimensional problems with poor wavelet smoothness we demonstrate that there are considerable restrictions on how one can subsample from the Fourier basis with optimal incoherence. This can be remedied by using a sufficiently smooth generating wavelet. It is also shown that using tensor bases will always provide suboptimal decay marred by problems associated with dimensionality. The impact of asymptotic incoherence on the ability to subsample is demonstrated with some simple two dimensional numerical experiments.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Density theorems for nonuniform sampling of bandlimited functions using derivatives or bunched measurements

We provide sufficient density condition for a set of nonuniform samples to give rise to a set of sampling for multivariate bandlimited functions when the measurements consist of pointwise evaluations of a function and its first $k$ derivatives. Along with explicit estimates of corresponding frame bounds, we derive the explicit density bound and show that, as $k$ increases, it grows linearly in $k+1$ with the constant of proportionality $1/\mathrm{e}$. Seeking larger gap conditions, we also prove a multivariate perturbation result for nonuniform samples that are sufficiently close to sets of sampling, e.g. to uniform samples taken at $k+1$ times the Nyquist rate. Additionally, in the univariate setting, we consider a related problem of so-called nonuniform bunched sampling, where in each sampling interval $s+1$ bunched measurements of a function are taken and the sampling intervals are permitted to be of different length. We derive an explicit density condition which grows linearly in $s+1$ for large $s$, with the constant of proportionality depending on the width of the bunches. The width of the bunches is allowed to be arbitrarily small, and moreover, for sufficiently narrow bunches and sufficiently large $s$, we obtain the same result as in the case of univariate sampling with $s$ derivatives.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Infinite-dimensional $\ell^1$ minimization and function approximation from pointwise data

We consider the problem of approximating a smooth function from finitely-many pointwise samples using $\ell^1$ minimization techniques. In the first part of this paper, we introduce an infinite-dimensional approach to this problem. Three advantages of this approach are as follows. First, it provides interpolatory approximations in the absence of noise. Second, it does not require \textit{a priori} bounds on the expansion tail in order to be implemented. In particular, the truncation strategy we introduce as part of this framework is independent of the function being approximated, provided the function has sufficient regularity. Third, it allows one to explain the key role weights play in the minimization; namely, that of regularizing the problem and removing aliasing phenomena. In the second part of this paper we present a worst-case error analysis for this approach. We provide a general recipe for analyzing this technique for arbitrary deterministic sets of points. Finally, we use this tool to show that weighted $\ell^1$ minimization with Jacobi polynomials leads to an optimal method for approximating smooth, one-dimensional functions from scattered data.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Resolution-optimal exponential and double-exponential transform methods for functions with endpoint singularities

We introduce a numerical method for the approximation of functions which are analytic on compact intervals, except at the endpoints. This method is based on variable transforms using particular parametrized exponential and double-exponential mappings, in combination with Fourier-like approximation in a truncated domain. We show theoretically that this method is superior to variable transform techniques based on the standard exponential and double-exponential mappings. In particular, it can resolve oscillatory behaviour using near-optimal degrees of freedom, whereas the standard mappings require degrees of freedom that grow superlinearly with the frequency of oscillation. We highlight these results with several numerical experiments. Therein it is observed that near-machine epsilon accuracy is achieved using a number of degrees of freedom that is between four and ten times smaller than those of existing techniques.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On Asymptotic Incoherence and its Implications for Compressed Sensing of Inverse Problems

Recently, it has been shown that incoherence is an unrealistic assumption for compressed sensing when applied to many inverse problems. Instead, the key property that permits efficient recovery in such problems is so-called local incoherence. Similarly, the standard notion of sparsity is also inadequate for many real world problems. In particular, in many applications, the optimal sampling strategy depends on asymptotic incoherence and the signal sparsity structure. The purpose of this paper is to study asymptotic incoherence and its implications towards the design of optimal sampling strategies and efficient sparsity bases. It is determined how fast asymptotic incoherence can decay in general for isometries. Furthermore it is shown that Fourier sampling and wavelet sparsity, whilst globally coherent, yield optimal asymptotic incoherence as a power law up to a constant factor. Sharp bounds on the asymptotic incoherence for Fourier sampling with polynomial bases are also provided. A numerical experiment is also presented to demonstrate the role of asymptotic incoherence in finding good subsampling strategies.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Weighted frames of exponentials and stable recovery of multidimensional functions from nonuniform Fourier samples

In this paper, we consider the problem of recovering a compactly supported multivariate function from a collection of pointwise samples of its Fourier transform taken nonuniformly. We do this by using the concept of weighted Fourier frames. A seminal result of Beurling shows that sample points give rise to a classical Fourier frame provided they are relatively separated and of sufficient density. However, this result does not allow for arbitrary clustering of sample points, as is often the case in practice. Whilst keeping the density condition sharp and dimension independent, our first result removes the separation condition and shows that density alone suffices. However, this result does not lead to estimates for the frame bounds. A known result of Groechenig provides explicit estimates, but only subject to a density condition that deteriorates linearly with dimension. In our second result we improve these bounds by reducing the dimension dependence. In particular, we provide explicit frame bounds which are dimensionless for functions having compact support contained in a sphere. Next, we demonstrate how our two main results give new insight into a reconstruction algorithm---based on the existing generalized sampling framework---that allows for stable and quasi-optimal reconstruction in any particular basis from a finite collection of samples. Finally, we construct sufficiently dense sampling schemes that are often used in practice---jittered, radial and spiral sampling schemes---and provide several examples illustrating the effectiveness of our approach when tested on these schemes.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A note on compressed sensing of structured sparse wavelet coefficients from subsampled Fourier measurements

This note complements the paper "The quest for optimal sampling: Computationally efficient, structure-exploiting measurements for compressed sensing" [2]. Its purpose is to present a proof of a result stated therein concerning the recovery via compressed sensing of a signal that has structured sparsity in a Haar wavelet basis when sampled using a multilevel-subsampled discrete Fourier transform. In doing so, it provides a simple exposition of the proof in the case of Haar wavelets and discrete Fourier samples of more general result recently provided in the paper "Breaking the coherence barrier: A new theory for compressed sensing" [1].

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Breaking the coherence barrier: A new theory for compressed sensing

This paper provides an extension of compressed sensing which bridges a substantial gap between existing theory and its current use in real-world applications. It introduces a mathematical framework that generalizes the three standard pillars of compressed sensing - namely, sparsity, incoherence and uniform random subsampling - to three new concepts: asymptotic sparsity, asymptotic incoherence and multilevel random sampling. The new theorems show that compressed sensing is also possible, and reveals several advantages, under these substantially relaxed conditions. The importance of this is threefold. First, inverse problems to which compressed sensing is currently applied are typically coherent. The new theory provides the first comprehensive mathematical explanation for a range of empirical usages of compressed sensing in real-world applications, such as medical imaging, microscopy, spectroscopy and others. Second, in showing that compressed sensing does not require incoherence, but instead that asymptotic incoherence is sufficient, the new theory offers markedly greater flexibility in the design of sensing mechanisms. Third, by using asymptotic incoherence and multi-level sampling to exploit not just sparsity, but also structure, i.e. asymptotic sparsity, the new theory shows that substantially improved reconstructions can be obtained from fewer measurements.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Linear Stable Sampling Rate: Optimality of 2D Wavelet Reconstructions from Fourier Measurements

In this paper we analyze two-dimensional wavelet reconstructions from Fourier samples within the framework of generalized sampling. For this, we consider both separable compactly-supported wavelets and boundary wavelets. We prove that the number of samples that must be acquired to ensure a stable and accurate reconstruction scales linearly with the number of reconstructing wavelet functions. We also provide numerical experiments that corroborate our theoretical results.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

New exponential variable transform methods for functions with endpoint singularities

The focus of this article is the approximation of functions which are analytic on a compact interval except at the endpoints. Typical numerical methods for approximating such functions depend upon the use of particular conformal maps from the original interval to either a semi-infinite or an infinite interval, followed by an appropriate approximation procedure on the new region. We first analyse the convergence of these existing methods and show that, in a precisely defined sense, they are sub-optimal. Specifically, they exhibit poor resolution properties, by which we mean that many more degrees of freedom are required to resolve oscillatory functions than standard approximation schemes for analytic functions such as Chebyshev interpolation. To remedy this situation, we introduce two new transforms; one for each of the above settings. We provide full convergence results for these new approximations and then demonstrate that, for a particular choice of parameters, these methods lead to substantially better resolution properties. Finally, we show that optimal resolution power can be achieved by an appropriate choice of parameters, provided one forfeits classical convergence. Instead, the resulting method attains a finite, but user-controlled accuracy specified by the parameter choice.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On asymptotic structure in compressed sensing

This paper demonstrates how new principles of compressed sensing, namely asymptotic incoherence, asymptotic sparsity and multilevel sampling, can be utilised to better understand underlying phenomena in practical compressed sensing and improve results in real-world applications. The contribution of the paper is fourfold: First, it explains how the sampling strategy depends not only on the signal sparsity but also on its structure, and shows how to design effective sampling strategies utilising this. Second, it demonstrates that the optimal sampling strategy and the efficiency of compressed sensing also depends on the resolution of the problem, and shows how this phenomenon markedly affects compressed sensing results and how to exploit it. Third, as the new framework also fits analog (infinite dimensional) models that govern many inverse problems in practice, the paper describes how it can be used to yield substantial improvements. Fourth, by using multilevel sampling, which exploits the structure of the signal, the paper explains how one can outperform random Gaussian/Bernoulli sampling even when the classical $l^1$ recovery algorithm is replaced by modified algorithms which aim to exploit structure such as model based or Bayesian compressed sensing or approximate message passaging. This final observation raises the question whether universality is desirable even when such matrices are applicable. Examples of practical applications investigated in this paper include Magnetic Resonance Imaging (MRI), Electron Microscopy (EM), Compressive Imaging (CI) and Fluorescence Microscopy (FM). For the latter, a new compressed sensing approach is also presented.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On stable reconstructions from nonuniform Fourier measurements

We consider the problem of recovering a compactly-supported function from a finite collection of pointwise samples of its Fourier transform taking nonuniformly. First, we show that under suitable conditions on the sampling frequencies - specifically, their density and bandwidth - it is possible to recover any such function $f$ in a stable and accurate manner in any given finite-dimensional subspace; in particular, one which is well suited for approximating $f$. In practice, this is carried out using so-called nonuniform generalized sampling (NUGS). Second, we consider approximation spaces in one dimension consisting of compactly supported wavelets. We prove that a linear scaling of the dimension of the space with the sampling bandwidth is both necessary and sufficient for stable and accurate recovery. Thus wavelets are up to constant factors optimal spaces for reconstruction.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Parameter selection and numerical approximation properties of Fourier extensions from fixed data

Fourier extensions have been shown to be an effective means for the approximation of smooth, nonperiodic functions on bounded intervals given their values on an equispaced, or in general, scattered grid. Related to this method are two parameters. These are the extension parameter $T$ (the ratio of the size of the extended domain to the physical domain) and the oversampling ratio $η$ (the number of sampling nodes per Fourier mode). The purpose of this paper is to investigate how the choice of these parameters affects the accuracy and stability of the approximation. Our main contribution is to document the following interesting phenomenon: namely, if the desired condition number of the algorithm is fixed in advance, then the particular choice of such parameters makes little difference to the algorithm's accuracy. As a result, one is free to choose $T$ without concern that it is suboptimal. In particular, one may use the value $T=2$ - which corresponds to the case where the extended domain is precisely twice the size of the physical domain - for which there is known to be a fast algorithm for computing the approximation. In addition, we also determine the resolution power (points-per-wavelength) of the approximation to be equal to $T η$, and address the trade-off between resolution power and stability.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Recovering piecewise smooth functions from nonuniform Fourier measurements

In this paper, we consider the problem of reconstructing piecewise smooth functions to high accuracy from nonuniform samples of their Fourier transform. We use the framework of nonuniform generalized sampling (NUGS) to do this, and to ensure high accuracy we employ reconstruction spaces consisting of splines or (piecewise) polynomials. We analyze the relation between the dimension of the reconstruction space and the bandwidth of the nonuniform samples, and show that it is linear for splines and piecewise polynomials of fixed degree, and quadratic for piecewise polynomials of varying degree.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The quest for optimal sampling: Computationally efficient, structure-exploiting measurements for compressed sensing

An intriguing phenomenon in many instances of compressed sensing is that the reconstruction quality is governed not just by the overall sparsity of the signal, but also on its structure. This paper is about understanding this phenomenon, and demonstrating how it can be fruitfully exploited by the design of suitable sampling strategies in order to outperform more standard compressed sensing techniques based on random matrices.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A stability barrier for reconstructions from Fourier samples

We prove that any stable method for resolving the Gibbs phenomenon - that is, recovering high-order accuracy from the first $m$ Fourier coefficients of an analytic and nonperiodic function - can converge at best root-exponentially fast in $m$. Any method with faster convergence must also be unstable, and in particular, exponential convergence implies exponential ill-conditioning. This result is analogous to a recent theorem of Platte, Trefethen & Kuijlaars concerning recovery from pointwise function values on an equispaced $m$-grid. The main step in our proof is an estimate for the maximal behaviour of a polynomial of degree $n$ with bounded $m$-term Fourier series, which is related to a conjecture of Hrycak & Groechenig. In the second part of the paper we discuss the implications of our main theorem to polynomial-based interpolation and least-squares approaches for overcoming the Gibbs phenomenon. Finally, we consider the use of so-called Fourier extensions as an attractive alternative for this problem. We present numerical results demonstrating rapid convergence in a stable manner.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Beyond consistent reconstructions: optimality and sharp bounds for generalized sampling, and application to the uniform resampling problem

Generalized sampling is a recently developed linear framework for sampling and reconstruction in separable Hilbert spaces. It allows one to recover any element in any finite-dimensional subspace given finitely many of its samples with respect to an arbitrary frame. Unlike more common approaches for this problem, such as the consistent reconstruction technique of Eldar et al, it leads to completely stable numerical methods possessing both guaranteed stability and accuracy. The purpose of this paper is twofold. First, we give a complete and formal analysis of generalized sampling, the main result of which being the derivation of new, sharp bounds for the accuracy and stability of this approach. Such bounds improve those given previously, and result in a necessary and sufficient condition, the stable sampling rate, which guarantees a priori a good reconstruction. Second, we address the topic of optimality. Under some assumptions, we show that generalized sampling is an optimal, stable reconstruction. Correspondingly, whenever these assumptions hold, the stable sampling rate is a universal quantity. In the final part of the paper we illustrate our results by applying generalized sampling to the so-called uniform resampling problem.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Generalized sampling: stable reconstructions, inverse problems and compressed sensing over the continuum

The purpose of this paper is to report on recent approaches to reconstruction problems based on analog, or in other words, infinite-dimensional, image and signal models. We describe three main contributions to this problem. First, linear reconstructions from sampled measurements via so-called generalized sampling (GS). Second, the extension of generalized sampling to inverse and ill-posed problems. And third, the combination of generalized sampling with sparse recovery techniques. This final contribution leads to a theory and set of methods for infinite-dimensional compressed sensing, or as we shall also refer to it, compressed sensing over the continuum.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On optimal wavelet reconstructions from Fourier samples: linearity and universality of the stable sampling rate

In this paper we study the problem of computing wavelet coefficients of compactly supported functions from their Fourier samples. For this, we use the recently introduced framework of generalized sampling. Our first result demonstrates that using generalized sampling one obtains a stable and accurate reconstruction, provided the number of Fourier samples grows linearly in the number of wavelet coefficients recovered. For the class of Daubechies wavelets we derive the exact constant of proportionality. Our second result concerns the optimality of generalized sampling for this problem. Under some mild assumptions we show that generalized sampling cannot be outperformed in terms of approximation quality by more than a constant factor. Moreover, for the class of so-called perfect methods, any attempt to lower the sampling ratio below a certain critical threshold necessarily results in exponential ill-conditioning. Thus generalized sampling provides a nearly-optimal solution to this problem.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On the numerical stability of Fourier extensions

An effective means to approximate an analytic, nonperiodic function on a bounded interval is by using a Fourier series on a larger domain. When constructed appropriately, this so-called Fourier extension is known to converge geometrically fast in the truncation parameter. Unfortunately, computing a Fourier extension requires solving an ill-conditioned linear system, and hence one might expect such rapid convergence to be destroyed when carrying out computations in finite precision. The purpose of this paper is to show that this is not the case. Specifically, we show that Fourier extensions are actually numerically stable when implemented in finite arithmetic, and achieve a convergence rate that is at least superalgebraic. Thus, in this instance, ill-conditioning of the linear system does not prohibit a good approximation. In the second part of this paper we consider the issue of computing Fourier extensions from equispaced data. A result of Platte, Trefethen & Kuijlaars states that no method for this problem can be both numerically stable and exponentially convergent. We explain how Fourier extensions relate to this theoretical barrier, and demonstrate that they are particularly well suited for this problem: namely, they obtain at least superalgebraic convergence in a numerically stable manner.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On the resolution power of Fourier extensions for oscillatory functions

Functions that are smooth but non-periodic on a certain interval possess Fourier series that lack uniform convergence and suffer from the Gibbs phenomenon. However, they can be represented accurately by a Fourier series that is periodic on a larger interval. This is commonly called a Fourier extension. When constructed in a particular manner, Fourier extensions share many of the same features of a standard Fourier series. In particular, one can compute Fourier extensions which converge spectrally fast whenever the function is smooth, and exponentially fast if the function is analytic, much the same as the Fourier series of a smooth/analytic and periodic function. With this in mind, the purpose of this paper is to describe, analyze and explain the observation that Fourier extensions, much like classical Fourier series, also have excellent resolution properties for representing oscillatory functions. The resolution power, or required number of degrees of freedom per wavelength, depends on a user-controlled parameter and, as we show, it varies between 2 and π. The former value is optimal and is achieved by classical Fourier series for periodic functions, for example. The latter value is the resolution power of algebraic polynomial approximations. Thus, Fourier extensions with an appropriate choice of parameter are eminently suitable for problems with moderate to high degrees of oscillation.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A Generalized Sampling Theorem for Stable Reconstructions in Arbitrary Bases

We introduce a generalized framework for sampling and reconstruction in separable Hilbert spaces. Specifically, we establish that it is always possible to stably reconstruct a vector in an arbitrary Riesz basis from sufficiently many of its samples in any other Riesz basis. This framework can be viewed as an extension of that of Eldar et al. However, whilst the latter imposes stringent assumptions on the reconstruction basis, and may in practice be unstable, our framework allows for recovery in any (Riesz) basis in a manner that is completely stable. Whilst the classical Shannon Sampling Theorem is a special case of our theorem, this framework allows us to exploit additional information about the approximated vector (or, in this case, function), for example sparsity or regularity, to design a reconstruction basis that is better suited. Examples are presented illustrating this procedure.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Stable reconstructions in Hilbert spaces and the resolution of the Gibbs phenomenon

We introduce a method to reconstruct an element of a Hilbert space in terms of an arbitrary finite collection of linearly independent reconstruction vectors, given a finite number of its samples with respect to any Riesz basis. As we establish, provided the dimension of the reconstruction space is chosen suitably in relation to the number of samples, this procedure can be numerically implemented in a stable manner. Moreover, the accuracy of the resulting approximation is completely determined by the choice of reconstruction basis, meaning that the reconstruction vectors can be tailored to the particular problem at hand. An important example of this approach is the accurate recovery of a piecewise analytic function from its first few Fourier coefficients. Whilst the standard Fourier projection suffers from the Gibbs phenomenon, by reconstructing in a piecewise polynomial basis, we obtain an approximation with root exponential accuracy in terms of the number of Fourier samples and exponential accuracy in terms of the degree of the reconstruction function. Numerical examples illustrate the advantage of this approach over other existing methods.

0 citations0 reviewsNo code linkedOpen access