Optimal compressed sensing for mixing stochastic processes
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912511783075840 |
|---|---|
| author | Gutman, Yonatan Śpiewak, Adam |
| author_facet | Gutman, Yonatan Śpiewak, Adam |
| contents | Jalali and Poor introduced an asymptotic framework for compressed sensing of stochastic processes, demonstrating that any rate strictly greater than the mean information dimension serves as an upper bound on the number of random linear measurements required for (universal) almost lossless recovery of $ψ^*$-mixing processes, as measured in the normalized $L^2$ norm. In this work, we show that if the normalized number of random linear measurements is strictly less than the mean information dimension, then almost lossless recovery of a $ψ^*$-mixing process is impossible by any sequence of decompressors. This establishes the mean information dimension as the fundamental limit for compressed sensing in this setting (and, in fact, the precise threshold for the problem). To this end, we introduce a new quantity, related to techniques from geometric measure theory: the correlation dimension rate, which is shown to be a lower bound for compressed sensing of arbitrary stationary stochastic processes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_23175 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal compressed sensing for mixing stochastic processes Gutman, Yonatan Śpiewak, Adam Information Theory Dynamical Systems Probability 68P30, 94A29, 31E05, 37A35, 60G10 Jalali and Poor introduced an asymptotic framework for compressed sensing of stochastic processes, demonstrating that any rate strictly greater than the mean information dimension serves as an upper bound on the number of random linear measurements required for (universal) almost lossless recovery of $ψ^*$-mixing processes, as measured in the normalized $L^2$ norm. In this work, we show that if the normalized number of random linear measurements is strictly less than the mean information dimension, then almost lossless recovery of a $ψ^*$-mixing process is impossible by any sequence of decompressors. This establishes the mean information dimension as the fundamental limit for compressed sensing in this setting (and, in fact, the precise threshold for the problem). To this end, we introduce a new quantity, related to techniques from geometric measure theory: the correlation dimension rate, which is shown to be a lower bound for compressed sensing of arbitrary stationary stochastic processes. |
| title | Optimal compressed sensing for mixing stochastic processes |
| topic | Information Theory Dynamical Systems Probability 68P30, 94A29, 31E05, 37A35, 60G10 |
| url | https://arxiv.org/abs/2507.23175 |