Group-theoretic constructions of erasure-robust frames

Many emerging frame theories and compressed sensing problems involve estimating the singular values of a combinatorially large number of submatrices. Such problems include explicitly constructing matrices with the restricted isometry property (RIP) and numerically erasure robust frames (NERFs), both of which seemingly requiring an enormous amount of computation in even low-dimensional examples. In this paper, we focus on NERFs which are the latest invention in a long line of research concerning the design of linear encoders that are robust against data loss. We begin by examining a subtle difference between the definition of a NERF and that of an RIP matrix, one that allows us to introduce a new computational trick for quickly estimating NERF bounds. In short, we estimate these bounds by evaluating the frame analysis operator at every point of an ε-net for the unit sphere. We then borrow ideas from the theory of group frames to construct explicit frames and ε-nets with such high degrees of symmetry that the requisite number of operator evaluations is greatly reduced. We conclude with numerical results, using these new ideas to quickly produce reasonable estimates of NERF bounds which would otherwise not be possible with existing methods.