Group-theoretic constructions of erasure-robust frames (Q2348016)

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.