We give an overview of recent developments in the problem of reconstructing a band-limited signal from non-uniform sampling from a numerical analysis view point. It is shown that the appropriate design of the finite-dimensional model plays a key role in the numerical solution of the non-uniform sampling problem. In the one approach (often proposed in the literature) the finite-dimensional model leads to an ill-posed problem even in very simple situations. The other approach that we consider leads to a well-posed problem that preserves important structural properties of the original infinite-dimensional problem and gives rise to efficient numerical algorithms. Furthermore a fast multilevel algorithm is presented that can reconstruct signals of unknown bandwidth from noisy non-uniformly spaced samples. We also discuss the design of efficient regularization methods for ill-conditioned reconstruction problems. Numerical examples from spectroscopy and exploration geophysics demonstrate the performance of the proposed methods.

The stories told in this paper are dealing with the solution of finite, infinite, and biinfinite Toeplitz-type systems. A crucial role plays the off-diagonal decay behavior of Toeplitz matrices and their inverses. Classical results of Gelfand et al. on commutative Banach algebras yield a general characterization of this decay behavior. We then derive estimates for the approximate solution of (bi)infinite Toeplitz systems by the finite section method, showing that the approximation rate depends only on the decay of the entries of the Toeplitz matrix and its condition number. Furthermore, we give error estimates for the solution of doubly infinite convolution systems by finite circulant systems. Finally, some quantitative results on the construction of preconditioners via circulant embedding are derived, which allow to provide a theoretical explanation for numerical observations made by some researchers in connection with deconvolution problems.

A shift-invariant system is a collection of functions $\{g_{m,n}\}$ of the form $g_{m,n}(k) = g_m(k-an)$. Such systems play an important role in time-frequency analysis and digital signal processing. A principal problem is to find a dual system $\gamma_{m,n}(k) = \gamma_m(k-an)$ such that each function $f$ can be written as $f = \sum < f, \gamma_{m,n} > g_{m,n}$. The mathematical theory usually addresses this problem in infinite dimensions (typically in $L_2(R)$ or $l_2(Z)$), whereas numerical methods have to operate with a finite-dimensional model. Exploiting the link between the frame operator and Laurent operators with matrix-valued symbol, we apply the finite section method to show that the dual functions obtained by solving a finite-dimensional problem converge to the dual functions of the original infinite-dimensional problem in $l_2(Z)$. For compactly supported $g_{m,n}$ (FIR filter banks) we prove an exponential rate of convergence and derive explicit expressions for the involved constants. Further we investigate under which conditions one can replace the discrete model of the finite section method by the periodic discrete model, which is used in many numerical procedures. Again we provide explicit estimates for the speed of convergence. Some remarks on tight frames complete the paper.

Trigonometric polynomials are widely used for the approximation of a smooth function $f$ from a set of nonuniformly spaced samples $\{f(x_j)\}_{j=0}^{N-1}$. If the samples are perturbed by noise, controlling the smoothness of the trigonometric approximation becomes an essential issue to avoid overfitting and underfitting of the data. Using the polynomial degree as regularization parameter we derive a multi-level algorithm that iteratively adapts to the least squares solution of optimal smoothness. The proposed algorithm computes the solution in at most $\cal{O}(NM + M^2)$ operations ($M$ being the polynomial degree of the approximation) by solving a family of nested Toeplitz systems. It is shown how the presented method can be extended to multivariate trigonometric approximation. We demonstrate the performance of the algorithm by applying it in echocardiography to the recovery of the boundary of the Left Ventricle.

Is compressive sensing overrated? Or can it live up to our expectations? What will come after compressive sensing and sparsity? And what has Galileo Galilei got to do with it? Compressive sensing has taken the signal processing community by storm. A large corpus of research devoted to the theory and numerics of compressive sensing has been published in the last few years. Moreover, compressive sensing has inspired and initiated intriguing new research directions, such as matrix completion. Potential new applications emerge at a dazzling rate. Yet some important theoretical questions remain open, and seemingly obvious applications keep escaping the grip of compressive sensing. In this paper I discuss some of the recent progress in compressive sensing and point out key challenges and opportunities as the area of compressive sensing and sparse representations keeps evolving. I also attempt to assess the long-term impact of compressive sensing.

