Phase Transition in Binary Compressed Sensing via Annealing with Adaptive Regularization
Abstract
Regularization choice changes the recovery phase diagrams of annealing-based binary compressed sensing. We develop a regularization-selection method that combines systematic parameter search with random forest regression. Under noiseless Gaussian measurements with known sparsity, reference parameters are selected from a candidate grid by minimizing mean squared reconstruction error over repeated simulated annealing (SA) trials. The fitted model predicts these reference values from signal dimension, sampling ratio, and sparsity. With predicted regularization, the SA recovery transition broadly follows the asymptotic reference boundary for box-constrained ℓ1 recovery at the larger signal dimensions examined. Without retraining, the same predictor supplies identical regularization values to SA and a quantum--classical hybrid solver. On matched problem instances, the hybrid solver yields smaller mean squared reconstruction errors than SA in parts of the evaluated parameter space. The resulting rule reuses the searched information for subsequent reconstruction without repeating candidate searches at each setting. The results quantify empirical performance under the stated finite candidate grid and solver settings; they do not constitute a solver-independent recovery guarantee or a time-to-solution comparison.
Related
- Superfast Spectral Compressed Sensing with Quadratic Convergence
- Recovery Guarantees for Posterior Sampling of One-Bit Compressed Sensing
- Compressed Sensing with Quantized Tensor Trains (QTTs)
- Lifted Restricted Isometry Property and Fast Algorithm for Spectral Compressed Sensing With Near-Optimal Sample Complexity
- Full-Model Optimality for Tunable Linear Generative Priors in Compressed Sensing
BibTeX
@misc{huang2026phase,
title = {{Phase Transition in Binary Compressed Sensing via Annealing with Adaptive Regularization}},
author = {Xiaoxin Huang and Masayuki Ohzeki},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.16712},
eprint = {2609.16712},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.16712},
}
RIS
TY - UNPB
TI - Phase Transition in Binary Compressed Sensing via Annealing with Adaptive Regularization
AU - Xiaoxin Huang
AU - Masayuki Ohzeki
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.16712
UR - https://arxiv.org/abs/2609.16712
AB - Regularization choice changes the recovery phase diagrams of annealing-based binary compressed sensing. We develop a regularization-selection method that combines systematic parameter search with random forest regression. Under noiseless Gaussian measurements with known sparsity, reference parameters are selected from a candidate grid by minimizing mean squared reconstruction error over repeated simulated annealing (SA) trials. The fitted model predicts these reference values from signal dimension, sampling ratio, and sparsity. With predicted regularization, the SA recovery transition broadly follows the asymptotic reference boundary for box-constrained ℓ_1 recovery at the larger signal dimensions examined. Without retraining, the same predictor supplies identical regularization values to SA and a quantum--classical hybrid solver. On matched problem instances, the hybrid solver yields smaller mean squared reconstruction errors than SA in parts of the evaluated parameter space. The resulting rule reuses the searched information for subsequent reconstruction without repeating candidate searches at each setting. The results quantify empirical performance under the stated finite candidate grid and solver settings; they do not constitute a solver-independent recovery guarantee or a time-to-solution comparison.
ER -