arXiv:2507.23175v2

Optimal compressed sensing for mixing stochastic processes

Yonatan Gutman, Adam Śpiewak

cs.ITmath.DSmath.PR68P3094A2931E0537A3560G10

Abstract

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 L2L^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.

AI-generated audit

Audit summary

Audited against arXiv v2

Not a correctness certificate. A “Correct” result may include yellow typos or minor formal corrections that do not affect substantive soundness. It means this audit found no unresolved substantive error under the stated criteria; it does not replace expert scrutiny or formal verification.

Current report

Detailed mathematical audit

Generated August 18, 2026
01Statements2 reported findingsCorrect

The lower bound for arbitrary stationary sources in terms of correlation-dimension rate and the sharp mean-information-dimension converse for finite-variance, locally dimension-regular, ψ\psi^*-mixing sources are correct.

Theorems 1.3, 3.1, and 4.1Correct

Mean information dimension is the sharp converse threshold

Pages 3–6 and 14–25 · arXiv:2507.23175v2

Energy estimates for finite-dimensional marginals bound the probability that a Gaussian kernel contains two well-separated source points. This makes correlation-dimension rate a lower bound for any measurable decompressor. The ψ\psi^* condition produces exponentially controlled, high-probability restrictions whose block energies approximate the mean average local dimension. Local dimension regularity identifies that rate with upper mean information dimension, giving the strict converse in Theorem 1.3.

Full paper, version 2
Theorems 3.1 and 4.1Correct

Projection-energy and mean-dimension lower bounds imply the sharp converse

Sections 3–4 · arXiv:2507.23175v2

The random projection estimate converts successful Lipschitz recovery into a lower bound on blockwise local dimension. Mixing allows separated blocks to approximate the stationary law with a vanishing guard fraction, and normalization gives the mean information dimension threshold stated in Theorem 1.3.

02Proofs2 reported findingsCorrect

The projection-energy, Gaussian concentration, mixing-block, and dimension-identification proofs are correct and complete.

Sections 3–4 and Appendices C–FCorrect and complete

The high-dimensional energy bounds are uniform on the selected subsequences

Pages 14–37 · Sections 3–4 and appendices · arXiv:2507.23175v2

Truncation first gives uniformly bounded second moments, Gaussian singular-value concentration controls almost every compressor, and the potential-theoretic slicing estimate applies at dimensions strictly between measurement rate and source rate. The mixing decomposition loses only a vanishing proportion of coordinates, while the local-dimension regularity lemma permits the final interchange of quantization and block limits.

Sections 3–4Correct and complete

Gaussian projection estimates and mixing-block reduction close the converse proof

Pages 14–31 · arXiv:2507.23175v2

A Fubini/energy argument bounds the set that a low-dimensional Lipschitz decoder can recover after projection. Long data blocks are split by guards so ψ\psi^*-mixing controls dependence; the guard and atypical-block losses vanish, and the remaining local-dimension bound passes through limsup/liminf in the order used by the theorem.

03Novelty0 reported findingsNo non-novelty findings

No non-novelty findings.

Detailed audit reportFull reasoning, manuscript locations, and references.
Open report PDF ↗

Author response

Challenge an audit finding

Local workflow preview

A listed author may submit formal evidence that an audit is inaccurate. The response would be considered in a fresh AI re-evaluation; it would not edit the audit automatically.

Paper
arXiv:2507.23175v2
Authors listed
Yonatan Gutman, Adam Śpiewak
Audit date
August 18, 2026
  1. 01Establish identityMatch an authenticated scholarly identity to this paper.
  2. 02Submit evidenceIdentify the finding and give a formal mathematical response.
  3. 03Re-evaluateA separate agent checks the response and records a disposition.
Recommended production method

Authenticate with ORCID, then require an exact arXiv match

MathAudit should accept the identity only when ORCID OAuth authenticates the claimant's iD and this exact arXiv paper appears in arXiv's public authority feed for that iD. A matching name alone is not sufficient.

ORCID OAuth and arXiv authority-record lookup are not connected in this local prototype.

Email fallback for papers without a linked ORCID

A production fallback could send a one-time link only when the submitted address matches an independently maintained author-contact allowlist for this paper. MathAudit must return the same message for every address so the form cannot reveal which contacts are on that list.

This demonstration does not send, store, or compare the address.

Structured response preview

This form remains unavailable until production identity verification succeeds. Nothing entered here is submitted.

This panel never establishes authorship in the local prototype. A production result should be described narrowly as an authenticated ORCID match or control of a separately allowlisted author-contact mailbox.