We study the sample complexity of Bayesian recovery for solving inverse problems with general prior, forward operator and noise distributions. We consider posterior sampling according to an approximate prior $\mathcal{P}$, and establish sufficient conditions for stable and accurate recovery with high probability. Our main result is a non-asymptotic bound that shows that the sample complexity depends on (i) the intrinsic complexity of $\mathcal{P}$, quantified by its *approximate covering number*, and (ii) concentration bounds for the forward operator and noise distributions. As a key application, we specialize to generative priors, where $\mathcal{P}$ is the pushforward of a latent distribution via a Deep Neural Network (DNN). We show that the sample complexity scales log-linearly with the latent dimension $k$, thus establishing the efficacy of DNN-based priors. Generalizing existing results on deterministic (i.e., non-Bayesian) recovery for the important problem of random sampling with an orthogonal matrix $U$, we show how the sample complexity is determined by the *coherence* of $U$ with respect to the support of $\mathcal{P}$. Hence, we establish that coherence plays a fundamental role in Bayesian recovery as well. Overall, our framework unifies and extends prior work, providing rigorous guarantees for the sample complexity of solving Bayesian inverse problems with arbitrary distributions.

This work considers the fundamental problem of learning an unknown object from training data using a given model class. We introduce a framework that allows for objects in arbitrary Hilbert spaces, general types of (random) linear measurements as training data and general types of nonlinear model classes. We establish a series of learning guarantees for this framework, which provide explicit relations between the amount of training data and the model class to ensure near-best generalization bounds. In doing so, we introduce the key notion of the variation of a model class with respect to a distribution of sampling operators. We show that this framework can accommodate many different types of well-known problems of interest, such as matrix sketching by random sampling, compressed sensing with isotropic vectors, active learning in regression and compressed sensing with generative models. In all cases, known results become straightforward corollaries of our general theory. Hence, this work provides a powerful framework for studying and analyzing many different types of learning problems.