We consider three problems for Gabor frames that have recently received much attention. The first problem concerns the approximation of dual Gabor frames in $L_2(R)$ by finite-dimensional methods. Utilizing Wexler-Raz type duality relations we derive a method to approximate the dual Gabor frame, that is much simpler than previously proposed techniques. Furthermore it enables us to give estimates for the approximation rate when the dimension of the finite model approaches infinity. The second problem concerns the relation between the decay of the window function $g$ and its dual $\gamma$. Based on results on commutative Banach algebras and Laurent operators we derive a general condition under which the dual $\gamma$ inherits the decay properties of $g$. The third problem concerns the design of pulse shapes for orthogonal frequency division multiplex (OFDM) systems for time- and frequency dispersive channels. In particular, we provide a theoretical foundation for a recently proposed algorithm to construct orthogonal transmission functions that are well localized in the time-frequency plane.

A stylized compressed sensing radar is proposed in which the time-frequency plane is discretized into an N by N grid. Assuming the number of targets K is small (i.e., K much less than N^2), then we can transmit a sufficiently "incoherent" pulse and employ the techniques of compressed sensing to reconstruct the target scene. A theoretical upper bound on the sparsity K is presented. Numerical simulations verify that even better performance can be achieved in practice. This novel compressed sensing approach offers great potential for better resolution over classical radar.

The Kaczmarz method for solving linear systems of equations is an iterative algorithm that has found many applications ranging from computer tomography to digital signal processing. Despite the popularity of this method, useful theoretical estimates for its rate of convergence are still scarce. We introduce a randomized version of the Kaczmarz method for consistent, overdetermined linear systems and we prove that it converges with expected exponential rate. Furthermore, this is the first solver whose rate does not depend on the number of equations in the system. The solver does not even need to know the whole system, but only a small random part of it. It thus outperforms all previously known methods on general extremely overdetermined systems. Even for moderately overdetermined systems, numerical simulations as well as theoretical analysis reveal that our algorithm can converge faster than the celebrated conjugate gradient algorithm. Furthermore, our theory and numerical simulations confirm a prediction of Feichtinger et al. in the context of reconstructing bandlimited functions from nonuniform sampling.

We analyze the Basis Pursuit recovery of signals with general perturbations. Previous studies have only considered partially perturbed observations Ax + e. Here, x is a signal which we wish to recover, A is a full-rank matrix with more columns than rows, and e is simple additive noise. Our model also incorporates perturbations E to the matrix A which result in multiplicative noise. This completely perturbed framework extends the prior work of Candes, Romberg and Tao on stable signal recovery from incomplete and inaccurate measurements. Our results show that, under suitable conditions, the stability of the recovered signal is limited by the noise level in the observation. Moreover, this accuracy is within a constant multiple of the best-case reconstruction using the technique of least squares. In the absence of additive noise numerical simulations essentially confirm that this error is a linear function of the relative perturbation.

Suppose that we have $r$ sensors and each one intends to send a function $z_i$ (e.g. a signal or an image) to a receiver common to all $r$ sensors. During transmission, each $z_i$ gets convolved with a function $g_i$. The receiver records the function $y$, given by the sum of all these convolved signals. When and under which conditions is it possible to recover the individual signals $z_i$ and the blurring functions $g_i$ from just one received signal $y$? This challenging problem, which intertwines blind deconvolution with blind demixing, appears in a variety of applications, such as audio processing, image processing, neuroscience, spectroscopy, and astronomy. It is also expected to play a central role in connection with the future Internet-of-Things. We will prove that under reasonable and practical assumptions, it is possible to solve this otherwise highly ill-posed problem and recover the $r$ transmitted functions $z_i$ and the impulse responses $g_i$ in a robust, reliable, and efficient manner from just one single received function $y$ by solving a semidefinite program. We derive explicit bounds on the number of measurements needed for successful recovery and prove that our method is robust in presence of noise. Our theory is actually a bit pessimistic, since numerical experiments demonstrate that, quite remarkably, recovery is still possible if the number of measurements is close to the number of degrees of freedom.