Metraipolis › archive › dc_9eaccbdb6f99

Instance Optimal Sparse Recovery from Nonlinear Observations: A Unified Framework — arXiv:2609.02120

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.02120
License (as archived)
CC0-1.0
Archived
2026-10-17T05:26:06.912Z
SHA-256 of the archived text
abc192724c4aed9a00eaafbe81b7e526798e861f06e377a46f73b141e75b81d1
Stable URL of this page
https://metraipolis.com/documento/dc_9eaccbdb6f99

How to cite

Instance Optimal Sparse Recovery from Nonlinear Observations: A Unified Framework — arXiv:2609.02120 — arXiv (en), https://arxiv.org/abs/2609.02120 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_9eaccbdb6f99 (Metraipolis archive dc_9eaccbdb6f99, sha256 abc192724c4aed9a00eaafbe81b7e526798e861f06e377a46f73b141e75b81d1)
BibTeX
@misc{dc9eaccbdb6f99,
  title = {Instance Optimal Sparse Recovery from Nonlinear Observations: A Unified Framework — arXiv:2609.02120},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.02120},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_9eaccbdb6f99; sha256 abc192724c4aed9a00eaafbe81b7e526798e861f06e377a46f73b141e75b81d1},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.02120. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

This paper develops a unified framework for instance optimal sparse recovery from nonlinear observations. The main ingredient is a signal-dependent restricted approximate invertibility condition (RAIC) of some gradient, which leads to the instance optimality of iterative hard thresholding. Under Gaussian designs, we apply the proposed framework to phaseless, one-bit, and ReLU measurements, which correspond to the problems of sparse phase retrieval, one-bit compressed sensing, and sparse ReLU regression, respectively. For sparse phase retrieval, we propose a variant of thresholded amplitude flow and show its instance optimality under $O(s^3)$ measurements (up to logarithmic factors), where $s$ is the sparsity level. To our best knowledge, this is the first instance optimal efficient algorithm for sparse phase retrieval and complements Gao, Wang and Xu (2016) that achieved this via a computationally intractable program. In one-bit compressed sensing, we establish the instance optimality of normalized binary iterative hard thresholding and strengthen the recent result of Matsumoto and Mazumdar (2024). In sparse ReLU regression, it is shown that a slight variant of the algorithm in Soltanolkotabi (2017) is instance optimal. Moreover, $(\ell_2,\ell_2)$ non-uniform instance optimal guarantees are obtained for these problems. The analysis is built upon a number of high-dimensional concentration bounds, including bounds on restricted eigenvalues and a novel instance-dependent hyperplane tessellation result.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-03 in math.ST).
Categorie arXiv: Information Theory (cs.IT) ; Signal Processing (eess.SP); Statistics Theory (math.ST).
Pagina del lavoro: https://arxiv.org/abs/2609.02120 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T04:44:33.364Z dalla pagina https://arxiv.org/catchup/math.ST/2026-09-03?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).