Phase Transition in Binary Compressed Sensing via Annealing with Adaptive Regularization

• URL: http://arxiv.org/abs/2609.16712v1
• Date: Tue, 15 Sep 2026 06:35:58 GMT
• Title: Phase Transition in Binary Compressed Sensing via Annealing with Adaptive Regularization
• Abstract summary: Regularization choice changes the recovery phase diagrams of binary compressed sensing.<n>We develop a regularization-selection method that combines systematic parameter search with random forest regression.
• Score: 0.7734726150561088
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 $\ell_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 papers

• Response Renormalization for Critical Deep Equilibrium Models [0.0]
  Training through implicit differentiation requires solving an adjoint system built from the residual Jacobian.<n>We introduce Response Renormalization, a backward-pass framework that lifts selected near-pole denominators while leaving unlifted response channels unchanged.<n>We derive dense and matrix-free collective formulations, distinguish exact gradients of a modified frozen-anchor residual from backward-response surrogates, and extend the construction to Structured Implicit Layers and Vector Attractors.
  arXiv  Detail & Related papers  (2026-08-24T18:10:30Z)
• Causal Discovery in Equal Variance Linear Gaussian DAGs via SURE-Tuned Ridge Regression [18.884190660925444]
  SURE-Ridge is a non-iterative, closed-form estimator for equal variance linear Gaussian SEM.<n>It achieves the lowest structural Hamming distance in the small-sample regime and the lowest run time across all sample sizes tested.
  arXiv  Detail & Related papers  (2026-08-17T21:07:06Z)
• Active Learning for Conditional Generative Compressed Sensing [45.88028371034407]
  Generative compressed sensing uses the range of a pretrained generator as a nonlinear model for recovering structured signals from limited measurements.<n>Our framework separates two roles of conditioning: the prompt used to design the sampling distribution and the prompt used to define the recovery model.<n>Experiments with Stable Diffusion show that prompts meaningfully reshape Christoffel sampling distributions and influence image recovery.
  arXiv  Detail & Related papers  (2026-05-06T20:50:14Z)
• In-Context Symbolic Regression for Robustness-Improved Kolmogorov-Arnold Networks [3.7163623763519733]
  Symbolic regression aims to replace blackbox predictors with analytical expressions that can be inspected and validated in machine learning.<n> Kolmogorov-Arnold Pursuit Networks (KANs) are well suited to this goal because each connection between adjacent units (an "edge") ismetd by a univariate function.<n>In practice, however, symbolic extraction is a bottleneck: the standard KAN-to-symbol approach fits operators to each learned edge function in fine isolation.
  arXiv  Detail & Related papers  (2026-03-16T13:21:26Z)
• Simulation-Based Inference via Regression Projection and Batched Discrepancies [1.9435397960631862]
  We analyze a lightweight simulation-based inference method that infers simulator parameters using only a regression-based projection of the observed data.<n> Experiments on a tractable nonlinear model and on a cosmological calibration task using the DREAMS simulation suite illustrate the computational advantages of regression-based projections.
  arXiv  Detail & Related papers  (2026-02-03T15:07:40Z)
• Shift Before You Learn: Enabling Low-Rank Representations in Reinforcement Learning [56.87989363424]
  We show that a low-rank structure naturally emerges in the shifted successor measure.<n>We quantify the amount of shift needed for effective low-rank approximation and estimation.
  arXiv  Detail & Related papers  (2025-09-05T15:48:20Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Quantifying predictive uncertainty of aphasia severity in stroke patients with sparse heteroscedastic Bayesian high-dimensional regression [47.1405366895538]
  Sparse linear regression methods for high-dimensional data commonly assume that residuals have constant variance, which can be violated in practice. This paper proposes estimating high-dimensional heteroscedastic linear regression models using a heteroscedastic partitioned empirical Bayes Expectation Conditional Maximization algorithm.
  arXiv  Detail & Related papers  (2023-09-15T22:06:29Z)
• Optimal Cross-Validation for Sparse Linear Regression [5.156484100374059]
  We use k-fold cross-validation to select sparsity and robustness of linear regressors.<n>Cross-validation substantially increases the computational cost of sparse regression.<n>We improve upon this state of affairs by solving 50-80% fewer mixed-integer optimization problems.
  arXiv  Detail & Related papers  (2023-06-26T17:02:45Z)
• On the Double Descent of Random Features Models Trained with SGD [78.0918823643911]
  We study properties of random features (RF) regression in high dimensions optimized by gradient descent (SGD) We derive precise non-asymptotic error bounds of RF regression under both constant and adaptive step-size SGD setting. We observe the double descent phenomenon both theoretically and empirically.
  arXiv  Detail & Related papers  (2021-10-13T17:47:39Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  We present an analysis of the ExtraGradient (SEG) method with constant step size, and present variations of the method that yield favorable convergence. We prove that when augmented with averaging, SEG provably converges to the Nash equilibrium, and such a rate is provably accelerated by incorporating a scheduled restarting procedure.
  arXiv  Detail & Related papers  (2021-06-30T17:51:36Z)
• Fast OSCAR and OWL Regression via Safe Screening Rules [97.28167655721766]
  Ordered $L_1$ (OWL) regularized regression is a new regression analysis for high-dimensional sparse learning. Proximal gradient methods are used as standard approaches to solve OWL regression. We propose the first safe screening rule for OWL regression by exploring the order of the primal solution with the unknown order structure.
  arXiv  Detail & Related papers  (2020-06-29T23:35:53Z)
• Sample Complexity Bounds for 1-bit Compressive Sensing and Binary Stable Embeddings with Generative Priors [52.06292503723978]
  Motivated by advances in compressive sensing with generative models, we study the problem of 1-bit compressive sensing with generative models. We first consider noiseless 1-bit measurements, and provide sample complexity bounds for approximate recovery under i.i.d.Gaussian measurements. We demonstrate that the Binary $epsilon$-Stable Embedding property, which characterizes the robustness of the reconstruction to measurement errors and noise, also holds for 1-bit compressive sensing with Lipschitz continuous generative models.
  arXiv  Detail & Related papers  (2020-02-05T09:44:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.