
Functions of one or more variables are usually approximated with a basis: a
complete, linearlyindependent system of functions that spans a suitable
function space. The topic of this paper is the numerical approximation of
functions using the more general notion of frames: that is, complete systems
that are generally redundant but provide infinite representations with bounded
coefficients. While frames are wellknown in image and signal processing,
coding theory and other areas of applied mathematics, their use in numerical
analysis is far less widespread. Yet, as we show via a series of examples,
frames are more flexible than bases, and can be constructed easily in a range
of problems where finding orthonormal bases with desirable properties (rapid
convergence, high resolution power, etc.) is difficult or impossible.
A key concern when using frames is that computing a best approximation
requires solving an illconditioned linear system. Nonetheless, we construct a
frame approximation via regularization with bounded condition number (with
respect to perturbations in the data), and which approximates any function up
to an error of order $\sqrt{\epsilon}$, or even of order $\epsilon$ with
suitable modifications. Here $\epsilon$ is a threshold value that can be chosen
by the user. Crucially, rate of decay of the error down to this level is
determined by the existence of approximate representations of $f$ in the frame
possessing smallnorm coefficients. We demonstrate the existence of such
representations in all of our examples. Overall, our analysis suggests that
frames are a natural generalization of bases in which to develop numerical
approximation. In particular, even in the presence of severely illconditioned
linear systems, the frame condition imposes sufficient mathematical structure
in order to give rise to accurate, wellconditioned approximations.

The recovery of approximately sparse or compressible coefficients in a
Polynomial Chaos Expansion is a common goal in modern parametric uncertainty
quantification (UQ). However, relatively little effort in UQ has been directed
toward theoretical and computational strategies for addressing the sparse
corruptions problem, where a small number of measurements are highly corrupted.
Such a situation has become pertinent today since modern computational
frameworks are sufficiently complex with many interdependent components that
may introduce hardware and software failures, some of which can be difficult to
detect and result in a highly polluted simulation result.
In this paper we present a novel compressive samplingbased theoretical
analysis for a regularized $\ell^1$ minimization algorithm that aims to recover
sparse expansion coefficients in the presence of measurement corruptions. Our
recovery results are uniform, and prescribe algorithmic regularization
parameters in terms of a userdefined a priori estimate on the ratio of
measurements that are believed to be corrupted. We also propose an iteratively
reweighted optimization algorithm that automatically refines the value of the
regularization parameter, and empirically produces superior results. Our
numerical results test our framework on several mediumtohigh dimensional
examples of solutions to parameterized differential equations, and demonstrate
the effectiveness of our approach.

We consider the problem of approximating an analytic function on a compact
interval from its values at $M+1$ distinct points. When the points are
equispaced, a recent result (the socalled impossibility theorem) has shown
that the best possible convergence rate of a stable method is rootexponential
in $M$, and that any method with faster exponential convergence must also be
exponentially illconditioned at a certain rate. This result hinges on a
classical theorem of Coppersmith & Rivlin concerning the maximal behaviour of
polynomials bounded on an equispaced grid. In this paper, we first generalize
this theorem to arbitrary point distributions. We then present an extension of
the impossibility theorem valid for general nonequispaced points, and apply it
to the case of points that are equidistributed with respect to (modified)
Jacobi weight functions. This leads to a necessary sampling rate for stable
approximation from such points. We prove that this rate is also sufficient, and
therefore exactly quantify (up to constants) the precise sampling rate for
approximating analytic functions from such node distributions with stable
methods. Numerical results  based on computing the maximal polynomial via a
variant of the classical Remez algorithm  confirm our main theorems. Finally,
we discuss the implications of our results for polynomial leastsquares
approximations. In particular, we theoretically confirm the wellknown
heuristic that stable leastsquares approximation using polynomials of degree
$N < M$ is possible only once $M$ is sufficiently large for there to be a
subset of $N$ of the nodes that mimic the behaviour of the $N$th set of
Chebyshev nodes.

Parallel acquisition systems are employed successfully in a variety of
different sensing applications when a single sensor cannot provide enough
measurements for a highquality reconstruction. In this paper, we consider
compressed sensing (CS) for parallel acquisition systems when the individual
sensors use subgaussian random sampling. Our main results are a series of
uniform recovery guarantees which relate the number of measurements required to
the basis in which the solution is sparse and certain characteristics of the
multisensor system, known as sensor profile matrices. In particular, we derive
sufficient conditions for optimal recovery, in the sense that the number of
measurements required per sensor decreases linearly with the total number of
sensors, and demonstrate explicit examples of multisensor systems for which
this holds. We establish these results by proving the socalled Asymmetric
Restricted Isometry Property (ARIP) for the sensing system and use this to
derive both nonuniversal and universal recovery guarantees. Compared to
existing work, our results not only lead to better stability and robustness
estimates but also provide simpler and sharper constants in the measurement
conditions. Finally, we show how the problem of CS with blockdiagonal sensing
matrices can be viewed as a particular case of our multisensor framework.
Specializing our results to this setting leads to a recovery guarantee that is
at least as good as existing results.

