Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2512.22911 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912829761650688 |
|---|---|
| author | Riasat, Samin Mahdavifar, Hessam |
| author_facet | Riasat, Samin Mahdavifar, Hessam |
| contents | We study covering problems in Hamming and Grassmann spaces through a unified coding-theoretic and information-theoretic framework. Viewing covering as a form of quantization in general metric spaces, we introduce the notion of the average covering radius as a natural measure of average distortion, complementing the classical worst-case covering radius. By leveraging tools from one-shot rate-distortion theory, we derive explicit non-asymptotic random-coding bounds on the average covering radius in both spaces, which serve as fundamental performance benchmarks.
On the construction side, we develop efficient puncturing-based covering algorithms for generalized Reed--Solomon (GRS) codes in the Hamming space and extend them to a new family of subspace codes, termed character-Reed--Solomon (CRS) codes, for Grassmannian quantization under the chordal distance. Our results reveal that, despite poor worst-case covering guarantees, these structured codes exhibit strong average covering performance. In particular, numerical results in the Hamming space demonstrate that RS-based constructions often outperform random codebooks in terms of average covering radius. In the one-dimensional Grassmann space, we numerically show that CRS codes over prime fields asymptotically achieve average covering radii within a constant factor of the random-coding bound in the high-rate regime. Together, these results provide new insights into the role of algebraic structure in covering problems and high-dimensional quantization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_22911 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Covering in Hamming and Grassmann Spaces: New Bounds and Reed--Solomon-Based Constructions Riasat, Samin Mahdavifar, Hessam Information Theory Signal Processing 52C17, 05B40, 94B75 E.4 We study covering problems in Hamming and Grassmann spaces through a unified coding-theoretic and information-theoretic framework. Viewing covering as a form of quantization in general metric spaces, we introduce the notion of the average covering radius as a natural measure of average distortion, complementing the classical worst-case covering radius. By leveraging tools from one-shot rate-distortion theory, we derive explicit non-asymptotic random-coding bounds on the average covering radius in both spaces, which serve as fundamental performance benchmarks. On the construction side, we develop efficient puncturing-based covering algorithms for generalized Reed--Solomon (GRS) codes in the Hamming space and extend them to a new family of subspace codes, termed character-Reed--Solomon (CRS) codes, for Grassmannian quantization under the chordal distance. Our results reveal that, despite poor worst-case covering guarantees, these structured codes exhibit strong average covering performance. In particular, numerical results in the Hamming space demonstrate that RS-based constructions often outperform random codebooks in terms of average covering radius. In the one-dimensional Grassmann space, we numerically show that CRS codes over prime fields asymptotically achieve average covering radii within a constant factor of the random-coding bound in the high-rate regime. Together, these results provide new insights into the role of algebraic structure in covering problems and high-dimensional quantization. |
| title | Covering in Hamming and Grassmann Spaces: New Bounds and Reed--Solomon-Based Constructions |
| topic | Information Theory Signal Processing 52C17, 05B40, 94B75 E.4 |
| url | https://arxiv.org/abs/2512.22911 |