Operator learning problems arise in many key areas of scientific computing where Partial Differential Equations (PDEs) are used to model physical systems. In such scenarios, the operators map between Banach or Hilbert spaces. In this work, we tackle the problem of learning operators between Banach spaces, in contrast to the vast majority of past works considering only Hilbert spaces. We focus on learning holomorphic operators -- an important class of problems with many applications. We combine arbitrary approximate encoders and decoders with standard feedforward Deep Neural Network (DNN) architectures -- specifically, those with constant width exceeding the depth -- under standard $\ell^2$-loss minimization. We first identify a family of DNNs such that the resulting Deep Learning (DL) procedure achieves optimal generalization bounds for such operators. For standard fully-connected architectures, we then show that there are uncountably many minimizers of the training problem that yield equivalent optimal performance. The DNN architectures we consider are `problem agnostic', with width and depth only depending on the amount of training data $m$ and not on regularity assumptions of the target operator. Next, we show that DL is optimal for this problem: no recovery procedure can surpass these generalization bounds up to log terms. Finally, we present numerical results demonstrating the practical performance on challenging problems including the parametric diffusion, Navier-Stokes-Brinkman and Boussinesq PDEs.

We introduce a general framework for active learning in regression problems. Our framework extends the standard setup by allowing for general types of data, rather than merely pointwise samples of the target function. This generalization covers many cases of practical interest, such as data acquired in transform domains (e.g., Fourier data), vector-valued data (e.g., gradient-augmented data), data acquired along continuous curves, and, multimodal data (i.e., combinations of different types of measurements). Our framework considers random sampling according to a finite number of sampling measures and arbitrary nonlinear approximation spaces (model classes). We introduce the concept of \textit{generalized Christoffel functions} and show how these can be used to optimize the sampling measures. We prove that this leads to near-optimal sample complexity in various important cases. This paper focuses on applications in scientific computing, where active learning is often desirable, since it is usually expensive to generate data. We demonstrate the efficacy of our framework for gradient-augmented learning with polynomials, Magnetic Resonance Imaging (MRI) using generative models and adaptive sampling for solving PDEs using Physics-Informed Neural Networks (PINNs).

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 sampling strategies which are theoretically near-optimal for recovery of approximately gradient-sparse images. For Fourier sampling, we show recovery of such an image 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.

Convolutional analysis operator learning (CAOL) enables the unsupervised training of (hierarchical) convolutional sparsifying operators or autoencoders from large datasets. One can use many training images for CAOL, but a precise understanding of the impact of doing so has remained an open question. This letter presents a series of results that lend insight into the impact of dataset size on the filter update in CAOL. The first result is a general deterministic bound on errors in the estimated filters, and is followed by a bound on the expected errors as the number of training samples increases. The second result provides a high probability analogue. The bounds depend on properties of the training data, and we investigate their empirical values with real data. Taken together, these results provide evidence for the potential benefit of using more training data in CAOL.

Quadratically constrained 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 the robust instance optimality of any decoder in the noise-aware setting implies stability and robustness in the noise-blind setting. This is based on certain sup-inf constants referred to as quotients, strictly related to the quotient property of compressed sensing. Then, we apply this theory to prove the robustness of quadratically constrained basis pursuit under unknown error in the cases of random Gaussian matrices and of random matrices with heavy-tailed 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 the recovery of sparse polynomial expansions.

Parallel acquisition systems arise in various applications to moderate problems caused by insufficient measurements in single-sensor systems. These systems allow simultaneous data acquisition in multiple sensors, thus alleviating such problems by providing more overall measurements. In this paper, we consider the combination of compressed sensing with parallel acquisition. We establish the theoretical improvements of such systems by providing nonuniform 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 (i.e., independent sampling in each sensor) and identical (i.e., dependent sampling between sensors)-and a general mathematical framework that allows for a wide range of sensing matrices. We also consider not just the standard sparse signal model, but also the so-called sparse in levels signal model. As our results show, optimal recovery guarantees for both distinct and identical sampling are possible under much broader conditions on the so-called 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 different multi-sensor environments.

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 single-sensor acquisition scenarios. In this paper, we address the optimal recovery of compressible signals from multi-sensor measurements using compressed sensing techniques. This confirms the benefits of multi-over single-sensor environments in the sense of reducing the number of measurements required per sensor, and therefore, depending on the application, the total time, power or cost. 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 so-called sparsity in levels signal model.

We consider signal recovery from Fourier measurements using compressed sensing (CS) with wavelets. For discrete signals with structured sparse Haar wavelet coefficients, we give the first proof of near-optimal recovery from discrete Fourier samples taken according to an appropriate variable density sampling scheme. Crucially, in taking into account such structured sparsity-known as sparsity in levels-as opposed to just sparsity, this result yields recovery guarantees that agree with the empirically observed recovery properties of CS in this setting. This result complements a recent theorem in Adcock et al. [Breaking the coherence barrier: A new theory for compressed sensing, arXiv preprint arXiv: 1302.0561, 2014.], which addressed the case of continuous time signals. Moreover, we provide a significantly shorter and more expositional argument, which clearly illustrates the key factors governing recovery in this setting: namely the division of frequency space into dyadic bands corresponding to wavelet scales, the near-block diagonality of the Fourier/wavelet cross-Gramian matrix, and the structured sparsity of wavelet coefficients.

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 the 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 toward the design of optimal sampling strategies and efficient sparsity bases. How fast asymptotic incoherence can decay in general for isometries is determined. Furthermore, it is shown that Fourier sampling and wavelet sparsity, while 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.

The theory and techniques of compressed sensing (CS) have shown their potential as a breakthrough in accelerating k-space data acquisition for parallel magnetic resonance imaging (pMRI). However, the performance of CS reconstruction models in pMRI has not been fully maximized, and CS recovery guarantees for pMRI are largely absent. To improve reconstruction accuracy from parsimonious amounts of k-space data while maintaining flexibility, a new CS SENSitivity Encoding (SENSE) pMRI reconstruction framework promoting joint sparsity (JS) across channels (JS CS SENSE) is proposed in this paper. The recovery guarantee derived for the proposed JS CS SENSE model is demonstrated to be better than that of the conventional CS SENSE model and similar to that of the coil-by-coil CS model. The flexibility of the new model is better than the coil-by-coil CS model and the same as that of CS SENSE. For fast image reconstruction and fair comparisons, all the introduced CS-based constrained optimization problems are solved with split Bregman, variable splitting, and combined-variable splitting techniques. For the JS CS SENSE model in particular, these techniques lead to an efficient algorithm. Numerical experiments show that the reconstruction accuracy is significantly improved by JS CS SENSE compared with the conventional CS SENSE. In addition, an accurate residual-JS regularized sensitivity estimation model is also proposed and extended to calibration-less (CaL) JS CS SENSE. Numerical results show that CaL JS CS SENSE outperforms other state-of-the-art CS-based calibration-less methods in particular for reconstructing non-piecewise constant images.

A scheme for preserving privacy in MobilityFirst (MF) clean-slate future Internet architecture is proposed in this paper. The proposed scheme, called Anonymity in MobilityFirst (AMF), utilizes the three-tiered approach to effectively exploit the inherent properties of MF Network such as Globally Unique Flat Identifier (GUID) and Global Name Resolution Service (GNRS) to provide anonymity to the users. While employing new proposed schemes in exchanging of keys between different tiers of routers to alleviate trust issues, the proposed scheme uses multiple routers in each tier to avoid collaboration amongst the routers in the three tiers to expose the end users.

We consider the problem of recovering a compactly supported function from a finite collection of pointwise samples of its Fourier transform taken 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.