Compressed sensing matrices from orthogonal spaces over finite fields of odd characteristic
2026-08-24 • Information Theory
Information Theory
AI summaryⓘ
The authors create special, fixed matrices using certain geometric objects called subspaces over finite fields. These matrices are designed to help with compressed sensing, which is a technique to capture signals using fewer measurements. They analyze how well these matrices work by looking at a property called coherence and show when the matrices can reliably recover sparse signals. The authors also compare their matrices with another known construction to highlight strengths and weaknesses.
deterministic matricesorthogonal spacesfinite fieldscompressed sensingsubspacescoherenceRestricted Isometry Propertysparse recoveryDeVore's construction
Authors
Kanittakorn Moonchaisook, Poom Kumam, Songpon Sriwongsa
Abstract
In this paper, we construct deterministic matrices from subspaces of orthogonal spaces over finite fields of odd characteristic and investigate their applicability to compressed sensing. The construction is based on incidence relations among three types of subspaces, yielding families of matrices with explicitly computable dimensions and coherence. Using coherence-based estimates, we establish sufficient conditions under which these matrices satisfy the Restricted Isometry Property for prescribed sparsity levels. We also provide numerical comparisons with DeVore's deterministic construction to illustrate the trade-off between the number of measurements, coherence, and sparse recovery guarantees.