Recovery of signals from unordered partial frame coefficients (Q2409034)

Let \(H\) be a finite dimensional Hilbert space. \(\{f_i\}_{i=1}^N\) is called a frame if there exist two positive numbers \(A\) and \(B\) such that \(A\|f\|^2\leq\sum_{n=1}^N|\langle f,f_n\rangle|^2\leq B\|f\|^2\quad\forall f\in H.\) Let \(\{f_i\}_{i=1}^N\subseteq H\) be a frame. Then \(\{g_i\}_{i=1}^N\subseteq H\) is called a dual for \(\{f_i\}_{i=1}^N\) if \(f=\sum_{i=1}^N\langle f,f_i\rangle g_i=\sum_{i=1}^N\langle f,g_i\rangle f_i.\) Suppose that some frame coefficients \(\{\langle f,f_i\rangle\}_{i\in I}\), where \(I\subset\{1,\ldots,N\}\), are erased in data transmission. If \(\{f_i\}_{i\in I^c}\) is also a frame for \(H\), then \(f\) can be reconstructed using a dual frame of \(\{f_i\}_{i\in I^c}\). But since the index set for the erased coefficients varies, it is time consuming to compute a new dual frame every time. Another approach is to treat the erased frame coefficients as zeros and then reconstruct the input signal with the original reconstruction formula based on a dual. Obviously, this will bring some reconstruction error. The third approach is presented in [the first and third author, IEEE Trans. Inform. Theory. 60, 4013--4025 (2014; Zbl 1360.94072)] by introducing two concepts called \textit{almost robust frames} and \textit{almost self-located frames}. The authors of the present paper introduce \textit{almost self-located robust frames} and \textit{self-located robust frames}. They prove that with an almost self-located robust frame, any signal except from a Lebesgue measure zero subset can be recovered from its unordered partial frame coefficients. But the recovery is not necessarily stable with almost self-located robust frames. Hence the authors use self-located robust frames that ensure stable recovery for any input signal with unordered partial frame coefficients. They also present some characterizations and constructions for (almost) self-located robust frames. Based on these characterizations and construction algorithms, they prove that any randomly generated frame is almost surely self-located robust. Moreover, frames generated with cube roots of different prime numbers are also self-located robust.