In compressive sensing and sparse recovery, a wide class of popular measurement schemes can be analyzed within the framework of randomly sampled bounded orthonormal systems. This setting includes random measurement matrices such as subsampled isometries, partial Fourier matrices, and sampling matrices associated with orthogonal polynomials. All these random measurement matrices are formed by independent, identically distributed, and uniformly bounded rows with trivial covariance. 

Despite the generality of this framework, the orthogonality assumption is too restrictive in applications where the sampling matrix does not have trivial covariance. In this talk, we will discuss how to address this issue by working in the framework of randomly sampled bounded Riesz systems proposed and studied in \cite{RieszPaper}. Relaxing the orthogonality assumption, this leads to a wider class of structured random measurement matrices having independent, identically distributed, and uniformly bounded rows with nontrivial covariance.

The main theoretical tool of our analysis is a new upper bound for the expectation of the supremum of a Bernoulli process associated with the restricted isometry constant of the random matrix of interest. Using this bound, we will illustrate a restricted isometry analysis that (i) extends previous results from bounded orthonormal to bounded Riesz systems and (ii) improves the dependence of the sample complexity estimate on the restricted isometry constant while keeping the number of logarithmic factors equal to the best currently known one. In addition, we will show a robust null space property analysis in bounded Riesz systems, an application to local coherence-based sampling schemes, and discuss the extension to the weighted sparsity setting. 

Going beyond orthogonality, the additional flexibility of bounded Riesz systems allows for applications to a wider class of problems. Here, we will illustrate applications in scientific computing such as function approximation in high dimensions and numerical methods for partial differential equations, including compressive Petrov-Galerkin and spectral collocation methods.

Joint work with: Sjoerd Dirksen (Utrecht University), Hans C. Jung (DeepL), Holger Rauhut (RWTH Aachen University), Weiqi Wang (Concordia University)

References

[1] S. Brugiapaglia, S. Dirksen, H.C. Jung, and H. Rauhut. Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs. Applied and Computational Harmonic Analysis, 53, pages 231-269, 2021.