In a previous paper [Adcock & Huybrechs, 2016] we described the numerical
properties of function approximation using frames, i.e. complete systems that
are generally redundant but provide infinite representations with coefficients
of bounded norm. Frames offer enormous flexibility compared to bases. We showed
that, in spite of extreme illconditioning, a regularized projection onto a
finite truncated frame can provide accuracy up to order $\sqrt{\epsilon}$,
where $\epsilon$ is an arbitrarily small threshold. Here, we generalize the
setting in two ways. First, we assume information or samples from $f$ from a
wide class of linear operators acting on $f$, rather than inner products with
the frame elements. Second, we allow oversampling, leading to leastsquares
approximations. The first property enables the analysis of fully discrete
approximations based, for instance, on function values only. We show that the
second property, oversampling, crucially leads to much improved accuracy on the
order of $\epsilon$ rather than $\sqrt{\epsilon}$. Overall, we show that
numerical function approximation using truncated frames leads to highly
accurate approximations in spite of having to solve an illconditioned system
of equations. Once the approximations start to converge, i.e. once sufficiently
many degrees of freedom are used, any function $f$ can be approximated to
within order $\epsilon$ with coefficients of small norm.

In this paper, we analyze 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 tensorproduct 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 nearlinear dependence of the finite approximation system. Nevertheless,
wellconditioned 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 higherdimensional 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 Nikolskiitype
inequality for the domain. For a large class of nontrivial domains, we show
that the sample complexity for points drawn from the uniform measure is
quadratic in the dimension of the polynomial space, independently of $d$.

In recent years, the use of sparse recovery techniques in the approximation
of highdimensional functions has garnered increasing interest. In this work we
present a survey of recent progress in this emerging topic. Our main focus is
on the computation of polynomial approximations of highdimensional functions
on $d$dimensional hypercubes. We show that smooth, multivariate functions
possess expansions in orthogonal polynomial bases that are not only
approximately sparse, but possess a particular type of structured sparsity
defined by socalled lower sets. This structure can be exploited via the use of
weighted $\ell^1$ minimization techniques, and, as we demonstrate, doing so
leads to sample complexity estimates that are at most logarithmically dependent
on the dimension $d$. Hence the curse of dimensionality  the bane of
highdimensional approximation  is mitigated to a significant extent. We also
discuss several practical issues, including unknown noise (due to truncation or
numerical error), and highlight a number of open problems and challenges.

In compressed sensing, it is often desirable to consider signals possessing
additional structure beyond sparsity. One such structured signal model  which
forms the focus of this paper  is the local sparsity in levels class. This
class has recently found applications in problems such as compressive imaging,
multisensor acquisition systems and sparse regularization in inverse problems.
In this paper we present uniform recovery guarantees for this class when the
measurement matrix corresponds to a subsampled isometry. We do this by
establishing a variant of the standard restricted isometry property for sparse
in levels vectors, known as the restricted isometry property in levels.
Interestingly, besides the usual log factors, our uniform recovery guarantees
are simpler and less stringent than existing nonuniform recovery guarantees.
For the particular case of discrete Fourier sampling with Haar wavelet
sparsity, a corollary of our main theorem yields a new recovery guarantee which
improves over the current stateoftheart.

Quadraticallyconstrained basis pursuit has become a popular device in sparse
regularization; in particular, in the context of compressed sensing. However,
the majority of theoretical error estimates for this regularizer assume an a
priori bound on the noise level, which is usually lacking in practice. In this
paper, we develop stability and robustness estimates which remove this
assumption. First, we introduce an abstract framework and show that robust
instance optimality of any decoder in the noiseaware setting implies stability
and robustness in the noiseblind setting. This is based on certain supinf
constants referred to as quotients, strictly related to the quotient property
of compressed sensing. We then apply this theory to prove the robustness of
quadraticallyconstrained basis pursuit under unknown error in the cases of
random Gaussian matrices and of random matrices with heavytailed rows, such as
random sampling matrices from bounded orthonormal systems. We illustrate our
results in several cases of practical importance, including subsampled Fourier
measurements and recovery of sparse polynomial expansions.

From a numerical analysis perspective, assessing the robustness of
l1minimization is a fundamental issue in compressed sensing and sparse
regularization. Yet, the recovery guarantees available in the literature
usually depend on a priori estimates of the noise, which can be very hard to
obtain in practice, especially when the noise term also includes unknown
discrepancies between the finite model and data. In this work, we study the
performance of l1minimization when these estimates are not available,
providing robust recovery guarantees for quadratically constrained basis
pursuit and random sampling in bounded orthonormal systems. Several
applications of this work are approximation of highdimensional functions,
infinitedimensional sparse regularization for inverse problems, and fast
algorithms for nonCartesian Magnetic Resonance Imaging.

We study the problem of recovering an unknown compactlysupported
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 finitedimensional 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.

