A03 Group actions and t-designs in sparse and low rank matrix recovery

The objective of this project is to systematically apply group theoretic methods for constructing measurement schemes aimed at sparse and low-rank matrix recovery, as well as phase retrieval. We developed explicit measurement schemes based on group orbits for sparse recovery and established theoretical recovery guarantees using the restricted isometry property [The Restricted Isometry Property for Measurements from Group Orbits]. Our approach involved examining measurements derived from the actions of the left regular representation on finite groups, along with other representations.

For low-rank matrix recovery, we explored measurement schemes generated by randomly sampled points within t-designs. We demonstrated new recovery guarantees for t=3. Connections between coding theory and invariant theory in the context of Clifford-Weil groups and Γ-conjugate invariants are described in [Γ-conjugate weight enumerators and invariant theory]. These connections aid in constructing t-designs as orbits of Clifford-Weil groups. We combine ideas from representation theory, quantum physics, invariant theory, coding theory, and numerical algebra to create a toolbox using OSCAR [1] that is tailored to these constructions. Additionally, we aim to establish guarantees for measurements originating from the actions of finite Weyl-Heisenberg groups within the context of low-rank recovery. Numerical tests are being conducted for 4-designs arising as orbits of Clifford-Weil groups. We plan to use the routines we implemented for this purpose to systematically test and compare the different measurement schemes.

[1] Editors: W. Decker, C. Eder, C. Fieker, M. Horn and M. Joswig. The Computer Algebra System OSCAR: Algorithms and Examples. Algorithms and Computation in Mathematics, 32, Springer, 2025.