Group-theoretic constructions of erasure-robust frames

compressed sensing design of linear codes erasure robust frames frame analysis operator frames restricted isometry property singular values of matrices

Mathematics Subject Classification ID

General harmonic expansions, frames (42C15) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Source coding (94A29)

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.

Review text

Many frame theories and compressed sensing problems (such as construction of matrices with restricted isometry property) require the estimation of singular values of a large number of submatrices which can cause high computational cost. In this interesting paper, the authors present a new deterministic construction of a \textit{numerically erasure robust frame} (NERF): For \(M \leq K \leq N\) and \(0 < \alpha \leq \beta < \infty\), one says that \(\{\varphi_n \in {\mathbb R}^M; \,n=1,\ldots,N\}\) is a \((K,\alpha,\beta)\)-NERF for \({\mathbb R}^M\) if for any \(K\)-element subset \({\mathcal K} \subseteq \{1,\ldots,N\}\) and for all \(x\in {\mathbb R}^M\) \[ \alpha\, \|x\|^2 \leq \sum_{n\in {\mathcal K}} |\langle x,\varphi_n \rangle|^2 \leq \beta \, \|x \|^2\,. \] This means that \(\{\varphi_n \in {\mathbb R}^M; \,n \in {\mathcal K}\}\) is a frame for \({\mathbb R}^M\) with frame bounds \(\alpha\), \(\beta\) regardless of the choice of \({\mathcal K}\). NERFs are essential for the design of linear encoders that are robust against data loss. The authors propose a computational trick for quickly estimating NERF bounds \(\alpha\), \(\beta\). They estimate these bounds by evaluating the frame analysis operator at every point of an \(\varepsilon\)-net for the unit sphere of \({\mathbb R}^M\). This trick reduces the computational cost from being exponential in \(N\) to being exponential in \(M\). Imposing symmetry on the frame and \(\varepsilon\)-net, the computational cost for estimating NERF bounds \(\alpha\), \(\beta\) can be reduced further to being subexponential in \(M\). Finally, the implementation of this theory is described and applied to construct explicit NERFs.

Recommendations

Cites work

Cited in

(10)

This page was built for publication: Group-theoretic constructions of erasure-robust frames

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2348016)