We introduce and analyze a framework for function interpolation using
compressed sensing. This framework  which is based on weighted $\ell^1$
minimization  does not require a priori bounds on the expansion tail in either
its implementation or its theoretical guarantees, and in the absence of noise
leads to genuinely interpolatory approximations. We also establish a new
recovery guarantee for compressed sensing with weighted $\ell^1$ minimization
based on this framework. This guarantee has several key benefits. First, unlike
existing results, it is sharp (up to constants and log factors) for large
classes of functions regardless of the choice of weights. Second, by examining
the measurement condition in the recovery guarantee, we are able to suggest a
good overall strategy for selecting the weights. In particular, when applied to
the important case of multivariate approximation with orthogonal polynomials,
this weighting strategy leads to provably optimal estimates on the number of
measurements required, whenever the support set of the significant coefficients
is a socalled lower set. Finally, this guarantee can also be used to
theoretically confirm the benefits of alternative weighting strategies where
the weights are chosen based on prior support information. This provides a
theoretical basis for a number of recent numerical studies showing the
effectiveness of such approaches.

Parallel acquisition systems arise in various applications in order to
moderate problems caused by insufficient measurements in singlesensor systems.
These systems allow simultaneous data acquisition in multiple sensors, thus
alleviating such problems by providing more overall measurements. In this work
we consider the combination of compressed sensing with parallel acquisition. We
establish the theoretical improvements of such systems by providing recovery
guarantees for which, subject to appropriate conditions, the number of
measurements required per sensor decreases linearly with the total number of
sensors. Throughout, we consider two different sampling scenarios  distinct
(corresponding to independent sampling in each sensor) and identical
(corresponding to dependent sampling between sensors)  and a general
mathematical framework that allows for a wide range of sensing matrices (e.g.,
subgaussian random matrices, subsampled isometries, random convolutions and
random Toeplitz matrices). We also consider not just the standard sparse signal
model, but also the socalled sparse in levels signal model. This model
includes both sparse and distributed signals and clustered sparse signals. As
our results show, optimal recovery guarantees for both distinct and identical
sampling are possible under much broader conditions on the socalled sensor
profile matrices (which characterize environmental conditions between a source
and the sensors) for the sparse in levels model than for the sparse model. To
verify our recovery guarantees we provide numerical results showing phase
transitions for a number of different multisensor environments.

We consider the problem of approximating a smooth function from finitelymany
pointwise samples using $\ell^1$ minimization techniques. In the first part of
this paper, we introduce an infinitedimensional 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
worstcase 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,
onedimensional functions from scattered data.

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 onedimensional 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.

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
socalled 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.

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
doubleexponential mappings, in combination with Fourierlike approximation in
a truncated domain. We show theoretically that this method is superior to
variable transform techniques based on the standard exponential and
doubleexponential mappings. In particular, it can resolve oscillatory
behaviour using nearoptimal 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 nearmachine epsilon accuracy is achieved using a
number of degrees of freedom that is between four and ten times smaller than
those of existing techniques.

The problem of multiple sensors simultaneously acquiring measurements of a
single object can be found in many applications. In this paper, we present the
optimal recovery guarantees for the recovery of compressible signals from
multisensor measurements using compressed sensing. In the first half of the
paper, we present both uniform and nonuniform recovery guarantees for the
conventional sparse signal model in a socalled distinct sensing scenario. In
the second half, using the socalled sparse and distributed signal model, we
present nonuniform recovery guarantees which effectively broaden the class of
sensing scenarios for which optimal recovery is possible, including to the
socalled identical sampling scenario. To verify our recovery guarantees we
provide several numerical results including phase transition curves and
numericallycomputed bounds.

Many practical sensing applications involve multiple sensors simultaneously
acquiring measurements of a single object. Conversely, most existing sparse
recovery guarantees in compressed sensing concern only singlesensor
acquisition scenarios. In this paper, we address the optimal recovery of
compressible signals from multisensor measurements using compressed sensing
techniques, thereby confirming the benefits of multi over singlesensor
environments. Throughout the paper, we consider a broad class of sensing
matrices, and two fundamentally different sampling scenarios (distinct and
identical respectively), both of which are relevant to applications. For the
case of diagonal sensor profile matrices (which characterize environmental
conditions between a source and the sensors), this paper presents two key
improvements over existing results. First, a simpler optimal recovery guarantee
for distinct sampling, and second, an improved recovery guarantee for identical
sampling, based on the socalled sparsity in levels signal model.

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 algorithmbased on the existing
generalized sampling frameworkthat allows for stable and quasioptimal
reconstruction in any particular basis from a finite collection of samples.
Finally, we construct sufficiently dense sampling schemes that are often used
in practicejittered, radial and spiral sampling schemesand provide
several examples illustrating the effectiveness of our approach when tested on
these schemes.

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 socalled 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.

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.

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 realworld 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.

This paper provides an extension of compressed sensing which bridges a
substantial gap between existing theory and its current use in realworld
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 realworld 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 multilevel 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.

This note complements the paper "The quest for optimal sampling:
Computationally efficient, structureexploiting 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 multilevelsubsampled
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].