Instance Optimal Sparse Recovery from Nonlinear Observations: A Unified Framework
Abstract
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(s3) 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, (ℓ2,ℓ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.
Related
- Initial condition recovery in nonlinear damped viscous photoacoustic tomography using a convolutional neural network-guided gradient-free optimization framework
- A K-R defect framework for classical inequalities: curvature recovery, uniqueness, stability, and applications to nonlinear boundary value problems
- Halve-Then-Greedy: Adaptive Sampling for Posterior Success with Near-Optimal Instance Dependence
- Instance-Optimal Adaptive Location Estimation via Multiscale Mid-Summaries
- Relatively Smart II: Tractable or Semi-Supervised Instance-Optimal Learning
BibTeX
@misc{chen2026instance,
title = {{Instance Optimal Sparse Recovery from Nonlinear Observations: A Unified Framework}},
author = {Junren Chen and Arian Maleki},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.02120},
eprint = {2609.02120},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.02120},
}
RIS
TY - UNPB
TI - Instance Optimal Sparse Recovery from Nonlinear Observations: A Unified Framework
AU - Junren Chen
AU - Arian Maleki
PY - 2026
DA - 2026/09/02
PB - arXiv
DO - 10.48550/arxiv.2609.02120
UR - https://arxiv.org/abs/2609.02120
AB - 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, (ℓ_2,ℓ_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.
ER -