Group-theoretic Constructions of Erasure-robust Frames

Authors

Matthew C. Fickus, Air Force Institute of TechnologyFollow
John Jasper, University of Missouri
Dustin G. Mixon, Air Force Institute of Technology
Jesse D. Peterson, University of Missouri

Document Type

Article

Publication Date

8-29-2015

Abstract

In the field of compressed sensing, a key problem remains open: to explicitly construct matrices with the restricted isometry property (RIP) whose performance rivals those generated using random matrix theory. In short, RIP involves estimating the singular values of a combinatorially large number of submatrices, seemingly requiring an enormous amount of computation in even low-dimensional examples. In this paper, we consider a similar problem involving submatrix singular value estimation, namely the problem of explicitly constructing numerically erasure robust frames (NERFs). Such frames 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 focusing on 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 epsilon-net for the unit sphere. We then borrow ideas from the theory of group frames to construct explicit frames and epsilon-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 decent estimates of NERF bounds which would otherwise take an eternity. Though the more important RIP problem remains open, this work nevertheless demonstrates the feasibility of exploiting symmetry to greatly reduce the computational burden of similar combinatorial linear algebra problems.

Comments

The "Link to Full Text" button on this page loads the open access article version of record, hosted at Elsevier. The publisher retains permissions to re-use and distribute this article.

Previous version (Pre-print): arXiv:1210.0139 [math.FA].
Date of arXiv submission: 29 Sept 2012.

Reviewed at MR3345885

DOI

10.1016/j.laa.2015.04.004

Source Publication

Linear Algebra and its Applications

Recommended Citation

Fickus, M. C., Jasper, J., Mixon, D. G., & Peterson, J. D. (2015). Group-theoretic constructions of erasure-robust frames. Linear Algebra and Its Applications, 479, 131–154.