"Sparse Recovery from Group Orbits"Gilles, TimmIt is known that sparse recovery by measurements from random convolutions provides good recovery bounds. We aim to generalize this to measurements that arise as a random orbit of a group representation for some finite group $G$. Including symmetries in the generation of measurements can be understood as a partial derandomization step in compressed sensing. We systematically introduce group representations to sparse recovery, and discuss fundamental issues and obstacles in the construction of group orbits for sparse recovery. As a positive result, we prove that \[m\gtrsim s \,C_{\Omega,\pi,G}(1)^2 \, \log(C_{\Omega.\pi,G}(s))^2 (\log n)^2\] measurements enable recovery with high probability, using standard recovery algorithms such as $\ell^1$ - minimization. The constant $C_{\Omega,\pi,G}(s)$ entering in this estimate is further elucidated and determined for specific examples of representations. Lastly, we adapt our measurement process by sampling from the group orbit instead of choosing the measurements from some fixed set. Here, we can prove improved recovery guarantees. |
« back