Abstract

The problem that is the subject of this talk is simple to describe; take a change of basis matrix, remove the first N rows, find the size of the largest entry left & determine how this value decays with N. In certain compressed sensing problems the faster this decay is the more we are allowed to compress the problem by subsampling. Now suppose we have the freedom to permute the rows & are looking for the fastest decay possible. If the basis corresponding to the rows has some intrinsic structure, what does an optimal permutation look like within this structure and how does this impact on how we can subsample?

The talk will discuss some of the theoretical limits of this problem before moving onto various specific cases such as changing basis from complex exponentials to wavelets in one and many dimensions. No previous knowledge of compressed sensing or wavelets is required as I shall be introducing things from the ground up.